1、1,青蛙過河,快速排序,分書問題,計算組合數,6.4 遞歸算法舉例,2,3,mn| n=1 c(m,n) m=0|n=0 n=m n!=m 0 m 1 c(m-1,n) c(m-1,n-1) c(m-1,n)+ c(m-1,n-1),4,/ * / * 程 序 名：6_7.cpp * / * 編制時間：2002年10月28日 * / * 主要功能：計算組和數C(m,n) * / * #include / 預編譯命令 using namespace std;,5,int Cmn( int m, int n) if (m0 | n0 | mn) return 0; if (m=n) / C(m,m

2、)=1 return 1; if (n=1) / C(m,1)=m return m; return Cmn(m-1, n)+Cmn(m-1,n-1); ,6,int main()/ 主函數開始 / 測試一些結果 cout C(6,0)= Cmn(6,0) endl; cout C(6,1)= Cmn(6,1) endl; cout C(6,2)= Cmn(6,2) endl; cout C(6,6)= Cmn(6,6) endl; return 0; / 主函數結束,7,遞 歸 算 法 舉 例青蛙過河,8,討論問題青蛙過河,該題是2000年全國青少年信息學奧林匹克的一道試題。敘述如下： 一條

3、小溪尺寸不大，青蛙可以從左岸跳到右岸，在左岸有一石柱L，面積只容得下一只青蛙落腳，同樣右岸也有一石柱R，面積也只容得下一只青蛙落腳。有一隊青蛙從尺寸上一個比一個小。我們將青蛙從小到大，用1，2，n編號。規(guī)定初始時這隊青蛙只能趴在左岸的石頭L上，按編號一個落一個，小的落在大的上面。不允許大的在小的上面。在小溪中有S個石柱，有y片荷葉，規(guī)定溪中的柱子上允許一只青蛙落腳，如有多只同樣要求按編號一個落一個，大的在下，小的在上，而且必須編號相鄰。對于荷葉只允許一只青蛙落腳，不允許多只在其上。對于右岸的石柱R，與左岸的石柱L一樣允許多個青蛙落腳，但須一個落一個，小的在上，大的在下，且編號相鄰。當青蛙從左岸

4、的L上跳走后就不允許再跳回來；同樣，從左岸L上跳至右岸R，或從溪中荷葉或溪中石柱跳至右岸R上的青蛙也不允許再離開。問在已知溪中有S根石柱和y片荷葉的情況下，最多能跳過多少只青蛙？,9,思路： 1、簡化問題，探索規(guī)律。先從個別再到一般，要善于對多個因素作分解，孤立出一個一個因素來分析，化難為易。 2. 定義函數 Jump ( s ,y ) 最多可跳過河的青蛙數 其中：S 河中柱子數 y 荷葉數,10,3. 先看簡單情況，河中無柱子：S = 0 ， Jump ( 0 , y ) 當 y = 1 時，Jump ( 0 , 1 ) = 2 ； 第一步：1# 跳到荷葉上； 第二步：2# 從 L 直接跳至

5、 R 上； 第三步：1# 再從荷葉跳至 R 上。 如下圖： 1# 2#,11,當 y = 2 時， Jump ( 0 , 2 ) = 3 ； 1#，2#，3# 3只青蛙落在 L 上， 第一步：1# 從 L 跳至葉 1上， 第二步：2# 從 L 跳至葉 2上， 第三步：3# 從 L 直接跳至 R 上， 第四步：2# 從葉 2 跳至 R 上， 第五步：1# 從葉 1 跳至 R 上，,采用歸納法： Jump ( 0 , y ) = y+1；,12,再看Jump( S, y )先看一個最簡單情況： S = 1，y = 1 。 從圖上看出需要 9 步，跳過 4 只青蛙。 1# 青蛙從 L Y；2# 青蛙

6、從 L S；1# 青蛙從 Y S；3# 青蛙從 L Y；4# 青蛙從 L R；3# 青蛙從 Y R；1# 青蛙從 S Y；2# 青蛙從 S R；1# 青蛙從 Y R；,13,表一,14,為了將過河過程描述得更清楚，我們給出了表1。表中L1 L2 L3 L4表示左岸石柱上落在一起的青蛙的高度位置。L1 在最上面，L4 在最下面的位置。引入這個信息就可比較容易地看出對青蛙占位的約束條件。同理R1 R2 R3 R4也是如此。對水中石柱S，也分成兩個高度位置S1 S2。對荷葉Y無須分層，因為它只允許一只青蛙落在其上。t=0為初始時刻，青蛙從小到大落在石柱L上。t=1為第一步：1#從L跳至荷葉Y上；L上

7、只剩2# 3# 4#。T=2 為第二步；2#從L跳至石柱S上，處在S2位置上，L上只剩3#和4#。T=3為第三步，1#從Y跳至S，將Y清空。這時你看，S上有1#、2#，L上有3#、4#，好象是原來在L上的4只青蛙，分成了上下兩部分，上面的2只通過荷葉y轉移到了S上。這一過程是一分為二的過程。即將L上的一隊青蛙，分解為兩個隊，每隊各二只，且將上面的二只轉移到了S上。這時我們可以考慮形成兩個系統(tǒng)，一個是L，Y，R系統(tǒng)，一個是S，Y，R系統(tǒng)。前者二只青蛙號大；后者二只青蛙號小。先跳號大的，再跳號小的。從第五步到第九步可以看出的確是這么做的。,15,2,Y,R,S,L,3,1,16,L-Y-S ,將

8、L上的一半青蛙轉移到 S 上 L-Y-R,將 L上的青蛙轉移到 R 上 S-Y-R,將 S 上的青蛙轉移到 R 上 對于LYR系統(tǒng)，相當于Jump(0,1)對于SYR系統(tǒng)，相當于Jump(0,1) 兩個系統(tǒng)之和為2*Jump(0,1)，因此有：Jump(1,1)=2*Jump(0,1)=2*2=4,17,現在再看S=2，y=1 Jump(2,1) 我們將河中的兩個石柱稱作S1和S2，荷葉叫y，考慮先將L上的青蛙的一半借助于S2和y轉移到S1上，當然是一半小號的青蛙在S1上，大的留在L上。,18,S=2, y=1: S=S1+S2 S1=S2=S-1 L Y R S2 S1,19,S=2, y=

9、1: S=S1+S2 S1=S2=S-1 L Y R S2 S1 1,20,S=2, y=1: S=S1+S2 S1=S2=S-1 L Y R S2 S1 2 1,21,S=2, y=1: S=S1+S2 S1=S2=S-1 L Y R S2 S1 2 3 1,22,L-S2-Y-S1 以S1為跳轉的目的地，從L經S2Y到S1,相當于JAMP（1，1）=4, 即S1 上有4 只青蛙，L上還保留4 只。 1 2 Y 3 4 5 1 6 2 L 7 S2 1 3 S1 8 2 4,23,L,R,Y,S2,S1,24,L Y R S2 S1 LS2YR S1S2YR,25,這樣 L S1 S2 y

10、R 系統(tǒng)分解為 ： （L S2 y R 系統(tǒng)） + （S1 S2 y R 系統(tǒng)）= 2 * （L S2 y R 系統(tǒng)）= 2 * Jump(1,1) 用歸納法Jump(S, y)=2*Jump(S-1, y),26,5. 將上述分析出來的規(guī)律寫成遞歸形式的與或結點圖為：,27,舉例：S=3，y=4，算 Jump(3,4),28,/ * / * 程 序：6_5.cpp * / * 作 者：wuwh * / * 編制時間：2002年10月20日 * / * 主要功能：青蛙過河(遞歸) * / *,29,#include /預編譯命令 int Jump(int, int);/聲明有被調用函數 int

11、 main()/主函數 int s=0,y=0,sum=0; cout s;/輸入正整數s cout y;/輸入正整數y sum = Jump ( s , y ) ;/Jump(s,y)為被調用函數 cout Jump( s , /輸出結果 y )= sum endl; return 0; ,30,/以下函數是被主程序調用的函數 int Jump ( int r, int z )/自定義函數, r , z 為形參 /自定義函數體開始 int k=0;/整型變量 if (r=0) /如果 r 為 0 ,則為直接可解結點, k = z + 1;/直接可解結點, k 值為 z + 1 else /如

12、果r不為0,則要調用Jump( r-1, z ) k=2*Jump(r-1,z); return ( k ) ;/將 k 的值返回給 Jump ( s , y ) /自定義函數體結束,31,遞 歸 算 法 舉 例快速排序,32,快速排序的思路： 1、將待排序的數據放入數組 a 中，下標從 z 到 y ； 2、取 a z 放變量 k 中，通過分區(qū)處理，為 k 選擇應該排定的位置。這時要將比 k 大的數放右邊，比 k 小的數放左邊。當 k 到達最終位置后，由 k 劃分左右兩個集合。然后再用同樣的思路處理左集合與右集合。 3、令sort( z ,y )為將數組元素從下標為 z 到下標為 y 的 y

13、z + 1 個元素從小到大排序。,33,z y k z m y m-1 m+1 z m-1 m m+1 y,34,我們畫出與或圖來闡述快速排序的思路：,35,A sort( z,y ) z=y zy B C 不做事 D E F 分區(qū)處理 sort(z,m-1) sort(m+1,y),36,分區(qū)處理： k 1、讓 k=a z a = y，則什么也不做。這是直接可解結點。 C 結點是在 z y 情況下 A 結點的解。C 是一個與結點。要對 C 求解需分解為三步。依次為：,37,1、先解 D 結點，D 結點是一個直接可解結點，功能是進行所謂的分區(qū)處理，規(guī)定這一步要做的事情是 （1）將 a z 中的

14、元素放到它應該在的位置上，比如 m 位置。這時 a m a z ； （2）讓下標從 z 到 m-1 的數組元素小于等于a m ； （3）讓下標從 m+1 到 y 的數組元素大于a m ； 比如 a 數組中 a z = 5，經分組處理后，5 送至 a 4 。5 到位后，其左邊 a 0 a 3 的值都小于 5；其右邊 a 5 , a 6 都大于 5。 （見下圖）,38,a,z,y,a,m,下標：,下標：,z,m-1,y,m+1,39,2、再解 E 結點，這時要處理的是 a 0 a 3 ； 3、再解 F 結點，處理a 5 ,a 6 。 下面按照這種思路構思一個快速排序的程序框圖。 void sort

15、( int array , int zz, int yy ) int z, y, i , k ;,40,z,y,k,54,52,56,53,51,57,41,42,下面舉例說明排序過程,圖1 a數組中有7個元素待排序 1 讓 k = a z = a 0 = 5,z,y,圖 1,k,43,2 進入直到型循環(huán) 執(zhí)行（1）ay=a6=4 不滿足當循環(huán)條件，y不動。 執(zhí)行（2）zy，做兩件事： a z = a y ，即a 0 = a 6 = 4， z = z +1 = 0+1 = 1，見圖2,z,y,圖 2,k,44,執(zhí)行（3）圖2中的a1 5,z,y,圖 3,k,45,執(zhí)行（4）ay=az，即a6=

16、a2=6，見圖4。這時 z != y 還得執(zhí)行直到型循環(huán)的循環(huán)體。,z,y,圖 4,k,46,執(zhí)行（1）ay=a6=6，6k滿足當循環(huán)的條件， y = y-1 = 6-1 = 5 見圖5，之后退出當循環(huán)，因為 a y = 3k (k=5),z,y,圖 5,k,47,執(zhí)行（2）a z =a y ，并讓 z = z+1=3，見圖6,z,y,圖 6,k,48,執(zhí)行（3）由于a3=1k，退出循環(huán)。見圖7,z,y,圖 7,k,49,執(zhí)行（4）az=ay，a5=7。見圖8 這時仍然 zy ，應繼續(xù)執(zhí)行直到型循環(huán)的循環(huán)體。,z,y,圖 8,k,50,執(zhí)行（1），a y = 7k，讓 y = y-1 = 4。

17、見圖9,z,y,圖 9,k,51,之后，z = y，退出直到型循環(huán)，做 a z = k，z = 4， a 4 = 5，這是 5 的最終位置，5 將整個數據分成左右兩個集合，見圖10。,z,y,圖 10,左,右,k,52,用上述思路去排左邊的部分 從 z = 0 到 y = 3，見圖11。讓 k = a z = a 0 = 4，然后進到直到型循環(huán)， 執(zhí)行（1）a y = 1k，不滿足當循環(huán)的條件，y不動。 執(zhí)行（2）a z = a y ，z = z+1 = 1, 見圖12,z,y,圖 12,z,y,圖 11,k,53,執(zhí)行（3）a z k，z=z+1=2，a2k，z=z+1=3，這時z=y，不會

18、執(zhí)行（4），同時退出直到型循環(huán)，見圖13。然后做 a z =k，即a 3 =4，見圖14，左邊也排好了。,圖 14,z,y,圖 13,z,y,k,k,54,4、用上述思路去排右邊的部分，見圖15，讓k = a z = a 5 = 7，進入直到型循環(huán)； 執(zhí)行（1）a y = 6k，y不動 執(zhí)行（2）a z = a y =6，z = z+1=5+1=6，見圖16,圖 16,z,y,圖 15,z,y,k,55,這時 z = y，不再執(zhí)行（3）（4），退出直到型循環(huán)后，做 a z = k，見圖17。,圖 17,z,y,k,56,在有了遞歸調用函數之后，主程序很容易寫，主程序中應包含 1、 定義整型變量

19、：數組 a10 ，i ； 2、 用循環(huán)結構輸入待排序的數，將其放入 a 數組； 3、 調用 sort 函數，使用三個實際參數 a將數組 a 當實參； 0數組下標下界； 9數組下標上界； 4、 輸出排序結果 下面給出參考程序（分兩頁）,57,/ * / * 程 序：6_6.cpp * / * 作 者：wuwh * / * 編制時間：2002年10月28日 * / * 主要功能：快速排序 * / * #include /預編譯命令 using namespace std;,58,void sort(int array , int zz, int yy)/被調用函數，數組array,zz,yy為形參

20、 /函數體開始 int z,y,i,k; /定義變量 if ( zz=k) y-; /2.1,右邊的元素=k,讓 y 往中間移 if( z k, 讓 array z array y = array z ; /送給array y while( z != y ) ; /第2件事(結束),59,array z = k; /第3件事,k已排到位 for(i = zz ;i a i ; sort(a,0,9);/調用sort函數,實參為數組a和0，9 cout 排序結果為:; /提示信息 for (i =0; i10 ;i+ ) cout a i ;/輸出排序結果 cout endl; return 0

21、; /主函數結束,60,void sort(int array , int zz, int yy) /被調用函數，數組array,zz,yy為形參 /函數體開始 int z,y,i,k; /定義變量 if ( zzyy ) /如果 zz yy ,則做下列 7 件事:,61, / 7 件事開始 z = zz; y = yy; k = array z ; /第1件事,62,do /第2件事(開始) while( z=k) y-; /2.1,右邊的元素=k,讓 y 往中間移 if( z k, array y = array z ; while( z != y ) ; /第2件事(結束),63,k z

22、 y while(z=k) y- ; /2.1,右邊的元素=k,讓 y 往中間移,64,k z y if( z y ) array z = array y ; z = z+1; ,65,k z y while(zk; array y = array z ;,66,z y 5 2 6 1 7 3 4 z y 4 2 6 1 7 3 4 k z y 5 4 2 6 1 7 3 6 z y 4 2 3 1 7 3 6 z y 4 2 3 1 7 7 6 zy 4 2 3 1 5 7 6,67,array z = k; /第3件事,k已排到位 for(i = zz ;i = yy ;i+) /第4件事

23、，輸出 coutai=“ array i ; ; cout endl; /第5件事，換行 sort( array, zz ,z-1 ); /第6件事，排左邊部分 sort( array ,z+1, yy); /第7件事，排右邊部分 /7件事結束 /函數體結束,68,int main() /主函數開始 int a10, i=0; /整型變量 cout a i ; sort( a, 0, 9 ) ; /調用sort函數,實參為數組a和0,9 cout 排序結果為:; /提示信息 for (i =0; i10 ;i+ ) cout a i ;“; /輸出排序結果 coutendl; return 0

24、; /主函數結束,69,研究 sort( a , 0, 9 ) 主函數 調用 sort ( a , 0 , 9 ) 實在參數 子函數中 sort ( array, zz, yy ) 形式參數 a 0 9 Array zz yy 2、定義一個整型一維數組book5用來記錄書是否已被選用。用下標作為五本書的標號，被選過元素值為1，未被選過元素值為0，初始化皆置0。 int book5= 0,0,0,0,0 ;,解題思路：,77,3、畫出思路圖 定義 Try( i )試著給第 i 人分書 ( i=0, 1, 4 ),78,79,說明： （1）試著給第 i 個人分書，先試分 0 號書，再分 1 號書，分 2 號書，因此有一個與結點，讓 j 表示書 j = 0, 1, 2, 3 , 4 。 （2）LP 為循環(huán)結構的循環(huán)體。 （3）條件 C 是由兩部分“與”起來的?！暗?i 個人喜歡 j 書，且 j 書尚未被分走”。滿足這個條件是第 i 人能夠得到 j 書的條件。 （4）如果不滿足 C 條件，則什么也不做，這是直接可解結點