數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--猴子吃桃問題

1、山東交通學院數(shù)據(jù)結(jié)構(gòu)設(shè)計猴子吃桃問題院（系）別信息科學與電氣工程學院班級計算113學號11081131姓 名王室指導(dǎo)教師王成時 間 2012-03-092012-03-20課程設(shè)計任務(wù)書題目猴子吃桃院（部）信息科學與電氣工程學院專業(yè)計算機科學與技術(shù)班 級學生姓名 學 號3 月 9 日至 3 月 20 日共 2 周指導(dǎo)教師（簽字）王成系主任（簽字）2015年 月一、設(shè)計內(nèi)容及要求這個程序的內(nèi)容是以 C語言為程序語言載體分別用數(shù)組數(shù)據(jù)結(jié)構(gòu)、鏈數(shù)據(jù)結(jié)構(gòu)、遞歸等結(jié)構(gòu)形式實現(xiàn)此問題的求解。二、設(shè)計原始資料在這個程序中我們主要是用 C語言解決猴子吃桃問題，一群猴子摘了一堆桃子，他們每天都 吃當前桃子的一半

2、且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。生活中或?qū)W術(shù)上有很多類似的問題，這個問題看似簡單，卻可能使很多重大問題的重要組成部分或者是核心。解決此問題的目的是以便在生活中解決根本性問題， 是生活變得更加便利。三、設(shè)計完成后提交的文件和圖表1 .計算說明書部分如果用數(shù)組結(jié)構(gòu)解決這個問題，把猴子吃桃的天數(shù)倒過來看的話，以天數(shù)作為數(shù)組的下標i ,剩下桃子的個數(shù)ai的遞推公式為ai=(ai-1+1)*2ai實際代表了倒數(shù)第i天剩下的桃子數(shù)。所以可以求得此數(shù)組的通項公式為ai=3*2e(i-1)-2 (i=2)。如果用鏈結(jié)構(gòu)解決這個問題，建立一個鏈表，根據(jù)

3、每天桃子數(shù)與后一天桃子數(shù)的關(guān)系n=2*n+2,依次將每天的桃子數(shù)存進鏈表中，最后輸出第一天的桃子數(shù)。2 .圖紙部分：程序流程圖圖1-1開始N圖1-2四、進程安排(1)設(shè)計題目、設(shè)計要求以及系統(tǒng)功能需求分析；(2)總體設(shè)計：包括系統(tǒng)總體設(shè)計框架和系統(tǒng)功能模塊圖；(3)詳細設(shè)計：包括主要功能模塊的算法設(shè)計思路以及對應(yīng)的工作流程圖；(4)主要源程序代碼：包括存儲設(shè)計說明，以及完整源程序清單(放在附錄中)；(5)調(diào)試分析過程描述：包括測試數(shù)據(jù)、測試輸出結(jié)果，以及對程序調(diào)試過程中存在問題的思考(列出主要問題的出錯現(xiàn)象、出錯原因、解決方法及效果等)；(6)總結(jié)：包括課程設(shè)計過程中的學習體會與收獲、對C語言

4、和本次課程設(shè)計的認識等內(nèi)容。(7)附錄(完整源程序清單)五、主要參考資料1王紅梅，胡明，王濤.數(shù)據(jù)Z勾（C+版）.北京：清華大學出版社， 20072王紅梅，胡明，王濤.數(shù)據(jù)Z勾（C+版）學習輔導(dǎo)與實驗指導(dǎo).北京：清華大學出版，20073譚浩強.C+程序設(shè)計.北京：清華大學出版社,20044鄭阿奇，丁有和.Visual C+ 教程.北京：機械工業(yè)出版社，20065李文軍，李師賢，周曉聰.C+作為計算機專業(yè)程序設(shè)計入門語言的實踐與探討.計算機科學，1999, 26 （4） : 8083成績評定表作品成績報告成績口試（答辯）成績總評成績摘要當下C+叫言是一門重要的課程學習，學會運用并結(jié)合其他的知識一

5、起解題 是一件值得我們重視的，數(shù)據(jù)結(jié)構(gòu)是一門結(jié)合 C+跌口識的重要課程，因此我們要 學會將平時課本的知識運用到我們現(xiàn)實生活當中，這樣才能讓我們所學的知識更加深刻。 猴子吃桃的問題就是一個例子，我們可以運用簡單的三種解法進行解題，即數(shù)組求值解法，鏈表求值解法和遞歸求值解法，通過分析三種解法，根據(jù)各種解法的功能從而我們得到最合適的求法。關(guān)鍵詞：猴子吃桃，數(shù)組法，鏈表法，遞歸法，分析目錄1、需求分析 12、概要設(shè)計 11.1 .用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解 11.2 .用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解 11.3 用遞歸實現(xiàn)上述求解 11.4 用棧數(shù)據(jù)結(jié)構(gòu)實現(xiàn)求解 13、 運行環(huán)境 23.1 硬件環(huán)境 23.2

6、 軟件環(huán)境 24、 詳細設(shè)計 24.1 系統(tǒng)流程圖 24.2 用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解 34.3 用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解 44.4 用遞歸實現(xiàn)上述求解 44.5 用棧數(shù)據(jù)結(jié)構(gòu)實現(xiàn)求解 55、 調(diào)試分析 66、運行結(jié)果 7課程設(shè)計總結(jié) 10致謝 錯誤！未定義書簽。參考文獻 121 、需求分析1、 猴子吃桃子問題有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10 天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。要求：1) 采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解2) 采用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解3) 采用遞歸實現(xiàn)上述求解4) 如果采用第4 種做法，適當加分2、概要

7、設(shè)計2.1. 用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解在 peach 函數(shù)中定義一個一維數(shù)組，分別存儲每天的桃子個數(shù)，根據(jù)題目的內(nèi)容找出各個數(shù)之間的關(guān)系，用數(shù)組元素表示出來，根據(jù)用戶輸入要計算哪一天的桃子，用 for 循環(huán)控制結(jié)束。在main 函數(shù)中讓用戶輸入要計算的哪一天，調(diào)用peach 函數(shù)，以便用戶可查出任意一天的桃子個數(shù)，用switch 語句判斷用戶要執(zhí)行的功能，然后用while 循環(huán)控制，直到用戶輸入4 為止。2.2. 用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解先寫出預(yù)定義常量和類型，寫出結(jié)點的類型定義，創(chuàng)建結(jié)點，初始化鏈表，定義變量并初始化，找出結(jié)點與其后繼結(jié)點之間的聯(lián)系，然后在主函數(shù)中控制。2.3. 用遞歸實現(xiàn)

8、上述求解這種方法跟上述幾種不同，在函數(shù)的執(zhí)行函數(shù)的過程中，需多次進行自我調(diào)用，遞歸函數(shù)的運行過程類似與多個函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)，從主函數(shù)開始調(diào)用，一次更深一層，退出時一步一步返回到上一層，所以不需寫控制循環(huán)語句，不需要寫控制循環(huán)語句，比上幾種方法簡單點。3、運行環(huán)境3.1 硬件環(huán)境PC3.2 軟件環(huán)境1 1) Windows 72 2) Microsoft Visual C+6.04、詳細設(shè)計4.1 系統(tǒng)流程圖猴子吃桃問題的實現(xiàn)14用數(shù)組結(jié)構(gòu)實現(xiàn)用 鏈 數(shù) 據(jù) 結(jié) 構(gòu) 實 現(xiàn)用 遞 歸 方 法 實 現(xiàn)三種方法結(jié)合4.2 用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解#include

9、#define DAY 10 / 天數(shù)using namespace std;int main()int peachDAY;/存儲數(shù)組peachDAY-1 = 1;/ 最后一天桃子數(shù)for(int i=DAY-2;i=0;i-)peachi = (peachi+1+1)*2;cout桃子數(shù)：peach0endl;return 0;4.3用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解#include #include#define NULL 0typedef struct linknodeint data;struct linknode *next;node;node *head;void creat()node *

10、p,*s;int peaches=1;int day=10;head=(node*)malloc(sizeof(node);p=head;while(day0)s=(node*)malloc(sizeof(node);s-data=peaches;p-next=s;p=s;peaches=(peaches+1)*2;day-;p-next=NULL;p=head;head=head-next;free(p);void print()node *p;p=head;int day=10;while(p&day0)printf(%d:%dn,day,p-data);p=p-next;day-;voi

11、d main()creat();print();4.4用遞歸實現(xiàn)上述求解#includeint tao(int n)if(n=10) return 1;return 2*(tao(n+1)+1);void main()int sum=0;sum+=tao(1);printf(共摘了 桃子！ n,sum);5、調(diào)試分析調(diào)試基本無錯誤，僅字體及符號的錯誤，很容易便改正過來6、運行結(jié)果用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn): C：U &e nAdministratcTHQH-20141219RrWEXDesktop2.e)cc ,桃子數(shù)好34請按荏意鍵繼續(xù)-用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn):* *C ： Useminirtrator,

12、QH-20141219 FYWEDeslrtop 2 exe* -1pl桃子廣：334 請按荏意鍵繼續(xù).用遞歸實現(xiàn): *CAtlwrsAtiministratorHQH-20i41219FWEDeslrtDpSS2ejee*用綜合實現(xiàn):I C:U5er5Adm i nistratcr.Q H - 2 0141219 FYW EDes 仙叩，最終 綜合三項功能,eke 數(shù)歸組接數(shù)歸組接 子，遞饕 婁示示示七 組量表矗1 2 3 L落子數(shù)1534 i不遞歸；示教組:課程設(shè)計總結(jié)通過這兩周的實踐學習，我認識到學好計算機要重視實踐操作，不僅僅是學習數(shù)據(jù)結(jié)構(gòu)，以及其它的計算機方面的知識都要重在實踐，很多

13、以前學過的東西，在運用時都不能很熟練，也說明理論知識和實踐之間的差別。這就告訴了我們在以后的學習過程中要培養(yǎng)自己的動手能力，要將學過的知識轉(zhuǎn)化為實踐。作為一個計科專業(yè)的學生，通過這周的學習，使我更加明白了動手能力的重要性。在這次的課程設(shè)計中，我不斷地去找書本知識和查閱其它有關(guān)資料，不僅鞏固了對課本知識的掌握，還有利于以后更好的進步，提高了對課外知識的了解，雖然花費了不少時間，但只要學到有價值的東西，我認為都是值得的。在完成該試驗的過程中，我問了同學和老師，還查閱了很多和鏈表有關(guān)系的書籍，通過學習， 翻看以前學過的知識，使我明白了我在學習知識上的很多不足。不過在此同時又重新復(fù)習了課本，從中學到了

14、許多以前未學到的知識，感覺非常有成就感，讓我對自己更加有信心，讓我對數(shù)據(jù)結(jié)構(gòu)這門課程也更感興趣了，以前我一直感覺枯燥難學的數(shù)據(jù)結(jié)構(gòu)，現(xiàn)在我也愿意去認真研究學習了。這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計中，多虧了我的指導(dǎo)老師周海巖老師的悉心教導(dǎo)。在以后的學習過程中，我要認真負責地對待課本中的每一個知識點，進一步充實自己，提高自己。致謝這次課程設(shè)計，首先要感謝學院給了我們相當好的試驗環(huán)境，機房的設(shè)備很好，學習環(huán)境也很好，一點沒有吵鬧，也要老師，在這兩周的教導(dǎo)，每天陪著我們，解答我們的疑難，也監(jiān)督我們的學習。當然， 同學們的幫助也是很重要的，我們互相討論，雖然課題并不一樣，可是解決方法卻大同小異，各方面知識都要運用到，合作就顯得至關(guān)重要?？傊瓿蛇@次課程設(shè)計，要搞些的太多，以后一定要更好的學習數(shù)據(jù)結(jié)構(gòu)，冰靈活地運用。參考文獻數(shù)據(jù)結(jié)構(gòu)與算法分析（C+版）（第三版）Clifford A. Shaffer （克利福德A.謝弗）1馬安鵬.Visual C+程序設(shè)計導(dǎo)學。北京：清華大學出版社，20022電子書籍.Visual C+技術(shù)內(nèi)幕（第四版）.網(wǎng)址:3 Beck Zaratian.Microsoft Visual Visual