《算法策略》PPT课件.ppt

第四章第四章基本的算法策略基本的算法策略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）也称）也称“辗转法辗转法”，是一种不断用变量的旧，是一种不断用变量的旧值递推出新值的解决问题的方法。迭代算法一般用于数值值递推出新值的解决问题的方法。迭代算法一般用于数值计算。迭代法应该是我们早已熟悉的算法策略，程序设计计算。迭代法应该是我们早已熟悉的算法策略，程序设计语言课程中所学的累加、累乘都是迭代算法策略的基础应语言课程中所学的累加、累乘都是迭代算法策略的基础应用。用。利用迭代算法策略求解问题，设计工作利用迭代算法策略求解问题，设计工作主要有三步主要有三步：1）确定迭代模型）确定迭代模型2）建立迭代关系式）建立迭代关系式3）对迭代过程进行控制）对迭代过程进行控制411 递推递推法【例【例1】兔子繁殖问题】兔子繁殖问题问问题题描描述述：一一对对兔兔子子从从出出生生后后第第三三个个月月开开始始，每每月月生生一一对对小小兔兔子子。小小兔兔子子到到第第三三个个月月又又开开始始生生下下一一代代小小兔兔子子。假假若若兔兔子子只只生生不不死死，一一月月份份抱抱来来一一对对刚刚出出生生的的小小兔兔子子，问问一一年年中中每每个个月月各有多少只兔子。各有多少只兔子。问问题题分分析析：因因一一对对兔兔子子从从出出生生后后第第三三个个月月开开始始每每月月生生一一对对小小兔兔子子，则则每每月月新新下下小小兔兔子子的的对对儿儿数数(用用斜斜体体数数字字表表示示)显显然然由由前前两个月的小兔子的对儿数决定。则繁殖过程如下：两个月的小兔子的对儿数决定。则繁殖过程如下：一月一月二月二月三月三月四月四月五月五月六月六月111+1=22+1=33+2=55+3=8算法算法1 1：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=10;i+)=10;i+)c=a+b;c=a+b;print(c);print(c);a=b;a=b;b=c b=c；数学建模：数学建模：y y1 1=y=y2 2=1=1，y yn n=y=yn-1n-1+y+yn-2n-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 由此归纳出可以用由此归纳出可以用“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+3*42+3*4共共1414项。项。表表4-2 4-2 递推迭代表达式递推迭代表达式1 21 2 3 4 5 6 7 8 93 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(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);算法算法算法算法3 3 3 3：【例【例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的的最最大大公公约约数数与与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”相相除除的的余余数数，这这就就找找到到了了循循环环不不变变式式。循循环环在余数在余数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”);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 倒推法倒推法 所所谓谓倒倒推推法法：是是对对某某些些特特殊殊问问题题所所采采用用的的违违反反通通常常习习惯惯的的，从从 后后向向前前推推解解问问题题的的方方法法。如如下下面面的的例例题题，因因不不同同方方面面的的需需求求而而采采用了倒推策略。用了倒推策略。例例1在在不不知知前前提提条条件件的的情情况况下下，经经过过从从后后向向前前递递推推，从从而而求求解解问问题题。即即由由结结果果倒倒过过来来推推解解它它的的前前提提条条件件。又又如如例例2由由于于存存储储的的要要求求，而而必必须须从从后后向向前前进进行行推推算算。另另外外，在在对对一一些些问问题题进进行行分分析析或或建建立立数数学学模模型型时时，从从前前向向后后分分析析问问题题感感到到比比较较棘棘手手，而而采采用用倒倒推推法（如例法（如例3），则问题容易理解和解决。下面分别看这几个例子：），则问题容易理解和解决。下面分别看这几个例子：【例【例1 1】猴子吃桃问题猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第到第1010天时就只有一个桃子了，求原有多少个桃？天时就只有一个桃子了，求原有多少个桃？数数 学学 模模 型型：每每 天天 的的 桃桃 子子 数数 为为：a10=1,a10=1,a9=(1+a10)*2,a9=(1+a10)*2,a8=(1+a9)*2,a10=1a8=(1+a9)*2,a10=1，递推公式为：递推公式为：ai=(1+ai+1)*2 I=9,8,7,61ai=(1+ai+1)*2 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)*2 s=(s+1)*2 print(s)print(s)；【例【例2 2】输出如图输出如图4-14-1的杨辉三角形（限的杨辉三角形（限定用一个一维数组完成）。定用一个一维数组完成）。数学模型：数学模型：上下层规律较明显，中间的数上下层规律较明显，中间的数等于上行左上、右上两数之和。等于上行左上、右上两数之和。问题分析：问题分析：题目中要求用一个一维数组即题目中要求用一个一维数组即完成。数组空间一定是由下标从小到大完成。数组空间一定是由下标从小到大利用的，这样其实杨辉三角形是按下图利用的，这样其实杨辉三角形是按下图4-24-2形式存储的。若求形式存储的。若求n n层，则数组最多层，则数组最多存储存储n n个数据。个数据。1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1 3 3 1 1 3 3 1 1 3 3 1 1 3 3 11 4 6 4 11 4 6 4 11 4 6 4 11 4 6 4 1 图图图图4-1 4-1 4-1 4-1 杨辉三角形杨辉三角形杨辉三角形杨辉三角形1 11 11 11 2 11 2 11 3 3 11 3 3 11 14 4 6 6 4 4 1 1图图4-2杨辉三角形存储格式杨辉三角形存储格式 算法设计：算法设计：A1=Ai=1A1=Ai=1Aj=Aj+Aj-1 j=i-1Aj=Aj+Aj-1 j=i-1，i-2i-2，2 2i i行行 i-1 i-1行行 i-1 i-1行行算法如下：算法如下：main()int n,i,j,a100;input(n);print(“1”);print(“换行符换行符”);a1=a2=1;print(a1,a2);print(“换行符换行符”);for(i=3;i1，j=j-1)aj=aj+aj-1;for(j=1;j=i;j=j+1)print(aj);print(“换行符换行符”);【例【例3 3】穿越沙漠问题穿越沙漠问题 用一辆吉普车穿越用一辆吉普车穿越10001000公里的沙漠。吉普车的总装油量为公里的沙漠。吉普车的总装油量为500500加仑，耗油率为加仑，耗油率为1 1加仑加仑/公里。由于沙漠中没有油库，公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。油量。问题分析：问题分析：1 1）先看一简单问题：有一位探险家用先看一简单问题：有一位探险家用5 5天的时间徒步天的时间徒步 横穿横穿A A、B B两村，两村间是荒无人烟的沙漠，如果一两村，两村间是荒无人烟的沙漠，如果一 个人只能担负个人只能担负3 3天的食物和水，那么这个探险家至天的食物和水，那么这个探险家至 少雇几个人才能顺利通过沙漠。少雇几个人才能顺利通过沙漠。A A城雇用一人与探险家同带城雇用一人与探险家同带3 3天食物同行一天，然后被雇天食物同行一天，然后被雇 人带一天食物返回，并留一天食物给探险家，这样探险人带一天食物返回，并留一天食物给探险家，这样探险 家正好有家正好有3 3天的食物继续前行，并于第三天打电话雇天的食物继续前行，并于第三天打电话雇B B城城 人带人带3 3天食物出发，第四天会面他们会面，探险家得到一天食物出发，第四天会面他们会面，探险家得到一 天的食物赴天的食物赴B B城。如图城。如图4-34-3主要表示了被雇用二人的行程。主要表示了被雇用二人的行程。A BA B 图图4-3 4-3 被雇用二人的行程被雇用二人的行程 2 2）贮油点问题要求要以最少的耗油量穿越沙漠，即到达终贮油点问题要求要以最少的耗油量穿越沙漠，即到达终 点时，沙漠中的各临时油库和车的装油量均为点时，沙漠中的各临时油库和车的装油量均为0 0。这样只。这样只 能从终点开始向前倒着推解贮油点和贮油量。能从终点开始向前倒着推解贮油点和贮油量。数数学学模模型型：根根据据耗耗油油量量最最少少目目标标的的分分析析，下下面面从从后后向向前前分分段段讨论。讨论。第一段长度为第一段长度为500500公里且第一个加油点贮油为公里且第一个加油点贮油为500500加仑。加仑。第第二二段段中中为为了了贮贮备备油油，吉吉普普车车在在这这段段的的行行程程必必须须有有往往返返。下下面讨论怎样走效率高：面讨论怎样走效率高：1 1）首先不计方向这段应走奇数次（保证最后向前走）。首先不计方向这段应走奇数次（保证最后向前走）。2 2）每次向前行进时吉普车是满载。每次向前行进时吉普车是满载。3 3）要能贮存够下一加油点的贮油量，路上耗油又最少。要能贮存够下一加油点的贮油量，路上耗油又最少。下下图图是是满满足足以以上上条条件件的的最最佳佳方方案案，此此段段共共走走3 3次次：第第一一、二二次次来来回回耗耗油油2/32/3贮贮油油1/31/3，第第三三次次耗耗油油1/31/3贮贮油油2/32/3，所所以以第第二二个个加加油油点点贮贮油油为为10001000加加仑仑。由由于于每每公公里里耗耗油油率率为为1 1加加仑仑，则此段长度为则此段长度为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/5500/5公里公里 第二第二 第三第三 终点终点贮油点（贮油点（500500）贮油点（贮油点（10001000）贮油点（贮油点（15001500）图图4-4 4-4 贮油点及贮油量示意贮油点及贮油量示意综上分析综上分析，从终点开始分别间隔，从终点开始分别间隔 500 500，500/3500/3，500/5500/5，500/7500/7，（公里）设立贮油点，直到总距离超过（公里）设立贮油点，直到总距离超过10001000公里。每个贮油点的油量为公里。每个贮油点的油量为500500，10001000，15001500，。算法设计：算法设计：由模型知道此问题并不必用倒推算法解决（只由模型知道此问题并不必用倒推算法解决（只是分析过程用的是倒推法），只需通过累加算法就能解决。是分析过程用的是倒推法），只需通过累加算法就能解决。变量说明：变量说明：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,”oilquantity”,oil)；k=k+1;k=k+1;dis=dis+500/(2*k-1);dis=dis+500/(2*k-1);oil=500*k;oil=500*k;while(dis1000)while(dis1000)oil=500*(k-1)+(1000-dis)*(2*k-1);print(“storepoint”,k,”distance”,0,”oilquantity”,oil)print(“storepoint”,k,”distance”,0,”oilquantity”,oil)；4.1.3 4.1.3 迭代法解方程迭代法解方程迭迭代代法法解解 方方 程程的的 实实 质质是是 按按照照下下 列列步步骤骤 构构造造一一个个 序序列列x x0 0,x,x1 1,x,xn n,来逐步逼近方程来逐步逼近方程f(x)=0f(x)=0的解：的解：1 1）选选取适当的初取适当的初值值x x0 0；2 2）确确定定迭迭代代格格式式，即即建建立立迭迭代代关关系系，需需要要将将方方程程f(x)=0f(x)=0改改 写写为为x=(x)x=(x)的等价形式；的等价形式；构造序列构造序列x0，x1，xn，即先求得，即先求得x1=(x0)，再求，再求 x2=(x1)，如此反复迭代，就得到一个数列如此反复迭代，就得到一个数列x0，x1，xn，若这个数列收敛，即存在极值，且函数，若这个数列收敛，即存在极值，且函数 (x)连续，则很容易得到这个极限值连续，则很容易得到这个极限值x*就是方程就是方程f(x)=0的根。的根。【例【例1 1】迭代法求方程迭代法求方程组组根根算法算法说说明：明：方程方程组组解的初解的初值值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+)for(i=0;in;i+)xi=gi(X);xi=gi(X);for(i=0;in;i+)c=c+fabs(yi-xi)for(i=0;iw and kw and kmaxn)；for(i=0;in;i+)for(i=0;i=1e-4);while(fabs(x1-x0)=1e-4);return(x1);return(x1);令令a0,b0=a,ba0,b0=a,b，c0=(a0+b0)/2c0=(a0+b0)/2，若若f(c0)=0f(c0)=0，则则c0c0为为方方程程 f(x)=0f(x)=0的的 根根；否否 则则，若若 f(a0)f(a0)与与 f(c0)f(c0)异异 号号，即即 f(a0)*f(c0)0f(a0)*f(c0)0，则则令令a1,b1=a0,c0a1,b1=a0,c0；若若f(b0)f(b0)与与f(c0)f(c0)异异号号，即即 f(b0)*f(c0)0 f(b0)*f(c0)0，则则令令a1,b1=c0,b0a1,b1=c0,b0。依此做下去，当发现依此做下去，当发现f(cn)=0时，或区间时，或区间an,bn足够小，足够小，比如比如|an-bn时，就认为找到了方程的根。时，就认为找到了方程的根。用二分法求一元非线性方程用二分法求一元非线性方程f(x)=x3/2+2x2-8=0（其中（其中表示幂运算）在区间表示幂运算）在区间0，2上的近似实根上的近似实根r，精确到，精确到0.0001.算算法如下：法如下：图图4-6 4-6 二分法二分法求求解解方程方程示意示意【例【例【例【例3 3 3 3】二分法】二分法】二分法】二分法求求求求解方程解方程解方程解方程f(x)=0f(x)=0f(x)=0f(x)=0根根根根 用二用二用二用二分法求解方程分法求解方程分法求解方程分法求解方程f(x)=0f(x)=0f(x)=0f(x)=0根的前提条件是：根的前提条件是：根的前提条件是：根的前提条件是：f(x)f(x)f(x)f(x)在求解的区在求解的区在求解的区在求解的区间间间间a,ba,ba,ba,b上是上是上是上是连续连续连续连续的，且的，且的，且的，且已知已知已知已知f(a)f(a)f(a)f(a)与与与与f(b)f(b)f(b)f(b)异号，即异号，即异号，即异号，即 f(a)*f(b)0 f(a)*f(b)0 f(a)*f(b)0 f(a)*f(b)0。main()main()float x,x1=0,x2=2,f1,f2,f;float x,x1=0,x2=2,f1,f2,f;print(“input a,b(f(a)*f(b)0)”);input(a,b);print(“input a,b(f(a)*f(b)0)printf(No root);return;if(f1*f20)printf(No root);return;do do x=(x1+x2)/2;x=(x1+x2)/2;f=x*x*x/2+2*x*x-8;f=x*x*x/2+2*x*x-8;if(f=0)break;if(f=0)break;if(f1*f0.0)x1=x;f1=x1*x1*x1/2+2*x1*x1-8;if(f1*f0.0)x1=x;f1=x1*x1*x1/2+2*x1*x1-8;else x2=x;else x2=x;while(fabs(f)=1e-4);while(fabs(f)=1e-4);print(root=,x);print(root=,x);