《计算机常用算法与程序设计案例教程》习题解答：分数分解算法详解

《计算机常用算法与程序设计案例教程》中的习题11-1要求实现一个分数分解算法，将真分数a/b分解为若干个分母为整数，分子为1的埃及分数之和。算法的具体步骤如下： 1. 首先找到并输出小于a/b的最大埃及分数1/c。 2. 如果c大于900000000，则退出算法。 3. 如果c小于等于900000000，将差值a/b-1/c整理为一个新的分数a/b。若a/b已经是埃及分数，则输出结果并结束。 4. 如果a/b不是埃及分数，则继续执行第1、2、3步骤。 在算法描述中，我们设定d = int(b)，这里int(x)表示取正数x的整数部分。注意到d < b < d+1，然后利用等式aaa=1+a(d+1)-bbd+1b(d+1)来迭代计算得到新的分数。 具体算法描述如下： ``` Algorithm Fraction_Decomposition(a, b) d = int(b) while True: c = int(b / a) + 1 if c > 900000000: return else: print(1/c) a = a*c - b b = b*c if a == 1: return ``` 这段算法的核心是通过反复迭代计算，将原始分数a/b逐步转化为多个埃及分数的和。在每次迭代中，根据当前的a和b的值计算出一个新的分母c，并将其添加到结果中。当a等于1时，输出最终结果。算法的时间复杂度取决于a和b的大小，但在一般情况下可以接受。 这个算法的实现不仅帮助我们更深入理解埃及分数的概念，还能够提高我们对整数分解等基本数学概念的理解。通过学习这个算法，我们可以更好地理解和应用数学知识于实际问题中。