《算法設計與分析》第二版，李春葆，課後題詳解
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 機率算法和近似算法