用穷举法设计算法.

用穷举法设计算法问题1：有一把锁和一串钥匙（共有10把钥匙），怎样找出所有开这把锁的钥匙？穷举算法的概念：穷举算法就是按问题本身的性质，通过多重循环一一列举出该问题所有可能的解（不能遗漏，也不能重复），并在逐一列举的过程中，检验每个可能的解是否是问题的真正解，若是，我们采用这个解，否则抛弃它。用穷举法设计算法穷举算法的要点：列举所有可能的解（不能遗漏，也不能重复），检验每个可能的解。问题2：从1～10中找出所有是3倍数的数。用流程图描述解决此数学问题的算法。输出i开始i←1i≤10i←i+1结束NYi是3的倍数YN#includecstdiousingnamespacestd;intmain(){inti=1;while(i=10){if(i%3==0)printf(“%d\n”,i);i=i+1;}}问题3：从1～100中找出所有能被7或9整除的数。用流程图描述解决此数学问题的算法。输出i开始i←1i≤100i←i+1结束NYi能被7或9整除YN#includecstdiousingnamespacestd;intmain(){inti;for(i=1;i=100;i=i+1){if(i%7==0||i%9==0)printf(“%d\n”,i);}}问题4：打印输出由1、2……8、9这九个数字组成的所有可能的二位数n。用流程图描述。分析：•个位数上的数字可以是那几种数字？用变量i来表示。•十位数上的数字可以是那几种数字？用变量j来表示。•找出二位数n与i、j之间的关系。提示：548=5×100+4×10+8输出n开始j←1j≤9i←i+1结束NNi←1Yi≤9n←j*10+iYj←j+1执行过程：j=1in34567891021111213141516171819j=2#includecstdiousingnamespacestd;intmain(){intj,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、2……8、9这九个数字组成的所有可能的二位数n。#includecstdiousingnamespacestd;intmain(){inti,j;for(i=1;i=9;i++){for(j=1;j=9;j++){printf(%d\n,i*10+j);}}return0;}标准输入输出速度比较快。流输入输出在数据比较多，比如1000000个数据的时候会很慢。ios::sync_with_stdio(false)采用穷举算法解题的基本思想：（1）明确问题要求，确定枚举对象，用合适类型的变量表示枚举对象。（2）明确枚举对象的取值范围。（3）根据题目要求，写出有关的条件表达式。这里条件表达式可以是数学表达式、关系表达式或逻辑表达式；（4）使用循环语句枚举出可能的解，在循环体内验证各种条表达式是否满足；（5）根据问题背景，优化程序，以便缩小搜索范围，减少程序运行时间。【例5】：（百钱买百鸡问题）大约在公元5世纪，数学家张邱建在他的《算经》中提出了一个闻名于后世的百钱百鸡问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，翁、母、雏各几何？1.算法分析与设计(1)以三种鸡的个数为枚举对象，分别设为x,y,z。根据题意，可以列出下面的不定方程(2)确定枚举变量的取值范围。显然，x，y，z的取值范围为0≤x,y,z≤100;#includecstdiousingnamespacestd;intmain(){intx,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=%d\n,x,y,z);}x=0,y=25,z=75x=3,y=20,z=77x=4,y=18,z=78x=7,y=13,z=80x=8,y=11,z=81x=11,y=6,z=83x=12,y=4,z=84有错误#includecstdiousingnamespacestd;intmain(){intx,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=%d\n,x,y,z);}修改错误x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84#includecstdiointmain(){intx,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=%d\n,x,y,z);}第1次优化x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84Pressanykeytocontinue只要求出x，y后，z可以由方程(4)直接计算出来。在方程（3）中，假设y=0,则x=14,假设x=0,则y=25。即x,y的枚举范围是0≤x≤14,0≤y≤25.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次优化#includecstdiousingnamespacestd;intmain(){intx,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=%d\n,x,y,z);}}x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84Pressanykeytocontinue逻辑推理问题逻辑推理问题【例6】：（谁做的好事）已知有有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。A说：不是我。B说：是C。C说：是D。D说：他胡说。已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。1.算法分析将相关的陈述写成关系表达式和逻辑表达式⑴我们把四个人说的四句话写成关系表达式。定义变量thisman表示做好事的人（将其定义为字符型）。四个人说的话关系表达式A说：不是我。thisman!=‘A’B说：是C。thisman==‘C’C说：是D。thisman==‘D’D说：他胡说。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条件是否成立，然后再假设是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(做好事的人是：%C\n,thisman);}2.核心代码#includecstdiousingnamespacestd;intmain(){charthisman;intcond;for(thisman='A';thisman='D';thisman++){cond=(thisman!=‘A’)+(thisman==‘C’)+(thisman==‘D’)+(thisman!=‘D);if(cond==3)printf(做好事的人是：%C\n,thisman);}}【例7】:(四大湖问题)上地理课时，四个学生回答我国四个淡水湖大小时说：A学生：洞庭湖最大，洪泽湖最小，鄱阳湖第3B学生：洪泽湖最大，洞庭湖最小，鄱阳湖第2，太湖第3C学生：洪泽湖最小，洞庭湖第3D学生：鄱阳湖最大，太湖最小，洪泽湖第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))==1C学生的叙述可表示成：((b==4)+(a==3))==1D学生的叙述可表示成：((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=((c==1)+(d==4)+(b==2)+(a==3))==1;if(ca&&cb&&cc&&cd){printf(TongTing=%d\n,a);printf(Hongzhe=%d\n,b);printf(Poyang=%d\n,c);printf(Taihu=%d\n,d);}}//endfor(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)==evoid