《算法教程》习题详解：分数分解与程序复杂度分析

《计算机常用算法与程序设计案例教程》习题解答文档提供了一系列关于算法和程序设计的练习题及其详细解答。其中，第11-1题着重于分数分解算法，该算法的目标是将真分数a/b表示为若干个埃及分数之和。算法步骤如下： 1. 埃及分数分解：首先寻找并输出小于a/b的最大埃及分数1/c。埃及分数是指分母为整数且分子为1的分数，如1/2、1/3等。 2. 边界条件：如果c大于900000000，则认为已经找到了足够大的埃及分数，算法终止。 3. 迭代过程：当c在允许范围内时，计算新的差值a/b - 1/c，并更新a和b。如果a/b变成埃及分数，则输出结果并结束。 4. 递归调用：如果a/b不是埃及分数，重复步骤1至3，直到找到合适的分解。 接着，文档还提供了几段程序段的算法分析，涉及时间复杂度的计算。例如： - 第一个程序段是两个嵌套的for循环，用于计算1到n的所有数的和，其时间复杂度为O(n^2)。 - 第二个程序段是另一个嵌套的for循环，其中内层循环执行次数随着外层循环k的变化而减少，时间复杂度同样为O(n^2)。 - 第三个程序段涉及阶乘的累加，通过k的阶乘乘以1到k的累加和，时间复杂度为O((n+1)!), 表现出指数级增长。 - 第四个程序段是查找形如a*100减去99到100之间的完全平方数倍数的个数，当找到50个时输出对应的a值。这个循环结构的时间复杂度主要取决于a的范围和内部循环的执行次数，整体上看是线性的，但由于存在嵌套循环，实际复杂度难以简单表示。 这些习题展示了算法设计和分析的基本技巧，包括递归、边界条件、循环结构优化以及对时间复杂度的理解，是理解算法设计实践的重要组成部分。通过解决这些问题，学习者可以加深对算法理论和编程技巧的掌握，提升编程能力。