第四章1算法策略ppt课件

1、第四章第四章 基本的算法策略基本的算法策略4.1 4.1 迭代算法迭代算法 4.1.1 4.1.1 递推法递推法 4.1.2 4.1.2 倒推法倒推法 4.1.3 4.1.3 迭代法解方程迭代法解方程4.1 迭代算法迭代算法迭代法迭代法Iteration也称也称“辗转法辗转法”，是一种不断用变量的旧，是一种不断用变量的旧值递推出新值的解决问题的方法。迭代算法一般用于数值值递推出新值的解决问题的方法。迭代算法一般用于数值计算。迭代法应该是我们早已熟悉的算法策略，程序设计计算。迭代法应该是我们早已熟悉的算法策略，程序设计语言课程中所学的累加、累乘都是迭代算法策略的基础应语言课程中所学的累加、累乘都

2、是迭代算法策略的基础应用。用。利用迭代算法策略求解问题，设计工作主要有三步：利用迭代算法策略求解问题，设计工作主要有三步： 1确定迭代模型确定迭代模型 2建立迭代关系式建立迭代关系式 3对迭代过程进行控制对迭代过程进行控制411 递推法 【例【例1】兔子繁殖问题】兔子繁殖问题问题描述：一对兔子从出生后第三个月开始，每月生一对小兔问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔

3、子。个月各有多少只兔子。问题分析：因一对兔子从出生后第三个月开始每月生一对小兔问题分析：因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数子，则每月新下小兔子的对儿数(用斜体数字表示用斜体数字表示)显然由前显然由前两个月的小兔子的对儿数决定。则繁殖过程如下：两个月的小兔子的对儿数决定。则繁殖过程如下： 一月一月 二月二月 三月三月 四月四月 五月五月 六月六月 1 1 1+1=2 2+1=3 3+2=5 5+3=8 算法算法1 1： main( )main( ) int i,a=1,b=1; int i,a=1,b=1; print(a,b); print(a,b); f

4、or(i=1;i for(i=1;i=10;i+)=10;i+) c=a+b; c=a+b; print (c); print (c); a=b; a=b; b=c b=c； 数学建模：数学建模：y1=y2=1y1=y2=1，yn=yn-1+yn-2yn=yn-1+yn-2，n=3n=3，4 4，5 5，。算法算法2 2： 表表4-1 4-1 递推迭代表达式递推迭代表达式1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9a b c=a+b a=b+c b=a+c c=a+b a=b+c b=a+c a b c=a+b a=b+c b=a+c c=a+b a=b+c b=a+c

5、 由此归纳出可以用由此归纳出可以用“c=a+b; a=b+c; b=c+a;”c=a+b; a=b+c; b=c+a;”做循环做循环“不变式不变式”。算法算法2 2如下：如下： main( )main( ) int i,a=1,b=1; int i,a=1,b=1; print(a,b); print(a,b); for(i=1; i for(i=1; i=4;i+)=4;i+) c=a+b; a=b+c; b=c+a; print(a,b,c); c=a+b; a=b+c; b=c+a; print(a,b,c); 算法算法2 2，最后输出的并不是，最后输出的并不是1212项，而是项，而是2

6、+32+3* *4 4共共1414项。项。 表表4-2 4-2 递推迭代表达式递推迭代表达式1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9a b a=a+b b=a+b a=a+b b=a+b a b a=a+b b=a+b a=a+b b=a+b 由此归纳出可以用由此归纳出可以用“a=a+b; b=a+b;”a=a+b; b=a+b;”做循环做循环“不变式不变式”，从而得到以下算法，从而得到以下算法3:3:main( )main( ) int i,a=1,b=1; int i,a=1,b=1; print(a,b); print(a,b); for(i=1; i for

7、(i=1; i=5;i+)=5;i+) a=a+b; b=a+b; print(a,b); a=a+b; b=a+b; print(a,b); 【例【例2 2】求两个整数的最大公约数。】求两个整数的最大公约数。数学建模：辗转相除法是根据递推策略设计的。数学建模：辗转相除法是根据递推策略设计的。不妨设两个整数不妨设两个整数abab且且a a除以除以b b商商x x余余c c；则；则a-bx=ca-bx=c，不难看出，不难看出a a、b b的最大公约数也是的最大公约数也是c c的约数一个数能整除等式左边就一定能整除的约数一个数能整除等式左边就一定能整除等式的右边），则等式的右边），则a a、b b

8、的最大公约数与的最大公约数与b b、c c的最大公约数相同。的最大公约数相同。同样方法推出同样方法推出b b、c c的最大公约数与的最大公约数与，直到余数为，直到余数为0 0时，除数即时，除数即为所求的最大公约数。为所求的最大公约数。算法设计：循环算法设计：循环“不变式第一次是求不变式第一次是求a a、b b相除的余数相除的余数c c，第二，第二次还是求次还是求“a”“b” a”“b” 相除的余数，经相除的余数，经a=b,b=ca=b,b=c操作，就实现了第操作，就实现了第二次还是求二次还是求“a”“b” a”“b” 相除的余数，这就找到了循环不变式。循相除的余数，这就找到了循环不变式。循环在

9、余数环在余数c c为为0 0时结束。时结束。 算法如下：算法如下：mainmain（）（） int a, b; int a, b; input(a,b); input(a,b); if(b=0) if(b=0) print(“data error”); print(“data error”); return; return; else else c = a mod b; c = a mod b; while c0 while c0 a=b; a=b; b=c; b=c; c=a mod b; c=a mod b; print(b); print(b); 4.1.2 4.1.2 倒推法倒推法 所

10、谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从所谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从 后向前推解问题的方法。如下面的例题，因不同方面的需求而采后向前推解问题的方法。如下面的例题，因不同方面的需求而采用了倒推策略。用了倒推策略。例例1 1在不知前提条件的情况下，经过从后向前递推，从而求解问在不知前提条件的情况下，经过从后向前递推，从而求解问题。即由结果倒过来推解它的前提条件。又如例题。即由结果倒过来推解它的前提条件。又如例2 2由于存储的要由于存储的要求，而必须从后向前进行推算。另外，在对一些问题进行分析或求，而必须从后向前进行推算。另外，在对一些问题进行分析或建立数学模型

11、时，从前向后分析问题感到比较棘手，而采用倒推建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法如例法如例3 3），则问题容易理解和解决。下面分别看这几个例子：），则问题容易理解和解决。下面分别看这几个例子：【例【例1 1】猴子吃桃问题】猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第到第1010天时就只有一个桃子了，求原有多少个桃？天时就只有一个桃子了，求原有多少个桃？数学模型：每天的桃子数为：数学模型：每天的桃子数为：a10=1, a9=(1+a10)a10=1, a9=(1+a10)* *2, 2, a8=(1+a

12、9)a8=(1+a9)* *2,a10=12,a10=1， 递推公式为：递推公式为：ai=(1+ai+1)ai=(1+ai+1)* *2 I = 9,8,7,612 I = 9,8,7,61算法如下算法如下 ： main( )main( ) int i,s; int i,s; s=1; s=1; for (i=9 ;i=1;i=i-1) for (i=9 ;i=1;i=i-1) s=(s+1) s=(s+1)* *2 2 print (s) print (s)； 【例【例2 2】 输出如图输出如图4-14-1的杨辉三角形限的杨辉三角形限定用一个一维数组完成）。定用一个一维数组完成）。数学模型：

13、上下层规律较明显，中间的数数学模型：上下层规律较明显，中间的数等于上行左上、右上两数之和。等于上行左上、右上两数之和。问题分析：题目中要求用一个一维数组即问题分析：题目中要求用一个一维数组即完成。数组空间一定是由下标从小到大完成。数组空间一定是由下标从小到大利用的，这样其实杨辉三角形是按下图利用的，这样其实杨辉三角形是按下图4-24-2形式存储的。若求形式存储的。若求n n层，则数组最多层，则数组最多存储存储n n个数据。个数据。1 11 11 11 2 11 2 11 3 3 11 3 3 11 4 6 4 11 4 6 4 1图图4-2 4-2 杨辉三角形存储格式杨辉三角形存储格式 算法设

14、计：算法设计： A1 = Ai=1A1 = Ai=1Aj = Aj + Aj-1 j=i-1Aj = Aj + Aj-1 j=i-1，i-2i-2，2 2i i行行 i-1i-1行行 i-1i-1行行算法如下：算法如下：main( )main( ) int n,i,j,a100; int n,i,j,a100;input(n); input(n); print(“1”); print(“print(“1”); print(“换行符换行符”););a1=a2=1;a1=a2=1;print(a1,a2); print(“print(a1,a2); print(“换行符换行符”););for (i

15、=3;i=n;i=i+1)for (i=3;i1j1，j=j-1) j=j-1) aj=aj+aj-1; aj=aj+aj-1; for (j=1;j=i;j=j+1) print(aj); for (j=1;j=i;j=j+1) print(aj); print(“ print(“换行符换行符”);); 【例【例3 3】穿越沙漠问题】穿越沙漠问题 用一辆吉普车穿越用一辆吉普车穿越10001000公里的沙漠。吉普车的总装油量为公里的沙漠。吉普车的总装油量为500500加仑，耗油率为加仑，耗油率为1 1加仑加仑/ /公里。由于沙漠中没有油库，公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临

16、时油库。该吉普车以最少必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。油量。 问题分析：问题分析： 1 1先看一简单问题：有一位探险家用先看一简单问题：有一位探险家用5 5天的时间徒步天的时间徒步 横穿横穿A A、B B两村，两村间是荒无人烟的沙漠，如果一两村，两村间是荒无人烟的沙漠，如果一 个人只能担负个人只能担负3 3天的食物和水，那么这个探险家至天的食物和水，那么这个探险家至 少雇几个人才能顺利通过沙漠。少雇几个人才能顺利通过沙漠。 A A城雇用一人与探险家同带城雇用一人与探险家同

17、带3 3天食物同行一天，然后被雇天食物同行一天，然后被雇 人带一天食物返回，并留一天食物给探险家，这样探险人带一天食物返回，并留一天食物给探险家，这样探险 家正好有家正好有3 3天的食物继续前行，并于第三天打电话雇天的食物继续前行，并于第三天打电话雇B B城城 人带人带3 3天食物出发，第四天会面他们会面，探险家得到一天食物出发，第四天会面他们会面，探险家得到一 天的食物赴天的食物赴B B城。如图城。如图4-34-3主要表示了被雇用二人的行程。主要表示了被雇用二人的行程。 A B A B 图图4-3 4-3 被雇用二人的行程被雇用二人的行程 2 2贮油点问题要求要以最少的耗油量穿越沙漠，即到达

18、终贮油点问题要求要以最少的耗油量穿越沙漠，即到达终 点时，沙漠中的各临时油库和车的装油量均为点时，沙漠中的各临时油库和车的装油量均为0 0。这样只。这样只 能从终点开始向前倒着推解贮油点和贮油量。能从终点开始向前倒着推解贮油点和贮油量。数学模型：根据耗油量最少目标的分析，下面从后向前分段数学模型：根据耗油量最少目标的分析，下面从后向前分段讨论。讨论。第一段长度为第一段长度为500500公里且第一个加油点贮油为公里且第一个加油点贮油为500500加仑。加仑。第二段中为了贮备油，吉普车在这段的行程必须有往返。下第二段中为了贮备油，吉普车在这段的行程必须有往返。下面讨论怎样走效率高：面讨论怎样走效率

19、高：1 1首先不计方向这段应走奇数次保证最后向前走）。首先不计方向这段应走奇数次保证最后向前走）。2 2每次向前行进时吉普车是满载。每次向前行进时吉普车是满载。3 3要能贮存够下一加油点的贮油量，路上耗油又最少。要能贮存够下一加油点的贮油量，路上耗油又最少。下图是满足以上条件的最佳方案，此段共走下图是满足以上条件的最佳方案，此段共走3 3次：第一、二次：第一、二次来回耗油次来回耗油2/32/3贮油贮油1/31/3，第三次耗油，第三次耗油1/31/3贮油贮油2/32/3，所以第，所以第二个加油点贮油为二个加油点贮油为10001000加仑。由于每公里耗油率为加仑。由于每公里耗油率为1 1加仑，加仑

20、，则此段长度为则此段长度为500/3500/3公里。公里。第三段与第二段思路相同。下图是一最佳方案此段共走第三段与第二段思路相同。下图是一最佳方案此段共走5 5次：次：第一、二次来回耗油第一、二次来回耗油2/52/5贮油贮油3/53/5，第三、四次来回耗油，第三、四次来回耗油2/52/5贮油贮油3/53/5，第五次耗油，第五次耗油1/51/5贮油贮油4/54/5，第三个加油点贮油，第三个加油点贮油为为15001500加仑。此段长度为加仑。此段长度为500/5500/5。 500/5 500/5公里公里 第二第二 第三第三 终点终点贮油点贮油点500500）贮油点贮油点10001000）贮贮油点

21、油点15001500）图图4-4 4-4 贮油点及贮油量示意贮油点及贮油量示意综上分析，从终点开始分别间隔综上分析，从终点开始分别间隔 500500，500/3500/3，500/5500/5，500/7500/7，（公里设立贮油点，直到总距离超过（公里设立贮油点，直到总距离超过10001000公里。每个贮油点的油量为公里。每个贮油点的油量为500500，10001000，15001500，。 算法设计：由模型知道此问题并不必用倒推算法解决只算法设计：由模型知道此问题并不必用倒推算法解决只是分析过程用的是倒推法），只需通过累加算法就能解决。是分析过程用的是倒推法），只需通过累加算法就能解决。变

22、量说明：变量说明：disdis表示距终点的距离，表示距终点的距离，1000- dis1000- dis则表示距起则表示距起点的距离，点的距离，k k表示贮油点从后到前的序号。表示贮油点从后到前的序号。desertdesert（ ） int dis int dis，k k，oil,k;oil,k; dis=500;k=1;oil=500; dis=500;k=1;oil=500; do do print(“storepoint”,k,”distance”,1000- print(“storepoint”,k,”distance”,1000-dis,”oilquantity”,oil)dis,”o

23、ilquantity”,oil)； k=k+1;k=k+1; dis=dis+500/(2 dis=dis+500/(2* *k-1);k-1); oil= 500 oil= 500* *k;k; while ( dis1000) while ( dis1000) o i l = 5 0 0 o i l = 5 0 0 * * ( k - 1 ) + ( 1 0 0 0 - d i s )( k - 1 ) + ( 1 0 0 0 - d i s ) * * ( 2( 2 * * k - 1 ) ; k - 1 ) ; print(“storepoint”,k,”distance”,0,”oi

24、lquantity”,print(“storepoint”,k,”distance”,0,”oilquantity”,oil)oil)； 4.1.3 4.1.3 迭代法解方程迭代法解方程迭 代 法 解 方 程 的 实 质 是 按 照 下 列 步 骤 构 造 一 个 序 列迭 代 法 解 方 程 的 实 质 是 按 照 下 列 步 骤 构 造 一 个 序 列x0,x1,xn,x0,x1,xn,来逐步逼近方程来逐步逼近方程f(x)=0f(x)=0的解：的解： 1 1选取适当的初值选取适当的初值x0 x0； 2 2确定迭代格式，即建立迭代关系，需要将方程确定迭代格式，即建立迭代关系，需要将方程f(x

25、)=0f(x)=0改改 写为写为x=(x)x=(x)的等价形式；的等价形式； 构造序列构造序列x0 x0，x1x1，xnxn，即先求得，即先求得x1=(x0)x1=(x0)，再，再求求 x2=(x1)x2=(x1)，如此反复迭代，就得到一个数列如此反复迭代，就得到一个数列x0 x0， x1x1，xnxn，若这个数列收敛，即存在极值，且函数，若这个数列收敛，即存在极值，且函数 (x)(x)连续，则很容易得到这个极限值连续，则很容易得到这个极限值 x x* *就是方程就是方程f(x)=0f(x)=0的根。的根。 【例【例1 1】迭代法求方程组根】迭代法求方程组根算法说明：方程组解的初值算法说明：方

26、程组解的初值X=X=（x0 x0，x1x1，xn-1xn-1）, ,迭代迭代关系方程组为：关系方程组为：xi=gi(X)(i=0,1,n-1),wxi=gi(X)(i=0,1,n-1),w为解的精度为解的精度, ,则则算法如下：算法如下： for (i=0;in;i+) for (i=0;in;i+) xi= xi=初始近似根初始近似根; ; do k=k+1; do k=k+1; for (i=0;in;i yi=xi; for (i=0;in;i yi=xi; for (i=0;in;i+) xi=gi(X); for (i=0;in;i+) xi=gi(X); for (i=0;in;i

27、+) c=c+fabs(yi-xi) for (i=0;iw and kw and kmaxn )； for (i=0;in;i+) for (i=0;in;i+) print(i print(i，“变量的近似根是变量的近似根是”，xi)xi)； 【例【例2 2】牛顿迭代法】牛顿迭代法 牛顿迭代法又称为切线法，它比一般的迭代法有更高的收敛速牛顿迭代法又称为切线法，它比一般的迭代法有更高的收敛速度，如图度，如图4-54-5所示。首先所示。首先, , 选择一个接近函数选择一个接近函数f(x)f(x)零点的零点的x0, x0, 计算计算相应的相应的f(x0)f(x0)和切线斜率和切线斜率f(x0)f

28、(x0)（这里（这里f f 表示函数表示函数f f的导数）。的导数）。然后我们计算穿过点然后我们计算穿过点(x0,f (x0)(x0,f (x0)且斜率为且斜率为f (x0)f (x0)的直线方程的直线方程为：为：和和x x轴的交点的轴的交点的x x坐标坐标, , 也就是求如下方程的解：也就是求如下方程的解：)()(000 xxxfxfy0000)()(xxxfxf图图4-5 4-5 牛顿迭代法牛顿迭代法 示意图示意图迭代公式可化简为：迭代公式可化简为：此公式就是有名的牛顿迭代公式。已经证明此公式就是有名的牛顿迭代公式。已经证明, 如果如果f是连是连续的续的, 并且待求的零点并且待求的零点x是

29、孤立的是孤立的, 那么在零点那么在零点x周围存在周围存在一个区域一个区域, 只要初始值只要初始值x0位于这个邻近区域内位于这个邻近区域内, 那么牛顿那么牛顿法必定收敛。法必定收敛。 下面给出用牛顿迭代法，求形如下面给出用牛顿迭代法，求形如ax3+bx2+cx+d=0方程根的方程根的算法，系数算法，系数a、b、c、d的值依次为的值依次为1、2、3、4，由主函数，由主函数输入。求输入。求x在在1附近的一个实根。求出根后由主函数输出。附近的一个实根。求出根后由主函数输出。 main( ) float a , b, c, d, fx; print(输入系数输入系数 a,b,c,d:); input(a,b,c,d); fx=f(a,b,c,d); printf(方程的根为：方程的根为：,fx); 令令a0,b0=a,ba0,b0=a,b，c0=(a0+b0)/2c0=(a0+b0)/2，若，若f(c0)=0f(c0)=0，则，则c0