3 迭代算法.ppt

* 3 迭代算法 主要内容 3.1 递推法 3.2 倒推法 3.3 迭代法解方程 * 迭代算法 迭代法（Iteration）也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。迭代算法一般用于数值计算。迭代法应该是我们早已熟悉的算法策略，程序设计语言课程中所学的累加、累乘都是迭代算法策略的基础应用。 利用迭代算法策略求解问题，设计工作主要有三步： 1）确定迭代模型 2）建立迭代关系式 3）对迭代过程进行控制 3.1 递推法 【例1】兔子繁殖问题 问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。 问题分析：因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数(用斜体数字表示)显然由前两个月的小兔子的对儿数决定。则繁殖过程如下： 一月 二月 三月 四月 五月 六月 …… 1 1 1+1=2 2+1=3 3+2=5 5+3=8 …… 算法： main( ) { int i,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，……。 3.2 倒推法 所谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从后向前推解问题的方法。如下面的例题，因不同方面的需求而采用了倒推策略。 例1在不知前提条件的情况下，经过从后向前递推，从而求解问题。即由结果倒过来推解它的前提条件。又如例2由于存储的要求，而必须从后向前进行推算。另外，在对一些问题进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法（如例3），则问题容易理解和解决。下面分别看这几个例子： 【例1】猴子吃桃问题 一只小猴子摘了若干桃子，每天吃现有桃的一半多一个， 到第10天时就只有一个桃子了，求原有多少个桃？ 数学模型：每天的桃子数为：a10=1, a9=(1+a10)*2, a8=(1+a9)*2,……a10=1， 递推公式为：ai=(1+ai+1)*2 i= 9,8,7,6……1 算法如下 ： main( ) { int i,s; s=1; for (i=9 ;i=1;i=i-1) s=(s+1)*2 print (s)； } 【例2】 输出如图4-1的杨辉三角形（限定用一个一维数组完成）。 数学模型：上下层规律较明显，中间的数等于上行左上、右上两数之和。 问题分析：题目中要求用一个一维数组即完成。数组空间一定是由下标从小到大利用的，这样其实杨辉三角形是按下图4-2形式存储的。若求n层，则数组最多存储n个数据。 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 …………… 图4-1 杨辉三角形 1 1 1 1 2 1 1 3 3 1 1????4 6 4 1 …………… 图4-2 杨辉三角形存储格式 算法设计： A[1] = A[i]=1 A[j] = A[j] + A[j-1] j=i-1，i-2，……，2 i行 i-1行 i-1行 算法如下： main( ) {int n,i,j,a[100]; input(n); print(“1”); print(“换行符”); a[1]=a[2]=1; print(a[1],a[2]); print(“换行符”); for (i=3;i=n;i=i+1) {a[1]=a[i]=1; for (j=i-1，j1，j=j-1) a[j]=a[j]+a[j-1]; for (j=1;j=i;j=j+1) print(a[j]); print(“换行符”); } } 【例3】穿越沙漠问题 用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑，耗油率为1加仑/公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。 问题分析： 1）先看一简单问题：有一位探险家用5天的时间徒步横穿A