1、會計學1計算機程序設計基礎計算機程序設計基礎第七講第七講21111,125;123nmnnnmmmnm nmmnCmnCCCCC習題：已知表示從 個元素中取 個的組合數，又知、試畫出符合上述關系的與或結合圖；、指出哪個是直接可解結點；、畫出求解結點圖；4、寫出遞歸程序求解組合問題。第1頁/共53頁3遞 歸 算 法 舉 例青蛙過河第2頁/共53頁4討論問題青蛙過河該題是2000年全國青少年信息學奧林匹克的一道試題。敘述如下：一條小溪尺寸不大，青蛙可以從左岸跳到右岸，在左岸有一石柱L，面積只容得下一只青蛙落腳，同樣右岸也有一石柱R，面積也只容得下一只青蛙落腳。有一隊青蛙從尺寸上一個比一個小。我們將

2、青蛙從小到大，用1，2，n編號。規定初始時這隊青蛙只能趴在左岸的石頭L上，當然是一個落一個，小的落在大的上面。不允許大的在小的上面。在小溪中有S個石柱，有y片荷葉，規定溪中的柱子上允許一只青蛙落腳，如有多只同樣要求一個落一個，大的在下，小的在上。對于荷葉只允許一只青蛙落腳，不允許多只在其上。對于右岸的石柱R，與左岸的石柱L一樣允許多個青蛙落腳，但須一個落一個，小的在上，大的在下。當青蛙從左岸的L上跳走后就不允許再跳回來；同樣，從左岸L上跳至右岸R，或從溪中荷葉或溪中石柱跳至右岸R上的青蛙也不允許再離開。問在已知溪中有S根石柱和y片荷葉的情況下，最多能跳過多少只青蛙？第3頁/共53頁5這題看起來

3、較難，但是如果我們認真分析，理出思路，就可化難為易。思路：1、簡化問題，探索規律。先從個別再到一般，要善于對多個因素作分解，孤立出一個一個因素來分析，化難為易。2. 定義函數 Jump(S,y) 最多可跳過河的青蛙數 其中：S 河中柱子數 y 荷葉數第4頁/共53頁63. 先看簡單情況，河中無柱子：S=0，Jump(0,y) 當y=1時，Jump(0,1)=2； 說明：河中有一片荷葉，可以過兩只青蛙，起始時L上有兩只青蛙，1#在2#上面。 第一步：1# 跳到荷葉上； 第二步：2# 從L直接跳至R上； 第三步：1# 再從荷葉跳至R上。 如下圖：2#2#1#1#2 21 13 3L L左岸左岸R

4、R右岸右岸第5頁/共53頁7當y=2時， Jump(0,2)=3； 說明：河中有兩片荷葉時，可以過3只青蛙。起始時： 1#，2#，3# 3只青蛙落在L上， 第一步：1# 從L跳至葉 1上， 第二步：2# 從L跳至葉 2上， 第三步：3# 從L直接跳至R上， 第四步：2# 從葉2跳至R上， 第五步：1# 從葉1跳至R上，葉1葉13 31 15 5L LR R葉2葉22 24 4采用歸納法：Jump(0,y)=y+1； 意思是：在河中沒有石柱的情況下，過河的青蛙數僅取決于荷葉數，數目是荷葉數+1。第6頁/共53頁8再看Jump(S, y)先看一個最簡單情況： S=1，y=1。從圖上看出需要9步，跳

5、過4只青蛙。1# 青蛙從 L Y；2# 青蛙從 L S；1# 青蛙從 Y S；3# 青蛙從 L Y；4# 青蛙從 L R；3# 青蛙從 Y R；1# 青蛙從 S Y；2# 青蛙從 S R；1# 青蛙從 Y R；S SY Y5 54 46 6L LR R1 12 23 37 78 89 91#2#4#3#3#1#2#1#1#第7頁/共53頁9表一第8頁/共53頁10 為了將過河過程描述得更清楚，我們給出了表1。表中L1 L2 L3 L4表示左岸石柱上落在一起的青蛙的高度位置。L1 在最上面，L4 在最下面的位置。引入這個信息就可比較容易地看出對青蛙占位的約束條件。同理R1 R2 R3 R4也是如

6、此。對水中石柱S，也分成兩個高度位置S1 S2。對荷葉Y無須分層，因為它只允許一只青蛙落在其上。t=0為初始時刻，青蛙從小到大落在石柱L上。t=1為第一步：1#從L跳至荷葉Y上；L上只剩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上。這是我們可以考慮形成兩個系統，一個是L，Y，R系統，

7、一個是S，Y，R系統。前者二只青蛙號大；后者二只青蛙號小。先跳號大的，再跳號小的。從第五步到第九步可以看出的確是這么做的。第9頁/共53頁11對于LYR系統，相當于Jump(0,1)對于SYR系統，相當于Jump(0,1) 兩個系統之和為2*Jump(0,1)，因此有：Jump(1,1)=2*Jump(0,1)=2*2=4。現在再看S=2，y=1 Jump(2,1) 我們將河中的兩個石柱稱作S1和S2，荷葉叫y，考慮先將L上的青蛙的一半借助于S2和y轉移到S1上，當然是一半小號的青蛙在S1上，大的留在L上。y yLR RS1S1S2S2第10頁/共53頁12這樣 L S1 S2 y R 系統分

8、解為 ： （L S2 y R 系統） + （S1 S2 y R 系統）= 2 * （L S2 y R 系統）= 2 * Jump(1,1)用歸納法Jump(S, y)=2*Jump(S-1, y)第11頁/共53頁135. 將上述分析出來的規律寫成遞歸形式的與或結點圖為：Jump(S,y)y+1S!=0S=0Jump(S-1,y)2*Jump(S-1,y)第12頁/共53頁14舉例：S=3，y=4，算 Jump(3,4)A=Jump(2,4)2*B2*10=20Jump(3,4)2*A2*20=402*C2*5=10C=Jump(0,4)S=04+1 5B=Jump(1,4)3(3,4)2 (

9、1)2 (4 1)40SJumpy第13頁/共53頁15#include /預編譯命令int Jump(int, int);/聲明有被調用函數void main()/主函數/主程序開始int s,y,sum;/整型變量,s為河中石柱數,y為荷葉數printf(請輸入石柱數s= );/提示信息scanf(%d,&s);/輸入正整數sprintf(請輸入荷葉數y= );/提示信息scanf(%d,&y);/輸入正整數ysum=Jump(s,y);/Jump(s,y)為被調用函數printf(“Jump(%d,%d)=%dn,s,y,sum); /輸出結果/主程序結束/以下函數是被主程序調用的函數i

10、nt Jump(int r,int z)/整型自定義函數,r,z為形參/自定義函數體開始int k;/整型變量if (r=0)/如果r為0,則為直接可解結點,k=z+1;/直接可解結點,k值為z+1else/如果不為1,則要調用Jump(r-1,z) k=2*Jump(r-1,z);/計算Jump(r-1,z)再乘以2賦給kreturn(k);/將k的值返回給Jump(s,y)/自定義函數體結束第14頁/共53頁16遞 歸 算 法 舉 例快速排序第15頁/共53頁17快速排序的思路：1、將待排序的數據放入數組a中，下標從l到r；2、取al放變量k中，通過由右、左兩邊對k的大小的比較，為k選擇應

11、該排定的位置。這時要將比k大的數放右邊，比k小的數放左邊。當k到達最終位置后，由k劃分了左右兩個集合。然后再用同樣的思路處理左集合與右集合。3、令sort(l,r)為將數組元素從下標為l到下標為r的r-l+1個元素從小到大排序。第16頁/共53頁18我們畫出與或圖來闡述快速排序的思路：l=rl=rA sort(l,r)數據在al,.,ar中數據在al,.,ar中B什么也不做什么也不做ClrD分區處理分區處理Fsort(m+1,r)Esort(l,m-1)第17頁/共53頁19分區處理：1、讓k=al2、將k放在am3、使al,al+1,am-1=am4、使am=r，則什么也不做。這是直接可解結

12、點。C結點是在lr情況下A結點的解。C是一個與結點。要對C求解需分解為三步。依次為：第18頁/共53頁201、先解D結點，D結點是一個直接可解結點，功能是進行所謂的分區處理，規定這一步要做的事情是（1）將al中的元素放到它應該在的位置上，比如m位置。這時amal；（2）讓下標從l到m-1的數組元素小于等于am；（3）讓下標從m+1到r的數組元素大于am；比如a數組中al=5，經分組處理后，5送至a4。5到位后，其左邊a0a3的值都小于5；其右邊a5a6大于5。（見下圖）第19頁/共53頁21alram下標：下標：lm-1rm+1第20頁/共53頁222、再解E結點，這時要處理的是a0a3；3、

13、再解F結點，處理a5a6。下面按照這種思路構思一個快速排序的程序框圖。void sort(int array , int ll, int rr)int l,r,i,k;第21頁/共53頁23 ll r r l= ll; r = r r ; k = a r r a y l; T F d o w h ile (l = k ) (1 ) r = r-1 ; l r (2 ) T F a r r a y l= a r r a y r ; l= l+ 1 w h ile (l r )& & (a r r a y l = k ) (3 ) l= l+ 1 ; l r ; (4 ) T F a r r a

14、y r = a r r a y l; w h ile (l!= r ); a r r a y l= k ; fo r (i= ll; i = r r ; i= i+ 1 ) 輸輸 出出 a r r a y i; 換換 行行 ; s o r t(a r r a y, ll, l-1 ); s o r t(a r r a y, l+ 1 , r r ); 第22頁/共53頁24下面舉例說明排序過程圖1 a數組中有7個元素待排序1 讓k=al=a0=5lr圖 1k第23頁/共53頁252 進入直到型循環執行（1）ar=a6=4 不滿足當循環條件，r不動。執行（2）lr，做兩件事：al=ar，即a0=

15、a6=4，l=l+1=0+1=1，見圖2lr圖 2k第24頁/共53頁26執行（3）圖2中的a1k滿足當循環的條件，r=r-1=6-1=5見圖5，之后退出當循環，因為ar=3klr圖 5k第27頁/共53頁29執行（2）al=ar，并讓l=l+1=3，見圖6 lr圖 6k第28頁/共53頁30執行（3）由于a3=1k，退出循環。見圖7 lr圖 7k第29頁/共53頁31執行（4）ar=al，a5=7。見圖8 這時仍然lk，讓r=r-1=4。見圖9lr圖 9k第31頁/共53頁33之后，l=r，退出直到型循環，做al=k，l=4，a4=5，這是5的最終位置，5將整個數據分成左右兩個集合，見圖10

16、。lr圖 10左右k第32頁/共53頁34用上述思路去排左邊的部分從l=0到r=3，見圖11。讓k=al=a0=4，然后進到直到型循環，執行（1）ar=1k，不滿足當循環的條件，r不動。執行（2）al=ar，l=l+1=1,見圖12lr圖 12lr圖 11k第33頁/共53頁35執行（3）alk，l=l+1=2，a2k，l=l+1=3，這時l=r，不會執行（4），同時退出直到型循環，見圖13。然后做al=k，即a3=4，見圖14，左邊也排好了。圖 14lr圖 13lrkk第34頁/共53頁364、用上述思路去排右邊的部分，見圖15，讓k=al=a5=7，進入直到型循環；執行（1）ar=6k，r

17、不動執行（2）al=ar=6，l=l+1=5+1=6，見圖16圖 16lr圖 15lrk第35頁/共53頁37這時l=r，不再執行（3）（4），退出直到型循環后，做al=k，見圖17。圖 17lrk第36頁/共53頁38在有了遞歸調用函數之后，主程序很容易寫，主程序中應包含1、 定義整型變量：數組a10，i；2、 用循環結構輸入待排序的數，將其放入a數組；3、 調用sort函數，使用三個實際參數a將數組a當實參；0數組下標下界；9數組下標上界；4、 輸出排序結果下面給出參考程序（分兩頁）第37頁/共53頁39#include /預編譯命令void sort(int array ,int ll,

18、int rr) /被調用函數，數組array，ll,rr為形參 /函數體開始 int l,r,i,k; /定義變量 if(llrr) /如果llrr,則做下列7件事: /7件事開始l=ll;r=rr;k=arrayl; /第1件事do /第2件事(開始) while(l=k)r=r-1; /2.1,右邊的元素=k,讓r往中間移if(lr) /2.2,右邊的元素k,讓 arrayl=arrayr; /arrayr送給arrayl， l=l+1; /同時讓l往中間移 while(lr)&(arrayl=k)l=l+1; /2.3,左邊的元素=k,讓l往中間移 if (lk,讓arrayl /送給a

19、rrayr /while(l!=r); /第2件事(結束)arrayl=k; /第3件事,k已排到位for(i=ll;i=rr;i=i+1) /第4件事，輸出 printf(a%d=%d;,i,arrayi); /printf(n); /第5件事，換行sort(array,ll,l-1); /第6件事，排左邊部分sort(array,l+1,rr); /第7件事，排右邊部分 /7件事結束 /函數體結束第38頁/共53頁40void main() /主函數開始 int a10,i; /整型變量printf(請輸入10個整數n );/提示信息for (i=0;i10;i=i+1)/輸入10個整數s

20、canf(%d,&ai); /sort(a,0,9);/調用sort函數,實參為數組a和0，9printf(排序結果為:); /提示信息for (i=0;i0)&(bookj=0) 條件C=(likeij0)&(bookj=0)LpLp什么也不做什么也不做sh3c=1c=1c!=1n=n+1;輸出方案n;輸出方案n;takei=-1;bookj=0;takei=j;bookj=1;sh1i=4 i!=4i=4 i!=4try(i+1);try(i+1);sh2第45頁/共53頁47說明：（1）試著給第i個人分書，先試分0號書，再分1號書，分2號書，因此有一個與結點，讓j=0,1,2,3,4。j

21、表示書。（2）LP為循環結構的循環體。（3）條件C是由兩部分“與”起來的。“第i個人喜歡j書，且j書尚未被分走”。滿足這個條件是i人能夠得到j書的條件。（4）如果不滿足C條件，則什么也不做，這是直接可解結點。第46頁/共53頁48（5）滿足C條件，做三件事。sh1第一件事：將j書分給i，用一個數組takei=j，記住書j給了i人，同時記錄j書已被選用，booki=1。sh2第二件事：查看i是否為4，如果不為4，表示尚未將所有5個人所要的書分完，這時應遞歸再試下一人，即try(i+1)。如果i=4，則應先使方案數n=n+1，然后輸出第n個方案下的每個人所得之書。Sh3第三件事：回溯。讓第i人退回j書，恢復j書尚未被選的標志，即takei=-1和bookj=0。這是在已輸出第n個方案之后，去尋找下一個分書方案所必需的。（6）在有了上述的與或圖之后，我們很容易寫出一個程序框圖。先看被調用函數try(i)的框圖。第47頁/共53頁49 void try (int i) for ( j=0; j0)&(bookj=0) T F T F takei=j; 將將書書 j 給給 i sh1 bookj=1; j 書書已已分分 i=4 sh2 n=n+1; 輸輸出出方方案案 n; try(i+1); 試試