用穷举法设计算法

《用穷举法设计算法》由会员分享，可在线阅读，更多相关《用穷举法设计算法（43页珍藏版）》请在装配图网上搜索。

1、n问题问题1： 有一把锁和一串钥匙（共有有一把锁和一串钥匙（共有10把钥匙），把钥匙），怎样找出所有开这把锁的钥匙？怎样找出所有开这把锁的钥匙？n穷举算法的概念：穷举算法的概念： 穷举算法穷举算法就是按问题本身的性质，通过就是按问题本身的性质，通过多多重循环重循环一一列举出该问题所有可能的解（一一列举出该问题所有可能的解（不能不能遗漏，也不能重复遗漏，也不能重复），并在逐一列举的过程中，），并在逐一列举的过程中，检验每个可能的解是否是问题的真正解检验每个可能的解是否是问题的真正解，若是，若是，我们采用这个解，否则抛弃它。我们采用这个解，否则抛弃它。n 穷举算法的要点：穷举算法的要点： 列举所有

2、可能的解（不能遗漏，也不能重列举所有可能的解（不能遗漏，也不能重 复），检验每个可能的解。复），检验每个可能的解。 问题问题2：从：从110中找出所有中找出所有是是3倍数倍数的数。的数。用用流程图描述流程图描述解决此数学问题的算法。解决此数学问题的算法。输出输出i i开始开始i1i1i10i10i i +1i i +1结束结束NYi i是是3 3的倍数的倍数YN#includeusing namespace std;int main()int i=1; while(i=10) if (i%3=0) printf(“%dn”,i); i=i+1; 问题问题3：从：从1100中找出所有中找出所有能

3、被能被7或或9整除整除的数。用的数。用流程图描述流程图描述解决此数学问题的算法。解决此数学问题的算法。输出输出i i开始开始i1i1i100i100i i +1i i +1结束结束NYi i能被能被7 7或或9 9整除整除YN#includeusing namespace std;int main()int i; for(i=1;i=100;i=i+1) if (i%7=0|i%9=0) printf(“%dn”,i); 问题问题4：打印输出由：打印输出由1、28、9这九个数字组成的所有可能的二位这九个数字组成的所有可能的二位数数n。用流程图描述。用流程图描述。分析：分析：个位数个位数上的数字

4、可以是那几种上的数字可以是那几种数字？用数字？用变量变量i来表示。来表示。十位数十位数上的数字可以是那几种上的数字可以是那几种数字？数字？用变量用变量j来表示。来表示。找出二位数找出二位数n与与i、j之间的关之间的关系。提示：系。提示：548=5100+410+8输出输出n n开始开始j j11j j99i i i i +1 +1结束结束NNi i11Yi i99nj j* *10+10+i iYj j j j +1 +1执行过程：执行过程：j=1in3456789 102111 12 13 14 1516 17 18 19j=2#includeusing namespace std;int

5、main() int j,i,n; j=1; While(j=9) i=1; While(i=9) n=j*10+i; printf(“%d”,n); i=i+1; j=j+1; 问题问题4：打印输出由：打印输出由1、28、9这九个数这九个数字组成的所有可能的二位数字组成的所有可能的二位数n。#includeusing namespace std;int main() int i,j; for (i=1;i=9;i+) for (j=1;j=9;j+) printf(%dn,i*10+j); return 0; 标准输入输出速度比较快。标准输入输出速度比较快。流输入输出在数据比较多，比流输入输

6、出在数据比较多，比如如1000000个数据的时候会很个数据的时候会很慢。慢。ios:sync_with_stdio(false) 采用穷举算法解题的基本思想：采用穷举算法解题的基本思想：（1） 明确问题要求，确定枚举对象，用合适类型明确问题要求，确定枚举对象，用合适类型的变量表示枚举对象。的变量表示枚举对象。（2） 明确枚举对象的取值范围。明确枚举对象的取值范围。（3） 根据题目要求，写出有关的条件表达式。这根据题目要求，写出有关的条件表达式。这里条件表达式可以是数学表达式、关系表达式或里条件表达式可以是数学表达式、关系表达式或逻辑表达式；逻辑表达式；（4） 使用循环语句枚举出可能的解，在循环

7、体内使用循环语句枚举出可能的解，在循环体内验证各种条表达式是否满足；验证各种条表达式是否满足；（5） 根据问题背景，优化程序，以便缩小搜索范根据问题背景，优化程序，以便缩小搜索范围，减少程序运行时间。围，减少程序运行时间。【例5】：（百钱买百鸡问题）大约在公元5世纪，数学家张邱建在他的算经中提出了一个闻名于后世的百钱百鸡问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，翁、母、雏各几何？1.算法分析与设计(1) 以三种鸡的个数为枚举对象，分别设为x,y,z。根据题意，可以列出下面的不定方程(2)确定枚举变量的取值范围。显然，x，y，z的取值范围为 0 x,y,z100;#inc

8、ludeusing namespace std;int main() int x,y,z; for(x=0;x=100;x+) for(y=0;y=100;y+) for(z=0;z=100;z+) if(x+y+z=100 & 5*x+3*y+z/3=100) printf(x=%d,y=%d,z=%dn,x,y,z);x=0,y=25,z=75x=3,y=20,z=77x=4,y=18,z=78x=7,y=13,z=80 x=8,y=11,z=81x=11,y=6,z=83x=12,y=4,z=84有错误#includeusing namespace std;int main() int

9、x,y,z; for(x=0;x=100;x+) for(y=0;y=100;y+) for(z=0;z=100;z+) if(x+y+z=100 & 15*x+9*y+z=300) printf(x=%d,y=%d,z=%dn,x,y,z);修改错误x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84#includeint main() int x,y,z; for(x=0;x=20;x+) for(y=0;y=33;y+) for(z=0;z=100;z+) if(x+y+z=100 & 15*x+9*y+z=300) printf(x=

10、%d,y=%d,z=%dn,x,y,z);第1次优化x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84Press any key to continue只要求出x，y后，z可以由方程(4)直接计算出来。在方程（3）中，假设y=0,则x=14,假设x=0,则y=25。即x,y的枚举范围是 0 x14,0y25.for(x=0;x=14;x+) for(y=0;y=25;y+) if(7*x+4*y=100) z=100-x-y; output(x,y,z); 第2次优化#includeusing namespace std;int main(

11、) int x,y,z; for(x=0;x=14;x+) for(y=0;y=25;y+) if(7*x+4*y=100) z=100-x-y; printf(x=%d,y=%d,z=%dn,x,y,z); x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84Press any key to continue逻辑推理问题n逻辑推理问题【例6】：（谁做的好事）已知有有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。A说：不是我。B说：是C。C说：是D。D说：他胡说。已知三个人说的是真话，一个人说的是假话。现在要根据

12、这些信息，找出做了好事的人。1.算法分析将相关的陈述写成关系表达式和逻辑表达式我们把四个人说的四句话写成关系表达式。定义变量thisman表示做好事的人（将其定义为字符型）。四个人说的话关系表达式A说：不是我。thisman!=AB说：是C。thisman=CC说：是D。thisman=DD说：他胡说。thisman!=D关系表达式的计算结果只有0（假）和1（真）两种结果。现在“已知三个人说的是真话，一个人说假话”，也就是表中的4个关系表达式中有3个是真的，1个是假的。 因此4个关系表达式的值的和应该等于3。定义变量cond表示四个关系表达式的和 cond= thisman!=A+ thism

13、an=C+ thisman=D+ thisman!=D 那么，cond=3穷举试探。我们现在并不知道是谁做得好事，但我们知道做好事的人是A,B,C,D四个人中的某一个。因此，我们可以一个一个地试探。先假设是A做的好事，即thisman=A，然后看cond=3条件是否成立，然后再假设是B做的好事，即thisman=B,再测试条件cond=3 是否成立，如此继续下去，将所有可能的情况（本例自有4种情况）都测试一遍，在实际编程过程中，都是使用循环来一个一个的测试 for(thisman=A;thisman=D;thisman+) cond=(thisman!=A)+(thisman=C) +(thi

14、sman=D)+(thisman!=D); if(cond=3)printf(做好事的人是：%Cn,thisman); 2. 核心代码#includeusing namespace std;int main() char thisman;int cond;for(thisman=A; thisman=D;thisman+) cond=(thisman!=A)+(thisman=C) +(thisman=D)+(thisman!=D);if(cond=3)printf(做好事的人是：%Cn,thisman); 【例7】: (四大湖问题)上地理课时，四个学生回答我国四个淡水湖大小时说： A学生：洞

15、庭湖最大，洪泽湖最小，鄱阳湖第3 B学生：洪泽湖最大，洞庭湖最小，鄱阳湖第2，太湖第3 C学生：洪泽湖最小，洞庭湖第3 D学生：鄱阳湖最大，太湖最小，洪泽湖第2，洞庭第3 对于湖的大小，每个学生仅答对一个，请编程判断四个湖的大小1.分析与算法设计 (1)定义变量： a洞庭湖，a可能的取值1,2,3,4 b洪泽湖，b可能的取值1,2,3,4 c鄱阳湖，c可能的取值1,2,3,4 d太湖，d可能的取值1,2,3,4a,b,c,d四个变量的取值互不相同，1表示最大，四表最小(2) 用变量表示条件 A学生的叙述可表示为：a=1, b=4,c=3 这是三个关系表达式，由于每个学生的叙述只有一个正确，所以

16、这三个关系表达式的值的和应等于1。 A学生的叙述可表示成： ( (a=1)+(b=4)+(c=3）)=1 同理，B学生的叙述表示成： (b=1)+(a=4)+(c=2)+(d=3)=1 C学生的叙述可表示成： (b=4)+(a=3) =1 D学生的叙述可表示成： (c=1)+(d=4)+(b=2)+(a=3)=1for(a=1;a=4;a+) for(b=1;b=4;b+) for(c=1;c=4;c+) for(d=1;d=4;d+) ca=(a=1）+（b=4）+(c=3）)=1; cb=(b=1)+(a=4)+(c=2)+(d=3)=1; cc=(b=4)+(a=3) )=1; cd=(

17、c=1)+(d=4)+(b=2)+(a=3)=1; if(ca & cb & cc & cd) printf(TongTing=%dn,a); printf(Hongzhe=%dn,b);printf(Poyang=%dn,c); printf(Taihu=%dn,d); /end for(3) 穷举: 穷举a,b,c,d四个变量的所有可能取值,进行测试，满足前述四个条件的取值就是我们所要的结果【例8】（白帽子和红帽子问题）厅内有5个人，他们均戴着帽子白帽子和红帽子。已知戴白帽子的说真话，戴红帽子的说假话，请从他们各自提供的线索辨别谁戴白帽子，谁戴红帽子。甲：我看见一个戴白帽子的乙：我没有看见

18、戴红帽子的丙：我看见一个戴白帽子的，但不是甲丁：我没有看见戴白帽子的戊：我的帽子和丙一样 定义变量 用5个整型变量a,b,c,d,e分别表示甲、乙、丙、丁、戊，1表示戴白帽子，0表示戴红帽子。 写出五个人所说的每句话的逻辑表达式甲：(b+c+d+e=1)乙：(a+c+d+e=4)丙：(b+d+e=1)丁：(a+b+c+e=0)戊：(e=c)这里只是简单地将五个人说的话写成了表达式，但这还不够，由于这五个人本身有些说真话，有些说假话，因此如何判断上述五个表达式的真假呢？ 思考：每个人说话的真假与他所戴的帽子有关，如果他戴的是白帽子，则他说真话；如果他戴的是红帽子，则他所说的是假话，这样将每个人帽

19、子颜色与他说的话直接联系起来，因此上述条件可表示成： 甲：(b+c+d+e=1)=a乙：(a+c+d+e=4)=b丙：(b+d+e=1)=c丁：(a+b+c+e=0)=d戊：(e=c)=evoid main()int a,b,c,d,e,c1,c2,c3,c4,c5;for(a=0;a=1;a+) for(b=0;b=1;b+)for(c=0;c=1;c+) for(d=0;d=1;d+) for(e=0;e=1;e+)c1=(b+c+d+e=1)=a;c2=(a+c+d+e=4)=b;c3=(b+d+e=1)=c;c4=(a+b+c+e=0)=d;c5=(e=c)=e;if(c1 & c2

20、& c3 & c4 & c5) printf(a=%d,b=%d,c=%d,d=%d,e=%dn, a,b,c,d,e) ; 穷举：对变量a,b,c,d,e的所有可能取值情况进行枚举，这要用一个5重循环实现。例例9 9：输入绳子的长度：输入绳子的长度n n，将该绳子分成三段，每段，将该绳子分成三段，每段的长度为正整数，输出由该三段绳子组成的三角的长度为正整数，输出由该三段绳子组成的三角形个数。形个数。 s=0;s=0;for for （a=1;a=n-2;a+a=1;a=n-2;a+） for for （b=a;b=n-2;b+b=a;b=n-2;b+） for for （c=b;c=n-2;

21、c+c=b;cc) & (b+ca) & (c+ab) & if (a+bc) & (b+ca) & (c+ab) & (a+b+c=n) )(a+b+c=n) ) s+; s+;穷举法的基本概念 穷举算法模式 1、问题解的可能搜索的范围：问题解的可能搜索的范围： 用循环或循环嵌套结构实现用循环或循环嵌套结构实现 2、写出符合问题解的条件。写出符合问题解的条件。 3、能使程序优化的语句，以便缩小搜索范能使程序优化的语句，以便缩小搜索范 围，减少程序运行时间。围，减少程序运行时间。 穷举法应用 穷举法应用很多，比如一些密码破译软件通穷举法应用很多，比如一些密码破译软件通常就是用的穷举算法。如在常

22、就是用的穷举算法。如在QQQQ上，上，OicqPassOverOicqPassOver这个工具穷举你的口令，它根这个工具穷举你的口令，它根据机器性能最高可以每秒测试据机器性能最高可以每秒测试2000020000个口令，个口令，如果口令简单，一分钟内，密码就会遭到破如果口令简单，一分钟内，密码就会遭到破译。下面我们来以译。下面我们来以sznoisznoi上的例子说明穷举上的例子说明穷举法的基本应用。法的基本应用。 d052: 小球颜色方案内容：内容：一个看不见的袋子中装有红、橙、黄、绿、蓝五种颜色的小球若干，每次随意摸出三个小球，输出三个小球颜色都不一样的所有可能的方案总数。（我承认害了不少人，

23、大家认为：红、橙、黄 和 橙、红、黄不一样吧，这样就是XX种，谢谢）d052: 小球颜色方案#includeusing namespace std;int main() int a,b,c,n=0; for (a=1;a=5;a+) for (b=1;b=5;b+) for (c=1;c=5;c+) if (a!=b&b!=c&a!=c) n+; coutnendl; return 0; d058: 勾股数 内容：内容：20以内勾股数（假设a=b=c)a2+b2=c2 若有多组，按a从小到大顺序输出 .输入说明：输入说明：无输出说明：输出说明：一行一组三个数，用空格隔开d058: 勾股数 #i

24、nclude using namespace std; int main() int a,b,c; for (a=1;a=20;a+) for (b=a;b=20;b+) for (c=b;c=20;c+) if (a*a+b*b=c*c) couta b cendl; return 0; d071: 倒立勾股数 关键字： 内容：内容：1/x2+1/y2=1/z2 其中正整数xyz成为一组倒立的勾股数！注意，是正整数哦！你的任务是输出60以内的倒立勾股数，按x的的增序输出（每行一个）。 d071: 倒立勾股数 #includeusing namespace std;int main()int

25、x,y,z;for(x=1;x=60;x+) for(y=1;y=60;y+) for(z=1;z=60;z+)if(x*x*y*y=z*z*(x*x+y*y)&x=y)printf(%d %d %dn,x,y,z);return 0;f003: AB类数 (NOIP1995)内容：内容：若将一个正整数化为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为A类数，否则就称其为B类数。例如：（13）10=（1101）2其中1的个数为3，0的个数为1，则称此数为A类数；（10）10=（1010）2其中1的个数为2，0的个数也为2，称此数为B类数；（24）10=（1100

26、0）2其中1的个数为2，0的个数为3，则称此数为B类数；程序要求：求出11000000之中（包括1与1000），全部A、B两类数的个数。输入一个数，求出到这个数之间的AB类数输出一行输出两个数，空格隔开。f003: AB类数 #include using namespace std;int main() int one,zero; int N_one=0,N_zero=0,n,i,j,k,num; cinn; for (i=1;izero) N_one+; else N_zero+; coutN_one N_zeroendl; return 0; f010: 竞赛安排 NOIP 1996内容：

27、内容：设有有2 n（n=6）个球队进行单循环比赛，计划在2 n 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n 1天内每个队都与不同的对手比赛。例如n=2时的比赛安排：队 1 2 3 4比赛 1=2 3=4 一天1=3 2=4 二天1=4 2=3 三天输入样例：1输出样例输出样例 ： 1=2f010: 竞赛安排 int main() int n,day,cc,dui1,dui2; int a7; bool flag65,flag16565; cinn; a1=2;a2=4;a3=8;a4=16;a5=32;a6=64; memset(flag1,0,sizeof(flag1); for (day=1;day=an-1;day+) coutday ; memset(flag,0,sizeof(flag); for (cc=1;cc=an/2;cc+) for (dui1=1;dui1=an-1;dui1+) for (dui2=dui1+1;dui2=an;dui2+) if (flagdui1=0&flagdui2=0&flag1dui1dui2=0) coutdui1=dui2 ; flagdui1=1; flagdui2=1; flag1dui1dui2=1; coutendl; return 0;