《算法设计与分析》第二版，李春葆，课后题详解
1 绪论
2 递归
2.1 练习题
1 什么是直接递归和间接递归，消除递归一般用到什么数据结构
直接递归：p函数内部调用p函数
间接递归：p函数内部调用q函数，q函数内部调用p函数
消除递归通常使用栈这种数据结构
2 分析程序执行结果
#include <stdio.h>
void f(int n, int &m) {
if (n < 1) {
return;
}
printf("调用f(%d, %d)前，n=%d，m=%d\n", n - 1, m - 1, n, m);
n--;
m--;
f(n - 1, m);
printf("调用f(%d, %d)后，n=%d，m=%d\n", n - 1, m - 1, n, m);
}
int main() {
int n = 4, m = 4;
f(n, m);
return 0;
}
3 采用直接推导法求解以下递归方程T(1) = 1 T(n) = T(n - 1) + n 当n>1时
推导：
T(n) = T(n - 1) + n
= T(n - 2) + (n - 1) + n
= T(n - 3) + (n - 2) + (n - 1) + n
= ...
= T(1) + 2 + 3 + ... + (n - 2) + (n - 1) + n
= 1 + 2 + 3 + ... + (n - 2) + (n - 1) + n
= (1 + n)n/2
4 特征方程求解以下递归方程H(0) = 0 H(1) = 1 H(2) = 2 H(n) = H(n - 1) + 9H(n - 2) - 9H(n - 3) 当n>2时
解：
设H(n) = x^n
原式可以化简为：
x^n = x^(n - 1) + 9x^(n - 2) - 9x^(n - 3)
化简得：
x^3 - x^2 - 9x + 9 = 0
求得：
x1 = 3, x2 = -3, x3 = 1
故H(n) = a3^n + b(-3)^n + c
将H(0), H(1), H(2)三个特解带入，求出未知数a、b、c
a = 1/3
b = -1/12
c = -1/4
5 递归树求解递归方程T(1) = 1 T(n) = 4T(n/2) + n 当n>1时
所以该递归方程T(n) = 2n2(n>1时)，时间复杂度O(n2)
注意：一共是1+log2n层
6 采用主方法求解以下递归T(n) = 1 T(n) = 4T(n/2) + n^2
7 分析斐波那契数列f(n)的时间复杂度
已知斐波那契数列的递归表达式
Fib(0) = 0 n=0
Fib(1) = Fib(2) = 1 n=1或2
Fib(n) = Fib(n - 1) + Fib(n - 2) n>2
使用特征方程求解该递归：
令Fib(n)=x^n，化简得：
x^n = x^(n-1) + x^(n-2)
x^2=x+1
得到特征方程的根是：
x1 = (1 + sqrt(5)) / 2
x2 = (1 - sqrt(5)) / 2
得到递推式的解：
Fib(n) = ax1^n + bx2^n
带入特解（n=1,n=2,n=0）求a,b
a = 1 / sqrt(5)
b = -1 / sqrt(5)
最终递推式结果：
f(n) ≈ ((1 + sqrt(5))^n) / (sqrt(5) * 2^n) ≈ 1.618^n / sqrt(5)
可以看到，斐波那契数列时间复杂度是指数级别的，这也是为什么平常写斐波那契数列，都会用迭代法、公式法去解决的原因
8 数列首项a1 = 0，后序奇数项和偶数项计算公式如下：a2n = a2n-1 + 2，a2n+1 = a2n-1 + a2n - 1，写成计算数列第n项的递归算法
/**
* 第八题
* @param n 第几项
* @return
*/
int question8(int n) {
if(n == 1) {
return 0;
}
return n % 2 == 0 ? 2 + question8(n - 1) : question8(n - 1) + question8(n - 2) - 1;
}
9 对于一个采用字符数组存放的字符串str，设计一个递归算法求其长度
/**
* 判断下标i位置是否是结束位置
* @param str 字符数组
* @param i 字符数组下标
*/
void helper9(char str[], int & i) {
// 字符串尚未结束
if(str[i] != '\0') {
i++;
helper(str, i);
}
}
/**
* 第9题
* @param str
* @return
*/
int question9(char str[]) {
int i = 0;
helper9(str, i);
return i;
}
10 字符数组，递归判断是否是回文字符串
#include <cstring>
bool question10(char str[]) {
return helper10(str, 0, strlen(str) - 1);
}
/**
* 判断str字符数组[i,j]下标范围是否是回文
* @param str
* @param i
* @param j
* @return
*/
bool helper10(char str[], int i, int j) {
// 不断递归比较,左右边界相遇后交错,仍未false,说明是回文
if(i > j) {
return true;
}
if(str[i] != str[j]) {
return false;
}
// 如果i,j端点处字符相同,收缩判断
return helper10(str, i + 1, j - 1);
}
11 对于不带头结点的单链表L，设计一个递归算法正序输出所有结点值
#include <iostream>
using namespace std;
class Node {
private:
int data;
Node * next;
public: 省略set、get、以及构造
}
/**
* 正序输出无头结点链表结点值
* @param node
*/
void question11(Node * node) {
// 输出当前结点
cout << node->getData() << endl;
if(node->getNext() != nullptr) {
question11(node->getNext());
}
}
12 对于不带头结点的单链表L，设计递归算法，逆序输出所有结点值(类比二叉树前、中、后序遍历的递归写法，就是输出语句的位置变一变)
/**
* 正序输出无头结点链表结点值
* @param node
*/
void question12(Node * node) {
if(node->getNext() != nullptr) {
question11(node->getNext());
}
// 输出当前结点
cout << node->getData() << endl;
}
13 无头结点的单链表L，设计递归算法返回最大值结点的地址（可以假设最大值结点唯一）
Node * question13(Node * node) {
Node * maxNode = node;
helper13(node, maxNode);
return maxNode;
}
void helper13(Node * node, Node * &maxNode) {
if(node->getData() > maxNode->getData()) {
maxNode = node;
}
if(node->getNext() != nullptr) {
helper13(node->getNext(), maxNode);
}
}
14 设计一个递归算法，从无头结点的单链表中找到第一个值为x的结点，找不到返回null
/**
* 查找无头单链表中值为x的结点
* @param node
* @param x
* @return
*/
Node * question14(Node * node, int x) {
// 当前结点就是要找的结点
if(node->getData() == x) {
return node;
}
// 是否还有结点供递归查找
if(node->getNext() == nullptr){
return nullptr;
}
return question14(node->getNext(), x);
}
15 不带头结点的单链表，设计递归算法，删除第一个值为x的结点
/**
* 删除无头结点单链表中第一个值为x的结点
* @param preNode
* @param curNode
* @param x
*/
void question15(Node * preNode, Node * &curNode, int x) {
if(curNode == nullptr) {
return;
}
// 没有找到目标结点
if(curNode->getData() != x) {
Node * p = curNode->getNext();
question15(curNode, p, x);
return;
}
// 说明目标结点是首结点
if(preNode == nullptr) {
curNode = curNode->getNext();
} else {
preNode->setNext(curNode->getNext());
free(curNode);
}
}
16 二叉树采用二叉链表存储，结点值int，递归求二叉树叶子结点总和
/**
* 求二叉树叶子结点总和
* @param root
* @return
*/
int question16(TreeNode * root) {
int ret = 0;
helper16(root, ret);
return ret;
}
void helper16(TreeNode * root, int &ret) {
if(root == nullptr) {
return;
}
helper16(root->getLeft(), ret);
helper16(root->getRight(), ret);
// 如果是叶子
if(root->getLeft() == nullptr && root->getRight() == nullptr) {
ret += root->getData();
}
}
17 二叉树采用二叉链表存储，结点值int，递归求二叉树结点值大于k的结点数量
/**
* 第17题
* @param root
* @param k
* @return
*/
int question17(TreeNode * root, int k) {
int cnt = 0;
helper17(root, k, cnt);
return cnt;
}
void helper17(TreeNode * root, int k, int & cnt) {
if(root == nullptr) {
return;
}
helper17(root->getLeft(), k, cnt);
helper17(root->getRight(), k, cnt);
if(root->getData() >= k) {
cnt++;
}
}
18 二叉链表结构存储的二叉树，每个结点值不同，递归算法求值为x的结点所在层数，根节点是第一层，找不到返回0
/**
* 第18题
* @param root
* @param x
* @return
*/
int question18(TreeNode * root, int x) {
int ret = 0;
helper18(root, x, 1, ret);
return ret;
}
/**
* @param node 当前结点
* @param x 目标值
* @param level 当前结点在第几层
* @param ret 用来保存目标值所在层的变量
*/
void helper18(TreeNode * node, int x, int level, int & ret) {
if(node == nullptr) {
return;
}
if(node->getData() == x) {
ret = level;
return;
}
// 找左子树
helper18(node->getLeft(), x, level + 1, ret);
// 左子树没找到的话找右子树
if(ret == 0) {
helper18(node->getRight(), x, level + 1, ret);
}
}
2.2 上机实验题
1 递归逆置无头结点单链表
Node * question1(Node * node) {
if(node== nullptr || node->getNext() == nullptr) {
return node;
}
Node * newHead = question1(node->getNext());
node->getNext()->setNext(node);
node->setNext(nullptr);
return newHead;
}
2 递归判断两个二叉树是否同构。T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的，比如图1同构，图2不同构
/**
* 判断两棵树是否同构
* @param bt1
* @param bt2
* @return
*/
bool question2(TreeNode * bt1, TreeNode * bt2) {
// 两棵树为空，同构
if(bt1 == nullptr && bt2 == nullptr) {
return true;
}
// 一空一不空，不同构
if((bt1 != nullptr && bt2 == nullptr) || (bt1 == nullptr && bt2 != nullptr)) {
return false;
}
// 数据不同，不同构
if(bt1->getData() != bt2->getData()) {
return false;
}
// 左子树为空,判断右子树
if(bt1->getLeft() == nullptr && bt2->getLeft() == nullptr) {
return question2(bt1->getRight(), bt2->getRight());
}
// 判断两棵树的当前结点对应位置左右孩子是否一致
if(bt1->getLeft() != nullptr
&& bt2->getLeft() != nullptr
&& bt1->getLeft()->getData() == bt2->getLeft()->getData()
) {
return question2(bt1->getLeft(), bt2->getLeft())
&& question2(bt1->getRight(),bt2->getRight());
} else {
return question2(bt1->getLeft(), bt2->getRight())
&& question2(bt1->getRight(),bt2->getLeft());
}
}
3 递归求二叉树中最大路径（根结点到叶子）和
int question3(TreeNode *bt) {
if(bt == nullptr) {
return 0;
}
return bt->getData() + max(question3(bt->getLeft()) , question3(bt->getRight()));
}
4 输出与表达树等价的中缀表达式，通过括号表达运算符的先后顺序
string question4(TreeNode *root) {
if (root == nullptr) {
return "";
}
if (root->getLeft() == nullptr && root->getRight() == nullptr) {
return string(1,root->getData());
}
string ret(1, "(");
// 得到左表达式
string leftExpression = question4(root->getLeft());
ret.append(leftExpression).append(string(1,root->getData()));
return ret.append(question4(root->getRight())).append(")");
}
5 求两个正整数的最大公约数，递归与非递归
int gcd(int a, int b) {
return a % b == 0 ? b : gcd(b, a % b);
}
int gcd2(int a, int b) {
while(a % b) {
int c = a % b;
if(c == 0) {
return b;
}
a = b;
b = c;
}
return b;
}
2.3 在线编程题
1 求解n阶螺旋矩阵问题
int **spiralMatrix(int n) {
// 保存螺旋矩阵的二维数组
// 初始化该二维矩阵
int **a = new int *[n];
for (int i = 0; i < n; i++) {
*(a + i) = new int[n];
}
// 计数器
int counter = 1;
// 模拟螺旋,上-右-下-左逐个赋值
for (int row = 0; row < (n + 1) >> 1; row++) {
// 赋值上横一线
for (int col = row; col < n - row; col++) {
a[row][col] = counter++;
}
// 赋值右竖一线
int rightCol = n - row - 1;
for (int k = row + 1; k < n - row; k++) {
a[k][rightCol] = counter++;
}
// 赋值下横一线
int bottomRow = n - row - 1;
for (int k = rightCol - 1; k >= row; k--) {
a[bottomRow][k] = counter++;
}
// 赋值左竖一线
for (int k = bottomRow - 1; k > row; k--) {
a[k][row] = counter++;
}
}
return a;
}
/**
* 统计≤n的幸运数数量
* @param n
* @return
*/
int luckyNumber(int n) {
int ret = 0;
for(int i = 0; i <= n; ++i) {
if(gx(i) == fx(i)) {
// 输出幸运数
// cout << i << endl;
ret++;
}
}
return ret;
}
/**
* 获取n各个位置和
* @param n
* @return
*/
int fx(int n) {
int ret = 0;
while (n) {
ret += n % 10;
n /= 10;
}
return ret;
}
/**
* n二进制表示下有多少个1
* @param n
* @return
*/
int gx(int n) {
int ret = 0;
while(n) {
if(n & 1) ret++;
n >>= 1;
}
return ret;
}
/**
* 处理成回文的操作有几次
* @param arr
* @param len
* @param count
* @return
*/
int dealHuiwen(int arr[], int &len, int count) {
// 长度不足1一定是回文序列
if (len <= 1) return count;
// 倘若有首尾相同的，肯定是最终回文序列中的一员，进行删除
// 剩下的，就是需要处理成回文的序列
while (arr[0] == arr[len - 1]) {
delArrItem(arr, len, 0);
delArrItem(arr, len, len - 1);
}
if (len > 1) {
if (arr[0] > arr[len - 1]) {
reverseArr(arr, len);
}
// 进行操作
arr[0] += arr[1];
delArrItem(arr, len, 1);
count++;
count = dealHuiwen(arr, len, count);
}
return count;
}
/**
* 逆序数组
* @param arr
* @param len
*/
void reverseArr(int arr[], int len) {
int mid = len >> 1;
for (int i = 0; i < mid; ++i) {
int temp = arr[i];
arr[i] = arr[len - i - 1];
arr[len - i - 1] = temp;
}
}
/**
* 删除index位置的元素
* @param arr
* @param len
* @param index
*/
void delArrItem(int arr[], int &len, int index) {
for (int i = index; i < len - 1; ++i) {
arr[i] = arr[i + 1];
}
len--;
}
// 这是一个很糟糕的递归，指数级别的时间复杂度
// 可以用迭代法或者动态规划去将时间复杂度降为O(n)
int dice(int n) {
if(n < 0) {
return 0;
}
if(n <= 1) {
return 1;
}
return dice(n - 1) + dice(n - 2) + dice(n - 3) + dice(n - 4) + dice(n - 5) + dice(n - 6);
}
int dice1(int n) {
int dp[n + 1];
for(int i = 0; i <= n; ++i) dp[i] = 0;
dp[0] = dp[1] = 1;
for(int i = 2; i <= n; ++i) {
for(int j = i - 1, step = 0; j >= 0 && step < 6; --j, ++step) {
dp[i] += dp[j];
}
}
return dp[n];
}
3 分治
4 暴力
5 回朔法
6 分枝限界法
7 贪心
8 动态规划
9 图
10 计算几何
11 计算复杂性理论简述
12 概率算法和近似算法