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

枚举算法2 第三讲 遍历算法 回溯算法之一 如果可能解 不完美 不连续或离散 怎么办 把各种可能的情况都考虑到 并对全部可能结果逐一进行判断 过滤掉那些不符合要求的 保留符合要求的结果 这种方法叫枚举算法 一般思路 步骤一 确定可能解的范围 步骤二 根据各种约束条件 对每一个可能解进行判断 安财CA 255860045 中国古代 孙子算经 共三卷 成书大约在公元5世纪 鸡兔同笼 问题 今有雉兔同笼 上有三十五头 下有九十四足 问雉兔各几何 分析 则 x y 352 x 4 y 94可能的解 X 0 35Y 0 23 约束条件 设x y分别为鸡 兔的个数 可能的解 建立一个循环 可能的解如下 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分别为买的鸡翁 鸡母 鸡雏的个数则 x y z 1005 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 x 0s2 s7 x x 1s8 如果x 20 则转2 y 0s3 s5 y y 1s6 如果y 33 转3 否则7 z 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块瓦 这一百匹马 正好驼一百块瓦 问 大马 中马 小马各多少匹 请列出所有可能的方案 素数判断 任意给一个正整数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优化为 排除条件 是否是素数 判断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分别表示万位 千位 百味 十位 个位 垂帘画阁画帘垂 谁系怀思怀系谁 影弄花枝花弄影 丝牵柳线柳牵丝 脸波横泪横波脸 眉黛浓愁浓黛眉 永夜寒灯寒夜永 期归梦还梦归期 春闺 经典题目 虫食算 所谓虫食算 就是原先的算式中有一部分被虫子啃掉了 需要我们根据剩下的数字来判定被啃掉的字母 来看一个简单的例子 580 5 8 633 144678 解题范围 m n 约束条件 经典题目 虫食算 所谓虫食算 就是原先的算式中有一部分被虫子啃掉了 需要我们根据剩下的数字来判定被啃掉的字母 来看一个简单的例子 580 5 8 633 144678 解题范围 m 58005 58095n 80633 89633约束条件 S1 m从58005到58095 每次递增10 对每个m执行如下操作S1 1 n从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分别表示各位 S1 n从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或 看