资源描述：
《计算机常用算法枚举算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、枚举算法2第三讲（遍历算法）（回溯算法之一）如果可能解，不完美（不连续或离散）怎么办？把各种可能的情况都考虑到，并对全部可能结果逐一进行判断，过滤掉那些不符合要求的，保留符合要求的结果，这种方法叫枚举算法一般思路：步骤一：确定可能解的范围；步骤二：根据各种约束条件，对每一个可能解进行判断安财CA(255860045)中国古代《孙子算经》共三卷，成书大约在公元5世纪。“鸡兔同笼”问题：今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？分析：则：x+y=352*x+4*y=94可能的解：X:0-35Y:0-23约束条件设x，y分别为鸡、兔的个数可能
2、的解建立一个循环,可能的解如下：x<=35YN开始x←0x←x+1结束2x+4y=94？Ny←35-xY正确解xY=35-x035134233……350x<=35YN开始x←0x←x+1结束2x+4y=94？Ny←35-xY正确解S1]x从0到35，每次递增1。对每个x执行如下操作S1.1][头]y=35-xS1.2][腿]如果2x+4y=94,则x，y为正确解。又后一例：我国古代数学家张丘建在《算经》中提出了著名的百鸡百钱问题“鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1”现有100钱，欲买100只鸡，问：鸡翁、鸡母、鸡雏各买几只？分析：设x，y，z分
3、别为买的鸡翁、鸡母、鸡雏的个数则：x+y+z=1005*x+3*y+z/3=100可能的解X:0-20Y:0-33Z:100-x-y和：效率和逻辑的折中建立一个双重循环,可能的解如下：x<=20YN开始x←0x←x+1结束y<=33Ny←y+1y←0Y判断可能的解是否是真正的解xyz0010001990298………033671099………203347检验可能的解是否真正的解判断：5*x+3*y+z/3=100若是，x,y,z就是一个真正的解算法：s1.x←0s2.s7.x←x+1s8.如果x<=20,则转2y←0s3.s5.y←y+1s6.如果y<=
4、33,转3；否则7z←100-x-ys4.如果5x+3y+z/3=100,则输出x,y,z;否则转5百鸡百钱如何提高效率？S1]x从0到20，每次递增1,对每个x执行如下子操作。S1.1]y从0到33，每次子递增1，对每个y执行如下操作。S1.1.1]z=100-x-yS1.1.2]如果5x+3y+z/3=100，则输出x,y,z作业1：百马百瓦有一百匹马，分三种：大马，中马，小马。有一百块同样的瓦。一匹大马驼3块瓦，一匹中马驼1块瓦，三匹小马合驼1块瓦。这一百匹马，正好驼一百块瓦。问：大马，中马，小马各多少匹？请列出所有可能的方案。素数判断任意给一
5、个正整数n，判断其是否为素数素数（质数）：只能被1或本身整除。如2，3,5,7解题空间：2~n-1优化为：2~排除条件：是否整除素数判断任意给一个正整数n，判断其是否为素数素数（质数）：只能被1或本身整除。如2，3,4解题空间：2~n-1优化为：2~排除条件：是否整除S1]isPrime=trueS2]i从2到根下n，对每个i执行如下操作S2.1]如果n能整除i，则转s2.2S2.2]isPrime=falseS2.3]转s3S3]如果isPrime=true，是素数；否则不是素数求所有4位素数求所有的4位素数解题空间：1000~9999优化为：？排
6、除条件：是否是素数判断n是否是素数S1]isPrime=trueS2]i从2到根下n，对每个i执行如下操作S2.1]如果n能整除i，则转s2.2S2.2]isPrime=falseS2.3]转s3S3]如果isPrime=true，是素数；否则不是素数S1]n从1000到9999，对每个n执行如下操作S1.1]如果n是素数，则显示作业2：求5位正整数的所有回文数回文数：就是顺读和逆读都是一样的数字如：12321可设a,b,c,d,e分别表示万位、千位、百味、十位、个位垂帘画阁画帘垂，谁系怀思怀系谁？影弄花枝花弄影，丝牵柳线柳牵丝。脸波横泪横波脸，眉黛
7、浓愁浓黛眉。永夜寒灯寒夜永，期归梦还梦归期。春闺经典题目：虫食算所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：580*5 +8#633 ____________ 144678解题范围：m:n:约束条件：…..经典题目：虫食算所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：580*5 +8#633 ____________ 144678解题范围：m:58005~58095n:80633~89633约束条件：…..S1]m从5
8、8005到58095，每次递增10.对每个m执行如下操作S1.1]n从80633到89633，每次递增100
