(
课件网) 数据结构的应用 查找和排序，与我们的学习、生活息息相关。 如从字典 中查找汉字，从电话号码本中查找电话，在图书馆中查找图 书，高考查询成绩等；教师按身高来安排学生的座位，大学 按照高考成绩高低顺序录取新生，网上商城按照销量高低排 序来推荐商品等。在信息时代，数据的增长速度越来越快， 导致信息量呈几何级的增长。在庞大的数据里进行人工查找和排序是非常困难的，甚至是无法办到的，所以必须依靠计 算机才能快速、准确地对数据进行查找和排序。 5.1 迭代与递归 在利用计算机解决实际问题中，迭代和递归都是非常实用的算法，很多难的问题都是通过迭代或递归算法解出来的。 1．迭代法 迭代法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令（或一定步骤），在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。 int n,sum=0; //sum初始化为0 for(int i=1; i<=n; i++) //用循环实现迭代 { sum=sum+i; //迭代过程 } 用迭代法解决问题，需考虑三个方面的内容。 （1）确定迭代变量。在可以用迭代法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。在例1中，sum就是迭代变量。 （2）建立关系式。迭代关系式是指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用顺推或倒推的方法来完成。例1中，“sum=sum+i”就是迭代关系式，通过此式可以进行迭代求和。 （3）过程控制。编写迭代程序必须考虑在什么时候结束迭代过程，不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法预先确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析确定迭代过程结束的条件。在例1中，用了for循环语句进行过程控制。 例： 一对刚出生的小兔子，一个月后就能成长为成年兔，再过一个月后（即第三个 月起）就每月生一对兔子。新生的兔子也按这个规律繁殖。现在仅有一对刚出生的小兔子，问在没有兔子死亡的情况下，一年后总共繁殖成多少对兔子。 f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2) (n>=3) 算法分析： 设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个月的兔子对数，则有： 下面是实现求一年后繁殖的兔子总数的核心代码，其中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; } 每个月的兔子对数组成数列：1，1，2，3，5，8，13，21，34，55，89，144，…此数列也称为斐波那契数列。 5.1.2 递归 1．递归的基本概念若一个对象用自己来定义自己或部分地包含自己，则称这个对 ... ...
