计算机常用算法枚举算法.ppt
枚举算法2,第三讲（遍历算法）（回溯算法之一）,如果可能解，不完美（不连续或离散）怎么办？,把各种可能的情况都考虑到，并对全部可能结果逐一进行判断，过滤掉那些不符合要求的，保留符合要求的结果，这种方法叫枚举算法,一般思路：步骤一：确定可能解的范围；步骤二：根据各种约束条件，对每一个可能解进行判断,安财CA(255860045),中国古代孙子算经共三卷，成书大约在公元5世纪。“鸡兔同笼”问题：今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？,分析：则：x+y=35 2*x+4*y=94可能的解：X:0-35Y:0-23,约束条件,设x，y分别为鸡、兔的个数,可能的解,建立一个循环,可能的解如下：,S1x从0到35，每次递增1。对每个x执行如下操作S1.1头y=35-xS1.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-20Y:0-33Z:100-x-y,和：效率和逻辑的折中,建立一个双重循环,可能的解如下：,检验可能的解是否真正的解,判断：5*x+3*y+z/3=100若是，x,y,z就是一个真正的解,算法：s1.x0s2.s7.xx+1s8.如果x=20,则转2,y0s3.s5.yy+1s6.如果y=33,转3；否则7,z100-x-ys4.如果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-yS1.1.2如果5x+3y+z/3=100，则输出x,y,z,作业1：百马百瓦,有一百匹马，分三种：大马，中马，小马。有一百块同样的瓦。一匹大马驼3块瓦，一匹中马驼1块瓦，三匹小马合驼1块瓦。这一百匹马，正好驼一百块瓦。问：大马，中马，小马各多少匹？请列出所有可能的方案。,素数判断,任意给一个正整数n，判断其是否为素数素数（质数）：只能被1或本身整除。如2，3,5,7,解题空间：2n-1 优化为：2 排除条件：是否整除,素数判断,任意给一个正整数n，判断其是否为素数素数（质数）：只能被1或本身整除。如2，3,4,解题空间：2n-1 优化为：2 排除条件：是否整除,S1 isPrime=trueS2i从2到根下n，对每个i执行如下操作S2.1如果n能整除i，则转s2.2S2.2isPrime=falseS2.3转s3S3如果isPrime=true，是素数；否则不是素数,求所有4位素数,求所有的4位素数,解题空间：10009999 优化为：？排除条件：是否是素数,判断n是否是素数S1 isPrime=trueS2i从2到根下n，对每个i执行如下操作S2.1如果n能整除i，则转s2.2S2.2isPrime=falseS2.3转s3S3如果isPrime=true，是素数；否则不是素数,S1n从1000到9999，对每个n执行如下操作S1.1如果n是素数，则显示,作业2：求5位正整数的所有回文数,回文数：就是顺读和逆读都是一样的数字如：12321可设a,b,c,d,e分别表示万位、千位、百味、十位、个位,垂帘画阁画帘垂，谁系怀思怀系谁？影弄花枝花弄影，丝牵柳线柳牵丝。脸波横泪横波脸，眉黛浓愁浓黛眉。永夜寒灯寒夜永，期归梦还梦归期。,春闺,经典题目：虫食算,所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：580*5+8#633 _ 144678,解题范围：m:n:约束条件：.,经典题目：虫食算,所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：580*5+8#633 _ 144678,解题范围：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如果上述各位有零或相同，看下一个nS1.3 行如果a+b+c15或。,看下个nS1.4 列如果a+d+g15或。,看下个nS1.5 对角线如果a+e+i15或。,看下个nS1.6显示当前结果,二四为肩六八为足载九履一左三右七五居中央,思考：残缺的3阶魔方-作业4,现在不小心九宫格的四角被小虫子吃掉了，问：你能补全这个九宫格吗？写出算法。,
