《用穷举法设计算法》由会员分享，可在线阅读，更多相关《用穷举法设计算法（43页珍藏版）》请在金锄头文库上搜索。
1、用穷举法设计算法用穷举法设计算法n问题问题1： 有一把锁和一串钥匙（共有有一把锁和一串钥匙（共有10把钥匙），把钥匙），怎样找出所有开这把锁的钥匙？怎样找出所有开这把锁的钥匙？用穷举法设计算法n穷举算法的概念：穷举算法的概念： 穷举算法穷举算法就是按问题本身的性质，通过就是按问题本身的性质，通过多多重循环重循环一一列举出该问题所有可能的解（一一列举出该问题所有可能的解（不能不能遗漏，也不能重复遗漏，也不能重复），并在逐一列举的过程中，），并在逐一列举的过程中，检验每个可能的解是否是问题的真正解检验每个可能的解是否是问题的真正解，若是，若是，我们采用这个解，否则抛弃它。我们采用这个解，否则抛弃它
2、。用穷举法设计算法用穷举法设计算法n 穷举算法的要点：穷举算法的要点： 列举所有可能的解（不能遗漏，也不能重列举所有可能的解（不能遗漏，也不能重 复），检验每个可能的解。复），检验每个可能的解。 用穷举法设计算法问题问题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)
3、printf(“%dn”,i); i=i+1; 用穷举法设计算法问题问题3：从：从1100中找出所有中找出所有能被能被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
4、这九个数字组成的所有可能的二位这九个数字组成的所有可能的二位数数n。用流程图描述。用流程图描述。分析：分析：个位数个位数上的数字可以是那几种上的数字可以是那几种数字？用数字？用变量变量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 1
5、02111 12 13 14 1516 17 18 19j=2#includeusing namespace std;int 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+)
6、printf(%dn,i*10+j); return 0; 用穷举法设计算法标准输入输出速度比较快。标准输入输出速度比较快。流输入输出在数据比较多，比如流输入输出在数据比较多，比如1000000个数据的时候会很慢。个数据的时候会很慢。ios:sync_with_stdio(false) 用穷举法设计算法采用穷举算法解题的基本思想：采用穷举算法解题的基本思想：（1） 明确问题要求，确定枚举对象，用合适类型明确问题要求，确定枚举对象，用合适类型的变量表示枚举对象。的变量表示枚举对象。（2） 明确枚举对象的取值范围。明确枚举对象的取值范围。（3） 根据题目要求，写出有关的条件表达式。这根据题目要求，
7、写出有关的条件表达式。这里条件表达式可以是数学表达式、关系表达式或里条件表达式可以是数学表达式、关系表达式或逻辑表达式；逻辑表达式；（4） 使用循环语句枚举出可能的解，在循环体内使用循环语句枚举出可能的解，在循环体内验证各种条表达式是否满足；验证各种条表达式是否满足；（5） 根据问题背景，优化程序，以便缩小搜索范根据问题背景，优化程序，以便缩小搜索范围，减少程序运行时间。围，减少程序运行时间。用穷举法设计算法【例5】：（百钱买百鸡问题）大约在公元5世纪，数学家张邱建在他的算经中提出了一个闻名于后世的百钱百鸡问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，翁、母、雏各几何？1.
8、算法分析与设计(1) 以三种鸡的个数为枚举对象，分别设为x,y,z。根据题意，可以列出下面的不定方程(2)确定枚举变量的取值范围。显然，x，y，z的取值范围为 0x,y,z100;用穷举法设计算法#includeusing 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
9、=78x=7,y=13,z=80x=8,y=11,z=81x=11,y=6,z=83x=12,y=4,z=84有错误用穷举法设计算法#includeusing 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 & 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用穷举法设计算法#incl
10、udeint 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=%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的枚举范围是 0x14
11、,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() 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 k
12、ey to continue用穷举法设计算法逻辑推理问题n逻辑推理问题用穷举法设计算法【例6】：（谁做的好事）已知有有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。A说：不是我。B说：是C。C说：是D。D说：他胡说。已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。用穷举法设计算法1.算法分析将相关的陈述写成关系表达式和逻辑表达式我们把四个人说的四句话写成关系表达式。定义变量thisman表示做好事的人（将其定义为字符型）。四个人说的话关系表达式A说：不是我。thisman!=AB说：是C。thisman=CC说：是D。thisman=
13、DD说：他胡说。thisman!=D用穷举法设计算法关系表达式的计算结果只有0（假）和1（真）两种结果。现在“已知三个人说的是真话，一个人说假话”，也就是表中的4个关系表达式中有3个是真的，1个是假的。 因此4个关系表达式的值的和应该等于3。定义变量cond表示四个关系表达式的和 cond= thisman!=A+ thisman=C+ thisman=D+ thisman!=D 那么，cond=3穷举试探。我们现在并不知道是谁做得好事，但我们知道做好事的人是A,B,C,D四个人中的某一个。因此，我们可以一个一个地试探。先假设是A做的好事，即thisman=A，然后看cond=3条件是否成立，
14、然后再假设是B做的好事，即thisman=B,再测试条件cond=3 是否成立，如此继续下去，将所有可能的情况（本例自有4种情况）都测试一遍，在实际编程过程中，都是使用循环来一个一个的测试 用穷举法设计算法for(thisman=A;thisman=D;thisman+) cond=(thisman!=A)+(thisman=C) +(thisman=D)+(thisman!=D); if(cond=3)printf(做好事的人是：%Cn,thisman); 2. 核心代码用穷举法设计算法#includeusing namespace std;int main() char thisman;i
15、nt cond;for(thisman=A; thisman=D;thisman+) cond=(thisman!=A)+(thisman=C) +(thisman=D)+(thisman!=D);if(cond=3)printf(做好事的人是：%Cn,thisman); 用穷举法设计算法【例7】: (四大湖问题)上地理课时，四个学生回答我国四个淡水湖大小时说： A学生：洞庭湖最大，洪泽湖最小，鄱阳湖第3 B学生：洪泽湖最大，洞庭湖最小，鄱阳湖第2，太湖第3 C学生：洪泽湖最小，洞庭湖第3 D学生：鄱阳湖最大，太湖最小，洪泽湖第2，洞庭第3 对于湖的大小，每个学生仅答对一个，请编程判断四个湖的
16、大小用穷举法设计算法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 这是三个关系表达式，由于每个学生的叙述只有一个正确，所以这三个关系表达式的值的和应等于1。 A学生的叙述可表示成： ( (a=1)+(b=4)+(c=3）)=1 同理，B学生的叙述表示成： (b=1)+(a=4)+(c=2)+(d=3)=1 C学生
17、的叙述可表示成： (b=4)+(a=3) =1 D学生的叙述可表示成： (c=1)+(d=4)+(b=2)+(a=3)=1用穷举法设计算法for(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=(c=1)+(d=4)+(b=2)+(a=3)=1; if(ca & cb & cc & cd) printf(TongTing=%dn,a); printf(Hongzhe=%
18、dn,b);printf(Poyang=%dn,c); printf(Taihu=%dn,d); /end for(3) 穷举: 穷举a,b,c,d四个变量的所有可能取值,进行测试，满足前述四个条件的取值就是我们所要的结果用穷举法设计算法【例8】（白帽子和红帽子问题）厅内有5个人，他们均戴着帽子白帽子和红帽子。已知戴白帽子的说真话，戴红帽子的说假话，请从他们各自提供的线索辨别谁戴白帽子，谁戴红帽子。甲：我看见一个戴白帽子的乙：我没有看见戴红帽子的丙：我看见一个戴白帽子的，但不是甲丁：我没有看见戴白帽子的戊：我的帽子和丙一样用穷举法设计算法 定义变量 用5个整型变量a,b,c,d,e分别表示甲、
19、乙、丙、丁、戊，1表示戴白帽子，0表示戴红帽子。 写出五个人所说的每句话的逻辑表达式甲：(b+c+d+e=1)乙：(a+c+d+e=4)丙：(b+d+e=1)丁：(a+b+c+e=0)戊：(e=c)这里只是简单地将五个人说的话写成了表达式，但这还不够，由于这五个人本身有些说真话，有些说假话，因此如何判断上述五个表达式的真假呢？用穷举法设计算法 思考：每个人说话的真假与他所戴的帽子有关，如果他戴的是白帽子，则他说真话；如果他戴的是红帽子，则他所说的是假话，这样将每个人帽子颜色与他说的话直接联系起来，因此上述条件可表示成： 甲：(b+c+d+e=1)=a乙：(a+c+d+e=4)=b丙：(b+d+
20、e=1)=c丁：(a+b+c+e=0)=d戊：(e=c)=e用穷举法设计算法void 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 & c3 & c4 & c5) printf(a=%d,b=%d,c=%d,d=%d,e=%dn, a,b,c,
21、d,e) ; 穷举：对变量a,b,c,d,e的所有可能取值情况进行枚举，这要用一个5重循环实现。用穷举法设计算法例例9 9：输入绳子的长度：输入绳子的长度n n，将该绳子分成三段，每段，将该绳子分成三段，每段的长度为正整数，输出由该三段绳子组成的三角的长度为正整数，输出由该三段绳子组成的三角形个数。形个数。 算法分析：没有公式直接求出三角形的个数算法分析：没有公式直接求出三角形的个数算法分析：没有公式直接求出三角形的个数算法分析：没有公式直接求出三角形的个数, , , ,所以程所以程所以程所以程序只能采用穷举法序只能采用穷举法序只能采用穷举法序只能采用穷举法, , , ,一一验证范围内的数是否
22、能构成一一验证范围内的数是否能构成一一验证范围内的数是否能构成一一验证范围内的数是否能构成三角形三角形三角形三角形, , , ,若是则累计。若是则累计。若是则累计。若是则累计。 用穷举法设计算法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;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+;穷举法穷举法穷举法穷举法用穷举法
23、设计算法穷举法的基本概念 穷举方法是基于计算机特点而进行解题的思维方法。穷举方法是基于计算机特点而进行解题的思维方法。一般是在一时找不出解决问题的更好途径（即从数一般是在一时找不出解决问题的更好途径（即从数学上找不到求解的公式或规则）时，可以根据问题学上找不到求解的公式或规则）时，可以根据问题中的的部分条件（约束条件）将所有可能解的情况中的的部分条件（约束条件）将所有可能解的情况列举出来，然后通过一列举出来，然后通过一 一验证是否符合整个问题的一验证是否符合整个问题的求解要求，而得到问题的解。这样解决问题的方法求解要求，而得到问题的解。这样解决问题的方法我们称之为穷举算法。穷举算法特点是算法简
24、单，我们称之为穷举算法。穷举算法特点是算法简单，但运行时所花费的时间量大。因此，我们在用穷举但运行时所花费的时间量大。因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。情况排除在外，以尽快取得问题的解。 用穷举法设计算法穷举算法模式 1、问题解的可能搜索的范围：问题解的可能搜索的范围： 用循环或循环嵌套结构实现用循环或循环嵌套结构实现 2、写出符合问题解的条件。写出符合问题解的条件。 3、能使程序优化的语句，以便缩小搜索范能使程序优化的语句，以便缩小搜索范 围，减少程序运行时间。围，减少程序运行时间。 用
25、穷举法设计算法穷举法应用 穷举穷举法法应应用很多，比如一些密用很多，比如一些密码码破破译软译软件通件通常就是用的常就是用的穷举穷举算法。如在算法。如在QQQQ上，上，OicqPassOverOicqPassOver这这个工具个工具穷举穷举你的口令，它根你的口令，它根据机器性能最高可以每秒据机器性能最高可以每秒测试测试2000020000个口令，个口令，如果口令如果口令简单简单，一分，一分钟钟内，密内，密码码就会遭到破就会遭到破译译。下面我。下面我们们来以来以sznoisznoi上的例子上的例子说说明明穷举穷举法的基本法的基本应应用。用。 用穷举法设计算法d052: 小球颜色方案内容：内容：一个
26、看不见的袋子中装有红、橙、黄、绿、蓝五种颜色的小球若干，每次随意摸出三个小球，输出三个小球颜色都不一样的所有可能的方案总数。（我承认害了不少人，大家认为：红、橙、黄 和 橙、红、黄不一样吧，这样就是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: 勾股数 内容：内容：
27、20以内勾股数（假设a=b=c)a2+b2=c2 若有多组，按a从小到大顺序输出 .输入说明：输入说明：无输出说明：输出说明：一行一组三个数，用空格隔开用穷举法设计算法d058: 勾股数 #include 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成为一组
28、倒立的勾股数！注意，是正整数哦！你的任务是输出60以内的倒立勾股数，按x的的增序输出（每行一个）。 用穷举法设计算法d071: 倒立勾股数 #includeusing namespace std;int main()int 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的个数多于数字
29、0的个数的这类二进制数称为A类数，否则就称其为B类数。例如：（13）10=（1101）2其中1的个数为3，0的个数为1，则称此数为A类数；（10）10=（1010）2其中1的个数为2，0的个数也为2，称此数为B类数；（24）10=（11000）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
30、_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内容：内容：设有有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=2用穷举法设计算法
31、f010: 竞赛安排 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; 用穷举法设计算法
