吳文虎《程序設(shè)計(jì)基礎(chǔ)第2版》PPT-08.ppt

1、1,青蛙過(guò)河,快速排序,分書問(wèn)題,計(jì)算組合數(shù),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 * / * 編制時(shí)間：2002年10月28日 * / * 主要功能：計(jì)算組和數(shù)C(m,n) * / * #include / 預(yù)編譯命令 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()/ 主函數(shù)開始 / 測(cè)試一些結(jié)果 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; / 主函數(shù)結(jié)束,7,遞 歸 算 法 舉 例青蛙過(guò)河,8,討論問(wèn)題青蛙過(guò)河,該題是2000年全國(guó)青少年信息學(xué)奧林匹克的一道試題。敘述如下： 一條

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

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

5、 R 上； 第三步：1# 再?gòu)暮扇~跳至 R 上。 如下圖： 1# 2#,11,當(dāng) y = 2 時(shí)， 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 )先看一個(gè)最簡(jiǎn)單情況： S = 1，y = 1 。 從圖上看出需要 9 步，跳過(guò) 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,為了將過(guò)河過(guò)程描述得更清楚，我們給出了表1。表中L1 L2 L3 L4表示左岸石柱上落在一起的青蛙的高度位置。L1 在最上面，L4 在最下面的位置。引入這個(gè)信息就可比較容易地看出對(duì)青蛙占位的約束條件。同理R1 R2 R3 R4也是如此。對(duì)水中石柱S，也分成兩個(gè)高度位置S1 S2。對(duì)荷葉Y無(wú)須分層，因?yàn)樗辉试S一只青蛙落在其上。t=0為初始時(shí)刻，青蛙從小到大落在石柱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清空。這時(shí)你看，S上有1#、2#，L上有3#、4#，好象是原來(lái)在L上的4只青蛙，分成了上下兩部分，上面的2只通過(guò)荷葉y轉(zhuǎn)移到了S上。這一過(guò)程是一分為二的過(guò)程。即將L上的一隊(duì)青蛙，分解為兩個(gè)隊(duì)，每隊(duì)各二只，且將上面的二只轉(zhuǎn)移到了S上。這時(shí)我們可以考慮形成兩個(gè)系統(tǒng)，一個(gè)是L，Y，R系統(tǒng)，一個(gè)是S，Y，R系統(tǒng)。前者二只青蛙號(hào)大；后者二只青蛙號(hào)小。先跳號(hào)大的，再跳號(hào)小的。從第五步到第九步可以看出的確是這么做的。,15,2,Y,R,S,L,3,1,16,L-Y-S ,將

8、L上的一半青蛙轉(zhuǎn)移到 S 上 L-Y-R,將 L上的青蛙轉(zhuǎn)移到 R 上 S-Y-R,將 S 上的青蛙轉(zhuǎn)移到 R 上 對(duì)于LYR系統(tǒng)，相當(dāng)于Jump(0,1)對(duì)于SYR系統(tǒng)，相當(dāng)于Jump(0,1) 兩個(gè)系統(tǒng)之和為2*Jump(0,1)，因此有：Jump(1,1)=2*Jump(0,1)=2*2=4,17,現(xiàn)在再看S=2，y=1 Jump(2,1) 我們將河中的兩個(gè)石柱稱作S1和S2，荷葉叫y，考慮先將L上的青蛙的一半借助于S2和y轉(zhuǎn)移到S1上，當(dāng)然是一半小號(hào)的青蛙在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為跳轉(zhuǎn)的目的地，從L經(jīng)S2Y到S1,相當(dāng)于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. 將上述分析出來(lái)的規(guī)律寫成遞歸形式的與或結(jié)點(diǎn)圖為：,27,舉例：S=3，y=4，算 Jump(3,4),28,/ * / * 程 序：6_5.cpp * / * 作 者：wuwh * / * 編制時(shí)間：2002年10月20日 * / * 主要功能：青蛙過(guò)河(遞歸) * / *,29,#include /預(yù)編譯命令 int Jump(int, int);/聲明有被調(diào)用函數(shù) int

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

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

13、z + 1 個(gè)元素從小到大排序。,33,z y k z m y m-1 m+1 z m-1 m m+1 y,34,我們畫出與或圖來(lái)闡述快速排序的思路：,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，則什么也不做。這是直接可解結(jié)點(diǎn)。 C 結(jié)點(diǎn)是在 z y 情況下 A 結(jié)點(diǎn)的解。C 是一個(gè)與結(jié)點(diǎn)。要對(duì) C 求解需分解為三步。依次為：,37,1、先解 D 結(jié)點(diǎn)，D 結(jié)點(diǎn)是一個(gè)直接可解結(jié)點(diǎn)，功能是進(jìn)行所謂的分區(qū)處理，規(guī)定這一步要做的事情是 （1）將 a z 中的

14、元素放到它應(yīng)該在的位置上，比如 m 位置。這時(shí) a m a z ； （2）讓下標(biāo)從 z 到 m-1 的數(shù)組元素小于等于a m ； （3）讓下標(biāo)從 m+1 到 y 的數(shù)組元素大于a m ； 比如 a 數(shù)組中 a z = 5，經(jīng)分組處理后，5 送至 a 4 。5 到位后，其左邊 a 0 a 3 的值都小于 5；其右邊 a 5 , a 6 都大于 5。 （見(jiàn)下圖）,38,a,z,y,a,m,下標(biāo)：,下標(biāo)：,z,m-1,y,m+1,39,2、再解 E 結(jié)點(diǎn)，這時(shí)要處理的是 a 0 a 3 ； 3、再解 F 結(jié)點(diǎn)，處理a 5 ,a 6 。 下面按照這種思路構(gòu)思一個(gè)快速排序的程序框圖。 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,下面舉例說(shuō)明排序過(guò)程,圖1 a數(shù)組中有7個(gè)元素待排序 1 讓 k = a z = a 0 = 5,z,y,圖 1,k,43,2 進(jìn)入直到型循環(huán) 執(zhí)行（1）ay=a6=4 不滿足當(dāng)循環(huán)條件，y不動(dòng)。 執(zhí)行（2）zy，做兩件事： a z = a y ，即a 0 = a 6 = 4， z = z +1 = 0+1 = 1，見(jiàn)圖2,z,y,圖 2,k,44,執(zhí)行（3）圖2中的a1 5,z,y,圖 3,k,45,執(zhí)行（4）ay=az，即a6=

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

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

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

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

20、 /函數(shù)體開始 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件事(結(jié)束),59,array z = k; /第3件事,k已排到位 for(i = zz ;i a i ; sort(a,0,9);/調(diào)用sort函數(shù),實(shí)參為數(shù)組a和0，9 cout 排序結(jié)果為:; /提示信息 for (i =0; i10 ;i+ ) cout a i ;/輸出排序結(jié)果 cout endl; return 0

21、; /主函數(shù)結(jié)束,60,void sort(int array , int zz, int yy) /被調(diào)用函數(shù)，數(shù)組array,zz,yy為形參 /函數(shù)體開始 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件事(結(jié)束),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件事結(jié)束 /函數(shù)體結(jié)束,68,int main() /主函數(shù)開始 int a10, i=0; /整型變量 cout a i ; sort( a, 0, 9 ) ; /調(diào)用sort函數(shù),實(shí)參為數(shù)組a和0,9 cout 排序結(jié)果為:; /提示信息 for (i =0; i10 ;i+ ) cout a i ;“; /輸出排序結(jié)果 coutendl; return 0

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