算法策略学习.pptx

《算法策略学习.pptx》由会员分享，可在线阅读，更多相关《算法策略学习.pptx（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.1 迭代算法迭代法（Iteration）也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。迭代算法一般用于数值计算。迭代法应该是我们早已熟悉的算法策略，程序设计语言课程中所学的累加、累乘都是迭代算法策略的基础应用。利用迭代算法策略求解问题，设计工作主要有三步：1）确定迭代模型 2）建立迭代关系式 3）对迭代过程进行控制第1页/共25页4 41 11 1 递推法 【例1】兔子繁殖问题问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。问题分析：因一对兔子从

2、出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数(用斜体数字表示)显然由前两个月的小兔子的对儿数决定。则繁殖过程如下：一月 二月 三月 四月 五月 六月 1 1 1+1=2 2+1=3 3+2=5 5+3=8 第2页/共25页算法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

3、-1n-1+y+yn-2n-2，n=3n=3，4 4，5 5，。第3页/共25页算法2 2：表4-1 4-1 递推迭代表达式1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 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

4、);for(i=1;i for(i=1;i=4;i+)=4;i+)c=a+b;c=a+b;a=b+c;a=b+c;b=c+a;b=c+a;print(a,b,c);print(a,b,c);算法2 2，最后输出的并不是1212项，而是2+3*42+3*4共1414项。第4页/共25页 表4-2 4-2 递推迭代表达式1 21 2 3 4 5 6 7 8 3 4 5 6 7 8 9 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;”做循环“不变式”，从而得到以下算法

5、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;a=a+b;b=a+b;b=a+b;print(a,b);print(a,b);算法算法3 3 3 3：第5页/共25页【例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

6、 b的最大公约数与b b、c c的最大公约数相同。同样方法推出b b、c c的最大公约数与，直到余数为0 0时，除数即为所求的最大公约数。算法设计：循环“不变式”第一次是求a a、b b相除的余数c c，第二次还是求“a a”“b b”相除的余数，经a=b,b=ca=b,b=c操作，就实现了第二次还是求“a a”“b b”相除的余数，这就找到了循环不变式。循环在余数c c为0 0时结束。第6页/共25页算法如下：mainmain（）int a,b;int a,b;input(a,b);input(a,b);if(b=0)if(b=0)print(“data error”);return;els

7、e 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);第7页/共25页4.1.2 4.1.2 倒推法 所谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从 后向前推解问题的方法。如下面的例题，因不同方面的需求而采用了倒推策略。例1在不知前提条件的情况下，经过从后向前递推，从而求解问题。即由结果倒过来推解它的前提条件。又如例2由于存储的要求，而必须从后向前进行推算。另外，在对一些问题进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法（

8、如例3），则问题容易理解和解决。下面分别看这几个例子：第8页/共25页【例1 1】猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第1010天时就只有一个桃子了，求原有多少个桃？数学模型：每天的桃子数为：a10=1,a9=(1+a10)*2,a8=(1+a9)*2,a10=1,a9=(1+a10)*2,a8=(1+a9)*2,a10=1a10=1，递推公式为：ai=(1+ai+1)*2 I=9,8,7,6ai=(1+ai+1)*2 I=9,8,7,61 1算法如下 ：main()main()int i,s;int i,s;s=1;s=1;for(i=9;i=1;i=i-1)fo

9、r(i=9;i=1;i=i-1)s=(s+1)*2 s=(s+1)*2 print(s)print(s)；第9页/共25页【例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

10、 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-1i-1行 i-1i-1行第10页/共25页算法如下：main()int n,i,j,a100;input(n);print(“1”);print(“换行符”);a1=a2=1;print(a1,a2);print(“

11、换行符”);for(i=3;i1，j=j-1)aj=aj+aj-1;for(j=1;j=i;j=j+1)print(aj);print(“换行符”);第11页/共25页【例3 3】穿越沙漠问题 用一辆吉普车穿越10001000公里的沙漠。吉普车的总装油量为500500加仑，耗油率为1 1加仑/公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。问题分析：1 1）先看一简单问题：有一位探险家用5 5天的时间徒步 横穿A A、B B两村，两村间是荒无人烟的沙漠，如果一 个人只能担负3 3天的食物和水，那么这个探险家至

12、少雇几个人才能顺利通过沙漠。第12页/共25页 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。这样只 能从终点开始向前倒着推解贮油点和贮油量。第13页/共25页数学模型：根据耗油量最少目标的分析，下面

13、从后向前分段讨论。第一段长度为500500公里且第一个加油点贮油为500500加仑。第二段中为了贮备油，吉普车在这段的行程必须有往返。下面讨论怎样走效率高：1 1）首先不计方向这段应走奇数次（保证最后向前走）。2 2）每次向前行进时吉普车是满载。3 3）要能贮存够下一加油点的贮油量，路上耗油又最少。第14页/共25页下图是满足以上条件的最佳方案，此段共走3 3次：第一、二次来回耗油2/32/3贮油1/31/3，第三次耗油1/31/3贮油2/32/3，所以第二个加油点贮油为10001000加仑。由于每公里耗油率为1 1加仑，则此段长度为500/3500/3公里。第三段与第二段思路相同。下图是一最

14、佳方案此段共走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 贮油点及贮油量示意第15页/共25页综上分析，从终点开始分别间隔 500500，500/3500/3，500/5500/5，500/7500/7，（公里）设立贮油点，直到总距离超过10001000公里。每个贮油点的油量

15、为500500，10001000，15001500，。算法设计：由模型知道此问题并不必用倒推算法解决（只是分析过程用的是倒推法），只需通过累加算法就能解决。变量说明：disdis表示距终点的距离，1000-1000-disdis则表示距起点的距离，k k表示贮油点从后到前的序号。第16页/共25页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(print(“storepointstorepoint”,k,k,”distancedistance”,1

16、000-,1000-dis,dis,”oilquantityoilquantity”,oil),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(print(“storepointstorepoint”,k,k,”distancedistance”,0,0,”oilquantityoilquantity”,oil,oil)；第17页/共25页4.1.3 4.1

17、.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的根。第18页/共25页【例1 1】迭代法求方程组根算法说明：方程组解的初值X

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

19、in;i+)(i=0;i=1e-4);while(fabs(x1-x0)=1e-4);return(x1);return(x1);第22页/共25页 令 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)0f(b0)*f(c0)0，则 令a1

20、,b1=c0,b0a1,b1=c0,b0。依此做下去，当发现f(cn)=0时，或区间an,bn足够小，比如|an-bn|0.0001时，就认为找到了方程的根。用二分法求一元非线性方程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)在求解的区间在求解的区间

21、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)0f(a)*f(b)0f(a)*f(b)0f(a)*f(b)0。第23页/共25页main()main()float x,x1=0,x2=2,f1,f2,f;float x,x1=0,x2=2,f1,f2,f;print(print(“input a,b(f(a)*f(b)0)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);第24页/共25页感谢您的观看！第25页/共25页