課程設(shè)計(jì)說明書課程名稱：數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題目：猴子吃桃問題學(xué)院：計(jì)算機(jī)科學(xué)與信息工程學(xué)院學(xué)生姓名：學(xué)生學(xué)號(hào)：專業(yè)班級(jí)：軟件工程指導(dǎo)教師：宋強(qiáng)2014年06月15日課程設(shè)計(jì)任務(wù)書設(shè)計(jì)題目猴子吃桃問題學(xué)生姓名班級(jí)軟件工程設(shè)計(jì)要求：基本要求(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)上述求解(4)采用隊(duì)列實(shí)現(xiàn)上述求解學(xué)生應(yīng)完成的工作：參考文獻(xiàn)閱讀：參考文獻(xiàn)[1]嚴(yán)蔚敏等編著.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京：清華大學(xué)出版社，2003[2]李春葆，金晶編著.數(shù)據(jù)結(jié)構(gòu)教程（C語言版）.北京：清華大學(xué)出版社，2006[3]朱立華等編著.面向?qū)ο蟪绦蛟O(shè)計(jì)及C++.北京：人民郵電出版社，2008工作計(jì)劃：任務(wù)下達(dá)日期：2014年06月01日任務(wù)完成日期：2014年06月15日學(xué)生（簽名）：猴子吃桃問題摘要：數(shù)據(jù)結(jié)構(gòu)是一門結(jié)合C++知識(shí)的重要課程，因此我們要學(xué)會(huì)用平時(shí)課本的知識(shí)運(yùn)用到我們的現(xiàn)實(shí)生活當(dāng)中，這樣才能讓我們所學(xué)的知識(shí)更加深刻。分析了猴子吃桃子問題的實(shí)質(zhì)，得到了其數(shù)學(xué)模型ni-1=2*（ni+1）(0，接下來就是其需求分析和概要設(shè)計(jì)，大致的制定出其實(shí)現(xiàn)方案以及其系統(tǒng)結(jié)構(gòu)，然后就是利用掌握的語言C/C++編程實(shí)現(xiàn)這一生活問題，該軟件用了幾種不同的方法解答出了所需要的答案。猴子吃桃的問題就是一個(gè)例子，我們可以運(yùn)用簡(jiǎn)單的四種解法進(jìn)行解題，即數(shù)組求值解法，鏈表求值解法，遞歸求值解法和隊(duì)列求值法，通過分析四種解法，根據(jù)各種解法的功能，從而我們得到最合適的求法。關(guān)鍵詞：猴子吃桃子；數(shù)組法；鏈表法；遞歸法；隊(duì)列法；分析目錄TOC\o"3-3"\h\z\t"樣式0標(biāo)題1+黑體(西文)小三非(西文)粗體,1,1111,1,2222,2,3333,3"1設(shè)計(jì)背景 .設(shè)計(jì)背景1.1問題描述有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再多吃一個(gè)，到了第10天就只余下一個(gè)桃子。用多種方法實(shí)現(xiàn)求出原來這群猴子共摘了多少個(gè)桃子。1.2基本要求(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)上述求解(4)采用隊(duì)列實(shí)現(xiàn)上述求解1.3開發(fā)及運(yùn)行平臺(tái)在本課程設(shè)計(jì)中，系統(tǒng)開發(fā)平臺(tái)為Windows2000,程序設(shè)計(jì)語言為VisualC++6.0，程序的運(yùn)行環(huán)境為VisualC++6.0。VisualC++一般分為三個(gè)版本:學(xué)習(xí)版、專業(yè)版和企業(yè)版，不同的版本適合于不同類型的應(yīng)用開發(fā)。實(shí)驗(yàn)中可以使用這三個(gè)版本的任意一種，在本課程設(shè)計(jì)中，以VisualC++6.0為編程環(huán)境。MicrosoftVisualC++6.0是Microsof公司的MicrosoftVisualStudio6.0開發(fā)工具箱中的一個(gè)C++程序開發(fā)包。VisualC++包中除包括C++編譯器外，還包括所有的庫、例子和為創(chuàng)建Windows應(yīng)用程序所需要的文檔。自1993年Microsoft公司推出VisualC++1.0后，隨著其新版本的不斷問世，VisualC++已成為專業(yè)程序員進(jìn)行軟件開發(fā)的首選工具。VisualC++從最早期的1.0版本，發(fā)展到最新的7.0版本，VisualC++已經(jīng)有了很大的變化，在界面、功能、庫支持方面都有許多的增強(qiáng)。最新的7.0版本在編譯器、MFC類庫、編輯器以及聯(lián)機(jī)幫助系統(tǒng)等方面都比以前的版本做了較大改進(jìn)。VisualC++6.0是Microsoft公司推出的目前使用最廣泛的基于Windows平臺(tái)的可視化編程環(huán)境。VisualC++6.0是在以往版本不斷更新的基礎(chǔ)上形成的，由于其功能強(qiáng)大，靈活性好，完全課擴(kuò)展以及具有強(qiáng)大的Internet支持，因而在各種C++語言開發(fā)工具中脫穎而出，成為目前最為流行的C++語言集成開發(fā)環(huán)境。雖然微軟公司推出了Visual

C++.NET(Visual

C++7.0)，但它的應(yīng)用的很大的局限性，只適用于Windows

2000,Windows

XP和Windows

NT4.0。所以實(shí)際中，更多的是以VisualC++6.0為平臺(tái)。VisualC++6.0是Microsoft公司推出的目前使用最廣泛的基于Windows平臺(tái)的可視化編程環(huán)境。Visual

C++

6.0是在以往版本不斷更新的基礎(chǔ)上形成的，由于其功能強(qiáng)大，靈活性好，完全課擴(kuò)展以及具有強(qiáng)大的Internet支持，因而在各種C++語言開發(fā)工具中脫穎而出，成為目前最為流行的C++語言集成開發(fā)環(huán)境。VisualC++6.0秉承Visual

C++以前版本的優(yōu)異特性，為用戶提供了一套良好的可視化開發(fā)環(huán)境：主要包括文本編輯器、資源編輯器、工程創(chuàng)建工具、Debugger調(diào)試器等等。用戶可以在集成開發(fā)環(huán)境中創(chuàng)建工程、打開工程、建立、打開和編輯文件、編譯、鏈接、運(yùn)行、調(diào)試應(yīng)用程序。2.設(shè)計(jì)方案2.1題目分析根據(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，第九天時(shí)桃子個(gè)數(shù)n9，第十天時(shí)桃子個(gè)數(shù)n10。由題中“每天都吃當(dāng)前桃子的一半且再多吃一個(gè)”很容易知道n10=1，n9-（n9/2+1）=n10，n8-（n8/2+1）=n9……依次推出公式：ni-1-（ni-1/2+1）=ni(0。即ni-1=2*（ni+1）(0。2.2需求分析規(guī)格由上述描述及分析可知，該系統(tǒng)所要做的工作就是計(jì)算出原來這群猴子共摘了多少個(gè)桃子。通過分析不同的解法，找到每種解法的優(yōu)劣，得到最合適的求解方法。由問題描述可知，該系統(tǒng)運(yùn)行時(shí)，不需要手動(dòng)輸入任何數(shù)據(jù)，因此就沒有輸入的測(cè)試數(shù)據(jù)，只有輸出的測(cè)試數(shù)據(jù)，且輸出數(shù)據(jù)的形式是輸出每天剩下的桃子數(shù)，最后輸出這群猴子總共摘了多少桃子。2.2.1數(shù)組求解法分析分析：聲明一個(gè)長度為10的整形數(shù)組a[10],分別存放各天猴子吃前的桃子數(shù)。下圖1所示：n1n2n3n4n5n6n7n8n9n10a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a圖2.2.1數(shù)組元素分布圖先將a[9]賦值為1，用一個(gè)循環(huán)語句for(inti=8;i>=0;i--)a[i]=2*(a[i+1]+1);為其余各數(shù)組元素賦值，則數(shù)組元素a[0]的值便是該問題解。數(shù)據(jù)類型定義：inta[10];a[9]=1;2.2.2鏈表求解法分析分析：建立單鏈表，聲明一個(gè)類用來對(duì)鏈表的結(jié)點(diǎn)指針進(jìn)行定義，在初始化函數(shù)中利用頭插法創(chuàng)建具有10個(gè)元素的鏈表，并依次安公式ni-1=2*（ni+1）(0。賦值得到一個(gè)如圖2所示的鏈表。圖2.2.2鏈表結(jié)點(diǎn)邏輯結(jié)構(gòu)圖數(shù)據(jù)類型定義：classlist{public: intdata;classlist*next; voidpush();};typedefclasslistnode;//建立單鏈表(將class重定義為node)typedefnode*link;//定義結(jié)點(diǎn)指針2.2.3遞歸法分析分析：利用一個(gè)遞歸函數(shù)來進(jìn)行求值：依據(jù)返回值來記錄每一天剩余桃子情況。intprocess(intn){ if(n==10) return1; else return2*(process(n+1)+1);}2.2.4隊(duì)列法分析分析：定義一個(gè)隊(duì)列，和一個(gè)臨時(shí)變量，臨時(shí)變量存放第十天到第一天的剩下的桃子數(shù)目，每計(jì)算出一天的剩余的桃子數(shù)，就將其入隊(duì)，十天的剩余桃子數(shù)全部入隊(duì)以后就出對(duì)，即得到每一天的剩余桃子數(shù)，最后得到的一個(gè)數(shù)據(jù)就是所要求的桃子的總數(shù)。數(shù)據(jù)類型定義：typedefstructSqQueue{ intdata[QueueSize]; intfornt,rear;//隊(duì)首、隊(duì)尾指針}SqQueue;2.3數(shù)據(jù)流程圖圖2.3.1數(shù)據(jù)流程圖2.4系統(tǒng)結(jié)構(gòu)圖圖2.4.1系統(tǒng)結(jié)構(gòu)圖3.方案實(shí)施3.1數(shù)據(jù)類型定義ina[10];classlist{public: intdata;classlist*next; voidpush();};typedefclasslistnode;//建立單鏈表(將class重定義為node)typedefnode*link;//定義結(jié)點(diǎn)指針typedefstructSqQueue{ intdata[QueueSize]; intfornt,rear;//隊(duì)首、隊(duì)尾指針}SqQueue;3.2主要模塊設(shè)計(jì)3.2.1模塊1——數(shù)組求解模塊模塊算法：//數(shù)組求解voidArray_Solve(){ inta[10];//存放 inti;a[9]=1; cout<<"★數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn):"<<endl; cout<<"第10天剩下的桃子為:"<<a[9]<<endl;for(i=8;i>=0;i--) { a[i]=(a[i+1]+1)*2; cout<<"第"<<i+1<<"天剩下的桃子為:"<<a[i]<<endl; } cout<<"所以猴子共摘了"<<a[0]<<"個(gè)桃子"<<endl; cout<<endl;}流程圖圖3.2.1數(shù)組求解流程圖3.2.2模塊2——鏈表求解模塊模塊算法//鏈表求解voidLink_Solve(){ linkhead; listlist1; head=newnode;p=head; list1.push(); p=head->next; cout<<"★鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn):"<<endl;cout<<"第10天剩下的桃子為:1"<<endl;inti=9;while(p){ cout<<"第"<<i<<"天剩下的桃子為:"<<p->data<<endl; if(i==1) cout<<"所以猴子共摘了"<<p->data<<"個(gè)桃子"<<endl; p=p->next; i--; }cout<<endl;}3.2.3模塊3——遞歸求解模塊模塊算法intprocess(intn)//遞歸{ if(n==10) return1; else return2*(process(n+1)+1);}//遞歸求解voidFac_Solve(){ cout<<"★遞歸方法實(shí)現(xiàn):"<<endl; for(inti=10;i>0;i--) cout<<"第"<<i<<"天剩下的桃子為:"<<process(i)<<endl; cout<<"所以猴子共摘了"<<process(1)<<"個(gè)桃子"<<endl<<endl;}3.2.4模塊4——隊(duì)列求解模塊模塊算法//隊(duì)列求解voidQueue_Solve(){ SqQueueSQ; SQ.fornt=SQ.rear=0; inttemp;//臨時(shí)變量，存放每一天剩的桃子數(shù) temp=1;//初始放第十天的 for(inti=0;i<10;i++) { SQ.data[SQ.rear++]=temp; temp=2*(temp+1); } cout<<"★隊(duì)列數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn):"<<endl; while(SQ.fornt!=SQ.rear) cout<<"第"<<11-SQ.fornt<<"天剩下的桃子為:"<<SQ.data[SQ.fornt++]<<endl; cout<<"所以猴子共摘了"<<SQ.data[SQ.fornt-1]<<"個(gè)桃子"<<endl<<endl;}3.3源程序清單#include<iostream>#include<cstdlib>#include<cstdio>#defineQueueSize10usingnamespacestd;classlist{public: intdata;classlist*next; voidpush();};typedefclasslistnode;//建立單鏈表(將class重定義為node)typedefnode*link;//定義結(jié)點(diǎn)指針linkp=NULL;voidlist::push(){ links; intj=1; p->data=j; for(inti=9;i>0;i--) { s=newnode; s->data=(j+1)*2; j=s->data; s->next=NULL; p->next=s; p=p->next; }}typedefstructSqQueue{ intdata[QueueSize]; intfornt,rear;//隊(duì)首、隊(duì)尾指針}SqQueue;//數(shù)組求解voidArray_Solve(){ inta[10];//存放 inti;a[9]=1; cout<<"★數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn):"<<endl; cout<<"第10天剩下的桃子為:"<<a[9]<<endl; for(i=8;i>=0;i--) {a[i]=(a[i+1]+1)*2; cout<<"第"<<i+1<<"天剩下的桃子為:"<<a[i]<<endl; } cout<<"所以猴子共摘了"<<a[0]<<"個(gè)桃子"<<endl; cout<<endl;}//鏈表求解voidLink_Solve(){ linkhead; listlist1; head=newnode; p=head; list1.push(); p=head->next; cout<<"★鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn):"<<endl;cout<<"第10天剩下的桃子為:1"<<endl;inti=9;while(p){ cout<<"第"<<i<<"天剩下的桃子為:"<<p->data<<endl; if(i==1) cout<<"所以猴子共摘了"<<p->data<<"個(gè)桃子"<<endl; p=p->next;i--; }cout<<endl;}intprocess(intn)//遞歸{ if(n==10) return1; else return2*(process(n+1)+1);}//遞歸求解voidFac_Solve(){cout<<"★遞歸方法實(shí)現(xiàn):"<<endl; for(inti=10;i>0;i--) cout<<"第"<<i<<"天剩下的桃子為:"<<process(i)<<endl; cout<<"所以猴子共摘了"<<process(1)<<"個(gè)桃子"<<endl<<endl;}//隊(duì)列求解voidQueue_Solve(){ SqQueueSQ; SQ.fornt=SQ.rear=0; inttemp;//臨時(shí)變量，存放每一天剩的桃子數(shù) temp=1;//初始放第十天的 for(inti=0;i<10;i++) { SQ.data[SQ.rear++]=temp; temp=2*(temp+1); } cout<<"★隊(duì)列數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn):"<<endl; while(SQ.fornt!=SQ.rear) cout<<"第"<<11-SQ.fornt<<"天剩下的桃子為:"<<SQ.data[SQ.fornt++]<<endl; cout<<"所以猴子共摘了"<<SQ.data[SQ.fornt-1]<<"個(gè)桃子"<<endl<<endl;}voidmenu(){ system("cls"); system("color0A"); cout<<endl<<endl;cout<<"|************************主菜單**************************|"<<endl;cout<<"||"<<endl;cout<<"|1、數(shù)組求解|"<<endl;cout<<"|2、鏈表求解|"<<endl;cout<<"|3、遞歸求解|"<<endl;cout<<"|4、隊(duì)列求解|"<<endl;cout<<"|5、退出|"<<endl;cout<<"||"<<endl;}voidmain(){ intn; charch; while(1) { menu(); cout<<"請(qǐng)選擇："; cin>>n; switch(n) { case1:Array_Solve(); cout<<"按任意鍵繼續(xù)..."; ch=getchar();ch=getchar(); break; case2:Link_Solve();cout<<"按任意鍵繼續(xù)..."; ch=getchar();ch=getchar(); break; case3:Fac_Solve(); cout<<"按任意鍵繼續(xù)..."; ch=getchar();ch=getchar(); break; case4:Queue_Solve(); cout<<"按任意鍵繼續(xù)..."; ch=getchar();ch=getchar(); break; case5:exit(0); default:cout<<"選擇錯(cuò)誤!"<<endl; } }}4.結(jié)果與結(jié)論4.1調(diào)試分析4.1.1數(shù)組求解模塊的時(shí)間復(fù)雜度：因?yàn)槠渲醒h(huán)for(i=8;i>=0;i--)，因此其時(shí)間復(fù)雜度為O(9).數(shù)組求解模塊的空間復(fù)雜度：因?yàn)椴恍枰斎肴魏螖?shù)據(jù)，所以該算法為原地工作。4.1.2鏈表求解模塊的時(shí)間復(fù)雜度：因?yàn)樗惴ㄖ杏玫揭粋€(gè)循環(huán)來輸出，因此其時(shí)間復(fù)雜度為O(9).鏈表求解模塊的空間復(fù)雜度：原地工作。4.1.3隊(duì)列求解模塊的時(shí)間復(fù)雜度：因?yàn)閒or(i=0;i<10;i++)，所以時(shí)間復(fù)雜度為O(9)。隊(duì)列求解模塊的空間復(fù)雜度：因?yàn)橛昧艘粋€(gè)存儲(chǔ)臨時(shí)變量的空間，所以其空間復(fù)雜度為O(1)。4.2程序運(yùn)行結(jié)果程序運(yùn)行結(jié)果：第10天剩下的桃子為:1第9天剩下的桃子為:4第8天剩下的桃子為:10第7天剩下的桃子為:22第6天剩下的桃子為:46第5天剩下的桃子為:94第4天剩下的桃子為:190第3天剩下的桃子為:382第2天剩下的桃子為:766第1天剩下的桃子為:1534所以猴子共摘了1534個(gè)桃子本測(cè)試分別輸出了三種方法所求得的結(jié)果為：1534個(gè)，另外還用數(shù)組法，鏈表法，隊(duì)列法和遞歸法分別求出了，猴子在吃桃子的10天內(nèi)，各天含有桃子的數(shù)量：下面進(jìn)行驗(yàn)證結(jié)果：原始桃子為：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-（