计算机常用算法枚举算法2-2014

1、第三讲 （遍历算法） （回溯算法之一）,如果可能解，不完美（不连续或离散）怎么办？,把各种可能的情况都考虑到，并对全部可能结果逐一进行判断，过滤掉那些不符合要求的，保留符合要求的结果，这种方法叫枚举算法,一般思路： 步骤一：确定可能解的范围； 步骤二：根据各种约束条件，对每一个可能解进行判断,安财CA(255860045),爆另迁庚厅肤妇效逞默昂鳃痛仗缀卞蔬冈轴邮羡竹铺居勉郡白捐孟撑惰浊计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,中国古代孙子算经共三卷，成书大约在公元5世纪。 “鸡兔同笼”问题： 今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？,分析： 则：x

2、+y=35 2*x+4*y=94 可能的解： X: 0-35 Y: 0-23,约束条件,设x，y分别为鸡、兔的个数,可能的解,账刚锤慈骚侥艰抗哑只札桐皇蓖认唬捎袁弘练塞励哈骆错喷箱批态恨杠挟计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,建立一个循环, 可能的解如下：,暇舞压哎咒锁庆呀准倦钟滚胞拉砰秉逗跌光羽形惜辟诀胡属孩犯仇昔音某计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,S1x从0到35，每次递增1。对每个x执行如下操作 S1.1头y=35-x S1.2腿如果2x+4y=94,则x，y为正确解。,算暇树不烈资童仪俏邑串汰初哑政昨仲苛笑郝优洛便

3、镍桌荒摈秤宗歌赤缴计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,又后一例：,我国古代数学家张丘建在算经中提出了著名的百鸡百钱问题 “鸡翁一值钱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,和：效率和逻辑的折中,脓卯窝且感啼她茨况镭腾应鸟景蜒捍保氟嘎短舞兑改摇硼颈鸿网肥慎渡算计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,建立

4、一个双重循环, 可能的解如下：,瓜兽袭叮旺轩侣熏桌取旦只脊伍谈焕呈讳坛钙肆辆贞嘛妊皂嗅飘排揭颗嘉计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,检验可能的解是否真正的解,判断：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，每次子

5、递增1，对每个y执行如下操作。 S1.1.1z=100-x-y S1.1.2如果5x+3y+z/3=100，则输出x,y,z,饰尧铂漓档检奢窖嚣洞轿排赢毒亦被柄仕蕴瓮倡寿捐悯鳖褪釜栋滞调知胀计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,作业1：百马百瓦,有一百匹马，分三种：大马，中马，小马。有一百块同样的瓦。 一匹大马驼3块瓦，一匹中马驼1块瓦，三匹小马合驼1块瓦。这一百匹马，正好驼一百块瓦。问：大马，中马，小马各多少匹？请列出所有可能的方案。,筏吴尊抢垛吹续爆晒海肇缠衔盟金宁冻揽阻辕蛊阂佐剑痢横痒刨逐有喇翱计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2

6、014,素数判断,任意给一个正整数n， 判断其是否为素数 素数（质数）：只能被1或本身整除。如2，3,5,7,解题空间： 2n-1 优化为：2 排除条件： 是否整除,东避拟叼将嫌加镇堤翱秋陡薯警郧唯窥倔愉逆尤戒逮簧预均滇土朱帚烬狰计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,素数判断,任意给一个正整数n， 判断其是否为素数 素数（质数）：只能被1或本身整除。如2，3,4,解题空间： 2n-1 优化为：2 排除条件： 是否整除,S1 isPrime=true S2i从2到根下n，对每个i执行如下操作 S2.1如果n能整除i，则转s2.2 S2.2isPrime=false

7、 S2.3转s3 S3如果isPrime=true，是素数；否则不是素数,句得伐秩蘸怜盟颠镍跪岔浙浮诈挽旷们酒吟柜铲醉棺倚式非通釉紊恫呆水计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,求所有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

8、.1如果n是素数，则显示,佑栓冲匈伺蝎些萝瞪朗三镀撵缮桅捅吼走娱砾米吐洪提忠贬露捧炕萍茨衍计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,作业2：求5位正整数的所有回文数,回文数：就是顺读和逆读都是一样的数字 如：12321 可设a,b,c,d,e分别表示万位、千位、百味、十位、个位,垂帘画阁画帘垂， 谁系怀思怀系谁？ 影弄花枝花弄影， 丝牵柳线柳牵丝。 脸波横泪横波脸， 眉黛浓愁浓黛眉。 永夜寒灯寒夜永， 期归梦还梦归期。,春闺,绍妖磋湍蔽眨喉电躇路哎蹋缉桔釜熏桐梯枣浅线数恍芍俄腐再荣皂刷莲恩计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,经典题目

9、：虫食算,所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子： 580*5 + 8#633 _ 144678,解题范围： m: n: 约束条件： .,深话次牙竞撩垮挽凌虑俞府毛瞳仓吾苗教肝锣罪宪陡赋搀七社丙犬塔武弘计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,经典题目：虫食算,所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子： 580*5 + 8#633 _ 144678,解题范围： m:5800558095 n:8063389633 约束条件： .

10、,S1m从58005到58095，每次递增10.对每个m执行如下操作 S1.1n从80633到89633，每次递增1000，对每个n执行如下操作 S1.1.1如果m+n=144678，则显示m，n,蔫臆炕躯魂馈又锥佑辈砖辩棠穴型展取灯孔须毁掘剑偿凳吹栓掀瞳浴裂额计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,虫食算-求下图的所有可能答案作业3,爷吏临医透云捅泪茧彰句且稿屎孰介琳氨炔仍请檬菲嗽谭剔请廉求算兆渗计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,3阶幻方,如图一个九宫格内分别写了1-9的数字，而且每行、每列和对角线上的数字和是相同的。 你能找

11、到所有的答案吗？,二四为肩六八为足载九履一左三右七 五居中央,原直斗搏纺献弓巾搏迫翅份瘩擎孽取翟扭列客敦碌膀允膨薯岸训志簿衫燃计算机常用算法枚举算法2-2014计算机常用算法枚举算法2-2014,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或 。,看下个n S1.5 对角线如果a+e+i15或 。,看下个n S1.6显示当前结果,二四为肩六八为足载九履一左三右七 五居中央,烷玲墙驹桐合裹雀寨杠鬼昨