北航计算机研究生课程-算法设计与分析-HomeWork-1

一 已知下列递推式 C n 1 若 n 1 2C n 2 n 1 若 n 2 请由定理 1 导出 C n 的非递归表达式并指出其渐进复杂性 定理 1 设 a c 为非负整数 b d x 为非负常数 并对于某个非负整数 k 令 n ck 则以下递推式 f n d 若 n 1 af n c bnx 若 n 2 的解是 f n bnxlogcn dnx 若 a c x f n 若 a c xxaxncbbdc log 解 令 F n C n 1 则 F n 0 n 1 F n 2C n 2 n 2 n 2 2 F n 2 1 n 2 2F n 2 n 利用定理 1 其中 d 0 a 2 c 2 b 1 x 1 并且 a cx 所以 F n nlog 2n 所以 C n F n 1 nlog 2n 1 C n 的渐进复杂性是 O nlog2n 二 由于 Prim 算法和 Kruskal 算法设计思路的不同 导致了其对不同问题实例 的效率对比关系的不同 请简要论述 1 如何将两种算法集成 以适应问题的不同实例输入 2 你如何评价这一集成的意义 答 1 Prim 算法基于顶点进行搜索 所以适合顶点少边多的情况 Kruskal 从边集合中进行搜索 所以适合边少的情况 根据输入的图中的顶点和边的情况 边少的选用 kruskal 算法 顶点少的选 用 prim 算法 2 没有一个算法是万能的 没有一个算法是对所有情况都适合的 这一集成 体现了针对具体问题选用最适合的方法 即具体问题具体分析的哲学思想 三 分析以下生成排列算法的正确性和时间效率 HeapPermute n 实现生成排列的 Heap 算法 输入 一个正正整数 n 和一个全局数组 A 1 n 输出 A 中元素的全排列 if n 1 write A else for i 1 to n do HeapPermute n 1 if n is odd swap A 1 and A n else swap A i and A n 解 n 1 时 输出 a1 n 2 时 输出 a1a2 a2a1 n 3 时 1 第一次循环 i 1 时 HeapPermute 2 将 a1a2 做完全排列输出 记为 a1a2 a3 并将 A 变为 a2a1a3 并交换 1 3 位 得 a3a1a2 2 第二次循环 i 2 时 HeapPermute 2 输出 a3a1 a2 并将 A 变为 a1a3a2 交换 1 3 位 得 a2a3a1 3 第三次循环 i 3 时 HeapPermute 2 输出 a2a3 a1 并将 A 变为 a3a2a1 交换 1 3 位 得 a1a2a3 即全部输出完毕后数组 A 回到初始顺 序 n 4 时 1 i 1 时 HeapPermute 3 输出 a1a2a3 a4 并且 a1a2a3 顺序不变 交 换 1 4 位 得 a4a2a3a1 2 i 2 时 HeapPermute 3 输出 a4a2a3 a1 并且 a4a2a3 顺序不变 交 换 2 4 位 得 a4a1a3a2 3 i 3 时 HeapPermute 3 输出 a4a1a3 a2 并且 a4a1a3 顺序不变 交 换 3 4 位 得 a4a1a2a3 4 i 4 时 HeapPermute 3 输出 a4a1a2 a3 并且 a4a1a2 顺序不变 交 换 4 4 位 得 a4a1a2a3 即全部输出完毕后数组 A 循环右移一位 由以上分析可得出结论 当 n 为偶数时 HeapPermute n 输出全排列后数组元素循环右移一位 当 n 为奇数时 HeapPermute n 输出全排列后数组元素顺序保持不变 所以由归纳法证明如下 1 i 1 时 显然成立 2 i k 为偶数时 假设输出的是全排列 则 i k 1 奇数 时 k 1 次循环 中 每次前 k 个元素做全排列输出后循环右移一位 所以对换 swap A 1 and A n 可以保证每次将前 k 个元素中的一个换到 k 1 的位置 所以 k 1 次 循环后输出的是 A 1 k 1 的全排列 3 i k 为奇数时 假设输出的是全排列 则 i k 1 偶数 时 k 1 次循环中 每次前 k 个元素做全排列输出后顺序保持不变 所以对换 swap A i and A n 可以保证每次将前 k 个元素中的一个换到 k 1 的位置 所以 k 1 次循环后 输出的是 A 1 k 1 的全排列 证毕 时间复杂度递推公式为 T n 1 n 1 n T n 1 2 n 1 化简得 T n n O nn 1 所以时间复杂度为 O n O nn 1 四 对于求 n 个实数构成的数组中最小元素的位置问题 写出你设计的具有减 治思想算法的伪代码 确定其时间效率 并与该问题的蛮力算法相比较 解 1 算法思想 将 n 分为 n 2 n n 2 表示向下取整 两部分 分别找 出其中的最小元及其位置 比较这两个元素的大小 得出总的最小元素的位置 2 伪代码 x i FindLeastElement a b 从数组 A a b 中找出最小元 x 及其位置 i 输入 全局实数数组 A 1 n 搜索起始位置 a 结束位置 b 输出 最小元素 x 及其位置 i if a b return A a a else x1 i FindLeastElement 1 n 2 x2 j FindLeastElement n 2 1 n if x11 化简 F n 2F n 2 1 2 2F n 22 1 1 22F n 22 2 1 2kF 2k 2k 1 2 2k 1 n 2k 2n 1 所以复杂度为 O 2n 1 蛮力法的复杂度为 O n 所以此方法还没有蛮力法效率高 因为减治后会 增加比较次数 五 请给出约瑟夫斯问题的非递推公式 J n 并证明之 其中 n 为最初总 人数 J n 为最后幸存者的最初编号 解 已知幸存者号码的递推公式 J 1 1 J 2k 2J k 1 n 2k J 2k 1 2J k 1 n 2k 1 幸存者号码非递推公式 设 n 2m b J n 2 b 1 0 b 0 证明 数学归纳法 1 i 1 时 m 0 b 0 J 1 2 b 1 1 成立 2 i 1 时 当 i 为偶数时 设 k i 2 时成立 即 k 2m b 则 J k 2b 1 此时 i 2k 2m 1 2b J i J 2k 2J k 1 2 2b 1 1 4b 1 2 2b 1 即 k i 时成立 当 i 为奇数时 设 k i 1 2 时成立 即 k 2m b 则 J k 2b 1 此时 i 2k 1 2m 1 2b 1 J i J 2k 1 2J k 1 2 2b 1 1 4b 3 2 2b 1 1 即 k i 时成立 证毕