多重循环(穷举算法)概要.ppt

思考： 有一个小游戏被加密了，我们知道它的密码只有一位，你如何去破译该密码？ 用 0、1、2、3、4、5、6、7、8、9 逐一去试 如果要破译两位自然数的密码，你如何去手动破译？ 用 00、01、02……09； 10、11、12……19； … 90、91、92……99； 依次类推直至找出正确的密码。 一、什么是穷举算法 穷举算法就是把所有可能的情况一一列举，带入实际，一个个检验是否是符合。如果有符合条件的数据就把它输出。利用了计算机的高速，可以在很短的时间内有哪些信誉好的足球投注网站完毕。 二、穷举算法应用举例：? 情景： 某同学登录自己的QQ号时发现由于较长时间没有使用已经记不清了 ，你能帮他设计程序找回密码吗，他的密码是5位数，67xx8，其中百位数和十位数字他不记得了，但他记得该密码能被67和78整除。 分析问题： 6 7 x x 8 a b 0~9 0~9 设计算法： ??? 这个问题适合用穷举法进行有哪些信誉好的足球投注网站 分别用a、b表示这2位求知数字。 穷举范围： a:0~9 b:0~9 符合条件：首先要组成5位数x，然后判断x能否同时被78和67整除，即可得到结果。 ??? 流程图： a=9 b=9 a=0 退出循环 Y b=0 Y b←b+1 a←a+1 输出X N x←67000+a*100+b*10+8 x能否同时被78和67整除 ？ Y N N 程序如下： Private Sub Command1_Click() End Sub 程序执行过程 For a=0 to 9 Next a For b=0 to 9 Next b X=60000+7000+a*100+b*10+8 if (x mod 67=0) and (x mod 78=0) then print x end if 总结 利用穷举法首先要确定穷举范围，然后判断是否满足条件 提出问题思考： 存折或信用卡在柜员机上取钱时，为什么系统要限 制输入密码的次数？ 注：不要把密码设置成123456，要把密码设置成大小写、数字，要避免使用自己名字的拼音、生日数字、电话号码等 ? 三、拓展练习1： 我国古代数学家张丘建在《算经》中出了一道“百钱百鸡”题，题意是：公鸡五元一只，母鸡三元一只，小鸡一元三只。用100元钱买100只鸡，问公、母、小鸡各买多少只？编程输出所有满足条件的结果 分析： 设公鸡x只，母鸡y只，小鸡z只，可以列出方程： x+y+z=100 　 ① 5x+3y+z/3=100 ② 由于无法直接用代数方法解，可以用“穷举法”来解此问题。 穷举范围: X: 0~20 Y: 0~33 z:0~100 符合条件: 共有100只共花100元 即 ：x+y+z=100 5*x+3*y+z/3=100 四、拓展练习2： 有一道写于纸上的数学题被雨水淋湿，其中有两个数字已模糊不清（3□＋42）×6＝47□ 你能设计找出这两个数吗？ 分析： （3□＋42）×6＝47□ a b 0~9 0~9 穷举范围: a:0~9 b:0~9 符合条件: 让等式成立 即 ：3□＋42）×6＝47□ 课后小结 利用穷举法解决问题的方法，要注意以下几个方面： 1、穷举算法是一种比较“笨”的方法，它通过列举所 有情况逐一判断来得到结果。 2、明确穷举的范围 3、明确选出的数据必须符合什么条件 拓展练习3 书P107/2(马克思数学问题） 马克思手稿中的数学题：有30个人