计算机常用算法枚举算法.ppt

1、枚举算法2,第三讲 （遍历算法） （回溯算法之一）,如果可能解，不完美（不连续或离散）怎么办？,把各种可能的情况都考虑到，并对全部可能结果逐一进行判断，过滤掉那些不符合要求的，保留符合要求的结果，这种方法叫枚举算法,一般思路： 步骤一：确定可能解的范围； 步骤二：根据各种约束条件，对每一个可能解进行判断,安财CA(255860045),中国古代孙子算经共三卷，成书大约在公元5世纪。 “鸡兔同笼”问题： 今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？,分析： 则：x+y=35 2*x+4*y=94 可能的解： X: 0-35 Y: 0-23,约束条件,设x，y分别为鸡、兔的个数,可能的

2、解,建立一个循环, 可能的解如下：,S1x从0到35，每次递增1。对每个x执行如下操作 S1.1头y=35-x S1.2腿如果2x+4y=94,则x，y为正确解。,又后一例：,我国古代数学家张丘建在算经中提出了著名的百鸡百钱问题 “鸡翁一值钱5， 鸡母一值钱3， 鸡雏三值钱1” 现有100钱，欲买100只鸡，问：鸡翁、鸡母、鸡雏各买几只？,分析： 设x，y，z分别为买的鸡翁、鸡母、鸡雏的个数 则：x+y+z=100 5*x+3*y+z/3=100 可能的解 X: 0-20 Y: 0-33 Z: 100-x-y,和：效率和逻辑的折中,建立一个双重循环, 可能的解如下：,检验可能的解是否真正的解,

3、判断：5*x+3*y+z/3=100 若是，x,y,z就是一个真正的解,算法： s1.x0 s2. s7.xx+1 s8.如果x=20 ,则转2,y0 s3. s5.yy+1 s6.如果y=33,转3；否则7,z100-x-y s4.如果5x+3y+z/3=100,则输出x,y,z; 否则转5,百鸡,百钱,如何提高效率？,S1x从0到20，每次递增1,对每个x执行如下子操作。 S1.1y从0到33，每次子递增1，对每个y执行如下操作。 S1.1.1z=100-x-y S1.1.2如果5x+3y+z/3=100，则输出x,y,z,作业1：百马百瓦,有一百匹马，分三种：大马，中马，小马。有一百块同

4、样的瓦。 一匹大马驼3块瓦，一匹中马驼1块瓦，三匹小马合驼1块瓦。这一百匹马，正好驼一百块瓦。问：大马，中马，小马各多少匹？请列出所有可能的方案。,素数判断,任意给一个正整数n， 判断其是否为素数 素数（质数）：只能被1或本身整除。如2，3,5,7,解题空间： 2n-1 优化为：2 排除条件： 是否整除,素数判断,任意给一个正整数n， 判断其是否为素数 素数（质数）：只能被1或本身整除。如2，3,4,解题空间： 2n-1 优化为：2 排除条件： 是否整除,S1 isPrime=true S2i从2到根下n，对每个i执行如下操作 S2.1如果n能整除i，则转s2.2 S2.2isPrime=fa

5、lse S2.3转s3 S3如果isPrime=true，是素数；否则不是素数,求所有4位素数,求所有的4位素数,解题空间： 10009999 优化为：？ 排除条件： 是否是素数,判断n是否是素数 S1 isPrime=true S2i从2到根下n，对每个i执行如下操作 S2.1如果n能整除i，则转s2.2 S2.2isPrime=false S2.3转s3 S3如果isPrime=true，是素数；否则不是素数,S1n从1000到9999，对每个n执行如下操作 S1.1如果n是素数，则显示,作业2：求5位正整数的所有回文数,回文数：就是顺读和逆读都是一样的数字 如：12321 可设a,b,c

6、,d,e分别表示万位、千位、百味、十位、个位,垂帘画阁画帘垂， 谁系怀思怀系谁？ 影弄花枝花弄影， 丝牵柳线柳牵丝。 脸波横泪横波脸， 眉黛浓愁浓黛眉。 永夜寒灯寒夜永， 期归梦还梦归期。,春闺,经典题目：虫食算,所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子： 580*5 + 8#633 _ 144678,解题范围： m: n: 约束条件： .,经典题目：虫食算,所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子： 580*5 + 8#633 _ 144678,解题范围

7、： m:5800558095 n:8063389633 约束条件： .,S1m从58005到58095，每次递增10.对每个m执行如下操作 S1.1n从80633到89633，每次递增1000，对每个n执行如下操作 S1.1.1如果m+n=144678，则显示m，n,虫食算-求下图的所有可能答案作业3,3阶幻方,如图一个九宫格内分别写了1-9的数字，而且每行、每列和对角线上的数字和是相同的。 你能找到所有的答案吗？,二四为肩六八为足载九履一左三右七 五居中央,3阶幻方-一例,令a,b,c,d,e,f,g,h,i分别表示各位： S1n从123456789到987654321，每次递增1，对于每个n完成如下操作 S1.1把n的各位分别截取存入a,b,c,d,e,f,g,h,i. S1.2如果上述各位有零或相同，看下一个n S1.3 行如果a+b+c15或 。,看下个n S1.4 列如果a+d+g15或 。,看下