C語言：1.9遞推與遞歸.ppt

,主講老師： 歐陽堅(jiān),歡迎您到（千鋒學(xué)院）來學(xué)習(xí)! 遞推與遞歸,內(nèi)容摘要,遞推算法 遞歸算法 計(jì)算組合數(shù) 漢諾塔問題 快速排序問題 遞歸思想 遞推與遞歸,遞推算法,例題：古有善切餅者，名庖丙，庖丁之弟也。把一張大餅置于板上，不許離開，每一刀切下去都是一條直線。問切20刀最多能分成多少塊？,遞推算法,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ù)是1,遞推算法,編寫函數(shù)cutpie求解切n刀后得到的塊數(shù),遞推算法,將復(fù)雜運(yùn)算分解為若干重復(fù)的簡單運(yùn)算 后一步驟建立于前一步驟之上 計(jì)算每一步驟的方法相同 從開始向后計(jì)算出結(jié)果 使用循環(huán)結(jié)構(gòu)，通過多次循環(huán)逐漸逼近結(jié)果,a(i),a(i+1) = a(i) + i;,a(0),a(1),a(n), ,遞推算法,練習(xí)：遞推數(shù)列：數(shù)列的每一項(xiàng)都可以通過前面若干項(xiàng)計(jì)算生成，可用遞推公式定義 練習(xí)：階乘：1!, 2!, 3!, 4!, , (n-1)!, n! a(n) = n * a(n-1) /第n項(xiàng)通過第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) = 1,遞推算法,練習(xí)：老人死后留下一堆棗子，ABCDE五兄弟要來分。A先來了后把棗子平均分成5份后發(fā)現(xiàn)多出1個(gè)，就取走了其中一份和多出來的1個(gè)。B來后把剩下的棗子平均分成5份發(fā)現(xiàn)多出1個(gè)，就取走了其中一份和多出來的1個(gè)。CDE來了之后，分別使用同樣的做法。編程求解最初至少有多少棗子。 思路提示： BCDE看到的個(gè)數(shù)肯定應(yīng)該是4的倍數(shù) 每人都能把棗子分成5份多一個(gè)，說明他們看到的棗子數(shù)應(yīng)該是5的倍數(shù)加1 從小到大找到一個(gè)同時(shí)滿足上面條件的數(shù)，即為E看到的數(shù)目,遞推算法,遞歸算法,若一個(gè)過程直接或間接的調(diào)用自己，這個(gè)過程就是遞歸的過程 一個(gè)比較復(fù)雜的問題，如果可以分解成為幾個(gè)相對(duì)簡單或規(guī)模較小且解法相同或類似的子問題時(shí)，只要解決了這些子問題，那么原來的問題也就可以解決了。這種策略稱為分而治之法 比如：求10！，只要求出子問題 9!, 乘上10就得到了10!;要求 9!, 只要求出了8!, 乘上9就得到了9! 當(dāng)分解出的子問題可以直接解決時(shí)，就停止分解。直接可以解決的子問題稱為遞歸結(jié)束條件。比如：0! = 1就是結(jié)束條件 遞歸過程可以通過編寫自我調(diào)用的遞歸函數(shù)來簡單的解決,遞歸算法,切餅問題 a(n) = a(n-1) + n也可用以下遞歸方法求解 n=0，返回1 n0, 返回 n-1 的結(jié)果加上n,遞歸算法,參數(shù)：1 計(jì)算cutpie(0)+1 返回(2),參數(shù)：2 計(jì)算cutpie(1)+2 返回(4),參數(shù)：3 計(jì)算cutpie(2)+3 返回(7),參數(shù)：4 計(jì)算cutpie(3)+4 返回(11),main函數(shù),參數(shù)：0 直接返回1 返回(1),遞歸算法,練習(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í)：從鍵盤輸入底邊長，在屏幕上打印倒三角形,計(jì)算組合數(shù),編程實(shí)現(xiàn)組合計(jì)數(shù)C(10, 3) C(m,n) = 1; 當(dāng)m=n C(m,n) = m; 當(dāng)n=1 C(m,n) = C(m-1, n) + C(m-1, n-1) 思路提示 m個(gè)球取出來的n個(gè)，包含兩種情況：n在其中和n不在其中 編程實(shí)現(xiàn) 使用遞歸思想 編寫遞歸函數(shù) int cmn(int m, int n),計(jì)算組合數(shù),漢諾塔問題,據(jù)說在古代印度bramah神廟中，有個(gè)和尚整天把3根柱子上的金盤倒來倒去。初始在柱子A上有64個(gè)盤子串在一起，每一個(gè)盤子都比它下面的盤子小，可以在ABC三個(gè)柱子之間互相移動(dòng)，最終要全部移動(dòng)到柱子C上。移動(dòng)規(guī)則如下：每次只允許移動(dòng)一個(gè)，且較大的盤子永遠(yuǎn)不能放在較小的盤子上。 如果每秒移動(dòng)一個(gè)的話，移完需要5800億年。 若初始時(shí)盤子數(shù)是n, 編程求出移動(dòng)的過程 盤子從小到大（從上到下）編號(hào)依次為1, 2 n-1, 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),漢諾塔問題,假如初始時(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上無盤，或x2上任何一個(gè)盤都比較x1上的所有的盤大； 移動(dòng)過程可以借助x2,漢諾塔問題,快速排序問題,快速排序思路如下 將要排序的數(shù)據(jù)放在數(shù)組array中 取a0變?cè)谧兞縨中，通過分區(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的元素進(jìn)行快速排序,快速排序問題,5,7,3,8,1,4,2,6,2,7,3,8,1,4,5,6,2,5,3,8,1,4,7,6,2,4,3,8,1,5,7,6,2,4,3,5,1,8,7,6,2,4,3,1,5,8,7,6,1,4,3,2,5,8,7,6,1,2,3,4,5,8,7,6,1,2,3,4,5,6,7,8,快速排序問題,遞歸思想,遞歸定義 階乘函數(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)下面都是一棵子樹 遞歸算法 漢諾塔解法 快速排序,遞推與遞歸,遞推算法 從頭開始，通過循環(huán)迭代逐漸逼近結(jié)果 使用循環(huán)語句 執(zhí)行效率高 不易理解和寫程序 循環(huán)加大程序的復(fù)雜程序 遞歸算法 到著開始，每一次遞歸都縮小問題規(guī)模，直到問題足夠小 使用