资源描述：
《《算法策略》PPT课件(I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章基本的算法策略4.1迭代算法4.1.1递推法4.1.2倒推法4.1.3迭代法解方程4.1迭代算法迭代法（Iteration）也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。迭代算法一般用于数值计算。迭代法应该是我们早已熟悉的算法策略，程序设计语言课程中所学的累加、累乘都是迭代算法策略的基础应用。利用迭代算法策略求解问题，设计工作主要有三步：1）确定迭代模型2）建立迭代关系式3）对迭代过程进行控制4．1．1递推法【例1】兔子繁殖问题问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死
2、，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。问题分析：因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数(用斜体数字表示)显然由前两个月的小兔子的对儿数决定。则繁殖过程如下：一月二月三月四月五月六月……111+1=22+1=33+2=55+3=8……算法1：main(){inti,a=1,b=1;print(a,b);for(i=1;i＜=10;i++){c=a+b;print(c);a=b;b=c；}}数学建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，……。算法2：表4-1递推迭代表达式123456789
3、abc=a+ba=b+cb=a+cc=a+ba=b+cb=a+c……由此归纳出可以用“c=a+b;a=b+c;b=c+a;”做循环“不变式”。算法2如下：main(){inti,a=1,b=1;print(a,b);for(i=1;i＜=4;i++){c=a+b;a=b+c;b=c+a;print(a,b,c);}}算法2，最后输出的并不是12项，而是2+3*4共14项。表4-2递推迭代表达式123456789aba=a+bb=a+ba=a+bb=a+b……由此归纳出可以用“a=a+b;b=a+b;”做循环“不变式”，从而得到以下算法3:main(){inti,a
4、=1,b=1;print(a,b);for(i=1;i＜=5;i++){a=a+b;b=a+b;print(a,b);}}算法3：【例2】求两个整数的最大公约数。数学建模：辗转相除法是根据递推策略设计的。不妨设两个整数a>b且a除以b商x余c；则a-bx=c，不难看出a、b的最大公约数也是c的约数（一个数能整除等式左边就一定能整除等式的右边），则a、b的最大公约数与b、c的最大公约数相同。同样方法推出b、c的最大公约数与……，直到余数为0时，除数即为所求的最大公约数。算法设计：循环“不变式”第一次是求a、b相除的余数c，第二次还是求“a”“b”相除的余数，经a=b
5、,b=c操作，就实现了第二次还是求“a”“b”相除的余数，这就找到了循环不变式。循环在余数c为0时结束。算法如下：main（）{inta,b;input(a,b);if(b=0){print(“dataerror”);return;}else{c=amodb;whilec<>0{a=b;b=c;c=amodb;}}print(b);}4.1.2倒推法所谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从后向前推解问题的方法。如下面的例题，因不同方面的需求而采用了倒推策略。例1在不知前提条件的情况下，经过从后向前递推，从而求解问题。即由结果倒过来推解它的前提条件。又
6、如例2由于存储的要求，而必须从后向前进行推算。另外，在对一些问题进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法（如例3），则问题容易理解和解决。下面分别看这几个例子：【例1】猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第10天时就只有一个桃子了，求原有多少个桃？数学模型：每天的桃子数为：a10=1,a9=(1+a10)*2,a8=(1+a9)*2,……a10=1，递推公式为：ai=(1+ai+1)*2I=9,8,7,6……1算法如下：main(){inti,s;s=1;for(i=9;i>=1;i=i-1)s=(s+1)*
7、2print(s)；}【例2】输出如图4-1的杨辉三角形（限定用一个一维数组完成）。数学模型：上下层规律较明显，中间的数等于上行左上、右上两数之和。问题分析：题目中要求用一个一维数组即完成。数组空间一定是由下标从小到大利用的，这样其实杨辉三角形是按下图4-2形式存储的。若求n层，则数组最多存储n个数据。111121133114641……………图4-1杨辉三角形111121133114641……………图4-2杨辉三角形存储格式算法设计：A[1]=A[i]=1A[j]=A[j]+A[j-1]j=i-1，i-2，……，2i行i-1行i-1行算法如下：main(){int
8、n,i,j
