Page 120 - 高中 信息技术 选择性必修1 数据与数据结构

第五章 数据结构的应用

2．用迭代法解决问题
用迭代法解决问题，需考虑三个方面的内容。
（1）确定迭代变量。
在可以用迭代法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的

变量，这个变量就是迭代变量。在例1中，sum就是迭代变量。
（2）建立关系式。
迭代关系式是指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关
系式的建立是解决迭代问题的关键，通常可以使用顺推或倒推的方法来完成。例1中，

“sum=sum+i”就是迭代关系式，通过此式可以进行迭代求和。
（3）过程控制。
广东教育出版社
编写迭代程序必须考虑在什么时候结束迭代过程，不能让迭代过程无休止地重复执行
下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以

计算出来；另一种是所需的迭代次数无法预先确定。对于前一种情况，可以构建一个固定
次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析确定迭代过程结
束的条件。在例1中，用了for循环语句进行过程控制。

例2：一对刚出生的小兔子，一个月后就能成长为成年兔，再过一个月后（即第三个

月起）就每月生一对兔子。新生的兔子也按这个规律繁殖。现在仅有一对刚出生的小兔
子，问在没有兔子死亡的情况下，一年后总共繁殖成多少对兔子。
算法分析：设f(n)表示第n个月的兔子对数，先看前几个月的情况：第一个月有一对

刚出生的兔子，即f(1)=1；第二个月，这对兔子长成成年兔，兔子对数还是只有1对，
即f(2)=1；第三个月，这对成年兔生出一对小兔，共有两对兔子，即f(3)=2；第四个月，
成年兔又生出一对小兔，第三个月出生的兔子长成成年兔，共有三对兔子，即f(4)=3；
第五个月，原成年兔又生出一对小兔，新成年兔也生出一对小兔，共有五对兔子，即

f(5)=5……以此类推，每个月兔子数为1，1，2，3，5，8，13，21，…
转化为数学模型，设f(n)为第n个月的兔子对数，则有：
f(1)=1,
f(2)=1,

f(n)=f(n-1)+f(n-2) (n>=3)
下面是实现求一年后繁殖的兔子总数的核心代码，其中f1、f2、fn这三个迭代变量分
别代表前两个月、前一个月、当前月的兔子数，用迭代关系式“fn = f1 + f2;”计算当

月的兔子数，再用“f1 = f2; f2 = fn;”为下一个月的迭代计算做好准备。
int f1=1,f2=1,fn=0; //迭代变量
for(int i=3; i<=12; i++) //用i的值来控制迭代的次数
{

fn=f1+f2; //计算当月数量
f1=f2; //f1、f2迭代计算，为下个月迭代赋初值
f2=fn;
}

112 112

21X2204.indd 112 2019/9/26 13:53:37