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

1、 數(shù)據(jù)結構課程設計 猴子吃桃問題課程設計報告書設計名稱： 數(shù)據(jù)結構課程設計 題 目： 猴子吃桃問題 學生姓名： xxx 專 業(yè)： 計算機科學與技術（數(shù)字媒體） 班 別： x 學 號： x 指導老師： x 日 期： 2010 年 7 月 4 日 摘要當下c+語言是一門重要的課程學習，學會運用并結合結合其他的知識一起解題是一件值得我們重視的，數(shù)據(jù)結構是一門結合c+知識的重要課程，因此我們要學會用平時課本的知識運用到我們的現(xiàn)實生活當中，這樣才能讓我們所學的知識更加深刻。猴子吃桃的問題就是一個例子，我們可以運用簡單的三種解法進行解題，即數(shù)組求值解法，鏈表求值解法和遞歸求值解法，通過分析三種解法，根據(jù)各

2、種解法的功能，從而我們得到最合適的求法。關鍵詞：猴子吃桃，數(shù)組法，鏈表法，遞歸法，分析abstract：then the c + + language is an important course study, learn to use and combining together with other knowledge solution is worth our&

3、#160;attention, data structure is a combination of c + + classes, the important knowledge so that we must learn to use ordinary textbooks to apply our real life,

4、0;so that we can make us more profound knowledge. the monkeys eat the peach is a simple example, we can use the three solutions to solving method, i.e. arrays&#

5、160;are evaluated for value chain, and recursion evaluated method, by analyzing the three kinds of solutions, according to various solutions, which we have the function of

6、0;the most suitable solution.keywords: the monkeys eat the peach, the array method, the list of recursion, method, the method of analysis目錄1.問題描述 22.基本要求23工具/準備工作 24.分析與實現(xiàn)24.1題目分析24.2.1數(shù)組求解法分析24.2.2鏈表

7、求解法分析24.2.3遞歸法分析44.3功能代碼45.測試與結論86.課程設計總結96.1算法特點及在例題功能擴展96. 2感悟107.參考文獻1.問題描述有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。2.基本要求(1)采用數(shù)組數(shù)據(jù)結構實現(xiàn)上述求解(2)采用鏈式數(shù)據(jù)結構實現(xiàn)上述求解(3)采用遞歸實現(xiàn)上述求解3.工具/準備工作1）程序調(diào)試采用到vc6.0的win32 console application，所以要安裝英文版vc6.0。2）根據(jù)問題要求，深入復習有關數(shù)組，鏈表，遞歸函數(shù)相關內(nèi)容，了解數(shù)組

8、，鏈表的創(chuàng)建，特點，改如何使用，再者遞歸法是相對比較難理解，這就需要了解該如何使用遞歸函數(shù)了。4.分析與實現(xiàn)4.1題目分析根據(jù)題目要求，設猴子共摘的桃子個數(shù)為n即是第一天桃子的個數(shù)n1, 第第二天時桃子個數(shù)n2，第三天時桃子個數(shù)n3，第四天時桃子個數(shù)n4，第五天時桃子個數(shù)n5，第六天時桃子個數(shù)n6，第七天時桃子個數(shù)n7，第八天時桃子個數(shù)n8，第九天時桃子個數(shù)n9，第十天時桃子個數(shù)n10。由題中“每天都吃當前桃子的一半且再多吃一個”很容易知道n10=1，（n9/2+1）=n10，n8-（n8/2+1）= n9 依次推出公式：ni-1-（ni-1/2+1）= ni (0。即ni-1= 2*（ni+

9、1）(0。4.2.1數(shù)組求解法分析聲明一個長度為10的整形數(shù)組a10,分別存放各天猴子吃前的桃子數(shù)。下圖所示圖1n1n2n3n4n5n6n7n8n9n10a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 先將a9賦值為1，用一個循環(huán)語句for(int i=8;i>=0;i-)ai=2*(ai+1+1);為其余各數(shù)組元素賦值，則數(shù)組元素a0的值便是該問題的解。4.2.2鏈表求解法分析建立單鏈表，聲明一個類用來對鏈表的結點指針進行定義，在初始化函數(shù)中利用頭插法創(chuàng)建具有10個元素的鏈表，并依次安公式ni-1= 2*（ni+1）(0。賦值得到一個如圖所示的鏈表。圖4-2 headn6

10、nextn3 nextn4 nextn5 nextn1 nulln2 nextn7 nextn8 nextn9 nextn10 next next那么n1便是要求問題的解。4.2.3遞歸法分析利用一個遞歸函數(shù)來進行求值：依據(jù)返回值來記錄每一天剩余桃子情況。int process(int n) if(n=10)return 1;else return 2*(process(n+1)+1);4.3功能代碼#include <iostream.h>class listpublic:int data; class list *next;void push();typedef class l

11、ist node;/建立單鏈表(將class重定義為node)typedef node *link;/定義結點指針link p=null;void list:push()link s;int j=1;p->data=j;for(int i=9;i>0;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)/遞歸法if(n=10)return 1;else return 2*(process(n+1)+1);void main(

12、)cout<<"*數(shù)組數(shù)據(jù)結構實現(xiàn):"<<endl;int a10;int i,j=10; a9=1;for(i=8;i>=0;i-) ai=(ai+1+1)*2; for(i=9;i>=0;i-)cout<<"第"<<j<<"天剩下的桃子為:"<<ai<<endl;j-;cout<<"所以猴子共摘了"<<a0<<"個桃子"<<endl;cout<

13、<endl;cout<<"*鏈式數(shù)據(jù)結構實現(xiàn):"<<endl;link head;head=new node;list list1;p=head;list1.push();p=head->next; cout<<"第10天剩下的桃子為:1"<<endl; i=9; while(p) cout<<"第"<<i<<"天剩下的桃子為:"<<p->data<<endl;p=p->next;i-

14、; cout<<endl;cout<<"*遞歸實現(xiàn):"<<endl;for(i=10;i>0;i-)cout<<"第"<<i<<"天剩下的桃子為:"<<process(i)<<endl;cout<<"所以猴子共摘的桃子為:"<<process(1)<<endl;5.測試與結論本程序在debug下測試成功，如下圖所示：本測試分別輸出了三種方法所求得的結果為：1534個，另外還用數(shù)組

15、法，鏈表法和遞歸法分別求出了，猴子在吃桃子的10天內(nèi)，各天含有桃子的數(shù)量：下面進行驗證結果：原始桃子為：1534 第一天桃子為：3070-（3070/2+1）=1534第二天為：1534-（1534/2+1）=766 第三天為：766-（766/2+1）=382第四天為：382-（382/2+1）=190 第五天為：190-（190/2+1）=94第六天為：94-（94/2+1）=46 第七天為：46-（46/2+1）=22第八天為：22-（22/2+1）=10 第九天為：10-（10/2+1）=4第十天為：4-（4/2+1）=16.課程設計總結6.1各算法特點及在例題功能擴展數(shù)組的使用要先確定其長度，有時候會造成空間浪費，但是存取方便；用鏈式存儲方式是一種動態(tài)的存儲，長度是不用規(guī)定的，需要用指針來找到元素所在存儲單元；而遞歸算法，存儲空間要得少，但要知道準確計算函數(shù)，相對比較難。在本例題中，我們可以通過對各種方法，利用for循環(huán)進行輸出，就得到每一天桃子的剩余量。6.2感悟1.這一次的實驗可以說是對前面一些知識的回顧