算法设计与分析-习题2.4

目录

1.解下列递推关系。

2.对于计算n！的递归算法F(n)，建立其递归调用次数的递推关系并求解。

3.考虑下列递归算法，该算法用来计算前n个立方的和： ​编辑

a.建立该算法的基本操作执行次数的递推关系并求解。

b.如果将这个算法和直截了当的非递归算法比较，你做何评价?

4.考虑下面的递归算法。

a.建立该函数值的递推关系并求解，以确定该算法计算的是什么。

b.建立该算法所做的乘法运算次数的递推关系并求解。

c.建立该算法所做的加减运算次数的递推关系并求解。

5.汉诺塔谜题

a.汉诺塔谜题最早是由一个法国数学家卢卡斯于19世纪90年代提出的，当时的版本是这样的：当64个圆盘被从梵塔上移走时，世界末日也就来临了。如果祭司一分钟移动一个圆盘(假设该祭司不吃不睡，而且长生不老)，请估计一下，移走全部圆盘一共需要多少年?

b.在该算法中，要移动第i大的盘子(1≤i≤n)一共需要移动多少步?

规律

c.为汉诺塔谜题设计一个非递归的算法，并用你熟悉的语言实现。

6.受限汉诺塔 考虑以下版本的汉诺塔谜题：有n个圆盘需要从柱子A借助柱子B搬到柱子C，且任何移动要么把一个圆盘搬到柱子B或者从柱子B上搬走一个圆盘。(同样禁止把较大的圆盘放在较小的圆盘下面。)设计一个递归算法解决这个问题，并且确定实现它所需要的移动次数。

7.

a.请证明，对于一个任意十进制正整数n来说，递归算法BinRec(n)所做的加法运算的精确次数是[log₂n]。

b.对于该算法的非递归版本，建立其所做的加法运算次数的递推关系并求解(参见2.3 节, 例4)。

8.

a.请基于公式 ​编辑设计一个递归算法。当n是任意非负整数时，该算法能够计算2^n的值。

b.建立该算法所做的加法运算次数的递推关系并求解。

c.为该算法构造一棵递归调用树，然后计算它所做的递归调用的次数。

d.对于该问题的求解来说，这是一个好算法吗?

9.考虑下面的递归算法。

a.该算法计算的是什么?

b.建立该算法所做的基本操作次数的递推关系并求解。

10.考虑下面的算法来检查一个由邻接矩阵表示的图是否是完全图。

11.一个n阶方阵

a.假设有一个实现该定义的算法，建立该算法的乘法运算次数的递推关系并求解。

b.不对该递推关系求解，你认为它的增长次数和n！相比会有什么结论?

12.重温冯·诺依曼邻居问题 建立一个递推关系并求解，以计算n阶冯·诺依曼邻居的细胞数(参见习题2.3的第11题)。

13.烤汉堡 有n个汉堡需要在烤架上烤，但是烤架上一次只能放2个汉堡。每个汉堡都需要两面烤，不管是烤一个汉堡还是同时烤两个汉堡，烤好一个汉堡的一面用时1分钟。假设要在最短的时间内完成该任务，考虑下列递归算法。如果n≤2，一个汉堡单独烤并翻面，两个汉堡则同时烤并翻面。如果n>2，两个汉堡同时烤并翻面，然后对余下的n-2个汉堡递归地应用同样的过程。

a.给出该算法烤n个汉堡所需要时间的递推关系并求解。

b.对于任意n>0个汉堡，该算法完成任务的时间并不是最少的，为什么?

c.给出一个在最少时间内完成烤汉堡任务的正确递归算法。

14.名人问题 n 个人中的名人是指这样一个人：他不认识别人，但是每个人都认识他。任务就是找出这样一个名人，但只能通过询问“你认识他/她吗?”这种问题来完成。设计一个高效算法，找出该名人或者确定这群人中没有名人。你的算法在最坏情况下需要问多少个问题?

1.解下列递推关系。

a. x(n)=x(n-1)+5, 其中n>1, x(1)=0：

b. x(n)=3x(n-1),其中n>1, x(1)=4

c. x(n)=x(n-1)+n,其中n>0, x(0)=0

d. x(n)=x(n/2)+n,其中n>1, x(1)=1(对于的情况求解)

e. x(n)=x(n/3)+1,其中n>1, x(1)=1(对于的情况求解)

2.对于计算n！的递归算法F(n)，建立其递归调用次数的递推关系并求解。

F(n)=F(n-1)+1,F(0)=1

3.考虑下列递归算法，该算法用来计算前n个立方的和：

算法 S(n) //输入：正整数n //输出：前n个立方的和 if n=l return l else return S(n-1)+n*n*n

a.建立该算法的基本操作执行次数的递推关系并求解。

此时有

递推关系如下：

b.如果将这个算法和直截了当的非递归算法比较，你做何评价?

非递归算法更优：

1. 空间效率更高（非递归 Θ(1)，递归 Θ(n)）
2. 运行速度更快（无函数调用开销）
3. 更节省内存，不会出现栈溢出问题

4.考虑下面的递归算法。

Q(n): if n == 1 return 1 else return Q(n-1) + 2*n - 1

a.建立该函数值的递推关系并求解，以确定该算法计算的是什么。

b.建立该算法所做的乘法运算次数的递推关系并求解。

结果为：

c.建立该算法所做的加减运算次数的递推关系并求解。

答案为：

5.汉诺塔谜题

a.汉诺塔谜题最早是由一个法国数学家卢卡斯于19世纪90年代提出的，当时的版本是这样的：当64个圆盘被从梵塔上移走时，世界末日也就来临了。如果祭司一分钟移动一个圆盘(假设该祭司不吃不睡，而且长生不老)，请估计一下，移走全部圆盘一共需要多少年?

递推如下：

约5849 亿年

b.在该算法中，要移动第i大的盘子(1≤i≤n)一共需要移动多少步?

规律

• 最大盘（第 n 号）：移动1次
• 次大盘：移动2次
• 第 3 大：4次
• ...
• 第 i 大：2^n−i次

c.为汉诺塔谜题设计一个非递归的算法，并用你熟悉的语言实现。

#include <stdio.h> #include <stdlib.h> // 栈元素：盘子数 + 三个柱子 typedef struct { int num; char src; char dest; char aux; } StackItem; StackItem stack[1000]; // 栈空间 int top = -1; // 栈顶指针 // 入栈 void push(int num, char src, char dest, char aux) { stack[++top].num = num; stack[top].src = src; stack[top].dest = dest; stack[top].aux = aux; } // 出栈 StackItem pop() { return stack[top--]; } // 非递归汉诺塔 void hanoi_non_recursive(int n) { push(n, 'A', 'C', 'B'); while (top != -1) { StackItem item = pop(); if (item.num == 1) { printf("移动盘子 1 从 %c 到 %c\n", item.src, item.dest); } else { // 逆序入栈，保证执行顺序正确 push(item.num - 1, item.aux, item.dest, item.src); push(1, item.src, item.dest, item.aux); push(item.num - 1, item.src, item.aux, item.dest); } } } int main() { int n; printf("请输入盘子数："); scanf("%d", &n); hanoi_non_recursive(n); return 0; }

6.受限汉诺塔 考虑以下版本的汉诺塔谜题：有n个圆盘需要从柱子A借助柱子B搬到柱子C，且任何移动要么把一个圆盘搬到柱子B或者从柱子B上搬走一个圆盘。(同样禁止把较大的圆盘放在较小的圆盘下面。)设计一个递归算法解决这个问题，并且确定实现它所需要的移动次数。

伪代码：

算法 RestrictedHanoi(n, A, B, C) // 把 n 个盘从 A 经 B 移到 C，仅允许 A↔B、B↔C if n = 1: 移动圆盘 1: A → B 移动圆盘 1: B → C else: RestrictedHanoi(n-1, A, B, C) // n-1个：A→C 移动圆盘 n: A → B RestrictedHanoi(n-1, C, B, A) // n-1个：C→A 移动圆盘 n: B → C RestrictedHanoi(n-1, A, B, C) // n-1个：A→C

移动次数为：

c语言实现：

#include <stdio.h> // 受限汉诺塔递归函数 // n: 盘子数 src:A aux:B dest:C void restrictedHanoi(int n, char src, char aux, char dest) { if (n == 1) { // 1个盘子：必须 A→B→C printf("移动盘子 %d：%c -> %c\n", n, src, aux); printf("移动盘子 %d：%c -> %c\n", n, aux, dest); return; } // 1. 把 n-1 个盘子 从 A 移到 C（经过B） restrictedHanoi(n-1, src, aux, dest); // 2. 把第 n 号大盘 从 A 移到 B printf("移动盘子 %d：%c -> %c\n", n, src, aux); // 3. 把 n-1 个盘子 从 C 移到 A（经过B） restrictedHanoi(n-1, dest, aux, src); // 4. 把第 n 号大盘 从 B 移到 C printf("移动盘子 %d：%c -> %c\n", n, aux, dest); // 5. 把 n-1 个盘子 从 A 移到 C（经过B） restrictedHanoi(n-1, src, aux, dest); } int main() { int n; printf("请输入盘子数量："); scanf("%d", &n); printf("\n受限汉诺塔移动步骤：\n"); restrictedHanoi(n, 'A', 'B', 'C'); // 总移动次数公式 printf("\n总移动次数：%d\n", (int)pow(3, n) - 1); return 0; }

7.

a.请证明，对于一个任意十进制正整数n来说，递归算法BinRec(n)所做的加法运算的精确次数是[log₂n]。

BinRec(n) if n = 1 return 1 else return BinRec(⌊n/2⌋) + (n mod 2)

功能：求十进制数 n 的二进制表示（递归）

其中，A[1]=0,因此递推结果为：

设2^n<=k<2^(k+1),则有

b.对于该算法的非递归版本，建立其所做的加法运算次数的递推关系并求解(参见2.3 节, 例4)。

非递归版：

while n > 1: 输出 n mod 2 n = n / 2 加法次数 +1

显然结论与递归版相同

8.

a.请基于公式设计一个递归算法。当n是任意非负整数时，该算法能够计算2^n的值。

伪代码：

算法 PowerOfTwo(n) // 输入：非负整数 n // 输出：2^n if n = 0 return 1 else return PowerOfTwo(n-1) + PowerOfTwo(n-1)

b.建立该算法所做的加法运算次数的递推关系并求解。

即对于递推式有C(n)=2(n/2)+1,C(0)=0;因此答案为：

c.为该算法构造一棵递归调用树，然后计算它所做的递归调用的次数。

树如图：

最终调用次数（实际上是算树的节点）为：

d.对于该问题的求解来说，这是一个好算法吗?

并非好算法，这个算法效率冗余到了2^n，过于低效，应该改为直接循环*2，保持在Θ(n)

9.考虑下面的递归算法。

算法 Riddle(A[0..n-1]) if n == 1 return A[0] else temp = Riddle(A[0..n-2]) if temp ≤ A[n-1] return temp else return A[n-1]

a.该算法计算的是什么?

该算法计算数组 A [0..n-1] 中的最小值。

b.建立该算法所做的基本操作次数的递推关系并求解。

最终答案为：

10.考虑下面的算法来检查一个由邻接矩阵表示的图是否是完全图。

算法 GraphComplete(A[0..n-1, 0..n-1]) //输入: 一个n阶无向图G的邻接矩阵A //输出：如果G是完全图，返回1；否则返回0 if n = 1 return 1 else if not GraphComplete(A[0..n-2, 0..n-2]) return 0 else for j ← 0 to n-2 do if A[n-1, j] = 0 return 0 return 1

这个算法最坏情况下的效率类型是什么?

最坏效率是Θ(n^2)

11.一个n阶方阵

的行列式记作detA。当n=1时，我们可以把它定义为a₀₀；当n>1时，则定义为下面的递推关系：

当j为偶数时，取+1；当j为奇数时，取-1。是位于第0行和第j列的元素，Aj是把第0行和第j列从矩阵A中删除后获得的n-1阶方阵。

a.假设有一个实现该定义的算法，建立该算法的乘法运算次数的递推关系并求解。

依题：

因此可得：M(n)∈Θ(n!)

b.不对该递推关系求解，你认为它的增长次数和n！相比会有什么结论?

乘法次数的增长次数是 Θ(n!)，与 n! 同阶

12.重温冯·诺依曼邻居问题 建立一个递推关系并求解，以计算n阶冯·诺依曼邻居的细胞数(参见习题2.3的第11题)。

13.烤汉堡 有n个汉堡需要在烤架上烤，但是烤架上一次只能放2个汉堡。每个汉堡都需要两面烤，不管是烤一个汉堡还是同时烤两个汉堡，烤好一个汉堡的一面用时1分钟。假设要在最短的时间内完成该任务，考虑下列递归算法。如果n≤2，一个汉堡单独烤并翻面，两个汉堡则同时烤并翻面。如果n>2，两个汉堡同时烤并翻面，然后对余下的n-2个汉堡递归地应用同样的过程。

a.给出该算法烤n个汉堡所需要时间的递推关系并求解。

所以

b.对于任意n>0个汉堡，该算法完成任务的时间并不是最少的，为什么?

当 n 为奇数（如 n=3）时，烤架未被充分利用，算法产生空闲时间，因此不是最优。

c.给出一个在最少时间内完成烤汉堡任务的正确递归算法。

算法 OptimalHamburger(n) // 输入：正整数 n // 输出：烤完 n 个汉堡的最短时间 if n == 1 return 2 // 1个汉堡必须2分钟 elif n == 2 return 2 // 2个汉堡2分钟 elif n == 3 return 3 // 3个汉堡最优3分钟 else // 每次最优处理2个，用2分钟，剩下递归 return 2 + OptimalHamburger(n - 2)

14.名人问题 n 个人中的名人是指这样一个人：他不认识别人，但是每个人都认识他。任务就是找出这样一个名人，但只能通过询问“你认识他/她吗?”这种问题来完成。设计一个高效算法，找出该名人或者确定这群人中没有名人。你的算法在最坏情况下需要问多少个问题?

算法 FindCelebrity(n) // 第一步：找出候选者 候选者 = 1 for i = 2 to n: if 候选者 认识 i: 候选者 = i // 原来的候选者被淘汰 // 第二步：验证候选者是不是真名人 for i = 1 to n: if i != 候选者 AND (候选者认识i OR i不认识候选者): 输出 "没有名人" return 输出 候选者

最坏情况下需要询问：3n−3 次

效率类型：Θ(n)