程序設計綜合實踐　第三講　遞歸與分治

1、程序設計綜合實踐03 遞歸與分治趙中堂內容遞歸函數(shù)課本74頁分治法課本223頁練習題1、遞歸函數(shù)遞歸：recursion函數(shù)：function1、遞歸（recursion）函數(shù)（1）什么是遞歸函數(shù)直接或者間接調用自身的函數(shù)稱為遞歸函數(shù)。1、遞歸函數(shù)（2）具有明顯遞歸性質的問題求n！=n*(n-1)*(n-2)*.*1f(n)=1 n=1n*f(n-1) n11、遞歸函數(shù)（2）具有明顯遞歸性質的問題求n！=n*(n-1)*(n-2)*.*1int f(int n)if(n=1)return 1;elsereturn n*f(n-1);f(n)=1 n=1n*f(n-1) n11、遞歸函數(shù)（3）遞

2、歸方法的基本原理將復雜問題逐步化簡，最終轉化為一個最簡單的問題最簡單問題的解決，就意味著整個問題的解決 （4）遞歸調用應該能在有限次數(shù)內終止遞歸遞歸調用如果不加以限制，將無數(shù)次的循環(huán)調用必須在函數(shù)內部加控制語句，只有當滿足一定條件時，遞歸終止1、遞歸函數(shù)（5）任何一個遞歸調用程序必須包括兩部分遞歸調用結束部分遞歸循環(huán)繼續(xù)部分2、分治法Divide and Conquer分而治之（1）、分治法的基本思想對于一個規(guī)模為n的問題，若該問題可以容易地解決(比如說規(guī)模n較小)，則直接解決；否則將其分解為k個規(guī)模較小的子問題（這些子問題互相獨立且與原問題形式相同）遞歸地解這些子問題， 然后將各子問題的解合

3、并，得到原問題的解。這種算法設計策略叫做分治法(divide and conquer)。 分治法在每一層遞歸上由三個步驟組成： 1) 劃分(divide)：將原問題分解為若干規(guī)模較小、 相互獨立、 與原問題形式相同的子問題。 2) 解決(conquer)： 若子問題規(guī)模較小，則直接求解；否則遞歸求解各子問題。 3) 合并(combine)： 將各子問題的解合并為原問題的解。 （2）分治法的一般步驟它的一般算法設計范型如下： DIVIDE&CONQUER (P) 1 if （|P|c）/問題P的規(guī)模小于c 2 return(DSOLVE(P) else 把問題 P 分成k個子問題： P1, P2

4、, , Pk4 for（i=1;i=k;i+) 5 si DIVIDE&CONQUER(Pi) SCOMBINE(s1, s2, , sk) return S （3）分治法的設計范型 從分治法的一般設計模式可以看出， 直接用它設計出的算法是一個遞歸算法。1）、在數(shù)組A中尋找最大值2）、二叉樹遍歷、二分查找算法、歸并排序、快速排序等算法數(shù)據(jù)結構課程中講解（4）、常見的分治算法int max(int *A,int start, int end)/在數(shù)組A的下標start和end之間尋找最大值算法描述：如果start=end, return Astart;取start和end的中間mid分別在sta

5、rt,mid和mid+1,end中尋找最大值假設start,mid之間的最大值為max1假設mid+1，end之間的最大值為max2max1、max2的最大值就是數(shù)組A的最大值1）、求數(shù)組中的最大值#include int max(int *A,int start, int end)if(start=end)return Astart;elseint max1,max2,mid;mid=(start+end)/2;max1=max(A,start,mid);max2=max(A,mid+1,end);if(max1max2)return max1;elsereturn max2;1）、求數(shù)組中

6、的最大值int main()int a=1,4,6,2,5,3;int max0,min0;int n;n=sizeof(a)/sizeof(int);max0=max(a,0,n-1);printf(max=%dn,max0);return 0;1）求數(shù)組中的最大值3、練習題（1）、設計遞歸函數(shù)，求菲波納契數(shù)列的第n項的值fib(n)=1 n=1fib(n-1)+fib(n-2) n21 n=2參考答案：int fib(int n)if(n=1 | n=2)return 1;elsereturn fib(n-1)+fib(n-2);（2）設計遞歸函數(shù)，求m、n的最大公約數(shù)gcd(m,n)=n m%n=0gcd(