程序設(shè)計(jì)綜合實(shí)踐　第三講　遞歸與分治

1、程序設(shè)計(jì)綜合實(shí)踐03 遞歸與分治趙中堂內(nèi)容遞歸函數(shù)課本74頁(yè)分治法課本223頁(yè)練習(xí)題1、遞歸函數(shù)遞歸：recursion函數(shù)：function1、遞歸（recursion）函數(shù)（1）什么是遞歸函數(shù)直接或者間接調(diào)用自身的函數(shù)稱為遞歸函數(shù)。1、遞歸函數(shù)（2）具有明顯遞歸性質(zhì)的問(wèn)題求n！=n*(n-1)*(n-2)*.*1f(n)=1 n=1n*f(n-1) n11、遞歸函數(shù)（2）具有明顯遞歸性質(zhì)的問(wèn)題求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、歸方法的基本原理將復(fù)雜問(wèn)題逐步化簡(jiǎn)，最終轉(zhuǎn)化為一個(gè)最簡(jiǎn)單的問(wèn)題最簡(jiǎn)單問(wèn)題的解決，就意味著整個(gè)問(wèn)題的解決 （4）遞歸調(diào)用應(yīng)該能在有限次數(shù)內(nèi)終止遞歸遞歸調(diào)用如果不加以限制，將無(wú)數(shù)次的循環(huán)調(diào)用必須在函數(shù)內(nèi)部加控制語(yǔ)句，只有當(dāng)滿足一定條件時(shí)，遞歸終止1、遞歸函數(shù)（5）任何一個(gè)遞歸調(diào)用程序必須包括兩部分遞歸調(diào)用結(jié)束部分遞歸循環(huán)繼續(xù)部分2、分治法Divide and Conquer分而治之（1）、分治法的基本思想對(duì)于一個(gè)規(guī)模為n的問(wèn)題，若該問(wèn)題可以容易地解決(比如說(shuō)規(guī)模n較小)，則直接解決；否則將其分解為k個(gè)規(guī)模較小的子問(wèn)題（這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同）遞歸地解這些子問(wèn)題， 然后將各子問(wèn)題的解合

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

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

5、rt,mid和mid+1,end中尋找最大值假設(shè)start,mid之間的最大值為max1假設(shè)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、練習(xí)題（1）、設(shè)計(jì)遞歸函數(shù)，求菲波納契數(shù)列的第n項(xiàng)的值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è)計(jì)遞歸函數(shù)，求m、n的最大公約數(shù)gcd(m,n)=n m%n=0gcd(