Python算法100例-4.1 将真分数分解为埃及分数

完整源代码项目地址，关注博主私信'源代码'后可获取

• 1.问题描述
• 2.问题分析
• 3.算法设计
• 4.补充知识点
• 5.确定程序框架
• 6.完整的程序

1．问题描述

现输入一个真分数，请将该分数分解为埃及分数。

2．问题分析

真分数（a proper fraction）是指分子比分母小的分数，其分数值小于1。如1/2、3/5、8/9等都是真分数。

分子是1的分数，叫单位分数。古代埃及人在进行分数运算时，只使用分子是1的分数，因此这种分数也叫作埃及分数，或者叫单分子分数。例如，8/11=1/2+1/5+1/55+1/110。

我们约定分子分母都是自然数，分数的分子用a表示，分母用b表示。若真分数的分子a能整除分母b，则真分数经过化简就可以得到埃及分数，若真分数的分子不能整除分母，则可以从原来的分数中分解出一个分母为(b/a)+1的埃及分数。用这种方法将剩余部分反复分解，最后可得到结果。

3．算法设计

真分数分解为埃及分数的思路可归纳如下：

1）分数的分子用a表示、分母用b表示，变量c用来存储各个埃及分数的分母。

2）如果分母是分子的倍数，直接约简成埃及分数。此时，埃及分数的分母c=b/a，分子为1，即直接将变量a赋值为1。

3）若分母不是分子的倍数，则可以分解出一个分母为(b/a)+1的埃及分数，即变量c的值为(b/a)+1。

4）如果分子是1，表明已经是埃及分数，不用再分解，分解过程结束。

如果分数的分子a为1，则说明此时的分数已经是埃及分数，无须再分解，可结束循环。对于这种不受循环条件限制，当某一条件满足时便可结束循环的情况，可用break语句实现。

if a == 1:
    print("1/%ld\n" %c, end="")
    break

5）如果分子是3而且分母是偶数，直接分解成两个埃及分数1/(b/2)和1/b。

因分母为偶数，故变量b一定是2的倍数，对于分解出来的分数1/(b/2)经过约分之后肯定能得到一个埃及分数。原分数分解为两个埃及分数之后便可利用break语句结束循环。

if a == 3 and b % 2 == 0:       # 若余数分子为3，分母为偶数，输出最后两个埃及分数
    print("1/%ld + 1/%ld\n" %(b//2, b))
    break

6）从分数中减去这个分母为(b/a)+1的埃及分数，回到步骤2重复上述过程。

分解出此埃及分数之后用原分数a/b减去此埃及分数，得到新的分数。此新分数的分子a=ac-b，分母b=bc。

整个程序没有明确的循环条件，故为了能使循环继续，需将循环条件用一非0的常量表示条件为真。从上述过程可以看出，虽然利用循环条件不能结束循环，但当满足某一条件时利用break语句，仍然可以避免程序进入死循环。

将某一真分数分解为一个以上的埃及分数后，输出时要求以各分数相加的形式输出，故在输出语句中“+”是作为普通字符输出的。

print("1/%ld + " %c, end="")

4．补充知识点

（1）print()函数

print()函数的一般调用形式为：

print(格式控制  %输出表列)

也可以省略格式控制，直接输出。

格式说明符用于为输出项提供输出格式说明，也就是使数据按格式说明符的要求进行输出，其由%号和紧跟在其后的格式描述符组成。

部分常用的格式说明符及其描述如表所示。

在双引号中除了格式说明符之外的内容要全部原样输出；输出表列中各个输出项之间要用逗号隔开；输出项可以是任意合法的常量、变量或表达式。

注意事项：

·输出比较自由一些，输出的各个数之间到底是什么，取决于格式说明符之间的内容。

·格式说明符要与输出项一一对应。

·输出语句中还可以有\n、\r、\t、\a等转义字符。

·尽量不要在输出语句中改变输出变量的值。

·输出的数据中如果存在变量，一定是已经定义过的。

（2）不换行输出

在使用print()函数时，它会自动打印一个换行符。如果不想换行或不想自动添加换行符，可以在print()函数中加上参数end=" "来避免换行，其中end参数的双引号中可以添加任意字符，实现在打印的结果后面添加任意字符。

实例代码：

# @desc: print()函数

if __name__ == "__main__":

    pi = 3.141592657
    # 输出整数部分
    print("%d" %pi)
    # 指定占位符宽度，输出整数部分
    print("%5d" % pi)
    # 指定占位符宽度，左边补0，输出整数部分
    print("%05d" %pi)
    # 指定占位符宽度，右对齐，输出整数部分
    print("%-5d" %pi)

    # 保留2位小数
    print("%.2f" % pi)
    # 指定占位符，并保留3位小数
    print("%6.3f" %pi)
    # 指定占位符，并保留4位小数，左边补0
    print("%06.4f" %pi)
    # 指定占位符，保留2位小数，左边补0，始终带符号
    print("%+05.2f" %pi)

    # 使用科学记数法表示
    print("%e" %pi)

    # 输出字符串
    str = "HelloWorld!"
    print("str = %s" %str)
    # 也可以省略格式说明，直接输出
    print("str = " , str)
    # 保留3个字符
    print("%.3s" %str)

    # 输出字符
    str1 = 'a'
    print("str1 = %c" %str1)

    print("-------------")
    for i in range(3):
        print(i)                                    # 换行输出

    for i in range(3):
        print(i, end=" ")                           # 不换行输出

3
    3
00003
3    
3.14
 3.142
3.1416
+3.14
3.141593e+00
str = HelloWorld!
str =  HelloWorld!
Hel
str1 = a
-------------
0
1
2
0 1 2 

5．确定程序框架

程序流程图如图所示。

6．完整的程序

根据上面的分析，编写程序如下：

# @desc: 将真分数分解为埃及分数

if __name__ == "__main__":
    print("请输入一个分数：", end=" ")
    a, b = [int(i) for i in input().split()]
    print("输入的分数为：%ld/%ld" %(a, b))
    print("埃及分数：", end=" ")
    while 1:
        if b % a != 0:  # 若分子不能整除分母，则分解出一个分母为b//a+1的埃及数
            c = b // a + 1
        else:
            c = b // a
            a = 1
        if a == 1:
            print("1/%ld\n" %c, end="")
            break
        else:
            print("1/%ld + " %c, end="")
        a = a * c - b   # 求出余数的分子
        b = b * c  # 求出余数的分母
        if a == 3 and b % 2 == 0:  # 若余数分子为3，分母为偶数，输出最后两个埃及数
            print("1/%ld + 1/%ld\n" %(b//2, b))
            break

请输入一个分数： 输入的分数为：3/5
埃及分数： 1/2 + 1/10