c++課程設(shè)計報告---猴子吃桃問題

1、<p><b>　　課程設(shè)計報告書</b></p><p>　　設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 </p><p>　　題 目： 猴子吃桃問題 </p><p>　　學(xué)生姓名： xxx &

2、lt;/p><p>　　專 業(yè)： 計算機科學(xué)與技術(shù)（數(shù)字媒體） </p><p>　　班 別： x </p><p>　　學(xué) 號： x </p><p>　　指導(dǎo)老師： x </p>&

3、lt;p>　　日 期： 2010 年 7 月 4 日</p><p><b>　　摘要</b></p><p>　　當(dāng)下C++語言是一門重要的課程學(xué)習(xí)，學(xué)會運用并結(jié)合結(jié)合其他的知識一起解題是一件值得我們重視的，數(shù)據(jù)結(jié)構(gòu)是一門結(jié)合C++知識的重要課程，因此我們要學(xué)會用平時課本的知識運用到我們的現(xiàn)實生活當(dāng)中，這樣才能讓我們所學(xué)的知識更加深刻

4、。猴子吃桃的問題就是一個例子，我們可以運用簡單的三種解法進(jìn)行解題，即數(shù)組求值解法，鏈表求值解法和遞歸求值解法，通過分析三種解法，根據(jù)各種解法的功能，從而我們得到最合適的求法。</p><p>　　關(guān)鍵詞：猴子吃桃，數(shù)組法，鏈表法，遞歸法，分析</p><p>　　Abstract：Then the c + + language 

5、is an important course study, learn to use and combining together with other knowledge solution is worth our attention, data&

6、#160;structure is a combination of c + + classes, the important knowledge so that we must learn to use ordinary textbook

7、s to apply our real life, so that we can make us more profound knowledge. The monkeys eat the peach is a simpl

8、e example, we can use the three solutions to solving method, i.e. arrays are evaluated for value chain, and recursio</p>

9、;<p><b>　　目錄</b></p><p>　　1.問題描述………………………………………………………… 2</p><p>　　2.基本要求…………………………………………………………2</p><p>　　3工具/準(zhǔn)備工作 …………………………………………………2</p><p>　　4.分析與

10、實現(xiàn)………………………………………………………2</p><p>　　4.1題目分析………………………………………………………2</p><p>　　4.2.1數(shù)組求解法分析………………………………………………2</p><p>　　4.2.2鏈表求解法分析………………………………………………2</p><p>　　4.2.3遞歸法分析………

11、………………………………………4</p><p>　　4.3功能代碼………………………………………………………4</p><p>　　5.測試與結(jié)論………………………………………………………8</p><p>　　6.課程設(shè)計總結(jié)……………………………………………………9</p><p>　　6.1算法特點及在例題功能擴展…………………………

12、……9</p><p>　　6. 2感悟……………………………………………………………10</p><p><b>　　7.參考文獻(xiàn)</b></p><p><b>　　1.問題描述</b></p><p>　　有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再多吃一個，到了第10天就只余下一個

13、桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。</p><p><b>　　2.基本要求</b></p><p>　　(1)采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解</p><p>　　(2)采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解</p><p>　　(3)采用遞歸實現(xiàn)上述求解</p><p><b>

14、;　　3.工具/準(zhǔn)備工作</b></p><p>　　1）程序調(diào)試采用到VC6.0的Win32 Console Application，所以要安裝英文版VC6.0。</p><p>　　2）根據(jù)問題要求，深入復(fù)習(xí)有關(guān)數(shù)組，鏈表，遞歸函數(shù)相關(guān)內(nèi)容，了解數(shù)組，鏈表的創(chuàng)建，特點，改如何使用，再者遞歸法是相對比較難理解，這就需要了解該如何使用遞歸函數(shù)了。</p><

15、p><b>　　4.分析與實現(xiàn)</b></p><p><b>　　4.1題目分析</b></p><p>　　根據(jù)題目要求，設(shè)猴子共摘的桃子個數(shù)為n即是第一天桃子的個數(shù)n1, 第第二天時桃子個數(shù)n2，第三天時桃子個數(shù)n3，第四天時桃子個數(shù)n4，第五天時桃子個數(shù)n5，第六天時桃子個數(shù)n6，第七天時桃子個數(shù)n7，第八天時桃子個數(shù)n8，第九天

16、時桃子個數(shù)n9，第十天時桃子個數(shù)n10。</p><p>　　由題中“每天都吃當(dāng)前桃子的一半且再多吃一個”很容易知道n10=1，（n9/2+1）=n10，n8-（n8/2+1）= n9…… 依次推出公式：ni-1-（ni-1/2+1）= ni (0。即ni-1= 2*（ni+1）(0。</p><p>　　4.2.1數(shù)組求解法分析</p><p>　　聲明一個長度

17、為10的整形數(shù)組a[10],分別存放各天猴子吃前的桃子數(shù)。下圖所示</p><p><b>　　圖1</b></p><p>　　a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] </p><p>　　先將a[9]賦值為1，用一個循環(huán)語句</p

18、><p>　　for(int i=8;i>=0;i--)</p><p>　　a[i]=2*(a[i+1]+1);為其余各數(shù)組元素賦值，則數(shù)組元素a[0]的值便是該問題的解。</p><p>　　4.2.2鏈表求解法分析</p><p>　　建立單鏈表，聲明一個類用來對鏈表的結(jié)點指針進(jìn)行定義，在初始化函數(shù)中利用頭插法創(chuàng)建具有10個元素的鏈表

19、，并依次安公式ni-1= 2*（ni+1）(0。賦值得到一個如圖所示的鏈表。</p><p><b>　　圖4-2</b></p><p><b>　　head</b></p><p>　　那么N1便是要求問題的解。</p><p>　　4.2.3遞歸法分析</p><p>

20、　　利用一個遞歸函數(shù)來進(jìn)行求值：依據(jù)返回值來記錄每一天剩余桃子情況。</p><p>　　int process(int n)</p><p><b>　　{</b></p><p><b>　　if(n==10)</b></p><p>　　return 1;</p><p&

21、gt;<b>　　else </b></p><p>　　return 2*(process(n+1)+1);</p><p><b>　　}</b></p><p><b>　　4.3功能代碼</b></p><p>　　#include <iostream.h&g

22、t;</p><p>　　class list</p><p><b>　　{</b></p><p><b>　　public:</b></p><p><b>　　int data;</b></p><p>　　class list *next;&l

23、t;/p><p>　　void push();</p><p><b>　　};</b></p><p>　　typedef class list node;//建立單鏈表(將class重定義為node)</p><p>　　typedef node *link;//定義結(jié)點指針</p><p>　　

24、link p=NULL;</p><p>　　void list::push()</p><p><b>　　{</b></p><p><b>　　link s;</b></p><p><b>　　int j=1;</b></p><p>　　p-&

25、gt;data=j;</p><p>　　for(int i=9;i>0;i--)</p><p><b>　　{</b></p><p>　　s=new node;</p><p>　　s->data=(j+1)*2;</p><p>　　j=s->data;</p&

26、gt;<p>　　s->next=NULL;</p><p>　　p->next=s;</p><p>　　p=p->next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int p

27、rocess(int n)//遞歸法</p><p><b>　　{</b></p><p><b>　　if(n==10)</b></p><p>　　return 1;</p><p><b>　　else </b></p><p>　　ret

28、urn 2*(process(n+1)+1);</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　cout<<"*****數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn):"<<endl;<

29、;/p><p>　　int a[10];</p><p>　　int i,j=10;</p><p><b>　　a[9]=1;</b></p><p>　　for(i=8;i>=0;i--)</p><p><b>　　{ </b></p>&

30、lt;p>　　a[i]=(a[i+1]+1)*2;</p><p><b>　　}</b></p><p>　　for(i=9;i>=0;i--)</p><p><b>　　{</b></p><p>　　cout<<"第"<<j<&l

31、t;"天剩下的桃子為:"<<a[i]<<endl;</p><p><b>　　j--;</b></p><p><b>　　}</b></p><p>　　cout<<"所以猴子共摘了"<<a[0]<<"個桃子&

32、quot;<<endl;</p><p>　　cout<<endl;</p><p>　　cout<<"*****鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)實現(xiàn):"<<endl;</p><p>　　link head;</p><p>　　head=new node;</p><p&

33、gt;　　list list1;</p><p><b>　　p=head;</b></p><p>　　list1.push();</p><p>　　p=head->next;</p><p>　　cout<<"第10天剩下的桃子為:1"<<endl;</p&g

34、t;<p><b>　　i=9;</b></p><p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　cout<<"第"<<i<<"天剩下的桃子為:"&l

35、t;<p->data<<endl;</p><p>　　p=p->next;</p><p><b>　　i--;</b></p><p><b>　　}</b></p><p>　　cout<<endl;</p><p>　　cou

36、t<<"*****遞歸實現(xiàn):"<<endl;</p><p>　　for(i=10;i>0;i--)</p><p>　　cout<<"第"<<i<<"天剩下的桃子為:"<<process(i)<<endl;</p><p

37、>　　cout<<"所以猴子共摘的桃子為:"<<process(1)<<endl;</p><p><b>　　}</b></p><p><b>　　5.測試與結(jié)論</b></p><p>　　本程序在DEBUG下測試成功，如下圖所示：</p>

38、<p>　　本測試分別輸出了三種方法所求得的結(jié)果為：1534個，另外還用數(shù)組法，鏈表法和遞歸法分別求出了，猴子在吃桃子的10天內(nèi)，各天含有桃子的數(shù)量：</p><p><b>　　下面進(jìn)行驗證結(jié)果：</b></p><p>　　原始桃子為：1534 第一天桃子為：3070-（3070/2+1）=1534</p>

39、<p>　　第二天為：1534-（1534/2+1）=766 第三天為：766-（766/2+1）=382</p><p>　　第四天為：382-（382/2+1）=190 第五天為：190-（190/2+1）=94</p><p>　　第六天為：94-（94/2+1）=46 第七天為：46-（46/2+1）=22</p><

40、;p>　　第八天為：22-（22/2+1）=10 第九天為：10-（10/2+1）=4</p><p>　　第十天為：4-（4/2+1）=1</p><p><b>　　6.課程設(shè)計總結(jié)</b></p><p>　　6.1各算法特點及在例題功能擴展</p><p>　　數(shù)組的使用要先確定其長度，有

41、時候會造成空間浪費，但是存取方便；用鏈?zhǔn)酱鎯Ψ绞绞且环N動態(tài)的存儲，長度是不用規(guī)定的，需要用指針來找到元素所在存儲單元；而遞歸算法，存儲空間要得少，但要知道準(zhǔn)確計算函數(shù)，相對比較難。在本例題中，我們可以通過對各種方法，利用for循環(huán)進(jìn)行輸出，就得到每一天桃子的剩余量。</p><p><b>　　6.2感悟</b></p><p>　　1.這一次的實驗可以說是對前面一些

42、知識的回顧和溫習(xí)，由于有一段時間都未看過，發(fā)現(xiàn)自己對于鏈表結(jié)構(gòu)和遞歸法有些淡忘，所以花了不少時間去認(rèn)識，解題。解題思路要經(jīng)過在草紙上畫出，有時候急忙著反而使后面的不知道怎么寫。</p><p>　　2.發(fā)現(xiàn)自己在寫報告組織語言方面挺欠缺，開始不能很清楚的表達(dá)分析解題，所以經(jīng)過多次改進(jìn)。許多解法功能自己不僅要懂得簡單運用，更需要懂得如何表達(dá)出來。</p><p><b>　　7.參