高中信息技术选修1：算法与程序设计 4.2 用穷举法设计程序

主讲人:林武坚

QQ:364515313Email:linwujian@126.com信息技术普通高中选修1第四章算法及其程序实现第四章算法及其程序实现4.1用解析法设计程序4.2用穷举法设计程序4.3查找算法设计4.4排序算法设计4.5递归算法与递归程序4.6问题求解综合活动4.2用穷举法设计程序4.2用穷举法设计程序新快报：英发明“福尔摩斯”软件可助警方破奇案4.2用穷举法设计程序

现代福尔摩斯侦探之谁是小偷：案发现场，有A、B、C、D四个人，其中一人偷了东西。当被问到是谁偷的时，A说：“不是我”，B说：“是C偷的”，C说：“是D偷的”，D说：“C胡说！”。已知四个人中有三个说的是真话，一个说的是谎话，您能否快速判断小偷究竟是谁？借助程序设计呢？★问题描述4.2用穷举法设计程序小偷是谁？您是如何求解的？提问：假设小偷是A，可知A说谎话、B说谎话、C说谎话、D说真话，与已知的“三个说真话一个说谎话”不符，假设不成立；分析：1.分析问题★问题解决假设小偷是B，可知A说真话、B说谎话、C说谎话、D说真话，与已知的“三个说真话一个说谎话”不符，假设不成立；4.2用穷举法设计程序假设小偷是C，可知A说真话、B说真话、C说谎话、D说真话，与已知的“三个说真话一个说谎话”符合，假设成立；假设小偷是D，可知A说真话、B说谎话、C说真话、D说慌话，与已知的“三个说真话一个说谎话”不符，假设不成立。4.2用穷举法设计程序2.设计算法开始thief=Asc("A")Int(Chr(thief)<>"A")+Int(Chr(thief)="C")+Int(Chr(thief)="D")+Int(Chr(thief)<>"D")=-3thief<=Asc("D")thief增加1输出Chr(thief)结束是否是否4.2用穷举法设计程序3.编写程序4.2用穷举法设计程序3.编写程序PrivateSubForm_Click()Forthief=Asc("A")ToAsc("D")IfInt(Chr(thief)<>"A")+Int(Chr(thief)="C")+Int(Chr(thief)="D")+Int(Chr(thief)<>"D")=-3ThenPrint"TheThiefis:"PrintChr(thief)EndIfNextthiefEndSub4.调试运行5.检测结果4.2用穷举法设计程序★穷举法的基本思路使用穷举法时，要恰当地设计变量，并且决定用哪些变量作为搜索的主线，接着列举一切与命题相关的情况，然后根据问题设定的条件，逐个加以检查，找到满足条件的解答。穷举方案都是唯一的吗？★思考请总结穷举法求解问题的基本思路？★思考与讨论4.2用穷举法设计程序

现代福尔摩斯侦探之密码破译：案发现场有一个密码箱，主人失踪了，为了追寻密码箱主人的下落，现需找出密码打开密码箱。已知密码箱主人是8月1日出生，他太太的生日是9月1日，密码箱主人的太太不大记得密码是多少，但她清晰地记得她先生曾告诉她密码是一个5位数，并且同时是81和91的倍数，她还记得密码的中间一位（百位数）是1。您能帮她找回这个密码吗？借助程序设计呢？★问题描述4.2用穷举法设计程序数学上如何求解这个问题？提问：（1）建立数学模型（用数学语言描述问题）——分析：1.分析问题

求出一个5位数，它的百位是1，而且它能同时被81和91整除。（2）确定解决方案——

因为这个密码有4位数字是未知的，把各位数字都对所有可能性演变一次（最高位是1-9，其余各位都是0~9），就可以把可能的情况穷举完。再把各位数字合成一个5位数，判断是否同时被81和91整除就可以了。★问题解决4.2用穷举法设计程序2.设计算法开始a5=0d=a1*10000+a2*1000+1*100+a4*10+a5(dMod81=0)And(dMod91=0)a5增加1a5<=9输出d结束是否是否a4=0a2=0a1=1a4增加1a4<=9是a2<=9否a2增加1是否a1<=9否a1增加1是4.2用穷举法设计程序3.编写程序4.2用穷举法设计程序3.编写程序PrivateSubCommand1_Click()Fora1=1To9Fora2=0To9Fora4=0To9Fora5=0To9

d=a1*10000+a2*1000+1*100+a4*10+a5If(dMod81=0)And(dMod91=0)ThenPrintdNexta5,a4,a2,a1EndSub4.调试运行5.检测结果4.2用穷举法设计程序数学上如何求解这个问题？提问：（1）建立数学模型（用数学语言描述问题）——分析：1.分析问题

求出一个5位数，它的百位是1，而且它能同时被81和91整除。（2）确定解决方案——5位数字的范围是10000-99999，在此范围内穷举，并判断5位数是否同时被81和91整除，再对每一个数分解出它的百位数字检验它是否1就可以了。★问题解决4.2用穷举法设计程序2.设计算法开始a\100Mod10=1a<=99999a增加1输出a结束是否是否a=10000(aMod81=0)And(aMod91=0)

否是4.2用穷举法设计程序3.编写程序4.2用穷举法设计程序3.编写程序PrivateSubCommand1_Click()Fora=10000To99999If(aMod81=0)And(aMod91=0)ThenIfa\100Mod10=1ThenPrintaEndIfEndIfNextaEndSub4.调试运行5.检测结果4.2用穷举法设计程序★穷举法的改进思路

“与命题相关的情况”所包含的范围可能很广，如果不加以限制可能会白白耗费计算机的运行时间。所以在设计穷举的过程时，应当明确或建立适当的数学模型，构造穷举的框架，然后通过逐步求精的过程，改善算法，使穷举过程变得恰当。前面的搜索方案执行效率如何？可以改进吗？（改进是以效率的高低而不是按程序的长短来衡量）★思考4.2用穷举法设计程序数学上如何求解这个问题？提问：（1）建立数学模型（用数学语言描述问题）——分析：1.分析问题

求出一个5位数，它的百位是1，而且它能同时被81和91整除。（2）确定解决方案——

有解的范围只限于同时是81和91的倍数。81和91的最小公倍数是81*91，所以我们只在5位数中就81*91的倍数进行穷举，然后分离出它的百位数字判断是否是1就能得到答案。★问题解决4.2用穷举法设计程序2.设计算法开始p=10000\(81*91)+1a\100Mod10=1a<=99999a增加81*91输出a结束是否是否a=p*(81*91)4.2用穷举法设计程序3.编写程序4.2用穷举法设计程序3.编写程序PrivateSubCommand1_Click()p=10000\(81*91)+1Fora=p*(81*91)To99999Step(81*91)Ifa\100Mod10=1ThenPrintaEndIfNextaEndSub4.调试运行5.检测结果4.2用穷举法设计程序★穷举法中穷举方案的选择对于许多问题，解决问题的算法往往不只一种，这时我们就得注意加以选择，找一种更好的算法。评价一个算法的好坏，许多时候效率是很重要的。当然在考虑效率的同时有时也要重视程序的易读性。