C++與程式邏輯訓練 (1)

6. 遞迴方法

6. 遞迴方法

Quote "To iterate is human, to recurse divine." -- L. Peter Deutsch

「遞迴只應天上有，凡人應當用迴圈」--P老師

基本上，遞迴就是在同一個函式裡頭經過若干輾轉再次呼叫自己(but with 不同的參數)，就叫做遞迴。如果你去 google search 遞迴，它就會問你說「你要找的是不是遞迴？」

6.1 遞迴兩件事

1

遞迴最重要的就是「遞迴關係」和「終止條件」。有了可靠的這兩個東西之後，我們就不用考慮全局，只要關心我們目前關心的部份就好。

2

遞迴方法、數學歸納法、動態規劃其實是一體三面。Keep this in mind.

6.2 所有教科書上都有的死板例子

[ 練習] 計算階乘

題目敘述

給你一個整數 $0\le n \le 12$ ，請輸出 $n!$ 的值。

提示

利用 $n! = n \times (n-1)!$ 來解題。初始條件 $0! = 1$ 。

測試輸入

測試輸出

延伸思考

萬一輸入條件的 $0\le n\le 20$ 怎麼辦？
(!) 萬一輸入條件的 $0\le n\le 100$ 怎麼辦？

[ 練習] 費事數列

題目敘述

費式數列的定義是 $F_0 = 0, F_1 = 1, F_{n+2} = F_{n+1} + F_n$ 。現在給你一個整數 $0\le n \le 45$ ，請輸出 $F_n$ 的值。

測試輸入

測試輸出

延伸思考

萬一輸入條件的 $0\le n\le 90$ 怎麼辦？
(!)萬一輸入條件的 $0\le n\le 10^{12}$ ，只要輸出前 5 位數，怎麼辦？
(!)萬一輸入條件的 $0\le n\le 10^{12}$ ，只要輸出最末 5 位數，怎麼辦？
(!)萬一輸入條件改成 $0\le n\le 10^{100000}$ ，但是要輸出 $F_{F_n}$ 的最末 5 位數，怎麼辦？
(!) [ 習題 6.2.1] CF 126D - Fibonacci Sums

快速排序法 Quick Sort

這東西就是「分而治之法 Divide and Conquer」的基本應用。如果各位有興趣的話，我們之後會更深入探討這一系列的課題。

6.3 有些教科書會有的死板例子

[ 練習] 河內塔問題

題目敘述

你有一疊 $n$ 個圓盤(編號由小到大分別是 $1, 2, \cdots, n$ )，以及三根柱子 $A, B, C$ 。這些圓盤一開始由小到大排好在 $A$ 柱上面，如下圖所示。每一次我們可以將某一根柱子上的最上面圓盤，移動到相鄰的柱子上，但是移動後，仍須保證圓盤在每一根柱子上由小到大排列。請你給出一系列如下面格式的指令：move disk i from A to B，使得我們可以將所有圓盤從 $A$ 柱搬到 $C$ 柱。

程式碼範本

#include <iostream>
using namespace std;

void hanoi( /* 請定義你想要的參數 parameters */ ) {

    /* 請在這邊填上遞迴終止條件 */

    /* 請在這邊寫上你的遞迴關係 */

    return;
}

int main(void) {
    int n;
    cin >> n;

    hanoi( /* 請傳入你想要的引數 arguments */ );

    return 0;
}

延伸練習

[ 習題 6.3.1] UVa 10017 - The never ending towers of Hanoi
(!)[ 習題 6.3.2] UVa 254 - Towers of Hanoi
(!)[ 習題 6.3.3] CF 392B - Towers of Hanoi

[ 練習] L形鋪磚問題

題目敘述

[ 練習] 求最大公因數

給定兩個正整數 $n, m$ ，我們想要找出最大的正整數 $d = \gcd(n, m)$ ，可以同時整除這兩個數字。

利用關係式 $\gcd(n, m) = \gcd(n-m, m)$ 來解題！

[ 練習] 二元一次不定方程

給你兩個互質的正整數 $A, B$ ，我們想要找出某兩個整數 $x$ 以及 $y$ 使得 $Ax+By = 1$ 。

6.4 基本上教科書不會提及的例子--習題

[ 習題] TIOJ 1004 - 約瑟夫問題

於第一世紀時，猶太人受制於羅馬帝國，一批愛國志士反叛羅馬帝國，最後僅剩下 $41$ 人受困於山洞。這 $41$ 人不想受辱於羅馬帝國，又不想自殺，因此決定圍成一個圓圈，由1號開始將2號殺掉；3號將4號殺掉，依此類推，即由前一個殺掉下一個，欲將全團 $41$ 人全部殉戰而亡。然而，最後必定會剩下一人。試問哪一號最後得以苟且偷生？如果有 $n$ 個人圍成一圓圈，誰得以殘留餘命呢？

[ 習題] 摺紙問題

我們把一長條的紙，每一次很平均地向左摺，摺了 $n$ 次以後，全部展開。從側面看過去我們可以知道從紙的一側往另一側前進時，會依序「左轉」或「右轉」。現在給你 $n$ 以及位置 $x$ ，請你輸出第 $x$ 個褶痕所在的位置是左轉還是右轉。

[ 習題] 行列式問題

我們可以利用行列式值的遞迴關係，來求出行列式值。在這個矩陣很稀疏的時候，我們這樣計算會比較快得到結果。

[ 習題] 丟失的數

現在有 $a_1, a_2, \cdots, a_n$ ，總共 $n$ 個數字，它們都來自 $1$ 到 $n+1$ 這些數字之中，都不重複。我們想要從中找出哪一個數字不見了，但是，我們不能夠直接知道每一個數字是什麼！相對地，我們每一次可以花一塊錢，問得第 $k$ 個數字寫成二進位之後第 $i$ 位數是多少。你能夠花費盡量少的錢確認缺少的是哪一個數字嗎？

[ 習題] 刻度尺的對齊

有一種有趣的刻度尺，若我們將整數 $i$ 表示成二進位，則第 $i$ 個刻痕的長度恰好就是最右邊的 $1$ 所在的位數。例如第 $6$ 個刻痕我們可以寫成 $6=(110)_2$ ，則刻痕長度為 $2$ ；依此類推我們可以知道前 $10$ 個刻痕的長度分別是 $1, 2, 1, 3, 1, 2, 1, 4, 1, 2$ ，現在給你兩個區間 $[l_1, r_1]$ 以及 $[l_2, r_2]$ ，我們將這兩個區間所對應到的刻痕長度記錄下來，得到兩個序列 $a_1, a_2, \cdots$ 以及 $b_1, b_2, \cdots$ 。請你求出這兩個序列的最常共同部分連續子序列。