4.2.1用穷举法求解问题的基本过程

,4.2用穷举法设计程序,算法与程序设计,广东教育出版社,吉林省安图县第一中学邹娓娓,第四章算法与程序实现,课程内容标准,穷举法与问题解决、了解穷举法的基本概念及穷举法设计算法的基本过程。、能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。,教学目标,知识与技能（1）理解穷举法的基本思想；（2）学会建立正确的数学模型，确定穷举方案；过程与方法（1）能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题；（2）初步掌握程序调试、运行的方法；情感态度与价值观（1）经历用计算机解决问题的过程，体验成功的快乐；（2）在老师的指导下，与同学共同探究问题，让学生体验自主学习、协作学习的乐趣。,重点难点分析,教学重点：（1）建立正确的数学模型，确定穷举方案；（2）根据命题确定自变量的取值范围；（3）正确表达“符合条件”的判断。教学难点：（1）如何确定方案；（2）如何评价各种穷举方案的优劣。,浅浅要在青丘养几只鸡，打算养100只，预算是100个铜钱。一只公鸡5个铜钱，一只母鸡3个铜钱，小鸡三只一个铜钱。到底怎么买呢？,分析问题,预算一百个铜钱,设公鸡数为x，母鸡数为y,小鸡数为z;设循环把x所有可能的情况都一一列举出来；设循环把y所有可能的情况都一一列举出来；设循环把z所有可能的情况都一一列举出来；判断是否满足同时x*5+y*3+z/3=100和x+y+z=100，否回到;输出x,y,z的值;z是否超出范围，否回到;y是否超出范围，否回到;x是否超出范围，否回到;结束;,x+y+z=100,5x+3y+z/3=100,穷举法,编写程序,设计算法,浅浅要在青丘养几只鸡，打算养100只，预算是100个铜钱。一只公鸡5个铜钱，一只母鸡3个铜钱，小鸡三只一个铜钱。到底怎么买呢？,分析问题,预算一百个铜钱,设公鸡数为x，母鸡数为y,小鸡数为z;设循环把x所有可能的情况都一一列举出来；设循环把y所有可能的情况都一一列举出来；设循环把z所有可能的情况都一一列举出来；判断是否满足同时x*5+y*3+z/3=100和x+y+z=100，否回到;输出x,y,z的值;z是否超出范围，否回到;y是否超出范围，否回到;x是否超出范围，否回到;结束;,x+y+z=100,5x+3y+z/3=100,穷举法,编写程序,设计算法,浅浅要在青丘养几只鸡，打算养100只，预算是100个铜钱。一只公鸡5个铜钱，一只母鸡3个铜钱，小鸡三只一个铜钱。到底怎么买呢？,分析问题,预算一百个铜钱,设公鸡数为x，母鸡数为y,小鸡数为z;设循环把x所有可能的情况都一一列举出来；设循环把y所有可能的情况都一一列举出来；设循环把z所有可能的情况都一一列举出来；判断是否满足同时x*5+y*3+z/3=100和x+y+z=100，否回到;输出x,y,z的值;z是否超出范围，否回到;y是否超出范围，否回到;x是否超出范围，否回到;结束;,x+y+z=100,5x+3y+z/3=100,穷举法,编写程序,设计算法,设公鸡数为x，母鸡数为y,小鸡数为z;设循环把x所有可能的情况都一一列举出来；设循环把y所有可能的情况都一一列举出来；设循环把z所有可能的情况都一一列举出来；判断是否满足同时x*5+y*3+z/3=100和x+y+z=100，否回到;输出x,y,z的值;z是否超出范围，否回到;y是否超出范围，否回到;x是否超出范围，否回到;结束;,方法1,方法2,方法3,编写程序,x,y,z取值范围,设公鸡数为x，母鸡数为y,小鸡数为z;设循环把x所有可能的情况都一一列举出来；设循环把y所有可能的情况都一一列举出来；设循环把z所有可能的情况都一一列举出来；判断是否满足同时x*5+y*3+z/3=100和x+y+z=100，否回到;输出x,y,z的值;z是否超出范围，否回到;y是否超出范围，否回到;x是否超出范围，否回到;结束;,方法1,方法2,方法3,编写程序,x,y,z取值范围,穷举法也称为枚举法。这种算法是把问题涉及的可能情况一一罗列，并且根据题目的条件和实际背景逐个作出判断，从中挑选出符合条件的解答。,计算机的特点之一就是运算速度快、善于重复做一件事情，“穷举法”正是基于这一特点的最古老的算法。它一般是一时找不到解决问题的更好的途径，即从数学上找不到求解的公式或者规则时，根据问题中的“约束条件”，将解的所有可能情况一一列举出来，然后再逐一验证是否符合整个问题的求解要求，从而得到问题的所有解,穷举法,穷举法定义,1、问题解的可能搜索的范围：用循环或循环嵌套结构实现2、写出符合问题解的条件。3、能使程序优化的语句，以便缩小搜索范围，减少程序运行时间。,穷举算法模式,设一百只鸡中公鸡、母鸡、小鸡分别为x、y、z问题化为三元一次方程组：这里x、y、z为正整数，且z是的倍数（因为小鸡一元三只）；由于鸡和钱的总数都是100，可以确定xyz的取值范围：x的取值范围为020y的取值范围为033z的取值范围为399，步长为3对于这个问题我们可以用穷举的方法，遍历xyz的所有可能组合，最后得到的问题的解。,dimxasintegerDimyasintegerDimzasintegerforx=0to20fory=0to33forz=0to100step3z=100-x-yif(x*5+y*3+z/3=100)and(x+y+z=100)thenprint;“公鸡数”;x,print;“母鸡数”;y,print;“小鸡数”;z,printendifnextznextynextx,x的取值范围为020y的取值范围为033z的取值范围为399,方法1,方法2,方法3,返回,dimx,y,zasintegerforx=0to20fory=0to33z=100-x-yif(x*5+y*3+z/3=100)thenprint;“公鸡数”;x,print;“母鸡数”;y,print;“小鸡数”;z,printendifnextynextx,当公鸡与母鸡的数目确定了，小鸡的数目可用总数100减去公鸡与母鸡的数、于是三重循环可变为二重循环。,x的取值范围为020y的取值范围为033z的取值范围为100-x-y,方法1,方法2,方法3,返回,算法二中，当公鸡的数量确定，母鸡的数量是随公鸡的数量变化而变化，不需要每次都列举到33才结束。最大可能是33-x，于是程序可优化为：,dimx,y,zasintegerForx=0to20Fory=0to(33-x)z=100-x-yIf(x*5+y*3+z/3=100)thenPrint;”公鸡数”;x,Print;”母鸡数”;y,Print;”小鸡数”;z,PrintEndifNextyNextx,运行结果为：02575187881181484,方法1,方法2,方法3,小结,返回,算法一使用了三重循环、算法二使用了二重循环、算法三又将二重训环的次数减少，使程序不断优化。,返回,可见，对于同一个问题，由于思路不一样，算法就不一样，我们应从不同的角度思考问题，努力提高算法的效率,本题小结,4-6：陈婷有一个E-MALL邮箱的密码是一个5位数，但因为有一段比较长的日子没有打开这个邮箱了，陈婷把这个密码给忘了。不过陈婷自己是8月1日出生，而她妈妈的生日是9月1日，她特别喜欢把同时是81和91的倍数用作密码。陈婷还记得这个的中间一位（百位数）是。你能设计一个程序帮她找回这个密码吗？,分析问题,本问题的数学模型是：,求出一个位数，它的百位数是，而且它能同时被81和91整除。,设计算法A,那么，如何确定求解的算法呢？因为计算机最大的特长还是它的搜索能力，所以，这个问题适合用穷举法进行搜索。但是即使确定了使用穷举，我们还是面临着很多的选择。,设计算法B,设计算法C,4-6：陈婷有一个E-MALL邮箱的密码是一个5位数，但因为有一段比较长的日子没有打开这个邮箱了，陈婷把这个密码给忘了。不过陈婷自己是8月1日出生，而她妈妈的生日是9月1日，她特别喜欢把同时是81和91的倍数用作密码。陈婷还记得这个的中间一位（百位数）是。你能设计一个程序帮她找回这个密码吗？,分析问题,本问题的数学模型是：,求出一个位数，它的百位数是，而且它能同时被81和91整除。,设计算法A,那么，如何确定求解的算法呢？因为计算机最大的特长还是它的搜索能力，所以，这个问题适合用穷举法进行搜索。但是即使确定了使用穷举，我们还是面临着很多的选择。,设计算法B,设计算法C,设计算法A,因为主个密码有位数字是未知的，把各位数字都对所有可能性演变一次（最高位是19，其余各位是09），就可以把可能的情况穷举完。再把各位数字合成一个5位数，判断是否同时被81和91整除就可以了。,分别用a1、a2、a3、a4、a5表示这个5位数的各个数位（a3=在程序中没出现），在它们各自的范围中变化，然后组成5位数d，判断d能否同时被81和91整除即可得到结果。据此编写如下程序：,算法B,算法C,返回,代码A,算法A,编写程序,Privatesubcommand1_click()dimdaslongFora1=1to9fora2=0to9fora4=0to9fora5=0to9d=a1*10000+a2*1000+1*100+a4*10+a5if(dmod81=0)and(dmod91=0)thenprintdnexta5nexta4nexta2nexta1Endsub,A,算法B,算法C,代码A,返回,算法A,设计算法B,把方案A的方法反其道而行之。位数字的范围是1000099999，在此范围内穷举，并对每一个数分解出它的百位数字检验它是否，再判断此5位数是否同时被81和91整除就可以了。,用a表示这个位数。让a从10000变99999，逐个判断a是否同时为81与91的倍数。若是，再分离出它的百位数，并判断它是否.,请同学们完成程序的设计并评价这个解决方案,算法C,算法A,算法B,返回,代码B,程序代码B,PrivateSubCommand2_Click()Fora=10000To99999a1=a10000a2=(a-a1*10000)1000a3=(a-a1*10000-a2*1000)100Ifa3=1ThenIfaMod81=0AndaMod91=0ThenPrint这个5位的密码的：;aEndIfNextaEndSub,算法C,算法A,算法B,返回,代码B,设计算法C,受方案B的启发，有解的范围只限于同时是81和91的倍数。81和91的最小公倍数是7371，所以我们只在5位数中就7371的倍数进行穷举，然后分离出它的百位数判断是否是就能得到答案。按这个算法首先需要知道5位的7371的倍数中哪个最小。亦即求最小的正整数P，使7371=10000,这时P=10000/7371。显然，取10000/7371的整数部分加1就是可用的P。据此写出程序,算法B,算法C,返回,算法A,代码,编写程序C,Privatesubcommand1_click()P=100007371+1fora=P*7371to99999step7371c=a100mod10ifc=1thenprint“这个5位的密码的：”；anextaEndsub,算法B,算法C,代码C,返回,算法A,练习题,1、直角三