穷举法

LOGO网络信息与计算中心谢华成Page2问题导入希望大家能在学完习本课后能解决这个问题。某同学记不清QQ密码了，他的密码是一个5位数，67□□8，其中百位和十位不记得了，但记得5位数的密码能被78整除，也能被67整除，怎么找回密码？Page3穷举法简介是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止------维基百科把所有可能的情况一一测试，筛选出符合条件的各种结果进行输出。Page4教学目标知识与技能：了解穷举法及其特点；用穷举法设计算法的基本过程；能够根据具体问题的要求，使用穷举法设计程序。过程和方法：运用观察、发现、归纳、应用的方法，发展学生的归纳思维；培养学生独立探究与自主发现的学习能力。Page5重点与难点内容重点内容：穷举算法解决问题的一般步骤；能根据具体问题的要求，提高运用穷举算法解决问题的能力。难点内容：通过观察、类比多种方式培养学生归纳思维；应用穷举法解决非数据处理问题。Page6《孙子算经》中的孙子问题今有物不知其数三三数之剩二，五五数之剩三，七七数之剩二。问物最少几何？例1：利用穷举法求解古典数学问题三人同行七十稀，五树梅花廿一枝；七子团圆正半月，除百零五便得知。2×70+3×21+2×15＝233233-105-105=23中国剩余定理的局限性：数字线索须两两互素，如3，5，7…若数字线索不是两两互素，如何求解？Page7#includestdio.hmain(){intx;for(x=1;x5000;x++){if(x%3==2&&x%5==3&&x%7==2)printf(x=%d\n,x);}}孙子定理求解源程序x=23x=128x=233……x=4748x=4853x=4958思路：设物数为x，则x应满足：x%3==2&&x%5==3&&x%7==2应用穷举法对x从1开始试验此解的局限性?穷举法·求孙子问题最小解Page8穷举法·求孙子问题最小解#includestdio.hmain(){intx;for(x=1;;x++){if(x%3==2&&x%5==3&&x%7==2){printf(x=%d\n,x);break;}}}合理构造穷举的条件和终止条件Page9设公鸡为x只，母鸡为y只，小鸡为z只100335100zyxzyx穷举法中的多重循环编程问题我国古代数学家张丘建在《算经》一书中提出了“百鸡问题”：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？Page10百元百鸡问题分析设公鸡为x只，母鸡为y只，小鸡为z只100335100zyxzyxPage11main(){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=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84Page12main(){intx,y,z;for(x=0;x=100;x++)for(y=0;y=100;y++)for(z=0;z=100;z++){if(z%3==0&&x+y+z==100&&5*x+3*y+z/3==100)printf(x=%d,y=%d,z=%d\n,x,y,z);}}百钱百鸡问题源程序穷举法解决百钱百鸡问题【讨论】此算法运算达101×101×101=1030301次（100多万次）。结果：x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84Page13main(){intx,y,z;for(x=0;x=100;x++)for(y=0;y=100;y++){z=100-x-y;if(z%3==0&&5*x+3*y+z/3==100)printf(“x=%d,y=%d,z=%d\n,x,y,z);}}优化后的源程序初步优化【讨论】只进行101×101=10201次运算（运算量减少了1%）将三重循环改编为两重循环提高了程序效率Page14【课堂讨论】谁做了好事？4位同学中，有1位做了好事，不留名，表扬信来了之后，校长欲调查谁做了好事。调查中，得知4条信息。已知有3人说了真话，1人说了假话。根据信息，推断做好事之人。不是我。A是C。B是D。CC胡说。DPage15编程思路剖析为找出该人，先假设任一人是做好事者，逐一代入其他假设，检测其他3句话的真伪。若有3句为真，则锁定该人，否则换下一人再试。如，先假定是A同学，让thisman='A';A说：不是我。B说：是C。C说：是D。D说：C胡说。A说：thisman!=‘A’;‘A’!=‘A’假，值为0。(假设)B说：thisman==‘C’;‘A’==‘C’假，值为0。C说：thisman==‘D’;‘A’==‘D’假，值为0。D说：thisman!=‘D’;‘A’!=‘D’真，值为1。显然，不是‘A’做的好事(4个关系表达式值的和为1)Page16编程思路剖析人未找出，假定此人是B，即thisman=‘B';A说：不是我。B说：是C。C说：是D。D说：C胡说。A说：thisman!=‘A’;‘B’!=‘A’真，值为1。B说：thisman==‘C’;‘B’==‘C’假，值为0。C说：thisman==‘D’;‘B’==‘D’假，值为0。D说：thisman!=‘D’;‘B’!=‘D’真，值为1。显然，不是'B'所为(4个关系表达式值的和为2)Page17编程思路剖析接着假定此人是C，即thisman=‘C';代入到4句话中：A说：不是我。B说：是C。C说：是D。D说：C胡说。A说：thisman!=‘A’;‘C’!=‘A’真，值为1。B说：thisman==‘C’;‘C’==‘C’真，值为1。C说：thisman==‘D’;‘C’==‘D’假，值为0。D说：thisman!=‘D’;‘C’!=‘D’真，值为1。显然，就是‘C’做了好事(4个关系表达式值的和为3)采用穷举法，一个人一个人地去试，若4句话中有3句为真，该人即为所求。Page18穷举法解决测谎问题#includestdio.hmain(){charthisman;intra,rb,rc,rd,result;for(thisman='A';thisman='D';thisman++){ra=(thisman!='A');rb=(thisman=='C');rc=(thisman=='D');rd=(thisman!='D');result=ra+rb+rc+rd;if(result==3)printf(做好事的人是：%c\n,thisman);}}测谎问题源程序Page19穷举法课堂总结穷举法基本思想不重复、不遗漏地从所有可能中寻找满足条件的解穷举法的应用领域非常规数学问题密码破解逻辑问题求解优点：充分利用计算机的高速特性，使复杂的逻辑推理过程简单化。缺点：运算量较大穷举法运用关键：穷举范围的确定、穷举的终止条件构造。Page20网络信息与计算中心谢华成