枚举算法_举例

1、课前思考 有一个三位数x，百位是a，十位是b，个位是c，x=100*a+10*b+c,利用适当的VB表达式求出 a= b= c=X mod 10 x10 mod 10 x100 小明是一个数学迷，昨天他约了几个同学小明是一个数学迷，昨天他约了几个同学一起到会议室里举行一个联谊会，可是粗心的一起到会议室里举行一个联谊会，可是粗心的小明去总务处拿了一串钥匙回来准备开门时，小明去总务处拿了一串钥匙回来准备开门时，却忘记了到底哪一把才是会议室的钥匙。却忘记了到底哪一把才是会议室的钥匙。假设假设这串钥匙一共有这串钥匙一共有1010把。把。怎样才能找到正确的钥匙来开门怎样才能找到正确的钥匙来开门 找钥匙的

2、过程2.拿出第二把钥匙，拿出第二把钥匙， 试验第二把钥匙能否开门；试验第二把钥匙能否开门；1.拿出第一把钥匙，拿出第一把钥匙， 试验第一把钥匙能否开门；试验第一把钥匙能否开门；3.拿出第三把钥匙，拿出第三把钥匙， 试验第三把钥匙能否开门；试验第三把钥匙能否开门；10.拿出第十把钥匙，拿出第十把钥匙， 试验第十把钥匙能否开门。试验第十把钥匙能否开门。列举列举检验检验枚举法枚举法枚举算法枚举算法就是按照问题本身的性质，就是按照问题本身的性质，一一列举一一列举出该问题所有可能的解，并根据问题的条件对各出该问题所有可能的解，并根据问题的条件对各解进行解进行逐个检验逐个检验，从中挑选出符合条件的解，舍，

3、从中挑选出符合条件的解，舍弃不符合条件的解。弃不符合条件的解。在联欢会上，小明提议大家来玩数7的游戏。游戏规则游戏规则：从1开始数起，每个人数一个数， 凡是遇到7的倍数就要喊“过”, 这样一直数到100为止。帮小明找出帮小明找出1100所有要喊所有要喊“过过”的数的数列举列举检验检验用变量用变量i表示要列举的自然数。表示要列举的自然数。列举范围：列举范围：1100检验条件：检验条件：i能否被能否被7整除。整除。在列举过程中要既不遗漏，又不重复。开始开始结束结束NNYYi=100i mod 7=0i=i+1i=1输出输出i列举范围：列举范围：1100检验条件：检验条件：i能否被能否被7整除。整除

4、。用变量用变量i表示要列举的自然数。表示要列举的自然数。开始开始结束结束NNYYi=100i mod 7=0i=i+1i=1输出输出i（循环结构）（循环结构）（分支结构）（分支结构）循环中嵌套分支i=1Do while i=100 if i mod 7=0 then print i end if i=i+1loop开始开始结束结束NNYYi=100i mod 7=0i=i+1i=1输出输出i枚举算法的设计步骤 确定列举范围 明确检验条件 确定循环控制方式和列举方式枚举算法只适用于可能解的个数不太多的情况。 一张单据上有一个一张单据上有一个5 5位数的编号，万位数是位数的编号，万位数是1 1，千

5、位，千位数是数是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位数。位数。开始开始i=0i10(n mod 7=0) or(n mod 11=0)输出输出ni=i

6、+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生活中的枚举算法实例生活中的枚举算法实例 找钥匙找钥匙 警察审案警察审案 挑烂苹果挑烂苹果1.枚举算法的概念枚举算法的概念2.枚举算法的结构特征枚举算法的结构特征4.枚举算法的应用枚举算法的应用3.枚举算法的设计步骤枚举算法的设计步骤 一张单据上有一个一张单据上有一个5 5位数的编号，千位数是位数的编号，千位数是1 1，百位，百位数是数是7 7，个位数是，个位数是

7、8 8，万位数和十位数已经模糊不清，只，万位数和十位数已经模糊不清，只知道该知道该5 5位数是位数是7 7或或1111的倍数，找出所有满足这些条件的的倍数，找出所有满足这些条件的5 5位数并输出。位数并输出。 NO. ? 17 ? 8 该题要列举的对象有两个，分别是万位数和个位数。用循环的嵌套。找出找出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鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱鸡翁一，值钱五，鸡母一，值钱三

8、，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？一，百钱买百鸡，问翁、母、雏各几何？一一列举：初值：终值：递增值： a 0 20 1检验：鸡翁鸡翁 鸡母鸡母 鸡雏鸡雏 b 0 33 1 c 0 100 3a*5+b*3+c/3=100开始TFa=0a=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+1i mod 3=0TF输出 ii mod 3=0TF输出 i检验检验:枚举时注意：不遗漏，不重复，且可能的解有限。N NY Y输出输出X Xx100 x100Y YN NStartStartEndEnd找出所有找出所有100,1000100,1000之间之间3535的倍数的数字。的倍数的数字。练练 习习范围范围: :条件：条件：初初 值：值：100100100 100 1000 1000终终 值：值：10001000步步 长：长：1 1x mod 35 = 0 用用1010元和元和5050元两种纸币组成元两种纸币组成240240元，元，共有几种组合方式？试用枚举算法列共有几种组合方式？试用枚举算法列出所有不同的取法。出所有不同的取法。练一练1