枚举算法-举例课件.ppt

1、-1-2 小明是一个数学迷，昨天他约了几个同学一起到会议室里举行一个联谊会，可是粗心的小明去总务处拿了一串钥匙回来准备开门时，却忘记了到底哪一把才是会议室的钥匙。假设这串钥匙一共有1010把。怎样才能找到正确的钥匙来开门-3找钥匙的过程2.拿出第二把钥匙，试验第二把钥匙能否开门；1.拿出第一把钥匙，试验第一把钥匙能否开门；3.拿出第三把钥匙，试验第三把钥匙能否开门；10.拿出第十把钥匙，试验第十把钥匙能否开门。列举检验枚举法-4枚举算法就是按照问题本身的性质，一一列举出该问题所有可能的解，并根据问题的条件对各解进行逐个检验，从中挑选出符合条件的解，舍弃不符合条件的解。-5在联欢会上，小明提议大

2、家来玩数7的游戏。游戏规则：从1开始数起，每个人数一个数，凡是遇到7的倍数就要喊“过”,这样一直数到100为止。帮小明找出1100所有要喊“过”的数-6列举检验用变量i表示要列举的自然数。列举范围：1100检验条件：i能否被7整除。在列举过程中要既不遗漏，又不重复。-7开始结束NNYYi=100i mod 7=0i=i+1i=1输出i列举范围：1100检验条件：i能否被7整除。用变量i表示要列举的自然数。-8开始结束NNYYi=100i mod 7=0i=i+1i=1输出i（循环结构）（分支结构）循环中嵌套分支-9i=1Do while i=100 if i mod 7=0 then prin

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

4、-12开始i=0i10(n mod 7=0)or(n mod 11=0)输出ni=i+1结束NNYY程序代码：i=0Do while i10 n=14708+i*10 if n mod 7=0 or n mod 11=0 then Print n end if i=i+1Loopn=14708+i*10-13生活中的枚举算法实例 找钥匙 警察审案 挑烂苹果-141.枚举算法的概念2.枚举算法的结构特征4.枚举算法的应用3.枚举算法的设计步骤-15 一张单据上有一个5 5位数的编号，千位数是1 1，百位数是7 7，个位数是8 8，万位数和十位数已经模糊不清，只知道该5 5位数是7 7或1111的

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

6、33TFc=0c=100TFc=c+3b=b+1a=a+1a*5+b*3+c/3=100输出 a、b、c-19求1-1000中，能被3整除的数开始结束TFi=1i=1000i=i+1i mod 3=0TF输出 ii mod 3=0TF输出 i检验检验:枚举时注意：不遗漏，不重复，且可能的解有限。-20N NY Y输出X Xx100 x100Y YN NStartStartEndEnd找出所有100,1000100,1000之间3535的倍数的数字。练 习范围:条件：初 值：100100100 100 1000 1000终 值：10001000步 长：1 1x mod 35=0-21 用1010元和5050元两种纸币组成240240元，共有几种组合方式？试用枚举算法列出所有不同的取法。练一练-2210 x+50y=240输出x,yYx1x1YStartStartNEndEndy 1YNN 用1010元和5050元两种纸币组成240240元，共有几种组合方式？试用枚举算法列出所有不同的取法。练一练