枚举算法_举例.ppt

《枚举算法_举例.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、枚举算法课前思考有一个三位数x，百位是a，十位是b，个位是c，x=100*a+10*b+c,利用适当的VB表达式求出a=b=c=Xmod10x10mod10x100小明是一个数学迷，昨天他约了几个同学一起到会议室里举行一个联谊会，可是粗心的小明去总务处拿了一串钥匙回来准备开门时，却忘记了到底哪一把才是会议室的钥匙。假设这串钥匙一共有10把。找钥匙怎样才能找到正确的钥匙来开门问题：？找钥匙的过程2.拿出第二把钥匙，试验第二把钥匙能否开门；1.拿出第一把钥匙，试验第一把钥匙能否开门；3.拿出第三把钥匙，试验第三把钥匙能

2、否开门；10.拿出第十把钥匙，试验第十把钥匙能否开门。······列举检验枚举法枚举算法的概念枚举算法就是按照问题本身的性质，一一列举出该问题所有可能的解，并根据问题的条件对各解进行逐个检验，从中挑选出符合条件的解，舍弃不符合条件的解。一一列举；逐个检验数7游戏在联欢会上，小明提议大家来玩数7的游戏。游戏规则：从1开始数起，每个人数一个数，凡是遇到7的倍数就要喊“过”,这样一直数到100为止。任务：帮小明找出1——100所有要喊“过”的数!数7游戏分析：列举检验用变量i表示要列举的自然数。列举范围：1——100检验条件

3、：i能否被7整除。在列举过程中要既不遗漏，又不重复。注意：数7游戏开始结束NNYYi<=100imod7=0i=i+1i=1输出i列举范围：1——100检验条件：i能否被7整除。用变量i表示要列举的自然数。数7游戏开始结束NNYYi<=100imod7=0i=i+1i=1输出i一一列举逐个检验（循环结构）（分支结构）循环中嵌套分支数7游戏程序代码：i=1Dowhilei<=100ifimod7=0thenprintiendifi=i+1loop开始结束NNYYi<=100imod7=0i=i+1i=1输出i枚举算法的设

4、计步骤确定列举范围明确检验条件确定循环控制方式和列举方式枚举算法只适用于可能解的个数不太多的情况。注意：一张单据上有一个5位数的编号，万位数是1，千位数是4，百位数是7，个位数是8，十位数已经模糊不清，只知道该5位数是7或11的倍数，找出所有满足这些条件的5位数并输出。数据还原NO.147?8列举范围：0——9检验条件：n能被5或者11整除。即：(nmod7=0)or(nmod11=0)分析：用变量i表示十位上的数；变量n表示这个5位数。数据还原开始i=0i<10(nmod7=0)or(nmod11=0)输出ni=i+

5、1结束NNYY程序代码：i=0Dowhilei<10n=14708+i*10ifnmod7=0ornmod11=0thenPrintnendifi=i+1Loopn=14708+i*10生活中的枚举算法实例找钥匙警察审案挑烂苹果······小结：1.枚举算法的概念2.枚举算法的结构特征4.枚举算法的应用3.枚举算法的设计步骤一一列举；逐个检验循环结构中嵌套分支结构确定列举范围；明确检验条件适用于解的个数不太多思考：一张单据上有一个5位数的编号，千位数是1，百位数是7，个位数是8，万位数和十位数已经模糊不清，只知道该5位

6、数是7或11的倍数，找出所有满足这些条件的5位数并输出。NO.?17?8该题要列举的对象有两个，分别是万位数和个位数。用循环的嵌套。提示：找出1-1000中所有能被7和11整除的数。c开始结束TFi=1i<=1000i=i+1TF输出iimod7=0andimod11=0imod77=0imod3=0百鸡百钱问题。鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？一一列举：初值：终值：递增值：a0201检验：鸡翁鸡母鸡雏b0331c01003a*5+b*3+c/3=100开始TFa=0a<

7、=20结束TFb=0b<=33TFc=0c<=100TFc=c+3b=b+1a=a+1a*5+b*3+c/3=100输出a、b、c求1-1000中，能被3整除的数开始结束TFi=1i<=1000i=i+1imod3=0TF输出iimod3=0TF输出i检验检验:枚举时注意：不遗漏，不重复，且可能的解有限。NY输出Xx←100YNStartEnd找出所有[100,1000]之间35的倍数的数字。练习范围:条件：初值：1001001000终值：1000步长：1xmod35=0用10元和50元两种纸币组成240元，共有几种

8、组合方式？试用枚举算法列出所有不同的取法。练一练10x+50y=240输出x,yYx←1YStartNEndy←1YNN用10元和50元两种纸币组成240元，共有几种组合方式？试用枚举算法列出所有不同的取法。练一练