猴子吃桃問題

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

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

3、。四、分析與實現(xiàn)4.1.1題目分析由題目可設(shè)猴子共摘的桃子個數(shù)為n即是第一天猴子摘的桃子的個數(shù)n1, 第二天時猴子摘的桃子個數(shù)n2，第三天時猴子摘的桃子個數(shù)n3，第四天時猴子摘的桃子個數(shù)n4，第五天時猴子摘的桃子個數(shù)n5，第六天時猴子摘的桃子個數(shù)n6，第七天時猴子摘的桃子個數(shù)n7，第八天時猴子摘的桃子個數(shù)n8，第九天時猴子摘的桃子個數(shù)n9，第十天時猴子摘的桃子個數(shù)n10。由問題重述內(nèi)容中“每天都吃當(dāng)前桃子的一半且再多吃一個”可得n10=1，n9-（n9/2+1）=n10，n8-（n8/2+1）= n9， 依次推出公式：ni-1 -（ni-1/2+1）= ni (0i10)。即ni-1=2 *（

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

5、ss listpublic:int data; class list *next;void push();typedef class list node; /建立單鏈表typedef node *link; /定義結(jié)點(diǎn)指針4.2.3遞歸法分析遞歸法是通過一個遞歸函數(shù)來進(jìn)行求值，然后用返回值來記錄每一天剩余桃子個數(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)行實現(xiàn)的過程，這樣減少了代碼量，也利于運(yùn)行結(jié)果的顯示，具體代碼如下：；.#inc

6、ludeclass 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天剩下的桃子個數(shù)為:aiendl; j-; cout所以猴子共摘了a0個桃子endl;coutendl;cout采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)求解法:next;cout第10天剩下的桃子個數(shù)為:1endl;i=9;while(p)cout第i天剩下的桃子個數(shù)為:datanext;i-;coutendl;cout采用遞歸求解法:0;i-)cout第i天剩下的桃子個數(shù)

8、為:process(i)endl;cout所以猴子共摘了process(1)個桃子endl;.五、測試與結(jié)論5.1運(yùn)行結(jié)果顯示該運(yùn)行顯示了三種方法所求得的結(jié)果皆為：1534個，另外還顯示了每一天剩下的桃子個數(shù)以及原來這群猴子共摘的桃子個數(shù)，達(dá)到了預(yù)期的效果和目標(biāo)。5.2結(jié)果的驗證由運(yùn)行結(jié)構(gòu)可知原始桃子個數(shù)為：1534 個，則以下為每天所剩余桃子個數(shù)的驗證： 第一天：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-

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