c++課程設計報告---猴子吃桃問題

1、<p><b>　　課程設計報告書</b></p><p>　　設計名稱： 數據結構課程設計 </p><p>　　題 目： 猴子吃桃問題 </p><p>　　學生姓名： xxx &

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

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

4、。猴子吃桃的問題就是一個例子，我們可以運用簡單的三種解法進行解題，即數組求值解法，鏈表求值解法和遞歸求值解法，通過分析三種解法，根據各種解法的功能，從而我們得到最合適的求法。</p><p>　　關鍵詞：猴子吃桃，數組法，鏈表法，遞歸法，分析</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工具/準備工作 …………………………………………………2</p><p>　　4.分析與

10、實現………………………………………………………2</p><p>　　4.1題目分析………………………………………………………2</p><p>　　4.2.1數組求解法分析………………………………………………2</p><p>　　4.2.2鏈表求解法分析………………………………………………2</p><p>　　4.2.3遞歸法分析………

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

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

13、桃子。用多種方法實現求出原來這群猴子共摘了多少個桃子。</p><p><b>　　2.基本要求</b></p><p>　　(1)采用數組數據結構實現上述求解</p><p>　　(2)采用鏈式數據結構實現上述求解</p><p>　　(3)采用遞歸實現上述求解</p><p><b>

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

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

16、時桃子個數n9，第十天時桃子個數n10。</p><p>　　由題中“每天都吃當前桃子的一半且再多吃一個”很容易知道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數組求解法分析</p><p>　　聲明一個長度

17、為10的整形數組a[10],分別存放各天猴子吃前的桃子數。下圖所示</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);為其余各數組元素賦值，則數組元素a[0]的值便是該問題的解。</p><p>　　4.2.2鏈表求解法分析</p><p>　　建立單鏈表，聲明一個類用來對鏈表的結點指針進行定義，在初始化函數中利用頭插法創(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、　　利用一個遞歸函數來進行求值：依據返回值來記錄每一天剩余桃子情況。</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;//定義結點指針</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<<"*****數組數據結構實現:"<<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<<"*****鏈式數據結構實現:"<<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<<"*****遞歸實現:"<<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.測試與結論</b></p><p>　　本程序在DEBUG下測試成功，如下圖所示：</p>

38、<p>　　本測試分別輸出了三種方法所求得的結果為：1534個，另外還用數組法，鏈表法和遞歸法分別求出了，猴子在吃桃子的10天內，各天含有桃子的數量：</p><p><b>　　下面進行驗證結果：</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.課程設計總結</b></p><p>　　6.1各算法特點及在例題功能擴展</p><p>　　數組的使用要先確定其長度，有

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

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