用穷举法设计算法.ppt

用穷举法设计算法,问题1： 有一把锁和一串钥匙（共有10把钥匙），怎样找出所有开这把锁的钥匙？,穷举算法的概念： 穷举算法就是按问题本身的性质，通过多重循环一一列举出该问题所有可能的解（不能遗漏，也不能重复），并在逐一列举的过程中，检验每个可能的解是否是问题的真正解，若是，我们采用这个解，否则抛弃它。,用穷举法设计算法,穷举算法的要点： 列举所有可能的解（不能遗漏，也不能重 复），检验每个可能的解。,问题2：从110中找出所有是3倍数的数。用流程图描述解决此数学问题的算法。,#include using namespace std; int main() int i=1; while(i=10) if (i%3=0) printf(“%dn”,i); i=i+1; ,问题3：从1100中找出所有能被7或9整除的数。用流程图描述解决此数学问题的算法。,#include using 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。用流程图描述。,分析： 个位数上的数字可以是那几种数字？用变量i来表示。 十位数上的数字可以是那几种数字？用变量j来表示。 找出二位数n与i、j之间的关系。提示：548=5100+410+8,11,12,13,14,15,16,17,18,19,j=2,问题4：打印输出由1、28、9这九个数字组成的所有可能的二位数n。,#include using 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; ,标准输入输出速度比较快。 流输入输出在数据比较多，比如1000000个数据的时候会很慢。 ios:sync_with_stdio(false),采用穷举算法解题的基本思想： （1） 明确问题要求，确定枚举对象，用合适类型的变量表示枚举对象。 （2） 明确枚举对象的取值范围。 （3） 根据题目要求，写出有关的条件表达式。这里条件表达式可以是数学表达式、关系表达式或逻辑表达式； （4） 使用循环语句枚举出可能的解，在循环体内验证各种条表达式是否满足； （5） 根据问题背景，优化程序，以便缩小搜索范围，减少程序运行时间。,【例5】：（百钱买百鸡问题）大约在公元5世纪，数学家张邱建在他的算经中提出了一个闻名于后世的百钱百鸡问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，翁、母、雏各几何？,1.算法分析与设计 (1) 以三种鸡的个数为枚举对象，分别设为x,y,z。根据题意，可以列出下面的不定方程,(2)确定枚举变量的取值范围。显然，x，y，z的取值范围为 0x,y,z100;,#include using 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 ,x=0,y=25,z=75 x=3,y=20,z=77 x=4,y=18,z=78 x=7,y=13,z=80 x=8,y=11,z=81 x=11,y=6,z=83 x=12,y=4,z=84,有错误,#include using 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 ,修改错误,x=0,y=25,z=75 x=4,y=18,z=78 x=8,y=11,z=81 x=12,y=4,z=84,#include int 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 ,第1次优化,x=0,y=25,z=75 x=4,y=18,z=78 x=8,y=11,z=81 x=12,y=4,z=84 Press any key to continue,只要求出x，y后，z可以由方程(4)直接计算出来。在方程（3）中，假设y=0,则x=14,假设x=0,则y=25。即x,y的枚举范围是 0x14,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次优化,#include using 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=75 x=4,y=18,z=78 x=8,y=11,z=81 x=12,y=4,z=84 Press any key to continue,逻辑推理问题,逻辑推理问题,【例6】：（谁做的好事）已知有有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。 A说：不是我。 B说：是C。 C说：是D。 D说：他胡说。 已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。,1.算法分析 将相关的陈述写成关系表达式和逻辑表达式 我们把四个人说的四句话写成关系表达式。定义变量thisman表示做好事的人（将其定义为字符型）。,关系表达式的计算结果只有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条件是否成立，然后再假设是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. 核心代码,#include using 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学生：洞庭湖最大，洪泽湖最小，鄱阳湖第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,4 a,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学生的叙述可表示成： (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 /end for,(3) 穷举: 穷举a,b,c,d四个变量的所有可能取值,进行测试，满足前述四个条件的取值就是我们所要的结果,【例8】（白帽子和红帽子问题）厅内有5个人，他们均戴着帽子白帽子和红帽子。已知戴白帽子的说真话，戴红帽子的说假话，请从他们各自提供的线索辨别谁戴白帽子，谁戴红帽子。 甲：我看见一个戴白帽子的 乙：我没有看见戴红帽子的 丙：我看见一个戴白帽子的，但不是甲 丁：我没有看见戴白帽子的 戊：我的帽子和丙一样, 定义变量 用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),这里只是简单地将五个人说的话写成了表达式，但这还不够，由于这五个人本身有些说真话，有些说假话，因此如何判断上述五个表达式的真假呢？,思考：每个人说话的真假与他所戴的帽子有关，如果他戴的是白帽子，则他说真话；如果他戴的是红帽子，则他所说的是假话，这样将每个人帽子颜色与他说的话直接联系起来，因此上述条件可表示成：,甲：(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)=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 , 穷举：对变量a,b,c,d,e的所有可能取值情况进行枚举，这要用一个5重循环实现。,例9：输入绳子的长度n，将该绳子分成三段，每段的长度为正整数，输出由该三段绳子组成的三角形个数。,算法分析：没有公式直接求出三角形的个数,所以程序只能采用穷举法,一一验证范围内的数是否能构成三角形,若是则累计。,s=0; for （a=1;ac) ,穷举法,穷举法的基本概念,穷举方法是基于计算机特点而进行解题的思维方法。一般是在一时找不出解决问题的更好途径（即从数学上找不到求解的公式或规则）时，可以根据问题中的的部分条件（约束条件）将所有可能解的情况列举出来，然后通过一 一验证是否符合整个问题的求解要求，而得到问题的解。这样解决问题的方法我们称之为穷举算法。穷举算法特点是算法简单，但运行时所花费的时间量大。因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。,穷举算法模式,1、问题解的可能搜索的范围： 用循环或循环嵌套结构实现 2、写出符合问题解的条件。 3、能使程序优化的语句，以便缩小搜索范 围，减少程序运行时间。,穷举法应用,穷举法应用很多，比如一些密码破译软件通常就是用的穷举算法。如在QQ上，OicqPassOver这个工具穷举你的口令，它根据机器性能最高可以每秒测试20000个口令，如果口令简单，一分钟内，密码就会遭到破译。下面我们来以sznoi上的例子说明穷举法的基本应用。 32:8080/oj/,d052: 小球颜色方案 内容： 一个看不见的袋子中装有红、橙、黄、绿、蓝五种颜色的小球若干，每次随意摸出三个小球，输出三个小球颜色都不一样的所有可能的方案总数。（我承认害了不少人，大家认为：红、橙、黄 和 橙、红、黄不一样吧，这样就是XX种，谢谢）,d052: 小球颜色方案 #include using 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 ,d058: 勾股数 内容： 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成为一组倒立的勾股数！注意，是正整数哦！ 你的任务是输出60以内的倒立勾股数，按x的的增序输出（每行一个）。,d071: 倒立勾股数 #include using 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) ,f003: AB类数 (NOIP1995) 内容： 若将一个正整数化为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为A类数，否则就称其为B类数。 例如：（13）10=（1101）2 其中1的个数为3，0的个数