3.2　用穷举法解决问题　课件.pptx

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

1、用穷举法解决问题宜都一中 曹丹丹 “五一”小长假，我带着孩子到宜昌周边自驾游，没想到拿出搁置了很久的三位数字密码的行李箱，发现自己竟然忘记了开锁密码，只记得第一位密码是7，后面两位数字已经不记得了，我该怎么找回我的密码？新课引入穷举法也叫枚举法、列举也叫枚举法、列举法法将将求解对象一一列举求解对象一一列举出来，然后逐一加以分析、处理，并出来，然后逐一加以分析、处理，并验证结果验证结果是否满足是否满足给定的条件，穷举完所有对象，问题将最终得以给定的条件，穷举完所有对象，问题将最终得以解决解决。00010203040506070809101112131415161718199199用穷举法解决问题

2、宜都一中 曹丹丹问题求解900900次次编程编程数学中有一组有趣的数字，它满足以数学中有一组有趣的数字，它满足以下两个条下两个条件：件：p是一个三位正整数 （100999100999）p这个三位数刚好等于各个位上的数字立方和 （X=a3+b3+c3X=a3+b3+c3）p例如：153 153=13+53+33153=13+53+33水水仙仙花花数数算法设计思路一l三位数为三位数为X X。l三位数范围：三位数范围：100-999100-999。l约束条件：该三位数的各约束条件：该三位数的各位数位数a a、b b、c c的立方和正的立方和正好是等于该数本身好是等于该数本身 X=a3+b3+c3X=

3、a3+b3+c3 已知已知三位三位数数X X，如何分离出百位、，如何分离出百位、十位、个位上的十位、个位上的数字数字？a=X a=X 100100b b=(X a*100 )=(X a*100 )1010c=(X a*100 c=(X a*100 b*10)b*10)1 1算法设计思路一l三位数为三位数为X X。l三位数范围：三位数范围：100-999100-999。l约束条件：该三位数的各约束条件：该三位数的各位数位数a a、b b、c c的立方和正的立方和正好是等于该数本身好是等于该数本身 X=a3+b3+c3X=a3+b3+c3算术运算符含义实例结果指数2101024/除153/1001

4、.53整除1531001Mod求余153 Mod 103a=Y100b=Y 10 Mod 10c=Y Mod 10算法设计思路一l三位数为三位数为X X。l三位数范围：三位数范围：100-999100-999。l约束条件：该三位数的各约束条件：该三位数的各位数位数a a、b b、c c的立方和正的立方和正好是等于该数本身好是等于该数本身 X=a3+b3+c3X=a3+b3+c3l程序结构选择：一重程序结构选择：一重循环循环程序PrivateSubCommand1_Click()DimXAsIntegerDima,b,cAsIntegerForX=Toa=b=c=IfX=ThenPrintX&是

5、水仙花数是水仙花数EndIfNextXEndSub100999X 100(X a*100 b*10)1a3+b3+c3(X a*100 )10算法设计思路一思路二l三位数为三位数为X X。l三位数范围：三位数范围：100-999100-999。l约束条件：该三位数的各约束条件：该三位数的各位数位数a a、b b、c c的立方和正的立方和正好是等于该数本身好是等于该数本身 X=a3+b3+c3X=a3+b3+c3l程序结构选择：一重程序结构选择：一重循环循环l三位数为三位数为abcabc。l该数的百位范围该数的百位范围1-91-9，十，十位范围位范围0-90-9，个位范围，个位范围0-90-9l

6、约束条件：该数的个、十、百约束条件：该数的个、十、百位数的立方和正好是等于该数位数的立方和正好是等于该数本身本身 a*100+b*10+c=a3+b3+c3 a*100+b*10+c=a3+b3+c3l程序结构选择：三重循环程序结构选择：三重循环程序PrivateSubCommand1_Click()DimXAsIntegerDima,b,cAsIntegerFora=ToForb=ToForc=ToX=IfX=ThenPrintX&是水仙花数是水仙花数EndIfNextcNextbNextaEndSub190909a*100+b*10+ca*100+b*10+ca3+b3+c3a3+b3+c

7、3程序设计思路二l三位数为三位数为abcabc。l该数的百位范围该数的百位范围1-91-9，十，十位范围位范围0-90-9，个位范围，个位范围0-90-9l约束条件：该数的个、十、百约束条件：该数的个、十、百位数的立方和正好是等于该数位数的立方和正好是等于该数本身本身 a*100+b*10+c=a3+b3+c3 a*100+b*10+c=a3+b3+c3l程序结构选择：三重循环程序结构选择：三重循环思路二PrivateSubCommand1_Click()DimXAsIntegerDima,b,cAsIntegerFora=ToForb=ToForc=ToX=IfX=ThenPrintX&是水

8、仙花数是水仙花数EndIfNextcNextbNextaEndSub190909a*100+b*10+ca*100+b*10+ca3+b3+c3a3+b3+c3程序设计思路一PrivateSubCommand1_Click()DimXAsIntegerDima,b,cAsIntegerForX=Toa=b=c=IfX=ThenPrintX&是水仙花数是水仙花数EndIfNextXEndSub100999X 100(X a*100 b*10)1X=a3+b3+c3(X a*100 )10穷举对象穷举对象对象范围对象范围验证条件验证条件决定循环结构决定循环结构及循环层数及循环层数决定循环对象决定循

9、环对象的初值和终值的初值和终值决定循环体决定循环体内条件语句内条件语句巩固深化 问题：中国古代数学家张丘建在张丘建算经中提出一个“百钱买百鸡”的问题。“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡。问鸡翁、母、雏各几何？”解：设解：设公鸡数为公鸡数为x x，母鸡数为，母鸡数为y y，小鸡数为小鸡数为z zx+y+z=100 x+y+z=100 5*x+3*y+z/3=100 5*x+3*y+z/3=100X+y+z=1005*x+3*y+z/3=1000 X 1000 X 100；0 Y 1000 Y 100；0 Z 1000 Z 100公鸡数为公鸡数为x x，母鸡数为，母鸡数为

10、y y，小鸡数为，小鸡数为z z穷举对象穷举对象对象范围对象范围验证条件验证条件PrivateSubForm_Click()Dimx,y,zAsIntegerPrint公鸡公鸡,母鸡母鸡,小鸡小鸡Forx=1To100Fory=1To100Forz=1To100Ifx+y+z=100and5*x+3*y+z/3=100ThenPrintx,y,zEndifNextz NextyNextxEndSubPrivateSubForm_Click()Dimx,y,zAsIntegerPrint公鸡公鸡,母鸡母鸡,小鸡小鸡Forx=1To公鸡五钱一只Fory=1To母鸡三钱一只z=小鸡的数量 If5*x

11、+3*y+Z/3=100ThenPrintx,y,zEndif nextynextxEndSub2033100-x-y程序一：程序一：程序二：程序二：穷举算法穷举算法优化：优化：1 1、尽量、尽量减少穷举变减少穷举变量的个数。量的个数。2 2、精确、精确穷举范围。穷举范围。巩固深化课堂小结用穷举法解决问题的关键用穷举法解决问题的关键：确定确定需要穷举需要穷举的所有求解对象的所有求解对象 找出求解对象找出求解对象的穷举范围的穷举范围分析出满足问题所需的条件分析出满足问题所需的条件 算法优化：算法优化：尽量减少穷举变量的个数。尽量减少穷举变量的个数。根据题目条件，精确穷举范围。根据题目条件，精确穷举范围。因为信因为信息技术可能带息技术可能带来的不安全因素，特别是来的不安全因素，特别是穷举法在破解密码方面的穷举法在破解密码方面的应用应用。所以需要我们自。所以需要我们自觉觉遵守网络道德与法规，树遵守网络道德与法规，树立信息安全意识。立信息安全意识。