算法(穷举法)第二讲.ppt

《算法(穷举法)第二讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、穷举法1．什么是穷举法？也叫枚举法、列举法——将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有对象，问题将最终得以解决。穷举法的一般模式列出问题的可能范围，一般用循环或者循环嵌套结构来实现探究、挖掘出问题解的约束条件根据约束条件优化算法，尽可能地缩小穷举范围，减少穷举次数，降低算法的时间和空间复杂度。穷举法的应用举例11.判断2000～2500年中的每一年是否为闰年。自然语言描述：设y为被检测的年份，则算法可表示如下：S1：2000→y；S2：若y不能被4

2、整除，则输出y“不是闰年”，然后转到S6；S3：若y能被4整除，不能被100整除，则输出y“是闰年”，然后转到S6；S4：若y能被100整除，又能被400整除，输出y“是闰年”，然后转到S6；S5：输出y“不是闰年”，然后转到S6；S6：y+1→y；S7：当y≤2500时,返回S2继续执行，否则结束。流程图C语言程序#includevoidmain(){inty=2000;while(y<=2500){if((y%4)==0){if(y%100!=0)printf("%d年是闰

3、年",y);elseif(y%400==0)printf("%d年是闰年",y);elseprintf("%d年是非闰年",y);}elseprintf("%d年是非闰年",y);y=y+1;}}穷举法的应用举例2百钱百鸡问题：相传我国南北朝时，京城有个卖鸡的张姓老汉，他有一个儿子非常聪明，尤其擅长算术，到十二三岁时已是远近闻名的“小神童”了。当朝宰相听说后想试探个究竟，于是派仆人到张老汉的店里打听鸡的价钱，张老汉告知“公鸡五文钱一只，母鸡三文一只，小鸡一文三只”。于是，仆人给他

4、一百文钱，要求公鸡、母鸡、小鸡都要，数量不多不少正好一百只，命他次日送到府上。这可难为了张老汉，他怎么凑也凑不够这个数，只好问儿子。“小神童”不慌不忙，掐指一算就给出了答案，第二天照数送到宰相府。宰相见难不倒“小神童”，又让仆人给张老汉一百文钱，要求再买一百只鸡，搭配方法不能和上次一样。结果“小神童”又很快给出了答案，宰相暗暗称奇，想最后再试一次，谁知还是没有难倒“小神童”。这个故事就是我国古代数学名著《张邱建算经》里的百鸡百钱问题。请用穷举法求解所有的组合方法。自然语言描述：题目分析与算法设计

5、设鸡翁、鸡母、鸡雏的个数分别为x,y,z，题意给定共100钱要买百鸡，若全买公鸡最多买20只，显然x的值在0~20之间；同理，y的取值范围在0~33之间，可得到下面的不定方程：5x+3y+z/3=100x+y+z=100所以此问题可归结为求这个不定方程的整数解。由程序设计实现不定方程的求解与手工计算不同。在分析确定方程中未数变化范围的前提下，可通过对未知数可变范围的穷举，验证方程在什么情况下成立，从而得到相应的解。流程图C语言程序include  main()  {  i

6、nt x,y,z;  for(x=0;x<=20;x++)  for(y=0;y<=33;y++)   {if(5*x+3*y+z/3==100&&z%3==0)  printf(“cock=%d;hen=%d;chicken=%d",x,y,z);}  }我们使用信用卡在柜员机上取钱时，为什么系统要限制输入密码的次数？小结1、穷举法分析：⑴确定范围⑵验证条件2、自觉遵守网络道德与法规穷举法的作业1、换零钱问题。将一元钱换成1分，2分或5分的零钱有多少种换法？？C程序#inclu

7、de#includeintmain(){intone,two,five,num=0;for(one=0;one<=100;one++)for(two=0;two<=50;two++)for(five=0;five<=20;five++)if(one+two*2+five*5==100){num++;printf("100=%d*1+%d*2+%d*5",one,two,five);}printf("%dpossibilities

8、n",num);}