第四章算法策略1优秀PPT.ppt

《第四章算法策略1优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第四章算法策略1优秀PPT.ppt（88页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第四章算法策略1第一页，本课件共有88页4.1 迭代算法迭代算法4.1.1 4.1.1 递推法递推法4.1.2 4.1.2 倒推法倒推法4.1.3 4.1.3 迭代法解方程迭代法解方程第二页，本课件共有88页411 递推递推法【例例1 1】兔子繁殖问题兔子繁殖问题兔子繁殖问题兔子繁殖问题问问题题描描述述：一一对对兔兔子子从从出出生生后后第第三三个个月月开开始始，每每月月生生一一对对小小兔兔子子。小小兔兔子子到到第第三三个个月月又又开开始始生生下下一一代代小小兔兔子子。假假若若兔兔子子只只生生不不死死，一一月月份份抱抱来来一一对对刚刚出出生生的小兔子，问一年中每个月各有多少只兔子。的小兔子，问一

2、年中每个月各有多少只兔子。问题分析：问题分析：问题分析：问题分析：因一对兔子从出生后第三个月开始每月生一对小兔子，因一对兔子从出生后第三个月开始每月生一对小兔子，因一对兔子从出生后第三个月开始每月生一对小兔子，因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数则每月新下小兔子的对儿数则每月新下小兔子的对儿数则每月新下小兔子的对儿数(用斜体数字表示用斜体数字表示用斜体数字表示用斜体数字表示)显然由前两个月的小显然由前两个月的小显然由前两个月的小显然由前两个月的小兔子的对儿数决定。则繁殖过程如下：兔子的对儿数决定。则繁殖过程如下：兔子的对儿数决定。则繁殖过程如下：兔子的对儿数

3、决定。则繁殖过程如下：一月一月一月一月 二月二月二月二月 三月三月三月三月 四月四月四月四月 五月五月五月五月 六月六月六月六月 1 1 1+1 1 1+1 1=2 2+=2 2+1 1=3 3+=3 3+2 2=5 5+=5 5+3 3=8 =8 第三页，本课件共有88页算法算法算法算法1 1 1 1：main()main()main()main()int i,a=1,b=1;int i,a=1,b=1;int i,a=1,b=1;int i,a=1,b=1;print(a,b);print(a,b);print(a,b);print(a,b);for(i=1;i for(i=1;i for

4、(i=1;i for(i=1;i=1010;i+);i+);i+);i+)c=a+b;c=a+b;print(c);print(c);a=b;a=b;b=c b=c 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，。第四页，本课件共有88页算法算法算法算法2 2 2 2：表表表表4-1 4-1 4-1 4-1 递推迭代表达式递推迭代表达式递推迭代表达式递推迭代表达式1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 91 2 3 4 5 6

5、 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 a 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;c=a+b;a=b+c;b=c+a;c=a+b;a=b+c;b=c+a;”做循环做循环做循环做循环“不变式不变式不变式不变式”。算

6、法算法算法算法2 2 2 2如下：如下：如下：如下：main()main()main()main()int i,a=1,b=1;int i,a=1,b=1;int i,a=1,b=1;int i,a=1,b=1;print(a,b);print(a,b);print(a,b);print(a,b);for(i=1;i for(i=1;i for(i=1;i for(i=1;i=;i+)=;i+)=;i+)=;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);c=a+b;a=b+c;b=c+a;print(a,b,c

7、);c=a+b;a=b+c;b=c+a;print(a,b,c);算法算法2 2，最后输出的，最后输出的并不是并不是1212项，而是项，而是2+3*42+3*4共共1414项。项。4 4第五页，本课件共有88页 表表表表4-2 4-2 4-2 4-2 递推迭代表达式递推迭代表达式递推迭代表达式递推迭代表达式1 21 21 21 2 3 4 5 6 7 8 93 4 5 6 7 8 93 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 b a=a+b b=a+b a=a+b b=a

8、+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;a=a+b;b=a+b;a=a+b;b=a+b;”做循环做循环做循环做循环“不变式不变式不变式不变式”，从而，从而，从而，从而得到以下算法得到以下算法得到以下算法得到以下算法3:3:3:3:main()main()main()main()int i,a=1,b=1;int i,a=1,b=1;int i,a=1,b=1;int i,a=1,b=1;print(a,b);print(a,b);print(a,b);prin

9、t(a,b);for(i=1;i for(i=1;i for(i=1;i for(i=1;i=;i+)=;i+)=;i+)=;i+)a=a+b;b=a+b;print(a,b);a=a+b;b=a+b;print(a,b);a=a+b;b=a+b;print(a,b);a=a+b;b=a+b;print(a,b);算法算法3 3：5 5第六页，本课件共有88页【例例例例2 2 2 2】求两个整数的最大公约数。求两个整数的最大公约数。求两个整数的最大公约数。求两个整数的最大公约数。数学建模：数学建模：数学建模：数学建模：辗转相除法是根据递推策略设计的。辗转相除法是根据递推策略设计的。辗转相除法是

10、根据递推策略设计的。辗转相除法是根据递推策略设计的。设两个整数设两个整数设两个整数设两个整数abababab且且且且a a a a除以除以除以除以b b b b商商商商x x x x余余余余c c c c；则；则；则；则a-bx=ca-bx=ca-bx=ca-bx=c：l la a a a、b b b b的最大公约数也是的最大公约数也是的最大公约数也是的最大公约数也是c c c c的约数的约数的约数的约数l la a a a、b b b b的最大公约数与的最大公约数与的最大公约数与的最大公约数与b b b b、c c c c的最大公约数相同的最大公约数相同的最大公约数相同的最大公约数相同l l

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

12、操操作作作作，就就就就实实实实现现现现了了了了第第第第二二二二次次次次还还还还是是是是求求求求“a a a a”“”“b b b b”相相相相除除除除的的的的余余余余数数数数，这这这这就就就就找找找找到到到到了循环不变式。循环在余数了循环不变式。循环在余数了循环不变式。循环在余数了循环不变式。循环在余数c c c c为为为为0 0 0 0时结束。时结束。时结束。时结束。第七页，本课件共有88页算法如下：算法如下：mainmain（）（）int a,b;int a,b;input(a,b);input(a,b);if(b=0)if(b=0)print(“data error”);return;e

13、lse 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);第八页，本课件共有88页4.1.2 4.1.2 倒推法倒推法 倒倒推推法法：是是对对某某些些特特殊殊问问题题所所采采用用的的违违反反通通常常习习惯惯的的从从后后向向前前推推解解问问题题的的方方法法。如如下下面面的的例例题题，因因不不同同方方面面的的需需求求而而采采用用了了倒倒推推策策略。略。第九页，本课件共有88页【例【例1 1】猴子吃桃问题】猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一

14、半多一个，一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第到第1010天时就只有一个桃子了，求原有多少个桃？天时就只有一个桃子了，求原有多少个桃？数学模型数学模型：每天的桃子数为：每天的桃子数为：a10=1,a9=(1+a10)*2,a8=(1+a9)*2,a10=1，递推公式为：递推公式为：ai=(1+ai+1)*2 I=9,8,7,61算法如下算法如下：main()int i,s;s=1;for(i=9;i=1;i=i-1)s=(s+1)*2 print(s)；第十页，本课件共有88页P177 T2第十一页，本课件共有88页【例例例例2 2 2 2】输出如图输出如图输出如图输出如图4

15、-14-14-14-1的杨辉三角形（限定用一的杨辉三角形（限定用一的杨辉三角形（限定用一的杨辉三角形（限定用一个一维数组完成）。个一维数组完成）。个一维数组完成）。个一维数组完成）。(2(2(2(2个数组？个数组？个数组？个数组？)数学模型：数学模型：数学模型：数学模型：上下层规律较明显，中间的数等上下层规律较明显，中间的数等上下层规律较明显，中间的数等上下层规律较明显，中间的数等于上行左上、右上两数之和。于上行左上、右上两数之和。于上行左上、右上两数之和。于上行左上、右上两数之和。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

16、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 6 4 14 6 4 1图图4-2杨辉三角形存储格式杨辉三角形存储格式算法设计：算法设计：因为输出第因为输出第i行时，用一个一维行时，用一个一维数组存储，数组存储，每求出一个数将覆盖第每求出一个数将覆盖第i-1行对应列存储的值，这将导致下一个数行对应列存储的值，这将导致下一个数无法计算。无法计算。所以考虑每行元素从第所以考

17、虑每行元素从第i个元素倒着向前计算输出则可解个元素倒着向前计算输出则可解决这个问题决这个问题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行行问题分析：问题分析：问题分析：问题分析：题目中要求用一个一维数组即完成。其实杨辉题目中要求用一个一维数组即完成。其实杨辉题目中要求用一个一维数组即完成。其实杨辉题目中要求用一个一维数组即完成。其实杨辉三角形是按下图三角形是按下图三角形是按下图三角形是按下图4-24-2形式存储的。若求形式存储的。若求形式存储的。若求形式存储的。若求n n层，则

18、数组最多存储层，则数组最多存储层，则数组最多存储层，则数组最多存储n n个个个个数据。数据。数据。数据。用一个一维数组存储第用一个一维数组存储第i行数据，有：行数据，有：A1=Ai=1Aj=Aj+Aj-1 （j=2i-1）？第十二页，本课件共有88页算法如下：算法如下：算法如下：算法如下：main()main()int n,i,j,a100;int n,i,j,a100;input(n);input(n);print(print(“1 1”);print();print(“换行符换行符换行符换行符”););a1=a2=1;a1=a2=1;print(a1,a2);print(print(a1,

19、a2);print(“换行符换行符换行符换行符”););for(i=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=1e-4fabs(x1-x0)=1e-4););return(x1);return(x1);第十七页，本课件共有88页l l 令令aa0,b,b0=a,b=a,b，c c0=(a=(a0+b+b0)/2)/21.1.1.1.若若f(cf(c0)=0)=0，则则c c0为为方程方程f(x)=0f(x)=0的根；的根；2.2.2.2.若若f

20、(af(a0)*f(c)*f(c0)0)0，则则令令aa1,b,b1=a=a0,c,c0；3.3.3.3.若若f(bf(b0)*f(c)*f(c0)0)0，则则令令aa1,b,b1=c=c0,b,b0。l l当发现当发现当发现当发现f(cf(cn n)=0)=0时，或区间时，或区间时，或区间时，或区间aan n,b,bn n 足够小，比如足够小，比如足够小，比如足够小，比如|a|an n-b-bn n|0.0001|0.0001时，就认为时，就认为时，就认为时，就认为找到了方程的根。找到了方程的根。找到了方程的根。找到了方程的根。图图4-6 4-6 二分法二分法求求解解方程方程示意示意【例【例

21、【例【例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)异号，即异号，即异号，即异号，即

22、 f(a)*f(b)0 f(a)*f(b)0 f(a)*f(b)0 f(a)*f(b)0。第十八页，本课件共有88页l用二分法求一元非线性方程用二分法求一元非线性方程f(x)=x3/2+2x2-8=0（其中（其中表示幂表示幂运算）在区间运算）在区间0，2上的近似实根上的近似实根r，精确，精确到到0.0001.算法如下：算法如下：第十九页，本课件共有88页main()main()main()main()float x,x1=0,x2=2,f1,f2,f;float x,x1=0,x2=2,f1,f2,f;/x=(x1+x2)/2;f1=f(x1);f2=f(x2);f=f(x)=f(x1+x2)

23、/2)/x=(x1+x2)/2;f1=f(x1);f2=f(x2);f=f(x)=f(x1+x2)/2)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 do do x=(x1+x2)/2;x=(x1+x2)/2;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;f=x*x*x/2+2*x*x-8;f=x*x*x/2+2*x*x-8;if(f=

24、0)break;if(f=0)break;if(f=0)break;if(f=0)break;if(f1*f0.0)x1=x;f1=f;if(f1*f0.0)x1=x;f1=f;else x2=x;else x2=x;else x2=x;else x2=x;/需要需要需要需要 f2=f f2=f f2=f f2=f 吗？吗？吗？吗？while(fabs(f)=1e-4);while(fabs(f)=1e-4);print(root=,x);print(root=,x);第二十页，本课件共有88页4.2 蛮力法蛮力法4.2.1 4.2.1 枚举法枚举法4.2.2 4.2.2 其它范例其它范例蛮力

25、法是基于计算机运算速度快这一特性蛮力法是基于计算机运算速度快这一特性这种策略这种策略不经过（或者说是经过很少的）思考，把问题的所有情况或不经过（或者说是经过很少的）思考，把问题的所有情况或所有过程交给计算机去一一尝试所有过程交给计算机去一一尝试，从中找出问题的解。，从中找出问题的解。蛮力策略的应用很广，数据结构课程中学习的：选择排序、冒蛮力策略的应用很广，数据结构课程中学习的：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等，都是蛮力泡排序、插入排序、顺序查找、朴素的字符串匹配等，都是蛮力策略具体应用。策略具体应用。比较常用还有比较常用还有枚枚举举法法、盲目搜索、盲目搜索算法等算法等

26、第二十一页，本课件共有88页4 42 21 1 枚举法枚举法 枚枚举举（enumerate）法法（穷穷举举法法）是是蛮蛮力力策策略略的的一一种种表表现现形形式式，它它是是根根据据问问题题中中的的条条件件将将可可能能的的情情况况一一一一列列举举出出来来，逐逐一一尝尝试试从从中中找找出出满满足问题条件的解。足问题条件的解。但但有有时时一一一一列列举举出出的的情情况况数数目目很很大大，如如果果超超过过了了我我们们所所能能忍忍受受的的范范围围，则则需需要要进进一一步步考考虑虑，排排除除一一些些明明显显不不合合理理的的情情况况，尽尽可可能能减减少少问问题题可可能能解解的列举数目。的列举数目。用枚举法解决

27、问题，通常可以从用枚举法解决问题，通常可以从两个方面两个方面进行算法设计：进行算法设计：1）找出枚举范围：分析问题所涉及的各种情况。找出枚举范围：分析问题所涉及的各种情况。2 2）找找出出约约束束条条件件：分分析析问问题题的的解解需需要要满满足足的的条条件件，并并用用逻逻辑辑表达式表示。表达式表示。第二十二页，本课件共有88页【例【例1 1】百百钱钱百百鸡问题鸡问题。中国古代数学家。中国古代数学家张张丘建在他的算丘建在他的算经经中提出了著名的中提出了著名的“百百钱钱百百鸡问题鸡问题”：鸡鸡翁一，翁一，值钱值钱五；五；鸡鸡母一，母一，值钱值钱三；三；鸡雏鸡雏三，三，值钱值钱一；百一；百钱买钱买百

28、百鸡鸡，翁、母、，翁、母、雏雏各几何各几何?算法设计算法设计1：用用“懒惰懒惰”的的枚举枚举策略进行算法设计：策略进行算法设计：设设x，y，z分别为公鸡、母鸡、小鸡的数量。分别为公鸡、母鸡、小鸡的数量。尝试范围尝试范围：两个三元方程公鸡最多买公鸡最多买100/5=20只，显然只，显然x的取值范围的取值范围120之间；之间；y的取值范围在的取值范围在133之间，之间，z的取值范围在的取值范围在1100之间。之间。约束条件约束条件：x+y+z=100 且且 5*x+3*y+z/3=100第二十三页，本课件共有88页算法算法1如下：如下：main()main()int x,y,z;int x,y,z

29、;for(x=1;x=20;x=x+1)for(x=1;x=20;x=x+1)for(y=1;y=34;y=y+1)for(y=1;y=34;y=y+1)for(z=1;z=100;z=z+1)for(z=1;z=100;z=z+1)if(if(100=x+y+z and 100=5*x+3*y+z/3100=x+y+z and 100=5*x+3*y+z/3)print(the cock number is,x)print(the cock number is,x)；print(the hen number is,y)print(the hen number is,y)；print(the

30、chick number is z);print(the chick number is z);第二十四页，本课件共有88页算算法法分分析析：以以上上算算法法需需要要枚枚举举尝尝试试20*34*100=68000次次。算算法法的的效率显然太低效率显然太低算法设计算法设计2：在在公公鸡鸡（x x）、母母鸡鸡（y y）的的数数量量确确定定后后，小小鸡鸡的的数数量量z就就固固定定为为:100-x-y此时此时约约束条件只有一个：束条件只有一个：5*x+3*y+z/3=100算法算法2如下：如下：第二十五页，本课件共有88页main()main()main()main()int x,y,z;int x,

31、y,z;int x,y,z;int x,y,z;for(x=1;x=20;x=x+1)for(x=1;x=20;x=x+1)for(x=1;x=20;x=x+1)for(x=1;x=20;x=x+1)for(y=1;y=33;y=y+1)for(y=1;y=33;y=y+1)for(y=1;y=33;y=y+1)for(y=1;y=33;y=y+1)z=100-x-y;z=100-x-y;z=100-x-y;z=100-x-y;if(if(if(if(z mod 3=0z mod 3=0z mod 3=0z mod 3=0 and and and and 5*x+3*y+z/3=1005*x+

32、3*y+z/3=1005*x+3*y+z/3=1005*x+3*y+z/3=100)print(the cock number is,x)print(the cock number is,x)print(the cock number is,x)print(the cock number is,x)；print(the hen number is,y)print(the hen number is,y)print(the hen number is,y)print(the hen number is,y)；print(the chick number is z);print(the chick

33、 number is z);print(the chick number is z);print(the chick number is z);算法分析：算法分析：算法分析：算法分析：以上算法只需要枚举尝试以上算法只需要枚举尝试以上算法只需要枚举尝试以上算法只需要枚举尝试20*33=66020*33=660次。实现时约束条件又限定次。实现时约束条件又限定次。实现时约束条件又限定次。实现时约束条件又限定Z Z能被能被能被能被3 3整整整整除时，才会判断除时，才会判断除时，才会判断除时，才会判断“5*x+3*y+z/3=1005*x+3*y+z/3=1005*x+3*y+z/3=1005*x+3*

34、y+z/3=100”。这样这样这样这样省去了省去了省去了省去了z z z z不整除不整除不整除不整除3 3 3 3时时时时的算的算的算的算术计术计术计术计算和条件算和条件算和条件算和条件判断，判断，判断，判断，进进进进一步提高了算法的效率。一步提高了算法的效率。一步提高了算法的效率。一步提高了算法的效率。第二十六页，本课件共有88页【例例例例2 2 2 2】解数字迷：解数字迷：解数字迷：解数字迷：A B C A BA B C A BA B C A BA B C A B A A A A D D D D D D D D D D D D D D D D D D D D D D D D算法设计算法设计

35、算法设计算法设计1 1 1 1：按乘法枚举按乘法枚举按乘法枚举按乘法枚举1)1)1)1)枚举范围为：枚举范围为：枚举范围为：枚举范围为：A A A A：3 3 3 39 9 9 9（A=1A=1A=1A=1，2 2 2 2时积不会得到六位数）时积不会得到六位数）时积不会得到六位数）时积不会得到六位数）,B B B B：0 0 0 09,9,9,9,C C C C：0 0 0 09 9 9 9 六位数表示为六位数表示为六位数表示为六位数表示为A*10000+B*1000+C*100+A*10+BA*10000+B*1000+C*100+A*10+BA*10000+B*1000+C*100+A*1

36、0+BA*10000+B*1000+C*100+A*10+B，l l 共尝试共尝试共尝试共尝试700700700700次。次。次。次。2)2)2)2)约束条件为：约束条件为：约束条件为：约束条件为：每次尝试，先求六位数与每次尝试，先求六位数与每次尝试，先求六位数与每次尝试，先求六位数与A A A A的积，测试的积，测试的积，测试的积，测试积的各位是否相同积的各位是否相同积的各位是否相同积的各位是否相同 l l从低位开始，每次都取数据的个位，然后整除从低位开始，每次都取数据的个位，然后整除从低位开始，每次都取数据的个位，然后整除从低位开始，每次都取数据的个位，然后整除10101010，使高位的数

37、字，使高位的数字，使高位的数字，使高位的数字不断变成个位，并逐一比较。不断变成个位，并逐一比较。不断变成个位，并逐一比较。不断变成个位，并逐一比较。第二十七页，本课件共有88页算法算法算法算法1 1 1 1如下：如下：如下：如下：mainmain（）int A,B,C,D,E,E1,F,G1,G2,i;int A,B,C,D,E,E1,F,G1,G2,i;for(A=3;A=9;A+)for(A=3;A=9;A+)for(B=0;B=9;B+)for(B=0;B=9;B+)for(C=0;C=9;C+)for(C=0;C=9;C+)F=A*10000+B*1000+C*100+A*10+B;F

38、=A*10000+B*1000+C*100+A*10+B;E=F*A E=F*A；E1=E;E1=E;G1=E1 mod 10;G1=E1 mod 10;for(i=1;i=5;i+)for(i=1;i=5;i+)/G1:/G1:当前个位上的数字当前个位上的数字当前个位上的数字当前个位上的数字,G2:,G2:上一个位上的数字上一个位上的数字上一个位上的数字上一个位上的数字 G2=G1;E1=E1/10;G1=E1 mod 10;G2=G1;E1=E1/10;G1=E1 mod 10;if(G1G2)break;if(G1G2)break;if(i=6)print(F if(i=6)print(

39、F，”*”，A A，”=”，E);E);第二十八页，本课件共有88页算法分析算法分析算法分析算法分析1 1 1 1：以上算法的尝试范围是：以上算法的尝试范围是：以上算法的尝试范围是：以上算法的尝试范围是A A A A：3 3 3 39 9 9 9，B B B B：0 0 0 09 9 9 9，C C C C：0 0 0 09 9 9 9。共尝试。共尝试。共尝试。共尝试700700700700次，每次，不是一个好的算法。次，每次，不是一个好的算法。次，每次，不是一个好的算法。次，每次，不是一个好的算法。算法设计算法设计算法设计算法设计2 2 2 2：将算式变形为除法：将算式变形为除法：将算式变形

40、为除法：将算式变形为除法：DDDDDD/A=ABCABDDDDDD/A=ABCABDDDDDD/A=ABCABDDDDDD/A=ABCAB。此时此时此时此时枚举范围枚举范围枚举范围枚举范围:A A A A：3 3 3 39 D9 D9 D9 D：1 1 1 19 9 9 9，共尝试，共尝试，共尝试，共尝试7*9=637*9=637*9=637*9=63次。次。次。次。约束条件约束条件约束条件约束条件:测试商的测试商的测试商的测试商的万位、十位万位、十位万位、十位万位、十位与与与与除数除数除数除数是否相同，是否相同，是否相同，是否相同，千位与个位千位与个位千位与个位千位与个位是否相同，都相同时为

41、解。是否相同，都相同时为解。是否相同，都相同时为解。是否相同，都相同时为解。第二十九页，本课件共有88页mainmain（）（）int A,B,C,D,E,F;int A,B,C,D,E,F;for(A=3;A=9;A+)for(A=3;A=9;A+)for(D=1;D=9;D+)for(D=1;D=9;D+)E=D*100000+D*10000+D*1000+D*100+D*10+D;E=D*100000+D*10000+D*1000+D*100+D*10+D;if(E mod A=0)if(E mod A=0)/整除是条件整除是条件 F=EA;F=EA;if(F10000=A and(F

42、mod 100)10=A)if(F10000=A and(F mod 100)10=A)/万位与十位是否等于万位与十位是否等于A A if(F1000=F mod 10)if(F1000=F mod 10)/千位与个位数字是否相等千位与个位数字是否相等 print(F print(F，”*”，A A，”=”，E);E);第三十页，本课件共有88页 蛮力法的表现形式非常多，如第三章蛮力法的表现形式非常多，如第三章3.2.4例题、例题、3.2.5例例1及本及本章下一节章下一节4.3.3例例4的算法的算法1等。本节将通过蛮力策略，用算法模拟等。本节将通过蛮力策略，用算法模拟问题中所描述的全部过程和全

43、部状态，来找出问题的解，并与经问题中所描述的全部过程和全部状态，来找出问题的解，并与经过数学建模后的算法进行效率上的比较。过数学建模后的算法进行效率上的比较。4 42 22 2 其它范例其它范例第三十一页，本课件共有88页【例例例例3 3 3 3】狱吏问题狱吏问题狱吏问题狱吏问题 某国王对囚犯进行大赦，让一狱吏某国王对囚犯进行大赦，让一狱吏某国王对囚犯进行大赦，让一狱吏某国王对囚犯进行大赦，让一狱吏n n n n次通过一排锁着的次通过一排锁着的次通过一排锁着的次通过一排锁着的n n n n间牢房，间牢房，间牢房，间牢房，每通过一次，按所定规则转动每通过一次，按所定规则转动每通过一次，按所定规则

44、转动每通过一次，按所定规则转动n n n n间牢房中的某些门锁间牢房中的某些门锁间牢房中的某些门锁间牢房中的某些门锁,每转动一每转动一每转动一每转动一次次次次,原来锁着的被打开原来锁着的被打开原来锁着的被打开原来锁着的被打开,原来打开的被锁上；通过原来打开的被锁上；通过原来打开的被锁上；通过原来打开的被锁上；通过n n n n次后，门次后，门次后，门次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。锁开着的，牢房中的犯人放出，否则犯人不得获释。锁开着的，牢房中的犯人放出，否则犯人不得获释。锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把转动

45、门锁的规则是这样的，第一次通过牢房，要转动每一把转动门锁的规则是这样的，第一次通过牢房，要转动每一把转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第每隔一间转动一次；第每隔一间转动一次；第每隔一间转动一次；第k k k k次通过牢房，从第次通过牢房，从第次通过牢房，从第次通过牢房，从第k k k k间开始转动，每隔间开始转动，每隔间开始转动，

46、每隔间开始转动，每隔k-1 k-1 k-1 k-1 间转动一次；问通过间转动一次；问通过间转动一次；问通过间转动一次；问通过n n n n次后，哪些牢房的锁仍然是打开的？次后，哪些牢房的锁仍然是打开的？次后，哪些牢房的锁仍然是打开的？次后，哪些牢房的锁仍然是打开的？第三十二页，本课件共有88页算法设计算法设计算法设计算法设计1 1 1 1：1 1 1 1）用用用用n n n n个空间的一维数组个空间的一维数组个空间的一维数组个空间的一维数组an,an,an,an,每个元素每个元素每个元素每个元素记录一个锁的状记录一个锁的状记录一个锁的状记录一个锁的状 态，态，态，态，1 1 1 1为为为为被锁

47、上被锁上被锁上被锁上，0 0 0 0为被打开为被打开为被打开为被打开。2 2 2 2）用数学运算方便模拟开关锁的技巧，对）用数学运算方便模拟开关锁的技巧，对）用数学运算方便模拟开关锁的技巧，对）用数学运算方便模拟开关锁的技巧，对i i i i号锁的一次开号锁的一次开号锁的一次开号锁的一次开 关锁可以转化为算术运算：关锁可以转化为算术运算：关锁可以转化为算术运算：关锁可以转化为算术运算：ai=1-aiai=1-aiai=1-aiai=1-ai。3 3 3 3）第一次转动的是）第一次转动的是）第一次转动的是）第一次转动的是1 1 1 1，2 2 2 2，3 3 3 3，n n n n号牢房；号牢房

48、；号牢房；号牢房；第二次转动的是第二次转动的是第二次转动的是第二次转动的是2 2 2 2，4 4 4 4，6 6 6 6，号牢房；号牢房；号牢房；号牢房；第三次转动的是第三次转动的是第三次转动的是第三次转动的是3 3 3 3，6 6 6 6，9 9 9 9，号牢房；号牢房；号牢房；号牢房；第第第第i i i i次次次次转转转转动动动动的的的的是是是是i i i i，2i2i2i2i，3i3i3i3i，4i4i4i4i，号号号号牢牢牢牢房房房房，是是是是起起起起点点点点为为为为i i i i，公差为公差为公差为公差为i i i i的等差数列。的等差数列。的等差数列。的等差数列。4 4 4 4）用

49、蛮力法通过循环模拟狱吏的开关过程，最后当第）用蛮力法通过循环模拟狱吏的开关过程，最后当第）用蛮力法通过循环模拟狱吏的开关过程，最后当第）用蛮力法通过循环模拟狱吏的开关过程，最后当第i i号号号号牢房对应的数组元素牢房对应的数组元素牢房对应的数组元素牢房对应的数组元素aiaiaiai为为为为0 0 0 0时，该牢房的囚犯得到大赦。时，该牢房的囚犯得到大赦。时，该牢房的囚犯得到大赦。时，该牢房的囚犯得到大赦。第三十三页，本课件共有88页main1()main1()main1()main1()int*a,i,j,n;int*a,i,j,n;int*a,i,j,n;int*a,i,j,n;input(

50、n);input(n);input(n);input(n);a=calloc(n+1,sizeof(int);a=calloc(n+1,sizeof(int);a=calloc(n+1,sizeof(int);a=calloc(n+1,sizeof(int);for(i=1;i=n;i+)for(i=1;i=n;i+)for(i=1;i=n;i+)for(i=1;i=n;i+)ai=1;ai=1;ai=1;ai=1;for(i=1;i=n;i+)for(i=1;i=n;i+)for(i=1;i=n;i+)for(i=1;i=n;i+)for(for(for(for(j=i;j=n;j=j+ij