c++課程設(shè)計(jì)報(bào)告---猴子吃桃問題

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

2、lt;/p><p>　　專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)（數(shù)字媒體） </p><p>　　班 別： x </p><p>　　學(xué) 號(hào)： 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é)會(huì)運(yùn)用并結(jié)合結(jié)合其他的知識(shí)一起解題是一件值得我們重視的，數(shù)據(jù)結(jié)構(gòu)是一門結(jié)合C++知識(shí)的重要課程，因此我們要學(xué)會(huì)用平時(shí)課本的知識(shí)運(yùn)用到我們的現(xiàn)實(shí)生活當(dāng)中，這樣才能讓我們所學(xué)的知識(shí)更加深刻

4、。猴子吃桃的問題就是一個(gè)例子，我們可以運(yùn)用簡單的三種解法進(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、實(shí)現(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è)計(jì)總結(jié)……………………………………………………9</p><p>　　6.1算法特點(diǎn)及在例題功能擴(kuò)展…………………………

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

13、桃子。用多種方法實(shí)現(xiàn)求出原來這群猴子共摘了多少個(gè)桃子。</p><p><b>　　2.基本要求</b></p><p>　　(1)采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解</p><p>　　(2)采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解</p><p>　　(3)采用遞歸實(shí)現(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)建，特點(diǎn)，改如何使用，再者遞歸法是相對比較難理解，這就需要了解該如何使用遞歸函數(shù)了。</p><

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

16、時(shí)桃子個(gè)數(shù)n9，第十天時(shí)桃子個(gè)數(shù)n10。</p><p>　　由題中“每天都吃當(dāng)前桃子的一半且再多吃一個(gè)”很容易知道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>　　聲明一個(gè)長度

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，用一個(gè)循環(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>　　建立單鏈表，聲明一個(gè)類用來對鏈表的結(jié)點(diǎn)指針進(jìn)行定義，在初始化函數(shù)中利用頭插法創(chuàng)建具有10個(gè)元素的鏈表

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

20、　　利用一個(gè)遞歸函數(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é)點(diǎn)指針</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)實(shí)現(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]<<"個(gè)桃子&

32、quot;<<endl;</p><p>　　cout<<endl;</p><p>　　cout<<"*****鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)實(shí)現(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<<"*****遞歸實(shí)現(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個(gè)，另外還用數(shù)組法，鏈表法和遞歸法分別求出了，猴子在吃桃子的10天內(nèi)，各天含有桃子的數(shù)量：</p><p><b>　　下面進(jìn)行驗(yà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è)計(jì)總結(jié)</b></p><p>　　6.1各算法特點(diǎn)及在例題功能擴(kuò)展</p><p>　　數(shù)組的使用要先確定其長度，有

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

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