資源描述：
《數(shù)據(jù)結構課程設計--猴子吃桃子問題》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、Dataorganizationcurriculmproject數(shù)據(jù)結構課程設計設計題目：猴子吃桃子問題專業(yè)班級：通信工程0804班學生學號：0909082421學生姓名：王璐指導老師：彭春華完成時間：2010-06-06目錄1.問題描述……………………………………………….1頁2.基本要求………………………………………………..1頁3.程序設計思想………………………………………1---2頁4.軟件模塊結構圖………………………………………..2頁5.程序流程圖……………………………………………..3頁6.源程序………………………………………………4---7頁7.調試分析…………………
2、…………………………8---9頁8.測試數(shù)據(jù)…………………………………………..9---10頁9.心得體會…………………………………………11---12頁一．問題描述這是一個很經(jīng)典的簡易的程序設計題，具體題目為:有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。?二．基本要求1)采用數(shù)組數(shù)據(jù)結構實現(xiàn)上述求解2)采用鏈數(shù)據(jù)結構實現(xiàn)上述求解3)采用遞歸實現(xiàn)上述求解雖然題目很簡單，但是要求用多種方法實現(xiàn)，要求知識比較全面，涉及到數(shù)組，鏈表，函數(shù)，指針，結構體，循環(huán)等方面的基礎知識。三．程序設計思想1
3、．分析題目。每天吃當前桃子數(shù)目的一半再加一個，所以桃子數(shù)目肯定為偶數(shù)。用我們所熟悉的函數(shù)來表示，即：f(x+1)=f(x)/2-1;其中x代表第多少天。：猴子摘桃子的那天也就是第一天就吃了所摘桃子的一半加一個，所以桃子總數(shù)應該為第一天加1再乘以2，等效為f(0)。2.實現(xiàn)方法。最容易想到的也是最簡單的就是運用函數(shù)的遞歸。給出了邊界條件與遞歸函數(shù)，直接調用就可以了。用數(shù)組實現(xiàn)，先定義一個一維數(shù)組，然后結合循環(huán)，也可以求解。如果用鏈表的話，相對來說要復雜點。先要構建一個動態(tài)鏈表，將頭指針賦值給p,p賦值給q，使p,q同時指向鏈表頭,將第十天的桃子數(shù)放在鏈表第一個數(shù)據(jù)域中，然后移動p,q使
4、后一個數(shù)據(jù)域中存放的是前一個加1的2倍，即倒過來存放數(shù)據(jù)。四．軟件模塊結構圖猴子吃桃問題用數(shù)組實現(xiàn)用遞歸實現(xiàn)用鏈表實現(xiàn)五．程序流程圖開始選擇實現(xiàn)方法數(shù)組遞歸鏈表輸入x=10輸入nn==9輸出y【10】=1TFm=2*(duigui(n+1)+1)i>=0T輸出m=1FY【x-1】=(y【x】+1)*2輸出mx--輸出y【x】六．源程序#include#include#defineNULL0typedefintdatatype;typedefstructlink{datatypetao;structlink*next;}node;voidshuzu
5、(){intday[11],i;day[10]=1;for(i=10;i>0;i--){day[i-1]=2*(day[i]+1);printf("%dt",i);printf("%d",day[i]);}printf("thetotal:%d",day[0]);}intdigui(intn){intm;if(n==9)m=1;elsem=2*(digui(n+1)+1);printf("%dt",n+1);printf("%d",m);return(m);}node*init_link(node*head){head=NULL;return(head);}nodem
6、;voidtoutao(node*head){inti=10;node*p,*q;p=head;m.tao=1;p=&m;while(i>0){q=p;q->tao=p->tao;p->next=(node*)malloc(sizeof(node));p=p->next;p->tao=2*(q->tao+1);printf("%dt",i);printf("%d",q->tao);i--;}printf("thetotal:%d",p->tao);voidmain()}{inta,m,j;node*head;head=NULL;printf("pleasechooseone
7、method:1:shuzu2:digui3:lianbiao");for(j=0;j<3;j++){scanf("%d",&m);switch(m){case1:printf("theresultofusingshuzu:");shuzu();break;case2:printf("theresultofusingdigui:");a=digui(0);printf("thetotal:%d",2*(a+1));break;case3:p
