【正文】 2021/11/10 計算機算法設計與分析 1 第二章 遞歸與分治 2021/11/10 計算機算法設計與分析 2 遞歸的思想 ? 遞歸 (Recursion)就是通過把復雜問題分解為較簡單的同一問題來求解。 ? 遞歸求解問題的方法通常有兩步： ? 第一步是考慮最簡單的情況下該問題如何求解。 ? 第二步是考慮該問題的較復雜情況是如何由較簡單的所構成的。 ? 由此得出該問題求解的方法。 2021/11/10 計算機算法設計與分析 3 Hanoi塔問題 ? Hanoi塔問題：有 A、 B、 C三根柱子。 A上有 n個圓盤，自下而上由大到小地疊在一起。 ? 現(xiàn)要將 A上的全部圓盤移到 B上，并要求 ： ? (1)每次只能移動一個圓盤； ? (2)任何時刻都不允許將較大的圓盤壓在較小的圓盤上； ? (3)圓盤只能在 A、 B、 C三個柱子間移動。 如何解決此問題呢？ A B C 2021/11/10 計算機算法設計與分析 4 Hanoi塔問題 ? 讓我們先考慮最簡單的情況： ? 若沒有盤子 (n = 0)，自然不需要做任何事情。 A B C ? 若只有一個盤子，也很容易。直接把它移到 B盤即可。 ? 不妨設操作 Move(X, Y)將 X柱上的一個盤子 (最頂上的 )移到 Y柱上。 2021/11/10 計算機算法設計與分析 5 Hanoi塔問題 ? 讓我們先考慮最簡單的情況： ? 若沒有盤子 (n=0)，自然不需要做任何事情。 A B C ? 若只有一個盤子，也很容易。直接把它移到 B盤即可。 ? 不妨設操作 Move(X, Y)將 X柱上的一個盤子 (最頂上的 )移到 Y柱上。 ? 即通過操作 Move(A, B)即可實現(xiàn)。 2021/11/10 計算機算法設計與分析 6 Hanoi塔問題 ? 現(xiàn)在來考慮復雜的情況，即 n 1的情況。 A B C ? 怎樣將它變成 A柱上只有一個盤子，即 n = 1，呢？ ? 顯然應該先將 A柱上的 n – 1個盤子，移到 C柱上去。 2021/11/10 計算機算法設計與分析 7 Hanoi塔問題 ? 于是我們有了解決 n 1的的策略： A B C 2021/11/10 計算機算法設計與分析 8 Hanoi塔問題 ? 于是我們有了解決 n 1的的策略： A B C ? (1)先將 A上面 n–1個盤子移至 C。 2021/11/10 計算機算法設計與分析 9 Hanoi塔問題 ? 于是我們有了解決 n 1的的策略： A B C ? (1)先將 A上面 n–1個盤子移至 C。 ? (2)再將 A上面的 1個盤子移至 B。 2021/11/10 計算機算法設計與分析 10 Hanoi塔問題 ? 于是我們有了解決 n 1的的策略： A B C ? (1)先將 A上面 n–1個盤子移至 C。 ? (2)再將 A上面的 1個盤子移至 B。 ? (3)最后將 C上面 n–1個盤子移至 B。 第一步和第三步的移動都必須遵守 Hanoi塔移動的規(guī)則。 2021/11/10 計算機算法設計與分析 11 Hanoi塔問題 ? 我們用 Fr、 To和 As分別表示源柱、目標柱和輔助柱，解 Hanoi塔可以描寫為這樣的遞歸過程： ? 若 n = 0，什么也不做； 最簡單的情況 ? 若 n 0，則 ? ⑴用 Hanoi的方法將 Fr柱上的 n – 1個盤子移到 As柱上，用 To柱做輔助柱； ? ⑵將剩下的一個盤子從 Fr移到 To； ? ⑶用 Hanoi的方法將 As柱上的 n – 1個盤子移到 To柱上，用 Fr柱做輔助柱。 2021/11/10 計算機算法設計與分析 12 Hanoi塔問題 ? 若寫成 C語言，解 Hanoi塔可以描寫為這樣的遞歸過程： ? void Hanoi(int n, int Fr, int To, int As) ? { if (n 0) { ? Hanoi(n–1, Fro, Ass, To)。 ? Move(Fro, To)。 ? Hanoi(n–1, Ass, To, Fro)； ? } } 當 n ? 0時，遞歸終止，程序相當于 Skip語句。 2021/11/10 計算機算法設計與分析 13 Hanoi塔問題 ? Hanoi(3, A, B, C) { Hanoi(2, A, C, B)。 Move(A, B)。 Hanoi(2, C, B, A) } Hanoi(1, A, B, C)。 Move(A, C)。 Hanoi(1, B, C, A) Move(A, B)。 Move(B, C)。 Hanoi(1, C, A, B)。 Move(C, B)。 Hanoi(1, A, B, C) Move(C, A)。 Move(A, B)。 Move(A, C)。 Move(A, B)。 Move(C, B)。 2021/11/10 計算機算法設計與分析 14 Hanoi塔問題的時間復雜性 ? 不難證明 Hanoi塔問題的時間復雜性為 O(2n)。 ? 證明：對 n歸納證明移動次數(shù) move(n) = 2n – 1。 ? 歸納基礎：當 n = 1， move(1) = 1 = 21 – 1。 ? 歸納假設：當 n ? k， move(n) = 2n – 1。 ? 歸納步驟：當 n = k + 1，移動次數(shù)為 ? move(k+1) = 2(move(k)) + 1 = 2(2k – 1) + 1 ? = 2k+1 – 1 ? 由歸納法可知對任意的 n有 move(n) = 2n – 1。 2021/11/10 計算機算法設計與分析 15 遞歸的概念 ? 簡單地說，遞歸就是用自己來定義自己。 ? 一般地說，一個遞歸過程 P可以表示為基語句 S(不含 P)和 P自身的組合 β： P ? β(S, P)。 ? 這樣的表示包含了過程不終止的可能，因此遞歸算法應更準確地表述為 P ? if B then Q else β(S, P)， ? 其中 Q也不包含 P， B為遞歸終止條件。 2021/11/10 計算機算法設計與分析 16 遞歸元 ? 遞歸思想是將對較大規(guī)模的對象的操作歸結為對較小規(guī)模的對象實施同樣的操作。 ? 這種規(guī)模的變化體現(xiàn)在遞歸的參數(shù)表中的一類 (一個或幾個 )變元上，這類變元被稱之為遞歸元。 ? 在遞歸定義中遞歸元的變化應導致遞歸計算終止，即逐步變化為最簡單規(guī)模的計算。 ? 在遞歸算法的設計中遞歸元是非常重要的。 2021/11/10 計算機算法設計與分析 17 常見的遞歸形式 ? 除基本的遞歸形式外，其它常見的遞歸形式有四種，它們是： ? 多變元遞歸； ? 多步遞歸； ? 嵌套遞歸； ? 聯(lián)立遞歸 2021/11/10 計算機算法設計與分析 18 多變元遞歸 ? 多變元遞歸就是遞歸元多于一個的遞歸。 ? 例如，求最大公約數(shù)的輾轉相除法： GCD(x, y) = y, x = 0 x , y = 0 GCD(x – y, y), x ? y GCD(x, y – x), x y ? 其中 x和 y都是遞歸元。 最簡單的情況有兩種 2021/11/10 計算機算法設計與分析 19 多步遞歸 ? 若遞歸函數(shù) f(x, y)，其中 y是遞歸元，不僅與 f(x, y–1)有關，而且與 f(x, y–2)， …… ，乃至 f(x, 0)有關，則稱為多步遞歸。 ? 例如 Fibonacci函數(shù)： 1 n = 0 F(n) = 1 n = 1 F(n–1) + F(n–2) n 1 ? Fibonacci函數(shù)是一個兩步的遞歸函數(shù)。 2021/11/10 計算機算法設計與分析 20 嵌套遞歸 ? 所謂嵌套遞歸是指遞歸調用中又含有遞歸調用，又稱為多重遞歸。 ? 例如 Ackermann函數(shù)： y + 1 x = 0 A(x, y) = A(x–1, 1) y = 0 A(x–1, A(x, y–1)) x, y 0 ? Ackermann函數(shù)是一個雙重的遞歸函數(shù)。同時它也是個二元遞歸。 2021/11/10 計算機算法設計與分析 21 聯(lián)立遞歸 ? 聯(lián)立遞歸是同時定義幾個函數(shù)，它們彼此相互調用，從而形成遞歸，又稱間接遞歸。 ? 例如 Hilbert圖案，下面為 H1， H2和 H3： H1 H2 H3 2021/11/10 計算機算法設計與分析 22 Hilbert圖案 ? 將 Hi記為 Ai，將 Hi旋轉 90176。 , 180176。 和 270176。后的圖形分別記為 Bi， Ci和 Di，其中一、二級曲線如下所示： A1 B1 C1 D1 A2 D1 A1 A1 B1 B2 C1 B1 B1 A1 C2 B1 C1 C1 D1 D2 A1 D1 D1 C1 2021/11/10 計算機算法設計與分析 23 Hilbert圖案 ? 于是得出這些子曲線逐級間的關系如下： Ai+1： Di Ai Ai Bi Bi+1： Ci Bi Bi Ai Ci+1： Bi Ci Ci Di Di+1： Ai Di Di Ci 其中，箭頭表示曲線移動的方向， ? 于是 便可寫出畫這些曲線的遞歸子程序。 可將 0級的 Hilbert曲線視為一個點。 2021/11/10 計算機算法設計與分析 24 Hilbert圖案 A(i) { if (i 0) { D(i – 1)。 x = x – h。 ploting(x, y) 。 A(i – 1)。 y = y – h。 ploting(x, y) 。 A(i – 1)。 x = x + h。 ploting(x, y) 。 B(i – 1)。 }} //*ploting(x, y)是從畫筆現(xiàn)行坐標到坐標 (x, y)畫條直線。 *// ? 類似地可以寫出畫 B、 C和 D的曲線的子程序。 ? 畫 Hilbert曲線的程序在調用 A之前還應有一些初始化的工作，如計算 h，移動畫筆至起點等。 Ai+1： Di Ai Ai Bi ? 依據(jù) 有畫 A的子程序： 2021/11/10 計算機算法設計與分析 25 遞歸方法小結 ? 遞歸方法是將復雜問題分解為較為簡單的子問題的組合，且子問題與原問題相似。 ? 遞歸算法中必有一個或幾個最簡情況的計算 (非遞歸分支 )，若缺少或者不完備將造成遞歸不終止。 ? 遞歸算法中遞歸元必須隨遞歸的進程變化到最簡情況，保證導致非遞歸分支的計算。 ? 遞歸算法具有層次性，低層的解組合成高層的解。各層間最好通過參數(shù)傳遞來交流信息，如使用全局量，則要注意全局量的及時修訂。 2021/11/10 計算機算法設計與分析 26 遞歸復雜性的一般形式 ? 一般的，遞歸復雜性可描述為遞歸方程： 1 n = 1 af(n ~ b) + D(n) n＞ 1 f(n) = ? 其中， a是子問題個數(shù)， ~表示遞減方式， b是遞減步長， D(n)是合成子問題的開銷。 ? 顯然影響 f(n)的因素有：遞減方式 ~、 子問題個數(shù) a ，步長 b、以及合成開銷 D(n) 。 ? 我們先來看看遞減方式 ~這個因素。 2021/11/10 計算機算法設計與分析 27 遞歸復雜性的一般形式 ? 一般的，遞歸復雜性可描述為遞歸方程： 1 n = 1 af(n ~ b) + D(n) n＞ 1 f(n) =