用穷举法解决问题.ppt

《用穷举法解决问题.ppt》由会员分享，可在线阅读，更多相关《用穷举法解决问题.ppt（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、阅读下面程序，分析执行过程，说出程序功能For I=100 to 999A=int(I/100)B=int(I/10)mod 10C=I mod 10If a3+b3+c3=I then print INext Iiabc100 100101 101153 153999 999求出100到999之间的所有水仙花数3.2 用穷举法解决问题一、什么是穷举法穷举法又称枚举法、列举法，它将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有对象，问题将最终得以解决。方法一：For I=100 to 999A=int(I/100)B=int(I/10)mod 10C=I

2、 mod 10If a3+b3+c3=I then print INext I方法二：For a=1 to 9 for b=0 to 9 for c=0 to 9 if a3+b3+c3=a*100+b*10+c then print a*100+b*10+c endif next c next bnext a二、用穷举法解决问题的步骤1、确定问题解可能搜索的范围：用循环或嵌套来实现）2、写出符合问题解的条件：用if语句实现3、尽可能地缩小搜索的范围，减少程序运行时间，提高程序的执行效率。例：公元前5世纪，我国数学家张丘建在算经一书中提出了一个“百钱买百鸡问题”。问题如下：鸡翁一值钱5，鸡母一

3、值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、鸡母和鸡雏各几何？分析：穷举的对象：穷举的范围：判断式：鸡翁、鸡母、鸡雏0 X 1000 Y 1000 Z 100 x+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：生活中的问题某同学用自己的QQ号登录，可他记不清密码了，你能帮他找回密码吗？他的密码是一个5位数，678，其中百位和十位上的数字他不记得了，但他还记得该数能够被78整除，也能被67整除。你能帮

4、他设计一个算法求出该密码吗？(1)判断下列两题能否用穷举算法解决，为什么？在一个直角三角形中，三条边a、b、c的长度都为整数，且一条直角边a的长度已确定，斜边c的长度不能超过某数I，找出满足条件的所有直角三角形。使用一根长度为L厘米的铁丝，制作一个面积为S的矩形框，要求，计算出满足这种条件的矩形的高h和宽w。孙子算经中有许多有趣的数学题，“鸡兔同笼”问题就是一个典型的例子。原题是：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？”四、穷举算法的优点与缺点：优点：算法简单缺点：运行时所花费的时间长。三、穷举算法适用的条件：有明显的穷举范围且求解对象应该是有限的；可以按某种规则列举对象；有穷举规则；一时找不出解决问题的更好途径时。