《算法設(shè)計(jì)與分析》實(shí)驗(yàn)一_實(shí)驗(yàn)報(bào)告電子版.doc

學(xué) 號(hào) 09710118算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告一學(xué)生姓名范振山專業(yè)、班級(jí)09計(jì)算機(jī)一班指導(dǎo)教師唐國(guó)峰成績(jī)電子與信息工程系2012 年 3 月 9 日實(shí)驗(yàn)一：遞歸策略運(yùn)用練習(xí)一、實(shí)驗(yàn)?zāi)康谋敬螌?shí)驗(yàn)是針對(duì)遞歸算法的算法設(shè)計(jì)及應(yīng)用練習(xí)，旨在加深學(xué)生對(duì)該算法原理的理解，提高學(xué)生運(yùn)用該算法解決問(wèn)題的能力。二、實(shí)驗(yàn)步驟與要求1實(shí)驗(yàn)前復(fù)習(xí)課程所學(xué)知識(shí)以及閱讀和理解指定的課外閱讀材料；2學(xué)生獨(dú)自完成實(shí)驗(yàn)指定內(nèi)容；3實(shí)驗(yàn)結(jié)束后，用統(tǒng)一的實(shí)驗(yàn)報(bào)告模板編寫實(shí)驗(yàn)報(bào)告。4提交說(shuō)明： （1）電子版提交說(shuō)明：a 需要提交Winrar壓縮包，文件名為“算法設(shè)計(jì)與分析實(shí)驗(yàn)一_學(xué)號(hào)_姓名”，如“算法設(shè)計(jì)與分析實(shí)驗(yàn)一_09290101_張三”。 b 壓縮包內(nèi)為一個(gè)“算法設(shè)計(jì)與分析實(shí)驗(yàn)一_學(xué)號(hào)_姓名”命名的頂層文件夾，其下為兩個(gè)文件夾，一個(gè)文件夾命名為“源程序”，另一個(gè)文件夾命名為“實(shí)驗(yàn)報(bào)告電子版”。其下分別放置對(duì)應(yīng)實(shí)驗(yàn)成果物。 （2）打印版提交說(shuō)明：a 不可隨意更改模板樣式。 b 字體：中文為宋體，大小為10號(hào)字，英文為Time New Roman，大小為10號(hào)字。 c 行間距：?jiǎn)伪缎芯唷＃?）提交截止時(shí)間：2012年3月23日16:00。三、 實(shí)驗(yàn)項(xiàng)目1運(yùn)用遞歸策略設(shè)計(jì)算法實(shí)現(xiàn)下述題目的求解過(guò)程。題目列表如下：（1）運(yùn)動(dòng)會(huì)開(kāi)了N天，一共發(fā)出金牌M枚。第一天發(fā)金牌1枚加剩下的七分之一枚，第二天發(fā)金牌2枚加剩下的七分之一枚，第3天發(fā)金牌3枚加剩下的七分之一枚，以后每天都照此辦理。到了第N天剛好還有金牌N枚，到此金牌全部發(fā)完。編程求N和M。（2）國(guó)王分財(cái)產(chǎn)。某國(guó)王臨終前給兒子們分財(cái)產(chǎn)。他把財(cái)產(chǎn)分為若干份，然后給第一個(gè)兒子一份，再加上剩余財(cái)產(chǎn)的1/10；給第二個(gè)兒子兩份，再加上剩余財(cái)產(chǎn)的1/10；給第i個(gè)兒子i份，再加上剩余財(cái)產(chǎn)的1/10。每個(gè)兒子都竊竊自喜。以為得到了父王的偏愛(ài)，孰不知國(guó)王是“一碗水端平”的。請(qǐng)用程序回答，老國(guó)王共有幾個(gè)兒子？財(cái)產(chǎn)共分成了多少份？（3）出售金魚問(wèn)題：第一次賣出全部金魚的一半加二分之一條金魚；第二次賣出乘余金魚的三分之一加三分之一條金魚；第三次賣出剩余金魚的四分之一加四分之一條金魚；第四次賣出剩余金魚的五分之一加五分之一條金魚；現(xiàn)在還剩下11條金魚，在出售金魚時(shí)不能把金魚切開(kāi)或者有任何破損的。問(wèn)這魚缸里原有多少條金魚？（4）某路公共汽車，總共有八站，從一號(hào)站發(fā)軒時(shí)車上已有n位乘客，到了第二站先下一半乘客，再上來(lái)了六位乘客；到了第三站也先下一半乘客，再上來(lái)了五位乘客，以后每到一站都先下車上已有的一半乘客，再上來(lái)了乘客比前一站少一個(gè)，到了終點(diǎn)站車上還有乘客六人，問(wèn)發(fā)車時(shí)車上的乘客有多少？（5）猴子吃桃。有一群猴子摘來(lái)了一批桃子，猴王規(guī)定每天只準(zhǔn)吃一半加一只（即第二天吃剩下的一半加一只，以此類推），第九天正好吃完，問(wèn)猴子們摘來(lái)了多少桃子？（6）小華讀書。第一天讀了全書的一半加二頁(yè)，第二天讀了剩下的一半加二頁(yè)，以后天天如此，第六天讀完了最后的三頁(yè)，問(wèn)全書有多少錢頁(yè)？（7）日本著名數(shù)學(xué)游戲?qū)＜抑写辶x作教授提出這樣一個(gè)問(wèn)題：父親將2520個(gè)桔子分給六個(gè)兒子。分完 后父親說(shuō)：“老大將分給你的桔子的1/8給老二；老二拿到后連同原先的桔子分1/7給老三；老三拿到后連同原先的桔子分1/6給老四；老四拿到后連同原先的桔子分1/5給老五；老五拿到后連同原先的桔子分1/4給老六；老六拿到后連同原先的桔子分1/3給老大”。結(jié)果大家手中的桔子正好一樣多。問(wèn)六兄弟原來(lái)手中各有多少桔子？四、實(shí)驗(yàn)過(guò)程（一）題目一：運(yùn)動(dòng)會(huì)開(kāi)了N天，一共發(fā)出金牌M枚。第一天發(fā)金牌1枚加剩下的七分之一枚，第二天發(fā)金牌2枚加剩下的七分之一枚，第3天發(fā)金牌3枚加剩下的七分之一枚，以后每天都照此辦理。到了第N天剛好還有金牌N枚，到此金牌全部發(fā)完。編程求N和M。1. 題目分析第一天有(M-1)*1/7枚金牌，第二天又金牌2+f(2)-2*1/7,依次類推，第n天就有f(n,2)=f(n,1)-(1+(f(n,1)-1)/7)枚金牌。2. 算法構(gòu)造在此論證算法設(shè)計(jì)中的一些必要的設(shè)計(jì)依據(jù)。第一天的金牌數(shù)量為f(n,1)，發(fā)金牌的數(shù)量為1+(f(n,1)-1)/7,，第二天的金牌數(shù)量為f(n,2),發(fā)的金牌數(shù)量為2+(f(n,2)-2)/7，則f(n,2)=f(n,1)-(1+(f(n,1)-1)/7)，類推得：f(n,i)=f(n,i+1)+i+(f(n,i)-i)/7;3. 算法實(shí)現(xiàn)程序源代碼（請(qǐng)寫入必要的注釋）。/ 預(yù)編譯命令#include using namespace std;/定義每一天發(fā)放獎(jiǎng)牌中從剩余部分來(lái)源的幾分之一。如此處為7即為1/7#define Fenmu 7/遞歸函數(shù)，nMedalSum為第N天獎(jiǎng)牌的總數(shù)，包括當(dāng)天分發(fā)的和剩余的兩部分之和int nMedalSum(int i,int n)int result=0;if (i = n) result=Fenmu-1;elseresult=(nMedalSum(i+1,n)*Fenmu/(Fenmu-1)+i);return result; /主函數(shù)void main() int n=Fenmu-1;/運(yùn)動(dòng)會(huì)連續(xù)持續(xù)天數(shù)int m;/獎(jiǎng)牌總數(shù)for (int i=1; i=n; i+)/當(dāng)天的獎(jiǎng)牌總數(shù)必須被分母減一整除，以合乎題意，作為頭天剩余獎(jiǎng)牌數(shù)if ( nMedalSum(i,n)%(Fenmu-1)=0)if(n=i)break;else/一旦發(fā)現(xiàn)有余數(shù)，則當(dāng)前天數(shù)不合法，天數(shù)需加分母減一n=n+Fenmu-1; cout 運(yùn)動(dòng)會(huì)連續(xù)召開(kāi) n 天 ,共有金牌 nMedalSum(1,n) 塊。 endl endl;cout 具體分發(fā)情況如下所示： endl endl;for(i=1;i=n;i+)cout 第 i 天發(fā)獎(jiǎng)牌數(shù)為 i + (nMedalSum(i,n)-i)/7 塊，剩余 (nMedalSum(i,n)-i)/7*6 塊 endl;cout endl;system(pause);4 運(yùn)行結(jié)果5 經(jīng)驗(yàn)歸納這道程序題的基本思想已理解，可是程序中的應(yīng)用卻不是那么好。因?yàn)榭蠢蠋煹睦又笥X(jué)得更難理解。不過(guò)所幸的是在同學(xué)的講解下把那部分公式理解了?？墒墙形以賹懙脑掃@很復(fù)雜，我就不一定寫的出來(lái)了。 （2）國(guó)王分財(cái)產(chǎn)。某國(guó)王臨終前給兒子們分財(cái)產(chǎn)。他把財(cái)產(chǎn)分為若干份，然后給第一個(gè)兒子一份，再加上剩余財(cái)產(chǎn)的1/10；給第二個(gè)兒子兩份，再加上剩余財(cái)產(chǎn)的1/10；給第i個(gè)兒子i份，再加上剩余財(cái)產(chǎn)的1/10。每個(gè)兒子都竊竊自喜。以為得到了父王的偏愛(ài)，孰不知國(guó)王是“一碗水端平”的。請(qǐng)用程序回答，老國(guó)王共有幾個(gè)兒子？財(cái)產(chǎn)共分成了多少份？1.題目分析有n個(gè)兒子就有n分財(cái)產(chǎn)，并且由題意可知2.算法構(gòu)造在此論證算法設(shè)計(jì)中的一些必要的設(shè)計(jì)依據(jù)。國(guó)王有n個(gè)兒子，那么第總共有N份財(cái)產(chǎn)，那么n個(gè)兒子得到的是n份加上剩余的1/10,第n個(gè)兒子得到的是n份。，沒(méi)有剩余3.算法實(shí)現(xiàn)第一個(gè)兒子得到的是1+（N-1）1/10,第二個(gè)兒子得到的是2+N(2)*1/10,剩下的是f(3)=9/10*(f2-2)所以第i個(gè)兒子是fi-1=10/9*fi+(i-1)4. 算法實(shí)現(xiàn)程序源代碼（請(qǐng)寫入必要的注釋）。#includeusing namespace std;#includeusing namespace std;/主函數(shù)int main()int i; int n=0;n=n+9;int f100;fn=n;for(i=n;i1;i-)fi+1=10/9*(fi+i);cout老國(guó)王共有:n兒子endl;cout財(cái)產(chǎn)共分了n+nendl;return 0;運(yùn)行結(jié)果4,經(jīng)驗(yàn)歸納在做這個(gè)實(shí)驗(yàn)的時(shí)候，我再推推公式上的推倒花了很多時(shí)間，因?yàn)閷?duì)題目的理解不是很透徹，所以在計(jì)算的時(shí)候就老是出錯(cuò)。但是因?yàn)榫幊痰幕A(chǔ)不行所以實(shí)在是不能把每一次的財(cái)產(chǎn)算出。（三）出售金魚問(wèn)題：第一次賣出全部金魚的一半加二分之一條金魚；第二次賣出乘余金魚的三分之一加三分之一條金魚；第三次賣出剩余金魚的四分之一加四分之一條金魚；第四次賣出剩余金魚的五分之一加五分之一條金魚；現(xiàn)在還剩下11條金魚，在出售金魚時(shí)不能把金魚切開(kāi)或者有任何破損的。問(wèn)這魚缸里原有多少條金魚？（一）題目一：（基于冒泡排序）1 題目分析總共有金魚f(1)條，所以第一次賣出f(1)*1/2+1/2,第一次賣出之前剩余的金魚數(shù)位f(1);第2次賣出的為1/3f(0)+1/3,第2此賣出去之前的金魚數(shù)：f(2)=1/2f(1)-1/2;第三次賣出的金魚數(shù)為：1/4f(3)+1/4;第三次賣出之前的金魚數(shù)為：f(3)=2/3*f(2)-1/3;直到第五次賣出去之前的金魚數(shù)為f(5)=4/5f(4)-1/5.2 算法構(gòu)造在此論證算法設(shè)計(jì)中的一些必要的設(shè)計(jì)依據(jù)。因此推出i/(i-1)f(n)-1/2=f(i-1)3 算法實(shí)現(xiàn)程序源代碼（請(qǐng)寫入必要的注釋）。/*/* GOLDFISH SELLING PROBLEM */* 陳靜雯 2012年3月20日 */*/ / 預(yù)編譯命令#include using namespace std; /最后剩余的金魚數(shù)量#define SPARE_FISH_NUM 11/總共出售金魚的次數(shù)#define SALES_TIMES 4 /遞歸函數(shù)，nGoldfishNum為求第N次銷售金魚前的總金魚數(shù)的方法int nGoldfishNum(int i,int aSALES_TIMES) int result=0; if (i+1 = SALES_TIMES) /i+1表示出售次數(shù) ai=(int)(SPARE_FISH_NUM+(1/(double)(i+2)*(i+2)/(i+1)+0.5); result=ai; else ai=(int)(nGoldfishNum(i+1,a)+(1/(double)(i+2)*(i+2)/(i+1)+0.5); result=ai; return result; /主函數(shù)void main() int GoldfishNumSALES_TIMES; /賦初始值 for(int i=0;iSALES_TIMES;i+) GoldfishNumi=0; int m=nGoldfishNum(0,GoldfishNum); /輸出結(jié)果 cout /*/ endl; cout /* GOLDFISH SELLING PROBLEM */ endl; cout /* 陳靜雯 2012年3月20日 */ endl; cout /*/ endl endl; cout 共有金魚 GoldfishNum0 條，詳細(xì)銷售情況如下所示： endl endl; /格式化輸出信息內(nèi)容 for(i=0;i+1=SALES_TIMES;i+) if(i+1=SALES_TIMES) cout 第 i+1 次出售金魚 GoldfishNumi-SPARE_FISH_NUM 條，; cout 剩余 SPARE_FISH_NUM 條。; else cout 第 i+1 次出售金魚 GoldfishNumi-GoldfishNumi+1 條，; cout 剩余 GoldfishNumi+1 條；; cout endl; cout endl; system(pause); 4 運(yùn)行結(jié)果5. 經(jīng)驗(yàn)歸納每次做這類題的時(shí)候，第一步就遇見(jiàn)了很大的困難，就是在計(jì)算遞推公式時(shí)不能翻譯成老師的那種形式。因?yàn)樵绦蚋木幹鬀](méi)有錯(cuò)誤但是不能出結(jié)果。所以我就把形式改成別的了。（4）某路公共汽車，總共有八站，從一號(hào)站發(fā)軒時(shí)車上已有n位乘客，到了第二站先下一半乘客，再上來(lái)了六位乘客；到了第三站也先下一半乘客，再上來(lái)了五位乘客，以后每到一站都先下車上已有的一半乘客，再上來(lái)了乘客比前一站少一個(gè)，到了終點(diǎn)站車上還有乘客六人，問(wèn)發(fā)車時(shí)車上的乘客有多少？（一）題目一：（基于冒泡排序）1 題目分析設(shè)下一站下車之前的初始人數(shù)為f(1),第二站下車的人數(shù)人數(shù)為f(1)/2-6,第二站下之前的人數(shù)為f(2)=f(1);第三站下車之前的人數(shù)為f(3)=f(2)/2-5,下車之前的人數(shù)為f(3)=f(2)/2-6第四站下車之前的人數(shù)為f(4)=1/2f(3)-4,下車之前的人數(shù)為f(4)=1/2f(3)-4;第五站下車之前的人數(shù)為f(4)1/2-3,下車之前的人數(shù)為f(5)=1/2f(5)-22 算法構(gòu)造在此論證算法設(shè)計(jì)中的一些必要的設(shè)計(jì)依據(jù)。因此推出f(i)=1/2*f(i-1)-(8-i)3 算法實(shí)現(xiàn)程序源代碼（請(qǐng)寫入必要的注釋）。#includeusing namespace std;/遞歸函數(shù)getoutsum為第n站下車之后的人數(shù)int getoutsum(int i,int n)int result=0;if(i=7)result=6;elseresult=(getoutsum(i+1,n)-7+i)*2;return result;/主函數(shù)void main() int i; int n=7;/總站數(shù) for(i=1;i=7;i+)if(getoutsum(i,n)%7=0)if(n=i)break;elsen=7+n;cout發(fā)車時(shí)車上的乘客:getoutsum(1,n)endl;4 運(yùn)行結(jié)果5 經(jīng)驗(yàn)歸納這次的實(shí)驗(yàn)雖然用自己的方法改編了，可是運(yùn)行的沒(méi)錯(cuò)誤但是結(jié)果不顯示。（五）猴子吃桃。有一群猴子摘來(lái)了一批桃子，猴王規(guī)定每天只準(zhǔn)吃一半加一只（即第二天吃剩下的一半加一只，以此類推），第九天正好吃完，問(wèn)猴子們摘來(lái)了多少桃子？（一）題目一：（基于冒泡排序）1 題目分析第九天吃了一半還加一個(gè)，所以還剩兩個(gè)。2 算法構(gòu)造在此論證算法設(shè)計(jì)中的一些必要的設(shè)計(jì)依據(jù)。f(i)=(f(i+1)+1)*2為遞推公式；3 算法實(shí)現(xiàn)程序源代碼（請(qǐng)寫入必要的注釋）。#includeusing namespace std;/遞歸函數(shù)eatsum為第九天之前吃的桃子數(shù)量int eatsum(int i,int n)int result=0;if(i=n)result=2;/第九天吃之前還剩余的數(shù)量else result=(eatsum(i+1,n)+1)*2;/遞歸公式return result;/主函數(shù)void main()int i;int n=9;/總天數(shù)for(i=1;i=9;i+)if(eatsum(i,n)%9=0)if(n=i)break;elsen=9+n;4.試驗(yàn)結(jié)果4 經(jīng)驗(yàn)歸納我寫出的這個(gè)程序是由發(fā)金牌的程序改編的，能容易理解。不過(guò)我本來(lái)是想用賣金魚的程序理解后再寫的，可是賣金魚的遞推公式很難理解，for循環(huán)還是兩個(gè)部分，所以我就選擇了更易懂的的來(lái)寫了。（六）小華讀書。第一天讀了全書的一半加二頁(yè)，第二天讀了剩下的一半加二頁(yè)，以后天天如此，第六天讀完了最后的三頁(yè)，問(wèn)全書有多少錢頁(yè)？（一）題目一：（基于冒泡排序）1 題目分析第六天剩余三頁(yè)，所以就用每天讀的和第二天讀的之和為總頁(yè)數(shù)2 算法構(gòu)造在此論證算法設(shè)計(jì)中的一些必要的設(shè)計(jì)依據(jù)。F(i)=(f(i+1)+2)*2為遞推公式；3 算法實(shí)現(xiàn)程序源代碼（請(qǐng)寫入必要的注釋）。#includeusing namespace std;/遞歸函數(shù)readsum為第九天讀之前的頁(yè)數(shù)int readsum(int i,int n)int result=0;if(i=n)result=3;elseresult=(readsum(i+1,n)+2)*2;return result;/主函數(shù)void main()int i;int n=6;/總天數(shù)for(i=1;i=6;i+)if(readsum(i,n)%6=0)if(n=i)break;elsen=6+n;cout總共的頁(yè)數(shù):readsum(1,n)endl;4 運(yùn)行結(jié)果5 經(jīng)驗(yàn)歸納首先要理解調(diào)用函數(shù)如何用，再寫個(gè)循環(huán)就行了，最后就是輸出結(jié)果。（7）日本著名數(shù)學(xué)游戲?qū)＜抑写辶x作教授提出這樣一個(gè)問(wèn)題：父親將2520個(gè)桔子分給六個(gè)兒子。分完 后父親說(shuō)：“老大將分給你的桔子的1/8給老二；老二拿到后連同原先的桔子分1/7給老三；老三拿到后連同原先的桔子分1/6給老四；老四拿到后連同原先的桔子分1/5給老五；老五拿到后連同原先的桔子分1/4給老六；老六拿到后連同原先的桔子分1/3給老大”。結(jié)果大家手中的桔子正好一樣多。問(wèn)六兄弟原來(lái)手中各有多少桔子？（一）題目一：（基于冒泡排序）6 題目分析每個(gè)兒子有之前分到的和后面得到的橘子，大兒子先給后得，其他兒子先得后給，但是結(jié)果是一樣的。7 算法構(gòu)造在此論證算法設(shè)計(jì)中的一些必要的設(shè)計(jì)依據(jù)。8 算法實(shí)現(xiàn)程序源代碼（請(qǐng)寫入必要的注釋）。/ 預(yù)編譯命令#include using namespace std;#define ORANGE_NUMBER 2520/桔子總數(shù)#define SUN_NUMBER 6/孩子總數(shù)#define DENOMINATOR_MAX 8/均分分母最大值#define DENOMINATOR_MIN 3/均分分母最小值/遞歸函數(shù)，用來(lái)計(jì)算每個(gè)孩子分給弟弟的桔子數(shù)量/關(guān)于數(shù)組a62的解釋：/ai0表示第i個(gè)孩子分出的桔子總數(shù)/ai1表示第i個(gè)孩子從國(guó)王那里分到的桔子總數(shù)int DistributeOrangeForBrother(int a62,int i)int average=ORANGE_NUMBER/SUN_NUMBER;int p;if (i=0)/第一個(gè)孩子從國(guó)王那里分到的桔子總數(shù)應(yīng)為平均數(shù)減去最后一個(gè)孩子分出去的部分后乘以8/7。ai1 = (average-average/(DENOMINATOR_MIN-1)*(DENOMINATOR_MAX-i)/(DENOMINATOR_MAX-1-i);/第一個(gè)孩子分給第二個(gè)孩子的桔子數(shù)量。 ai0 = ai1 - (average-average/(DENOMINATOR_MIN-1); else /第i個(gè)孩子從國(guó)王那里分到的桔子總數(shù)。 ai1 = average *(DENOMINATOR_MAX-i)/(DENOMINATOR_MAX-1-i) - DistributeOrang