迭代方法程序设计-C语言程序设计基础

2025-09-30 理论教育版权反馈

【摘要】：递推就是一个不断由变量旧值按照一定的规律推出变量新值的过程，递推在程序设计中往往通过迭代方法实现。迭代过程在程序结构上使用循环结构进行处理。求出斐波那契数列的前n项。题目分析：设用f1、f2和f3表示相邻的3个裴波那契数据项，据题意有f1、f2的初始值为1，即迭代的初始条件为：f1＝f2＝1；迭代的公式为：f3＝f1+f2。

递推就是一个不断由变量旧值按照一定的规律推出变量新值的过程，递推在程序设计中往往通过迭代方法实现。迭代一般与3个因素有关，它们是初始值、迭代公式、迭代结束条件（迭代次数）。

迭代算法的基本思想：迭代变量先取初值，据初值（或旧值）按迭代公式计算出新值，用新值对变量原值进行更新替换；重复以上过程，直到迭代结束条件满足时结束迭代。迭代过程在程序结构上使用循环结构进行处理。

【例4.11】　求两个正整数的最大公约数和最小公倍数。

题目分析：使用辗转相除法实现求两个非负整数m和n（m＞n）的最大公倍数，其算法可以描述为：

①m除以n得到余数r（0≤r＜n）。

②若r＝0则算法结束，n为最大公约数。否则执行步骤③。

③m←n，n←r，转回到步骤①。(https://www.chuimin.cn)

当已知两个非负整数m和n的最大公约数后，求其最小公倍数的算法可以简单描述为：两个正整数之积除以它们的最大公约数。

上面程序代码是完全按照算法描述的步骤书写的，考虑到除数肯定不能为0，两个数的乘积可以在迭代之前计算等因素，程序可以进行如下优化，请读者对照理解。

【例4.12】　求出斐波那契数列的前n项。裴波那契（Fibonacci）数列：前两个数据项都是1，从第3个数据项开始，其后的每一个数据项都是其前面的两个数据项之和。

题目分析：设用f1、f2和f3表示相邻的3个裴波那契数据项，据题意有f1、f2的初始值为1，即迭代的初始条件为：f1＝f2＝1；迭代的公式为：f3＝f1+f2。有初始条件和迭代公式只能描述前3项之间的关系，为了反复使用迭代公式，可以在每一个数据项求出后将f1、f2和f3顺次向后移动一个数据项，即将f2的值赋给f1，f3的值赋给f2，从而构成如下的迭代语句序列：f3＝f1+f2；、f1＝f2；、f2＝f3；，反复使用该语句序列就能够求出所要求的裴波那契数列。

／Name:ex0412.c／

迭代方法程序设计-C语言程序设计基础

相关推荐