枚举算法 举例.pptVIP

小明是一个数学迷，昨天他约了几个同学一起到会议室里举行一个联谊会，可是粗心的小明去总务处拿了一串钥匙回来准备开门时，却忘记了到底哪一把才是会议室的钥匙。假设这串钥匙一共有10把。 怎样才能找到正确的钥匙来开门 找钥匙的过程 2.拿出第二把钥匙， 试验第二把钥匙能否开门； 1.拿出第一把钥匙， 试验第一把钥匙能否开门； 3.拿出第三把钥匙， 试验第三把钥匙能否开门； 10.拿出第十把钥匙， 试验第十把钥匙能否开门。 ······ 列举 检验 枚举法 枚举算法就是按照问题本身的性质，一一列举 出该问题所有可能的解，并根据问题的条件对各 解进行逐个检验，从中挑选出符合条件的解，舍 弃不符合条件的解。 数7游戏 在联欢会上，小明提议大家来玩数7的游戏。 游戏规则：从1开始数起，每个人数一个数， 凡是遇到7的倍数就要喊“过”, 这样一直数到100为止。 帮小明找出1——100所有要喊“过”的数 数7游戏 列举 检验 用变量i表示要列举的自然数。 列举范围： 1——100 检验条件： i能否被7整除。 在列举过程中要既不遗漏，又不重复。 数7游戏 开始 结束 N N Y Y i=100 i mod 7=0 i=i+1 i=1 输出i 列举范围： 1——100 检验条件： i能否被7整除。 用变量i表示要列举的自然数。 数7游戏 开始 结束 N N Y Y i=100 i mod 7=0 i=i+1 i=1 输出i （循环结构） （分支结构） 循环中嵌套分支 数7游戏 i=1 Do while i=100 if i mod 7=0 then print i end if i=i+1 loop 开始 结束 N N Y Y i=100 i mod 7=0 i=i+1 i=1 输出i 枚举算法的设计步骤 确定列举范围 明确检验条件 确定循环控制方式和列举方式 枚举算法只适用于可能解的个数不太多的情况。 一张单据上有一个5位数的编号，万位数是1，千位数是4，百位数是7，个位数是8，十位数已经模糊不清，只知道该5位数是7或11的倍数，找出所有满足这些条件的5位数并输出。 NO. 147 ? 8 列举范围： 0——9 检验条件： n能被5或者11整除。 即：(n mod 7=0) or (n mod 11=0) 用变量i表示十位上的数；变量n表示这个5位数。 开始 i=0 i10 (n mod 7=0) or (n mod 11=0) 输出n i=i+1 结束 N N Y Y 程序代码： i=0 Do while i10 n=14708+i*10 if n mod 7=0 or n mod 11=0 then Print n end if i=i+1 Loop n=14708+i*10 生活中的枚举算法实例 找钥匙 警察审案 挑烂苹果 1.枚举算法的概念 2.枚举算法的结构特征 4.枚举算法的应用 3.枚举算法的设计步骤 一张单据上有一个5位数的编号，千位数是1，百位数是7，个位数是8，万位数和十位数已经模糊不清，只知道该5位数是7或11的倍数，找出所有满足这些条件的5位数并输出。 NO. ? 17 ? 8 该题要列举的对象有两个，分别是万位数和个位数。用循环的嵌套。 找出1-1000中所有能被7和11整除的数。 c 开始 结束 T F i=1 i=1000 i=i+1 T F 输出 i i mod 7=0 and i mod 11=0 i mod 77=0 i mod 3=0