当前位置：首页 > news >正文

算法设计与分析-习题5.1

news 2026/3/26 19:37:55

a.为一个分治算法编写伪代码，该算法求一个n元素数组中最大元素的位置。

b.如果数组中的若干个元素都具有最大值，该算法的输出是怎样的呢?

c.建立该算法的键值比较次数的递推关系式并求解。

d.请将该算法与解同样问题的蛮力算法做一个比较。

a.为一个分治算法编写伪代码，该算法同时求出一个n元素数组的最大元素和最小元素的值。

b.假设n=2^k,为该算法的键值比较次数建立递推关系式并求解。

c.请将该算法与解同样问题的蛮力算法做一个比较。

a.为一个分治算法编写伪代码，该算法用来计算指数函数a^n的值，其中a>0，n是一个正整数。

b.建立该算法执行的乘法次数的递推关系式并求解。

c.请将该算法与解同样问题的蛮力算法做一个比较。

4.我们在第2章中讨论算法设计和分析的框架时，曾经提到过，在分析算法效率类型的大多数情况下，对数的底是可以忽略的。对于主定理中两个包含对数的断言来说，这个论点也成立吗?

5.求下列递推式的解的增长次数。

a. T(n)=4T(n/2)+n, T(1)=1

b. 编辑

C. 编辑

6.应用合并排序将序列E，X，A，M，P，L，E按照字母顺序排序。

7.合并排序是一个稳定的排序算法吗?

a.对合并排序的最差键值比较次数的递推关系式求解(可以假设；n=2^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, mid+1, high) 如果 A[leftPos] ≥ A[rightPos] 返回 leftPos 否则 返回 rightPos

b.如果数组中的若干个元素都具有最大值，该算法的输出是怎样的呢?

会输出最左边那个最大值的位置。

c.建立该算法的键值比较次数的递推关系式并求解。

T(n)=2T(n/2)+1，且T(1)=0

最终：T(n)=n−1

d.请将该算法与解同样问题的蛮力算法做一个比较。

分治与蛮力比较次数相同、时间复杂度相同，分治递归空间更高。

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, mid+1, high) currentMin ← min(leftMin, rightMin) currentMax ← max(leftMax, rightMax) return (currentMin, currentMax) 结束如果

b.假设n=2^k,为该算法的键值比较次数建立递推关系式并求解。

T(1)=1,T(2)=1

最终结果：

c.请将该算法与解同样问题的蛮力算法做一个比较。

分治比较次数更少，蛮力更简单、省空间

3.

a.为一个分治算法编写伪代码，该算法用来计算指数函数a^n的值，其中a>0，n是一个正整数。

算法：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 * a

b.建立该算法执行的乘法次数的递推关系式并求解。

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)=1

a=4,b=2,,d=1;a>b^d,T(n)∈Θ(n^(log_2 4))=Θ(n^2)

b.

相比a，d=2，T(n)∈Θ(n^2 logn)

C.

相比a，d=3，T(n)∈Θ(n^3)

6.应用合并排序将序列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] ↓ 拆分 ↓ 拆分 [E] [X][A] [M][P] [L][E]

流程如下：

7.合并排序是一个稳定的排序算法吗?

归并排序是稳定的，前提是其实现中在归并时使用比较运算符 ≤

8.

a.对合并排序的最差键值比较次数的递推关系式求解(可以假设；n=2^k)。

最坏情况：

解为

b.建立合并排序的最优键值比较次数的递推关系式，并对的情况求解。

最优为：

解：

c.对于5.1节给出的合并排序算法，建立它的键值移动次数的递推关系式。考虑了该算法的键值移动次数之后，是否会影响它的效率类型呢?

不会影响效率类型。

9. A[0. n-1]是一个n个不同实数构成的数组。如果i<j, 但是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, mid+1, 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 crossInv

10.任意选择一种语言实现自底向上的合并排序版本。

#include <stdio.h> #include <stdlib.h> // 合并两个有序区间：A[low..mid] 和 A[mid+1..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; }