目录1.a.为一个分治算法编写伪代码该算法求一个n元素数组中最大元素的位置。b.如果数组中的若干个元素都具有最大值该算法的输出是怎样的呢?c.建立该算法的键值比较次数的递推关系式并求解。d.请将该算法与解同样问题的蛮力算法做一个比较。2.a.为一个分治算法编写伪代码该算法同时求出一个n元素数组的最大元素和最小元素的值。b.假设n2^k,为该算法的键值比较次数建立递推关系式并求解。c.请将该算法与解同样问题的蛮力算法做一个比较。3.a.为一个分治算法编写伪代码该算法用来计算指数函数a^n的值其中a0n是一个正整数。b.建立该算法执行的乘法次数的递推关系式并求解。c.请将该算法与解同样问题的蛮力算法做一个比较。4.我们在第2章中讨论算法设计和分析的框架时曾经提到过在分析算法效率类型的大多数情况下对数的底是可以忽略的。对于主定理中两个包含对数的断言来说这个论点也成立吗?5.求下列递推式的解的增长次数。a. T(n)4T(n/2)n, T(1)1b. ​编辑C. ​编辑6.应用合并排序将序列EXAMPLE按照字母顺序排序。7.合并排序是一个稳定的排序算法吗?8.a.对合并排序的最差键值比较次数的递推关系式求解(可以假设n2^k)。b.建立合并排序的最优键值比较次数的递推关系式并对 ​编辑 的情况求解。c.对于5.1节给出的合并排序算法建立它的键值移动次数的递推关系式。考虑了该算法的键值移动次数之后是否会影响它的效率类型呢?9. A[0. n-1]是一个n个不同实数构成的数组。如果i A[j], 则这对元素(A[i],A[j])被称为一个倒置(inversion)。设计一个O(nlogn)算法来计算数组中的倒置数量。10.任意选择一种语言实现自底向上的合并排序版本。11. Tromino 谜题 Tromino(更准确地说是“右 Trominio”)是一个由棋盘上的三个1×1方块组成的L 型骨牌。我们的问题是如何用 Tromino覆盖一个缺少了一个方块(可以在棋盘上的任何位置)的 ​编辑 棋盘。除了这个缺失的方块 Tromino应该覆盖棋盘上的所有方块 Tromino 可以任意转向但不能有重叠([Gol94])。1.a.为一个分治算法编写伪代码该算法求一个n元素数组中最大元素的位置。二分查找算法FindMaxIndex(A[0..n-1]) // 输入n个元素的数组A // 输出最大值元素的下标位置 如果 low high 返回 low 否则 mid ← ⌊(low high) / 2⌋ leftPos ← FindMaxIndex(A, low, mid) rightPos ← FindMaxIndex(A, mid1, high) 如果 A[leftPos] ≥ A[rightPos] 返回 leftPos 否则 返回 rightPosb.如果数组中的若干个元素都具有最大值该算法的输出是怎样的呢?会输出最左边那个最大值的位置。c.建立该算法的键值比较次数的递推关系式并求解。T(n)2T(n/2)1且T(1)0最终T(n)n−1d.请将该算法与解同样问题的蛮力算法做一个比较。分治与蛮力比较次数相同、时间复杂度相同分治递归空间更高。2.a.为一个分治算法编写伪代码该算法同时求出一个n元素数组的最大元素和最小元素的值。算法MinMax(A, low, high) // 输入数组A区间[low, high] // 输出(min, max) 一对值 如果 low high then return (A[low], A[low]) // 只有一个元素 否则如果 high low 1 then // 两个元素 如果 A[low] A[high] then return (A[low], A[high]) 否则 return (A[high], A[low]) 结束如果 否则 mid ← ⌊(low high) / 2⌋ (leftMin, leftMax) ← MinMax(A, low, mid) (rightMin, rightMax) ← MinMax(A, mid1, high) currentMin ← min(leftMin, rightMin) currentMax ← max(leftMax, rightMax) return (currentMin, currentMax) 结束如果b.假设n2^k,为该算法的键值比较次数建立递推关系式并求解。T(1)1,T(2)1最终结果c.请将该算法与解同样问题的蛮力算法做一个比较。分治比较次数更少蛮力更简单、省空间3.a.为一个分治算法编写伪代码该算法用来计算指数函数a^n的值其中a0n是一个正整数。算法Power(a, n) if n 1 then return a mid ← ⌊n/2⌋ p ← Power(a, mid) if n 是偶数 then return p * p else return p * p * ab.建立该算法执行的乘法次数的递推关系式并求解。T(n)T(n/2​)1,T(1)0效率为Θ(logn)c.请将该算法与解同样问题的蛮力算法做一个比较。蛮力 Θ(n)分治 Θ(logn)分治效率更高4.我们在第2章中讨论算法设计和分析的框架时曾经提到过在分析算法效率类型的大多数情况下对数的底是可以忽略的。对于主定理中两个包含对数的断言来说这个论点也成立吗?因为不同底数的对数之间只相差常数因子而渐近复杂度记号会忽略常数因子因此在主定理的对数相关断言中对数的底不影响效率类型。5.求下列递推式的解的增长次数。a. T(n)4T(n/2)n, T(1)1a4,b2,,d1;ab^d,T(n)∈Θ(n^(log_2 4))Θ(n^2)b.相比ad2T(n)∈Θ(n^2 logn)C.相比ad3T(n)∈Θ(n^3)6.应用合并排序将序列EXAMPLE按照字母顺序排序。[E, X, A, M, P, L, E] ↓ 拆分 [E, X, A] [M, P, L, E] ↓ 拆分 ↓ 拆分 [E] [X, A] [M, P] [L, E] ↓ 拆分 ↓ 拆分 [E] [X][A] [M][P] [L][E]流程如下7.合并排序是一个稳定的排序算法吗?归并排序是稳定的前提是其实现中在归并时使用比较运算符 ≤8.a.对合并排序的最差键值比较次数的递推关系式求解(可以假设n2^k)。最坏情况解为b.建立合并排序的最优键值比较次数的递推关系式并对的情况求解。最优为解c.对于5.1节给出的合并排序算法建立它的键值移动次数的递推关系式。考虑了该算法的键值移动次数之后是否会影响它的效率类型呢?不会影响效率类型。9. A[0. n-1]是一个n个不同实数构成的数组。如果ij, 但是A[i]A[j], 则这对元素(A[i],A[j])被称为一个倒置(inversion)。设计一个O(nlogn)算法来计算数组中的倒置数量。将数组二分为左右两半。递归计算左半部分的倒置数、右半部分的倒置数。在合并两个有序子数组的过程中统计跨左右的倒置数。总倒置数 左 右 跨。算法CountInversions(A[0..n-1]) // 输入n个不同实数的数组A // 输出数组中的倒置总数 返回 MergeSortCount(A, 0, n-1) 算法MergeSortCount(A, low, high) // 递归分治计算倒置数 invCount ← 0 if low high then mid ← ⌊(low high) / 2⌋ invCount ← invCount MergeSortCount(A, low, mid) // 左 invCount ← invCount MergeSortCount(A, mid1, high) // 右 invCount ← invCount MergeAndCount(A, low, mid, high) // 跨 return invCount 算法MergeAndCount(A, low, mid, high) // 合并并计算跨左右的倒置数 创建临时数组 B[low..high] i ← low // 左指针 j ← mid 1 // 右指针 k ← low // 临时数组指针 crossInv ← 0 while i ≤ mid AND j ≤ high do if A[i] ≤ A[j] then B[k] ← A[i] i ← i 1 else B[k] ← A[j] j ← j 1 crossInv ← crossInv (mid - i 1) // 关键累加倒置 k ← k 1 // 复制剩余元素 while i ≤ mid do B[k] ← A[i] i ← i 1 k ← k 1 while j ≤ high do B[k] ← A[j] j ← j 1 k ← k 1 // 复制回原数组 for t ← low to high do A[t] ← B[t] return crossInv10.任意选择一种语言实现自底向上的合并排序版本。#include stdio.h #include stdlib.h // 合并两个有序区间A[low..mid] 和 A[mid1..high] void merge(int A[], int low, int mid, int high, int temp[]) { int i low; // 左区间起点 int j mid 1;// 右区间起点 int k low; // 临时数组下标 // 把两个有序序列合并到 temp 数组 while (i mid j high) { if (A[i] A[j]) { temp[k] A[i]; } else { temp[k] A[j]; } } // 复制左区间剩余元素 while (i mid) { temp[k] A[i]; } // 复制右区间剩余元素 while (j high) { temp[k] A[j]; } // 把合并好的结果复制回原数组 for (i low; i high; i) { A[i] temp[i]; } } // 自底向上归并排序 void mergeSortBottomUp(int A[], int n) { int *temp (int *)malloc(n * sizeof(int)); // 临时数组 int size; // 当前子数组大小1,2,4,8... int leftStart; // 每次合并的左块起点 // 子数组大小从 1 开始成倍增长 for (size 1; size n; size size * 2) { // 两两合并 for (leftStart 0; leftStart n - size; leftStart size * 2) { int mid leftStart size - 1; // 左块终点 int rightEnd leftStart size * 2 - 1; // 右块终点 if (rightEnd n) rightEnd n - 1; // 防止越界 merge(A, leftStart, mid, rightEnd, temp); // 合并 } } free(temp); } // 打印数组 void printArray(int A[], int n) { for (int i 0; i n; i) { printf(%d , A[i]); } printf(\n); } // 主函数测试 int main() { int A[] {6, 3, 1, 8, 5, 2, 7, 4}; int n sizeof(A) / sizeof(A[0]); printf(排序前); printArray(A, n); mergeSortBottomUp(A, n); printf(排序后); printArray(A, n); return 0; }11. Tromino谜题 Tromino(更准确地说是“右 Trominio”)是一个由棋盘上的三个1×1方块组成的L 型骨牌。我们的问题是如何用 Tromino覆盖一个缺少了一个方块(可以在棋盘上的任何位置)的棋盘。除了这个缺失的方块 Tromino应该覆盖棋盘上的所有方块 Tromino 可以任意转向但不能有重叠([Gol94])。为此问题设计一个分治算法。把大棋盘切成 4 个小象限在中心放 1 块 L 型骨牌让 4 个象限都各缺 1 格然后递归解决每个小象限。看缺失格子在哪个象限在另外 3 个象限靠近中心的位置各放 1 格这 3 格正好拼成1 块 L 型骨牌结果4 个象限现在都各有 1 个缺失格时间复杂度 O (4ⁿ)