猴子吃桃問題-數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告

合肥學(xué)院計算機科學(xué)與技術(shù)系課程設(shè)計報告2009～2010學(xué)年第二學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計名稱猴子吃桃問題學(xué)生姓名王康可學(xué)號0804012014專業(yè)班級計算機科學(xué)與技術(shù)08級（2）班指導(dǎo)教師王昆侖張貫虹2010年6月題目：（猴子吃桃問題）有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。問題分析和任務(wù)定義本題目中，猴子每天都吃當前桃子的一半且再多吃一個，假設(shè)第一天開始時，即摘的桃子總數(shù)有a0只桃子，第一天吃過之后剩下a1只桃子，第二天吃過之后剩下a2只，...，第9天吃過之后剩下a9只，第10天吃過之后剩下a10只，在a0，a1，a2，...，a10中，只有a10=1是知道的，現(xiàn)要求a0，而我們可以看出，a0，a1，a2，...，a10之間存在一個簡單的關(guān)系：a9=2*(a10+1)a8=2*(a9+1)┇a1=2*(a2+1)a0=2*(a1+1)也就是：ai=2*(ai+1)，其中i=10,9，8，7，6，...，1，0。這就是此題的數(shù)學(xué)模型。通過閱讀題目、分析題意，要求利用不同方法實現(xiàn)這群猴子摘桃子總數(shù)，為了實現(xiàn)題目要求，可采用遞歸、鏈式、數(shù)組等方法，而不管是采用哪種方法、哪種數(shù)據(jù)結(jié)構(gòu)，其基本語句都是ai=2*(ai+1+1)，其中i=10,9，8，7，6，...，1，0。數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計按照題目要求，采用數(shù)組數(shù)據(jù)結(jié)構(gòu)、鏈式數(shù)據(jù)結(jié)構(gòu)。分別利用遞歸算法、鏈式存儲、數(shù)組來實現(xiàn)函數(shù)功能。將所有模塊放在一起，利用主函數(shù)中的菜單來調(diào)用不同子函數(shù)以實現(xiàn)題目要求。三、詳細設(shè)計和編碼1、采用遞歸算法子函數(shù)中，關(guān)鍵語句為N=2*recursion(N+1)+2，采用判斷語句if…else…，“if(N==10)return1；”，給出第十天吃過桃子后剩下桃子數(shù)為1，其他天數(shù)returnN=2*recursion(N+1)+2，即通過遞歸調(diào)用計算，通過已知的后一天剩下的桃子總數(shù)來求出前一天剩下的桃子總數(shù)。在主函數(shù)中，利用for循環(huán)，來調(diào)用遞歸函數(shù)，即N=recursion(i)。具體實現(xiàn)為：for(i=0;i<=10;i++){ N=recursion(i); printf("第%d天,還剩桃子%d個\n",i,N); }可知N=2*recursion(N+1)+2語句要調(diào)用10+9+……+1共55次，桃子原來的總數(shù)為：recursion(0)。2、采用數(shù)組數(shù)據(jù)結(jié)構(gòu)構(gòu)建子函數(shù)voidArray(inta[])，初始化i=10，從10開始計算，i--，通過語句while(i>0)，來循環(huán)運行a[i-1]=2*a[i]+2，以求出每天剩下的桃子數(shù)當i<=0時退出循環(huán)。在主函數(shù)中定義數(shù)組inta[11]來存儲每天剩下的桃子總數(shù)，初始化a[10]=1，通過調(diào)用子函數(shù)Array(a)，并利用for循環(huán)來輸出每天剩下的桃子總數(shù)，其中a[0]即為原來猴群所摘的桃子的總數(shù)。3、采用鏈式數(shù)據(jù)結(jié)構(gòu)構(gòu)建創(chuàng)建鏈表子函數(shù)LinkList*CreatList()，定義兩個結(jié)點*L、*p，L->next=NULL，數(shù)據(jù)域為L->data=1，即第十天剩下的桃子數(shù)目為1個。p結(jié)點存儲前一天的桃子數(shù)，一個一個往前插，即p->data=2*L->data+2，p->next=L，L=p。構(gòu)建子函數(shù)voidDisplayList(LinkList*L)，inti=0，定義LinkList*p，p=L。通過循環(huán)語句while(p!=NULL)，i++，輸出p->data域，然后p=p->next，來輸出每天剩余桃子總數(shù)。在主函數(shù)中調(diào)用鏈表創(chuàng)建函數(shù)L=CreatList()以及輸出函數(shù)DisplayList(L)，原來猴群所摘的桃子的總數(shù)為L->data。四、上機調(diào)試由于此程序是分模塊進行，且每一個模塊相對比較簡單，所以在做程序的過程中比較順利。剛開始時，每一個算法我都是單獨的一個程序來實現(xiàn)，基本上沒有出現(xiàn)問題，在將所有方法、程序做好后，再將所有程序集合在一起，利用主函數(shù)的菜單來分塊調(diào)用以實現(xiàn)題目要求。在整合過程中，出現(xiàn)了一些編輯錯誤，但是都是比較小的錯誤，很快就找出來了，應(yīng)該說整個程序做的過程還是比較順利的。在做程序的過程中，對題目的理解有問題，造成結(jié)果的不確定。到第十天剩下1個桃子，是指吃完才剩下，還是沒吃就剩下，不同的理解所求結(jié)果就不同。如果是吃剩下再剩下所求結(jié)果就為3070個，如果是第十天吃之前剩下桃子數(shù)為1個，那么求得的桃子總數(shù)為1534個。最后將第十天剩下1個理解為吃過之后剩下的桃子數(shù)，因為如果不是第十天吃過之后，那么到第九天吃過之后就只剩下1個桃子了，與題意中的第十天剩下1個不符。五、測試結(jié)果及其分析1、采用遞歸算法解決問題：2、采用數(shù)組數(shù)據(jù)結(jié)構(gòu)算法解決問題：3、采用鏈式數(shù)據(jù)結(jié)構(gòu)算法解決問題：4、退出功能：5、提示菜單輸入錯誤六、用戶使用說明按題目要求，本程序需要用不同的方法實現(xiàn)函數(shù)功能，需分模塊進行。利用菜單將所有實現(xiàn)的方法列舉出來，用戶只要按提示輸入選項，即可選擇實現(xiàn)函數(shù)功能的方法并輸出題目的結(jié)果。七、附錄#include<stdio.h>#include<malloc.h>#include"stdlib.h"#defineNULL0#defineDays10//常量////////////////////遞歸方法////////////////////intrecursion(intN){ if(N==10) return1;//跳出循環(huán) else returnN=2*recursion(N+1)+2;//遞歸調(diào)用計算}////////////////////數(shù)組方法////////////////////voidArray(inta[]){ inti=10;//初始化，從10開始計算 while(i>0){ a[i-1]=2*a[i]+2; i--; }}////////////////////單鏈表方法////////////////////typedefstructLnode{ intdata;//數(shù)據(jù)域 structLnode*next;//鏈表指針}LinkList;LinkList*CreatList(){//創(chuàng)建鏈表 LinkList*L,*p; L=(LinkList*)malloc(sizeof(LinkList)); L->next=NULL; L->data=1; for(inti=Days;i>0;i--){ p=(LinkList*)malloc(sizeof(LinkList)); p->data=2*L->data+2; p->next=L; L=p; } returnL;}voidDisplayList(LinkList*L){ LinkList*p; inti=0; p=L; while(p!=NULL){ printf("第%d天，還剩桃子%d個\n",i++,p->data); p=p->next; }}////////////////////主函數(shù)////////////////////voidmain(){ system("color3f"); inta[11]; inti,N; a[10]=1;//初始化a[10] LinkList*L; L=(LinkList*)malloc(sizeof(LinkList)); while(1){ printf("\n"); printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n"); printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n"); printf("@@問題：有一群猴子摘了一堆桃子，他們每天吃一半且再多吃一個，到了第10天@@\n"); printf("@@只余下1個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子?@@\n"); printf("@@####1:用遞歸算法解決問題####@@\n"); printf("@@****2:用數(shù)組數(shù)據(jù)結(jié)構(gòu)算法解決問題****@@\n"); printf("@@****3:用鏈式數(shù)據(jù)結(jié)構(gòu)算法解決問題****@@\n"); printf("@@####4:退出####@@\n"); printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n"); printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n"); intk; scanf("%d",&k); switch(k){ case1: for(i=0;i<=10;i++){ N=recursion(i); printf("第%d天,還剩桃子%d個\n",i,N); } printf("桃子原來的總數(shù)為：%d",recursion(0)); break; case2: Array(a);for(i=0;i<=10;i++){ printf("第%d天,還剩桃子%d個\n",i,a[i]); } printf("桃子原來的總數(shù)為：%d",a[0]); break; case3: L=CreatList(); DisplayList(L); printf("桃子原來的總數(shù)為：%d\n",L->data); break; case4:exit(0);