《山东省日照青山学校教科版高中信息技术选修一课件：3.2用穷举法解决问题 》由会员分享，可在线阅读，更多相关《山东省日照青山学校教科版高中信息技术选修一课件：3.2用穷举法解决问题 （17页珍藏版）》请在金锄头文库上搜索。
1、3.2 用穷举法解决问题,算法与程序设计,怎样找出所有开这把锁的钥匙？有没有同学愿意上来找找看。,在找钥匙的过程中，你运用的是什么算法？,请大家阅读课本P45最后两段，用自己的话说说什么是穷举法？,3.2 用穷举法解决问题,1什么是穷举法？ 也叫枚举法、列举法将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有对象，问题将最终得以解决。,任务一：水仙花数,水仙花数是指一个三位数，它的各位数的立方和正好等于该数本身。如：153=13+53+33。请设计算法求解“水仙花数问题”。,水仙花数算法：,For 某整数=100 to 999 If 该数百位数字的立方+该
2、数十位数字的立方+该数个位数字的立方=该数 Then print 该数 End if Next 某整数,穷举范围,满足条件,任务二：编写求三位水仙花数程序,a=x100 b=(x-a*100)10 c=x-a*100-b*10,水仙花数代码：,Dim x, b, s, g As IntegerFor x = 100 To 999 Step 1a = i 100b = (i - a * 100) 10c= i - a * 100 - b * 10 If a3 + b3 + c3 = x Then Print x End If Next x,求解对象应该是有限的； 有穷举规则 一时找不出解决问题的
3、更好途径时；,穷举法的适用条件：,穷举法解决问题步骤：,通常可以从两个方面进行分析： 确定范围：问题所涉及的情况有哪些，情况的种数可不可以确定。 验证条件：分析出来的这些情,任务三：百钱买百鸡”,相传我国南北朝时，京城有个卖鸡的张姓老汉，他有一个儿子非常聪明，尤其擅长算术，到十二三岁时已是远近闻名的“小神童”了。当朝宰相听说后想试探个究竟，于是派仆人到张老汉的店里打听鸡的价钱，张老汉告知“公鸡五文钱一只，母鸡三文一只，小鸡一文三只”。于是，仆人给他一百文钱，要求公鸡、母鸡、小鸡都要，数量不多不少正好一百只，命他次日送到府上。这可难为了张老汉，他怎么凑也凑不够这个数，只好问儿子。“小神童”不慌不
4、忙，掐指一算就给出了答案，第二天照数送到宰相府。宰相见难不倒“小神童”，又让仆人给张老汉一百文钱，要求再买一百只鸡，搭配方法不能和上次一样。结果“小神童”又很快给出了答案，宰相暗暗称奇，想最后再试一次，谁知还是没有难倒“小神童”。这个故事就是我国古代数学名著张邱建算经里的百鸡百钱问题。请用穷举法求解所有的组合方法。,百钱买百鸡,确定范围 验证条件：,百钱百鸡代码： Dim x, y, z As Integer For x = 1 To 20 For y = 1 To 33For z = 1 To 100 If (5 * x + 3 * y + 1 / 3 * z = 100) And (x + y + z = 100) Then Print x, y, z End If Next z Next y Next x End Sub,我们使用信用卡在柜员机上取钱时，为什么系统要限制输入密码的次数？,小结,1、穷举法分析：确定范围验证条件2、自觉遵守网络道德与法规,Thanks,
