《用穷举法设计程序》学案

本文格式为Word版，下载可任意编辑——《用穷举法设计程序》学案

4.2《用穷举法设计程序》学案

活动一：密码问题穷举算法基本模式：For穷举变量1=？to?For穷举变量2=？to?If条件then输出答案Next穷举变量2Next穷举变量1穷举次数与哪些因素有关？你能提出反暴力破解的对策吗？

活动二：礼品问题

班里要举行班级聚会，要用600元班会费为50名同学准备50份礼品进行抽奖。你要负责去购买礼品，选定了公仔(20元/个)、水杯(15元/个)和笔筒(10元/个)三类商品。要求刚好用完600元买50件礼品（每种礼品至少一件），这三种礼品的数量可以如何搭配？有多少种方案？

环节要求解的问题是什么？分析问题涉及到哪些未知数和条件？能用常用数学方法解决吗？穷举算法三个关键设计：(1)有多少个穷举变算法设计量？(2)各穷举变量的变化范围是什么？穷举变量对应物品变化范围任务破解三位密码算法关键：穷举变量变化范围验证条件1/4

(3)答案所需符合的条件是什么？编写程序开启“礼品问题〞程序，根据你的算法设计，程序中“？〞处应如何填写？调试运行点击启动运行程序，如发现错误可点击■终止运行，修改程序。程序穷举次数为多少次？

优化穷举，提高效率：

观测你所完善的“礼品问题〞程序运行结果，并与其他同学的运行结果比较。认真阅读问题的各个条件，尝试优化程序，在合理范围内尽量减少穷举的次数。穷举优化

活动三：密码问题

小陆有一EMail邮箱的密码是一个5位数。但由于有一段比较长的时间没有开启过这个邮箱了，小陆把这个密码给忘了。但他记得这个密码一定同时是61和83的倍数。小陆还记得这个密码的中间一位（百位数）是2。你能设计一个程序帮他找回这个密码吗？

序号方案一算法描述程序穷举次数分析优化措施优化后的穷举次数分别用a1、a2、Fora1=1To9'a1是密码万位上的数字a3、a4、a5表示Fora2=0To9'a2是密码千位上的数字这个5位数的Fora4=0To9'a4是密码十位上的数字各个数位(a3=2Fora5=0To9'a5是密码个位上的数字2/4

在程序中不出d=a1*10000+a2*1000+2*100+a4*现)，在它们的10+a5各自的范围中If(dMod61=0)And(dMod83=0)Then变化，然后组成Printd5位数d，判断Nexta5d能否同时被Nexta461和83整除即Nexta2可得到结果。Nexta1分别用a1、a2、Fora=10000To99999a3、a4、a5表示c=a\\100Mod10这个5位数的Ifc=2AndaMod(61*83)=0ThenPrint\密码各个数位(a3=2是：\方案二在程序中不出Nexta现)，在它们的各自的范围中变化，然后组成5位数d，判断d能否同时被61和83整除即可得到结果。有解的范围只p=(10000\\61\\83+1)*61*83限于同时是61Fora=pTo99999Step61*83方案三和83的倍数。61和83的最小c=a\\100Mod10Ifc=2ThenPrint\这个5位的密码是：\公倍数是Nexta5063，所以我们只在5位数中是5