C語(yǔ)言：1.9遞推與遞歸

1、遞推與遞歸1內(nèi)容摘要遞推算法遞歸算法計(jì)算組合數(shù)漢諾塔問(wèn)題快速排序問(wèn)題遞歸思想遞推與遞歸2遞推算法例題：古有善切餅者，名庖丙，庖丁之弟也。把一張大餅置于板上，不許離開，每一刀切下去都是一條直線。問(wèn)切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í)塊數(shù)是14遞推算法編寫函數(shù)cutpie求解

2、切n刀后得到的塊數(shù)5遞推算法將復(fù)雜運(yùn)算分解為若干重復(fù)的簡(jiǎn)單運(yùn)算后一步驟建立于前一步驟之上計(jì)算每一步驟的方法相同從開始向后計(jì)算出結(jié)果使用循環(huán)結(jié)構(gòu)，通過(guò)多次循環(huán)逐漸逼近結(jié)果a(i)a(i+1) = a(i) + i;a(0)a(1)a(n) 6遞推算法練習(xí)：遞推數(shù)列：數(shù)列的每一項(xiàng)都可以通過(guò)前面若干項(xiàng)計(jì)算生成，可用遞推公式定義練習(xí)：階乘：1!, 2!, 3!, 4!, , (n-1)!, n!a(n) = n * a(n-1)/第n項(xiàng)通過(guò)第n-1項(xiàng)乘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五兄弟要來(lái)分。A先來(lái)了后把棗子平均分成5份后發(fā)現(xiàn)多出1個(gè)，就取走了其中一份和多出來(lái)的1個(gè)。B來(lái)后把剩下的棗子平均分成5份發(fā)現(xiàn)多出1個(gè)，就取走了其中一份和多出來(lái)的1個(gè)。CDE來(lái)了之后，分別使用同樣的做法。編程求解最初至少有多少棗子。思路提示：BCDE看到的個(gè)數(shù)肯定應(yīng)該是4的倍數(shù)每人都能把棗子分成5份多一個(gè)，說(shuō)明他們看到的棗子數(shù)應(yīng)該是5的倍數(shù)加1從小到大找到一個(gè)同時(shí)滿足上面條件的數(shù)，即為E看到的數(shù)目8遞推算法9遞歸算法若一個(gè)過(guò)程直接或間接的調(diào)用自己，這個(gè)過(guò)程就是遞歸的過(guò)程一個(gè)比較復(fù)雜的問(wèn)題，如果可以分解成為幾個(gè)相對(duì)簡(jiǎn)單或規(guī)模較小且解法相同或類似的子問(wèn)題

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

5、計(jì)算cutpie(2)+3 返回(7)參數(shù)：4 計(jì)算cutpie(3)+4 返回(11)main函數(shù)參數(shù)：0 直接返回1 返回(1)12遞歸算法練習(xí)：使用遞歸方法求解斐波那契數(shù)列第n項(xiàng)a(n);練習(xí)：用遞歸方法求兩個(gè)整數(shù)m和n的最大公約若 m%n 為零是，n是m和n的最大公約數(shù)若 m%n 不為零，n和m%n 的最大公約數(shù)即為m和n的最大公約數(shù)練習(xí)：用遞歸的方法求整數(shù)1n的前n項(xiàng)和練習(xí)：讓用戶從鍵盤輸入10個(gè)整數(shù)，逆序顯示示例輸入：1 2 3 4 5 9 10 0 9 8示例輸出：8 9 0 10 9 5 4 3 2 1練習(xí)：從鍵盤輸入底邊長(zhǎng)，在屏幕上打印倒三角形13計(jì)算組合數(shù)編程實(shí)現(xiàn)組合計(jì)數(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個(gè)球取出來(lái)的n個(gè)，包含兩種情況：n在其中和n不在其中編程實(shí)現(xiàn)使用遞歸思想編寫遞歸函數(shù) int cmn(int m, int n)14計(jì)算組合數(shù)15漢諾塔問(wèn)題據(jù)說(shuō)在古代印度bramah神廟中，有個(gè)和尚整天把3根柱子上的金盤倒來(lái)倒去。初始在柱子A上有64個(gè)盤子串在一起，每一個(gè)盤子都比它下面的盤子小，可以在ABC三個(gè)柱子之間互相移動(dòng)，最終要全部移動(dòng)到柱子C上。移動(dòng)規(guī)則如下：每次只允許移動(dòng)一個(gè)，且較大的盤子永遠(yuǎn)不能放在較小的盤子上。如果每秒移動(dòng)一個(gè)的話，移

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

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