用穷举法解决问题.ppt

《用穷举法解决问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、阅读下面程序，分析执行过程，说出程序功能ForI=100to999A=int(I/100)B=int(I/10)mod10C=Imod10Ifa^3+b^3+c^3=IthenprintINextIiabc100100101101153153999999求出100到999之间的所有水仙花数3.2用穷举法解决问题一、什么是穷举法穷举法又称枚举法、列举法，它将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有对象，问题将最终得以解决。方法一：ForI=100to999A=

2、int(I/100)B=int(I/10)mod10C=Imod10Ifa^3+b^3+c^3=IthenprintINextI方法二：Fora=1to9forb=0to9forc=0to9ifa^3+b^3+c^3=a*100+b*10+cthenprinta*100+b*10+cendifnextcnextbnexta二、用穷举法解决问题的步骤1、确定问题解可能搜索的范围：用循环或嵌套来实现）2、写出符合问题解的条件：用if语句实现3、尽可能地缩小搜索的范围，减少程序运行时间，提高程序的执行效率。例

3、：公元前5世纪，我国数学家张丘建在《算经》一书中提出了一个“百钱买百鸡问题”。问题如下：鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、鸡母和鸡雏各几何？分析：穷举的对象：穷举的范围：判断式：鸡翁、鸡母、鸡雏0≤X≤1000≤Y≤1000≤Z≤100x+y+z=100且5*x+3*y+z/3=100思考：如何提高算法的效率？1、减少循环的次数，通过缩小穷举范围0≤a≤100/50≤b≤100/30≤c≤1002、减少循环嵌套的层数0≤a≤100/50≤b≤100/3c=100–a–b例3：

4、生活中的问题某同学用自己的QQ号登录，可他记不清密码了，你能帮他找回密码吗？他的密码是一个5位数，67□□8，其中百位和十位上的数字他不记得了，但他还记得该数能够被78整除，也能被67整除。你能帮他设计一个算法求出该密码吗？(1)判断下列两题能否用穷举算法解决，为什么？①在一个直角三角形中，三条边a、b、c的长度都为整数，且一条直角边a的长度已确定，斜边c的长度不能超过某数I，找出满足条件的所有直角三角形。②使用一根长度为L厘米的铁丝，制作一个面积为S的矩形框，要求，计算出满足这种条件的矩形的高h和宽w

5、。③《孙子算经》中有许多有趣的数学题，“鸡兔同笼”问题就是一个典型的例子。原题是：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？”四、穷举算法的优点与缺点：优点：算法简单缺点：运行时所花费的时间长。三、穷举算法适用的条件：有明显的穷举范围且求解对象应该是有限的；可以按某种规则列举对象；有穷举规则；一时找不出解决问题的更好途径时。