猴子吃桃問(wèn)題

1、目 錄一、問(wèn)題描述.3二、基本要求.3三、 工具/準(zhǔn)備工作.3四、分析與實(shí)現(xiàn).41.1題目分析.41.2基本流程圖.42.1數(shù)組求解法的分析.42.2鏈表求解法的分析.52.3遞歸求解法的分析.63.實(shí)現(xiàn)相應(yīng)功能的代碼.6五、測(cè)試與結(jié)論.81.運(yùn)行結(jié)果顯示.82.運(yùn)行結(jié)果的測(cè)試.9六、課程設(shè)計(jì)總結(jié).91.算法特點(diǎn)及其功能拓展.92.個(gè)人感悟.9一、問(wèn)題描述有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再多吃一個(gè)，到了第10天就只余下一個(gè)桃子。要求用多種方法實(shí)現(xiàn)求出原來(lái)這群猴子共摘了多少個(gè)桃子。1)采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解2)采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解3)采用遞歸實(shí)現(xiàn)上述求解二、基本

2、要求2.1分別用數(shù)組數(shù)據(jù)結(jié)構(gòu)、鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)和遞歸的方法實(shí)現(xiàn)上述問(wèn)題的求解。2.2運(yùn)行時(shí)分別顯示用上述三種方法求解過(guò)程中每一天所剩下的桃子個(gè)數(shù)以及原來(lái)這群猴子共摘的桃子個(gè)數(shù)。2.3程序要有必要的文字說(shuō)明，測(cè)試結(jié)果穩(wěn)定。三、工具/準(zhǔn)備工作3.1需要的工具：一臺(tái)安裝有Microsoft Visual C+ 6.0軟件的PC機(jī)3.2理論準(zhǔn)備：根據(jù)課程設(shè)計(jì)內(nèi)容的相關(guān)要求，深入復(fù)習(xí)有關(guān)數(shù)組、鏈表和遞歸函數(shù)的內(nèi)容，對(duì)相應(yīng)的知識(shí)進(jìn)行進(jìn)一步理解，如數(shù)組的定義和for循環(huán)的使用，另外鏈表方面要注意復(fù)習(xí)如何建立單鏈表以及指針的運(yùn)用，而遞歸則要著重于遞歸函數(shù)的理解，同時(shí)還要兼顧其他一些要運(yùn)用到的理論知識(shí)的查閱和復(fù)習(xí)。

3、四、分析與實(shí)現(xiàn)4.1.1題目分析由題目可設(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，第九天時(shí)猴子摘的桃子個(gè)數(shù)n9，第十天時(shí)猴子摘的桃子個(gè)數(shù)n10。由問(wèn)題重述內(nèi)容中“每天都吃當(dāng)前桃子的一半且再多吃一個(gè)”可得n10=1，n9-（n9/2+1）=n10，n8-（n8/2+1）= n9， 依次推出公式：ni-1 -（ni-1/2+1）= ni (0i10)。即ni-1=2 *（n

4、i+1）(0=0;i-)ai= (ai+1+1)*2;為其余各數(shù)組元素賦值，則當(dāng)i=0時(shí)就可得到我們要求的解a0了。4.2.2鏈表求解法分析要用鏈表求解首先要建立單鏈表，然后聲明一個(gè)類用來(lái)對(duì)鏈表的結(jié)點(diǎn)指針進(jìn)行定義，并在初始化函數(shù)中利用頭插法創(chuàng)建具有10個(gè)元素的鏈表，并依次通過(guò)ni-1= 2*（ni+1）(0i10)進(jìn)行賦值就可得到一個(gè)鏈表如圖2所示。headN3 nextN4 nextN5 nextN7 nextN8 nextN9 nextN10 next nextN6 nextN1 NULLN2 next圖2 鏈表結(jié)點(diǎn)邏輯結(jié)構(gòu)圖通過(guò)鏈表可知N1便是要求問(wèn)題的解。相關(guān)數(shù)據(jù)類型定義如下：clas

5、s listpublic:int data; class list *next;void push();typedef class list node; /建立單鏈表typedef node *link; /定義結(jié)點(diǎn)指針4.2.3遞歸法分析遞歸法是通過(guò)一個(gè)遞歸函數(shù)來(lái)進(jìn)行求值，然后用返回值來(lái)記錄每一天剩余桃子個(gè)數(shù)即可，相關(guān)代碼如下：int process(int n) if(n=10)return 1;else return 2*(process(n+1)+1);4.3相應(yīng)功能代碼以下所示代碼是三種求解方法放一起進(jìn)行實(shí)現(xiàn)的過(guò)程，這樣減少了代碼量，也利于運(yùn)行結(jié)果的顯示，具體代碼如下：#includ

6、eclass list public: int data; class list *next; void push();typedef class list node;/建立單鏈表（將class重定義為node）typedef node *link;/定義結(jié)點(diǎn)指針link p=NULL;void list:push() link s; int j=1; p-data=j; for(int i=9;i0;i-) s=new node; s-data=(j+1)*2; j=s-data; s-next=NULL; p-next=s; p=p-next; int process(int n)/遞歸法

7、 if(n=10) return 1; else return 2*(process(n+1)+1);void main() cout采用數(shù)組結(jié)構(gòu)求解法:=0;i-) ai=(ai+1+1)*2; for(i=9;i=0;i-) cout第j天剩下的桃子個(gè)數(shù)為:aiendl; j-; cout所以猴子共摘了a0個(gè)桃子endl;coutendl;cout采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)求解法:next;cout第10天剩下的桃子個(gè)數(shù)為:1endl;i=9;while(p)cout第i天剩下的桃子個(gè)數(shù)為:datanext;i-;coutendl;cout采用遞歸求解法:0;i-)cout第i天剩下的桃子個(gè)數(shù)為:p

8、rocess(i)endl;cout所以猴子共摘了process(1)個(gè)桃子endl;五、測(cè)試與結(jié)論5.1運(yùn)行結(jié)果顯示該運(yùn)行顯示了三種方法所求得的結(jié)果皆為：1534個(gè)，另外還顯示了每一天剩下的桃子個(gè)數(shù)以及原來(lái)這群猴子共摘的桃子個(gè)數(shù)，達(dá)到了預(yù)期的效果和目標(biāo)。5.2結(jié)果的驗(yàn)證由運(yùn)行結(jié)構(gòu)可知原始桃子個(gè)數(shù)為：1534 個(gè)，則以下為每天所剩余桃子個(gè)數(shù)的驗(yàn)證： 第一天：3070-（3070/2+1）=153 第二天：1534-（1534/2+1）=766 第三天：766-（766/2+1）=382 第四天：382-（382/2+1）=190 第五天：190-（190/2+1）=94 第六天：94-（94/

9、2+1）=46 第七天：46-（46/2+1）=22 第八天：22-（22/2+1）=10第九天：10-（10/2+1）=4 第十天：4-（4/2+1）=1六、課程設(shè)計(jì)總結(jié)6.1 各算法特點(diǎn)及其功能擴(kuò)展：運(yùn)用數(shù)組數(shù)據(jù)結(jié)構(gòu)求解最大的優(yōu)點(diǎn)是存取方便，但是由于在使用之前得確定數(shù)組長(zhǎng)度，所以有時(shí)會(huì)使得空間利用率不高，浪費(fèi)內(nèi)存；而鏈?zhǔn)酱鎯?chǔ)是一種動(dòng)態(tài)的存儲(chǔ)方式，其長(zhǎng)度可以根據(jù)需要進(jìn)行適當(dāng)?shù)淖儎?dòng)的，因?yàn)樗抢弥羔榿?lái)找元素所在的存儲(chǔ)單元的；另外遞歸算法所需的存儲(chǔ)空間要相對(duì)少，但在分析時(shí)相對(duì)來(lái)說(shuō)會(huì)顯得較復(fù)雜些。其實(shí)，我們可以綜合各種方法的利弊，通過(guò)以下代碼的功能，如利用for循環(huán)進(jìn)行輸出，就可以得到每一天桃子的剩余量，從而提高解決問(wèn)題的效率。6.2個(gè)人感悟由于這段時(shí)間都在進(jìn)行期末的復(fù)習(xí)工作，所以相對(duì)來(lái)說(shuō)本次課程設(shè)計(jì)所要用到的知識(shí)還是不陌生的，而且在以前上機(jī)實(shí)驗(yàn)中也做過(guò)類似實(shí)驗(yàn)，所以做起來(lái)還是有一定頭緒的。但是，畢竟之前學(xué)習(xí)時(shí)掌握的知識(shí)比較凌亂，真正運(yùn)用到時(shí)還是會(huì)出現(xiàn)一些頭腦短路現(xiàn)象，我覺(jué)得還是知識(shí)掌握得不夠系統(tǒng)，其次在編寫代碼時(shí)有些語(yǔ)句不能牢記，還是要參考之前編寫的代碼，這使得