算法设计与分析试题

贪心算法总体思想 顾名思义 贪心算法总是做出在当前看来最好的选择 也就是说贪心顾名思义 贪心算法总是做出在当前看来最好的选择 也就是说贪心 算法并不从整体最优考虑 它所做出的选择只是在某种意义上的算法并不从整体最优考虑 它所做出的选择只是在某种意义上的 局部最优选择 当然 希望贪心算法得到的最终结果也是整体最局部最优选择 当然 希望贪心算法得到的最终结果也是整体最 优的 虽然贪心算法不能对所有问题都得到整体最优解 但对许优的 虽然贪心算法不能对所有问题都得到整体最优解 但对许 多问题它能产生整体最优解 如单源最短路径问题 最小生成树多问题它能产生整体最优解 如单源最短路径问题 最小生成树 问题等 在一些情况下 即使贪心算法不能得到整体最优解 其问题等 在一些情况下 即使贪心算法不能得到整体最优解 其 最终结果却是最优解的很好近似 最终结果却是最优解的很好近似 棋盘 骨牌 覆盖问题算法思想 一个 2k 2k k 为非负整数 个方格组成的特殊棋盘中 有一个 方格为特殊方格 用 4 种不同形态的 L 型骨牌覆盖给定的特殊棋 盘上除特殊方格以外的所有方格 任何 2 个 L 型骨牌不得重叠覆 盖 4 种 L 型骨牌 核心算法思想 分治思想核心算法思想 分治思想 在在 2 2 2 2个方格组成的棋盘中用到的个方格组成的棋盘中用到的 L L 型骨牌有型骨牌有 4 4 1 3 1 3 个 个 k k k k k k 从分治的思想易得到需将问题微型化 于是我们将棋盘平均分成从分治的思想易得到需将问题微型化 于是我们将棋盘平均分成 四个相似的棋盘 若特殊方格恰在图示的第一块区域 为了符合四个相似的棋盘 若特殊方格恰在图示的第一块区域 为了符合 分治思想我们需要将其他三部分转化成同样具有特殊方格的棋盘 分治思想我们需要将其他三部分转化成同样具有特殊方格的棋盘 依次递归直到棋盘为依次递归直到棋盘为 1 11 1 的规模即可解决问题 的规模即可解决问题 符号三角形问题算法思想 第 1 行有 n 个符号 两个同号下是 两个异号下是 对于给定 n 计算有多少个不同符号三角形 使其所含的 和 的个数相同 回溯法是一种通用性解法 可以将回溯法看作是带优化的穷举 法 回溯法的基本思想是在一棵含有问题全部可能解的状态空间树 上进行深度优先搜索 解为叶子结点 搜索过程中 每到达一 个结点时 则判断该结点为根的子树是否含有问题的解 如果 可以确定该子树中不含有问题的解 则放弃对该子树的搜索 退回到上层父结点 继续下一步深度优先搜索过程 在回溯法中 并不是先构造出整棵状态空间树 再进行搜索 而是在搜索过程 逐步构造出状态空间树 即边搜索 边构造 减枝 个数超过 n n 1 4 n n 1 2 为奇数 对于符号三角形问题 用对于符号三角形问题 用 n n 元组元组 x 1x 1 n n 表示符号三角形的第一行的表示符号三角形的第一行的 n n 个符号 当个符号 当 x i 1x i 1 时 表示符号三角形的第一行的第时 表示符号三角形的第一行的第 i i 个符号个符号 为为 号 当号 当 x i 0 x i 0 时 表示符号三角形的第一行的第时 表示符号三角形的第一行的第 i i 个符个符 号为号为 号 号 1 1 i i n n 由于 由于 x i x i 是二值的 所以在用回溯是二值的 所以在用回溯 法解符号三角形问题时 可以用一棵完全二叉树来表示其解空间 法解符号三角形问题时 可以用一棵完全二叉树来表示其解空间 在符号三角形的第一行的前在符号三角形的第一行的前 i i 个符号个符号 x 1x 1 i i 确定后 就确定了确定后 就确定了 一个由一个由 i i i 1i 1 2 2 个符号组成的符号三角形 下一步确定了个符号组成的符号三角形 下一步确定了 x i 1 x i 1 的值后 只要在前面已确定的符号三角形的右边加一条边 的值后 只要在前面已确定的符号三角形的右边加一条边 就可以扩展为就可以扩展为 x 1x 1 i 1 i 1 所相应的符号三角形 最终由所相应的符号三角形 最终由 x 1x 1 n n 所所 确定的符号三角形中包含的确定的符号三角形中包含的 号个数与号个数与 号个数同为号个数同为 n n n 1n 1 4 4 因此在回溯搜索过程中可用当前符号三角形所包含 因此在回溯搜索过程中可用当前符号三角形所包含 的的 号个数与号个数与 号个数均不超过号个数均不超过 n n n 1n 1 4 4 作为可行性作为可行性 约束 用于剪去不满足约束的子树 对于给定的约束 用于剪去不满足约束的子树 对于给定的 n n 当 当 n n n 1n 1 2 2 为奇数时 显然不存在所包含的为奇数时 显然不存在所包含的 号个数与号个数与 号个数相号个数相 同的符号三角形 同的符号三角形 用 c i j 记录序列 Xi和 Yj的最长公共子序列的长度 其中 Xi x1 x2 xi Yj y1 y2 yj 证明 最长公共子序列问题的 动态规划算法的递归结构为 动态规划与分治法相同之处是也将原问题分解为若干子问题 再递 归求解 不同之处是所分解的子问题彼此并不独立 而是互有重叠 a 最长公共子序列的结构最长公共子序列的结构 若用穷举搜索法 耗时太长 算法需要指数时间 若用穷举搜索法 耗时太长 算法需要指数时间 易证最长公共子序列问题也有最优子结构性质易证最长公共子序列问题也有最优子结构性质 设序列设序列 X 和和 Y 的一个最长公共子序的一个最长公共子序 ji ji yxji yxji ji jicjic jicjic 0 0 0 0 1 1 max 1 1 1 0 列列 Z 则 则 i 若若 xm yn 则 则 zk xm yn 且且 Zk 1 是是 Xm 1 和和 Yn 1 的最长公共子的最长公共子 序列 序列 ii 若若 xm yn 且且 zk xm 则 则 Z 是是 Xm 1 和和 Y 的最长公共子序列 的最长公共子序列 iii 若若 xm yn 且且 zk yn 则 则 Z 是是 X 和和 Yn 1 的最长公共子序列 的最长公共子序列 其中其中 Xm 1 Yn 1 Zk 1 最长公共子序列问题具有最优子结构性质 最长公共子序列问题具有最优子结构性质 b 子问题的递归结构子问题的递归结构 由最长公共子序列问题的最优子结构性质可知 要找出由最长公共子序列问题的最优子结构性质可知 要找出 X 和和 Y 的最长公共子序列 可按以下方式的最长公共子序列 可按以下方式 递归地进行 当递归地进行 当 xm yn 时 找出时 找出 Xm 1 和和 Yn 1 的最长公共子序的最长公共子序 列 然后在其尾部加上列 然后在其尾部加上 xm yn 即可得即可得 X 和和 Y 的一个最长公共子的一个最长公共子 序列 当序列 当 xm yn 时 必须解两个子问题 即找出时 必须解两个子问题 即找出 Xm 1 和和 Y 的的 一个最长公共子序列及一个最长公共子序列及 X 和和 Yn 1 的一个最长公共子序列 这两的一个最长公共子序列 这两 个公共子序列中较长者即为个公共子序列中较长者即为 X 和和 Y 的一个最长公共子序列 的一个最长公共子序列 由此递归结构容易看到最长公共子序列问题具有子问题重叠性质 例由此递归结构容易看到最长公共子序列问题具有子问题重叠性质 例 如 在计算如 在计算 X 和和 Y 的最长公共子序列时 可能要计算出的最长公共子序列时 可能要计算出 X 和和 Yn 1 及及 Xm 1 和和 Y 的最长公共子序列 而这两个子问题都包含一的最长公共子序列 而这两个子问题都包含一 个公共子问题 即计算个公共子问题 即计算 Xm 1 和和 Yn 1 的最长公共子序列 的最长公共子序列 我们来建立子问题的最优值的递归关系 用我们来建立子问题的最优值的递归关系 用 c i j 记录序列记录序列 Xi 和和 Yj 的最长公共子序列的长度 其中的最长公共子序列的长度 其中 Xi Yj 当 当 i 0 或或 j 0 时 空序列是时 空序列是 Xi 和和 Yj 的最长公共子序列 的最长公共子序列 故故 c i j 0 建立递归关系如下 建立递归关系如下 c 计算最优值计算最优值 由于在所考虑的子问题空间中 总共只有由于在所考虑的子问题空间中 总共只有 m n 个不同的子问题 个不同的子问题 因此 用动态规划算法自底向上地计算最优值能提高算法的效率 因此 用动态规划算法自底向上地计算最优值能提高算法的效率 计算最长公共子序列长度的动态规划算法计算最长公共子序列长度的动态规划算法 LCS LENGTH X Y 以序以序 列列 X 和和 Y 作为输入 输出两个作为输入 输出两个 数组数组 c 0 m 0 n 和和 b 1 m 1 n 其中 其中 c i j 存储存储 Xi 与与 Yj 的最长的最长 公共子序列的长度 公共子序列的长度 b i j 记录指示记录指示 c i j 的值是由哪一个子问题的的值是由哪一个子问题的 解达到的 这在构造最长公共子序列时要用到 最后 解达到的 这在构造最长公共子序列时要用到 最后 X 和和 Y 的的 最长公共子序列的长度记录于最长公共子序列的长度记录于 c m n 中 中 1 最长公共子序列的结构 解最长公共子序列问题时最容易想到的算法是穷举搜索发 即对 X 的每一个子 序列 检查它是否也是 Y 的子序列 从而确定它是否为 X 和 Y 的公共子序 列 并且在检查过程中选出最长的公共子序列 X 的所有子序列都检查过 后即可求出 X 和 Y 的最长公共子序列 X 的一个子序列响应与下标序列 1 2 m 的一个子序列 隐刺 X 共有 2m 个不同子序列 从而 穷举搜索发需要指数时间 事实上 最长公共子序列问题也有最优子结构 性质 有如下定理 设序列设序列 X 和和 Y 的一个最长公共子序列的一个最长公共子序列 Z 则 则 i 若若 xm yn 则 则 zk xm yn 且且 Zk 1 是是 Xm 1 和和 Yn 1 的最长公共子的最长公共子 序列 序列 ii 若若 xm yn 且且 zk xm 则 则 Z 是是 Xm 1 和和 Y 的最长公共子序列 的最长公共子序列 iii 若若 xm yn 且且 zk yn 则 则 Z 是是 X 和和 Yn 1 的最长公共子序列 的最长公共子序列 其中其中 Xm 1 Yn 1 Zk 1 证明 用反证法 若证明 用反证法 若 zk xm 则则 是是 X 和和 Y 的长度为的长度为 k 1 的公共子序列 这与的公共子序列 这与 Z 是是 X 和和 Y 的一个最长公共子序列矛盾 的一个最长公共子序列矛盾 因此 必有因此 必有 zk xm yn 由此可知 由此可知 Zk 1 是是 Xm 1 和和 Yn 1 的一个的一个 长度为长度为 k 1 的公共子序列的公共子序列 W 则将 则将 xm 加在其尾部将产生加在其尾部将产生 X 和和 Y 的一个长度大于的一个长度大于 k 的公共子序列 此为矛盾 故的公共子序列 此为矛盾 故 Zk 1 是是 Xm 1 和和 Y 的一个最长公共子序列 的一个最长公共子序列 由于由于 zk xm Z 是是 Xm 1 和和 Y 的一个公共子序列 若的一个公共子序列 若 Xm 1 和和 Y 有一个长度大于有一个长度大于 k 的公共子序列的公共子序列 W 则 则 W 也是也是 X 和和 Y 的一个长的一个长 度大于度大于 k 的公共子序列 这与的公共子序列 这与 Z 是是 X 和和 Y 的一个最长公共子序的一个最长公共子序 列矛盾 由此可知列矛盾 由此可知 Z 是是 Xm 1 和和 Y 的一个最长公共子序列 的一个最长公共子序列 函数 A n m 定义如下 设计计算函数值 A n m 的递归函数 阿克曼 阿克曼 Ackermann Ackermann 函数的函数的 c c 程序程序 include include intint ackermann intackermann int m m intint n n intint main main intint m n result m n result cout Input endl cout Input m cin m cin n cin n resultresult ackermann m n ackermann m n cout result endl cout result endl 1 2 0 1 1 2 0 1 0 2 0 1 mn n m mmnAAmnA nnA mA A returnreturn 0 0 intint ackermann intackermann int m m intint n n ifif m m 0 0 returnreturn n 1 n 1 ifif n n 0 0 returnreturn ackermann m 1 ackermann m 1 1 1 returnreturn ackermann m 1 ackermann m 1 ackermann m ackermann m n 1 n 1 或者 或者 include include intint Ack intAck int m intm int n n if m 0 if m 0 returnreturn n 1 n 1 elseelse if m 0Ack m 1 1 elseelse if m 0Ack m 1 Ack m n 1 voidvoid main main intint a b a b scanf d d scanf d d printf d n Ack a b printf d n Ack a b 在一个 n n 的棋盘上放置彼此不受攻击 n 个皇后 即任何 2 个皇 后不放在同一行或同一列或同一斜线上 使用回溯法求解如下 static int n 皇后个数皇后个数 static int x 当前解当前解 static long sum 当前已找到的可行方案数当前已找到的可行方案数 public static long nQueen int nn n nn sum 0 x new int n 1 for int i 0 i n i x i 0 初始户初始户 backtrack 1 return sum 请设计方法 函数 backtrack int t 书上第五章 书上第五章 5 5 节节 165 页页 已知方法 randomizedPartition a p r 书上第二章 书上第二章 2 9 节节 39 页页 1 设计找出这 n 个元素中第 k 小的元素的算法 2 分析算法的时间复杂性 template classtemplateType TypeType RandomizedSelect TypeRandomizedSelect Type a inta int p intp int r intr int k k ifif p r p r returnreturn a p a p intint i RandomizedPartition a p r i RandomizedPartition a p r j i p 1 j i p 1 ifif k j k j returnreturn RandomizedSelect a p i k RandomizedSelect a p i k elseelse returnreturn RandomizedSelect a i 1 r k j RandomizedSelect a i 1 r k j 在最坏情况下 算法在最坏情况下 算法 randomizedSelec