C語言：1.9遞推與遞歸

1、遞推與遞歸1內(nèi)容摘要遞推算法遞歸算法計算組合數(shù)漢諾塔問題快速排序問題遞歸思想遞推與遞歸2遞推算法例題：古有善切餅者，名庖丙，庖丁之弟也。把一張大餅置于板上，不許離開，每一刀切下去都是一條直線。問切20刀最多能分成多少塊？3遞推算法a(n) 表示切n刀可以分成的塊數(shù)a(1) = 1 + 1 = 2/切第1刀多出1塊a(2) = 2 + 2 = 4/切第2刀多出2塊a(3) = 4 + 3 = 7/切第3刀多出3塊a(4) = 7 + 4 = 11/切第4刀多出4塊歸納后得到規(guī)律：a(n) = a(n-1) + n/切第n刀多出n塊a(0) = 1/不切時塊數(shù)是14遞推算法編寫函數(shù)cutpie求解

2、切n刀后得到的塊數(shù)5遞推算法將復(fù)雜運算分解為若干重復(fù)的簡單運算后一步驟建立于前一步驟之上計算每一步驟的方法相同從開始向后計算出結(jié)果使用循環(huán)結(jié)構(gòu)，通過多次循環(huán)逐漸逼近結(jié)果a(i)a(i+1) = a(i) + i;a(0)a(1)a(n) 6遞推算法練習(xí)：遞推數(shù)列：數(shù)列的每一項都可以通過前面若干項計算生成，可用遞推公式定義練習(xí)：階乘：1!, 2!, 3!, 4!, , (n-1)!, n!a(n) = n * a(n-1)/第n項通過第n-1項乘n得到a(1) = 1練習(xí)：斐波那契數(shù)列：1, 1, 2, 3, 5, 8 a(n) = a(n-1) + a(n-2)a(0) = a(1) = 17

3、遞推算法練習(xí)：老人死后留下一堆棗子，ABCDE五兄弟要來分。A先來了后把棗子平均分成5份后發(fā)現(xiàn)多出1個，就取走了其中一份和多出來的1個。B來后把剩下的棗子平均分成5份發(fā)現(xiàn)多出1個，就取走了其中一份和多出來的1個。CDE來了之后，分別使用同樣的做法。編程求解最初至少有多少棗子。思路提示：BCDE看到的個數(shù)肯定應(yīng)該是4的倍數(shù)每人都能把棗子分成5份多一個，說明他們看到的棗子數(shù)應(yīng)該是5的倍數(shù)加1從小到大找到一個同時滿足上面條件的數(shù)，即為E看到的數(shù)目8遞推算法9遞歸算法若一個過程直接或間接的調(diào)用自己，這個過程就是遞歸的過程一個比較復(fù)雜的問題，如果可以分解成為幾個相對簡單或規(guī)模較小且解法相同或類似的子問題

4、時，只要解決了這些子問題，那么原來的問題也就可以解決了。這種策略稱為分而治之法比如：求10！，只要求出子問題 9!, 乘上10就得到了10!;要求 9!, 只要求出了8!, 乘上9就得到了9! 當(dāng)分解出的子問題可以直接解決時，就停止分解。直接可以解決的子問題稱為遞歸結(jié)束條件。比如：0! = 1就是結(jié)束條件遞歸過程可以通過編寫自我調(diào)用的遞歸函數(shù)來簡單的解決10遞歸算法切餅問題 a(n) = a(n-1) + n也可用以下遞歸方法求解n=0，返回1n0, 返回 n-1 的結(jié)果加上n11遞歸算法參數(shù)：1 計算cutpie(0)+1 返回(2)參數(shù)：2 計算cutpie(1)+2 返回(4)參數(shù)：3

5、計算cutpie(2)+3 返回(7)參數(shù)：4 計算cutpie(3)+4 返回(11)main函數(shù)參數(shù)：0 直接返回1 返回(1)12遞歸算法練習(xí)：使用遞歸方法求解斐波那契數(shù)列第n項a(n);練習(xí)：用遞歸方法求兩個整數(shù)m和n的最大公約若 m%n 為零是，n是m和n的最大公約數(shù)若 m%n 不為零，n和m%n 的最大公約數(shù)即為m和n的最大公約數(shù)練習(xí)：用遞歸的方法求整數(shù)1n的前n項和練習(xí)：讓用戶從鍵盤輸入10個整數(shù)，逆序顯示示例輸入：1 2 3 4 5 9 10 0 9 8示例輸出：8 9 0 10 9 5 4 3 2 1練習(xí)：從鍵盤輸入底邊長，在屏幕上打印倒三角形13計算組合數(shù)編程實現(xiàn)組合計數(shù)C

6、(10, 3)C(m,n) = 1;當(dāng)m=nC(m,n) = m;當(dāng)n=1C(m,n) = C(m-1, n) + C(m-1, n-1)思路提示m個球取出來的n個，包含兩種情況：n在其中和n不在其中編程實現(xiàn)使用遞歸思想編寫遞歸函數(shù) int cmn(int m, int n)14計算組合數(shù)15漢諾塔問題據(jù)說在古代印度bramah神廟中，有個和尚整天把3根柱子上的金盤倒來倒去。初始在柱子A上有64個盤子串在一起，每一個盤子都比它下面的盤子小，可以在ABC三個柱子之間互相移動，最終要全部移動到柱子C上。移動規(guī)則如下：每次只允許移動一個，且較大的盤子永遠不能放在較小的盤子上。如果每秒移動一個的話，移

7、完需要5800億年。若初始時盤子數(shù)是n, 編程求出移動的過程盤子從小到大（從上到下）編號依次為1, 2 n-1, n16漢諾塔問題假如n=1，直接移動到C假如n=2，則需要先把1號盤移到B上，再把2號盤移動到C上，最后把1號盤移動到C上。(1)(2)(3)17漢諾塔問題假如初始時有n個盤，把1到n-1看作一個整體第一步把n-1個盤子，從A借助C移動到B第二步把第n個盤子，從A移動到B第三步把n-1個盤子，從B借助A移動到C編寫遞歸函數(shù)void move(int n, char x1, char x2, char x3)表示x1上有n個盤，move函數(shù)需要把n個盤從x1上移動到x3上；x2上無盤

8、，或x2上任何一個盤都比較x1上的所有的盤大；移動過程可以借助x218漢諾塔問題19快速排序問題快速排序思路如下將要排序的數(shù)據(jù)放在數(shù)組array中取a0變在變量m中，通過分區(qū)處理把m排在適當(dāng)?shù)奈恢?，使m左邊的數(shù)都比m小，m右邊的數(shù)都比m大按照常上面的思路分別處理m左邊和右邊的數(shù)據(jù)如果分區(qū)長度是1，停止處理使用遞歸函數(shù)編程void qsort(int array, int start, int end)把數(shù)組下標(biāo)為start到end的元素進行快速排序20快速排序問題57381426273814562538147624381576243518762431587614325876123458761234567821快速排序問題22遞歸思想遞歸定義階乘函數(shù) a(n+1) = a(n) * (n+1)冪函數(shù) (n+1)! = n! * (n+1)斐波那契數(shù)列 f(n) = f(n-1) + f(n-2)遞歸數(shù)據(jù)結(jié)構(gòu)鏈表結(jié)構(gòu)，結(jié)點next指向的也是一個鏈表樹結(jié)構(gòu)，每個結(jié)點下面都是一棵子樹遞歸算法漢諾塔解法快速排序23遞推與遞歸遞推算法從頭開始，通過循環(huán)迭代逐漸逼近結(jié)果使用循環(huán)語句執(zhí)行效率高不易理解和寫程序循環(huán)加大程序的復(fù)雜程序遞歸算法到著開始，每一次遞歸都縮小問題規(guī)模，直到問題足夠小使用選擇分支語句多