【精選資料】貪心算法實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告題目實(shí)驗(yàn)四貪心算法開課實(shí)驗(yàn)室：數(shù)學(xué)實(shí)驗(yàn)室指導(dǎo)老師：韓逢慶時(shí)間：2011.12學(xué)院：理學(xué)院 姓名：古月專業(yè)：信息與計(jì)算科學(xué)學(xué)號(hào)：09180230班級(jí):2009級(jí)2班一、 實(shí)驗(yàn)?zāi)康? .加深學(xué)生對(duì)貪心算法設(shè)計(jì)方法的基本思想、基本步驟、基本方法的理解與掌握；2. 提高學(xué)生利用課堂所學(xué)知識(shí)解決實(shí)際問題的能力；3. 提高學(xué)生綜合應(yīng)用所學(xué)知識(shí)解決實(shí)際問題的能力。二、實(shí)驗(yàn)內(nèi)容題目見 P143416,4-23.三、實(shí)驗(yàn)要求（1）用分治法求解最少加油次數(shù)和最少硬幣個(gè)數(shù)問題；（2 ）再選擇自己熟悉的其它方法求解本問題；（3）上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的所有算法；四、實(shí)驗(yàn)過程設(shè)計(jì)（算法設(shè)計(jì)過程）（1）最少加油次數(shù)實(shí)驗(yàn)題

2、目一輛汽車加滿油以后可以行使n公里，旅途中有若干個(gè)加油站，設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站?？考佑停寡芈芳佑痛螖?shù)最少。 并證明算法能產(chǎn)生一個(gè)最優(yōu)解。過程設(shè)計(jì) 貪心算法總是作出在當(dāng)前看來最好的選擇。 也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部 最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖 然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。比如說最少加油次數(shù)的問題。在這個(gè)算法中，我采用 的貪心算法的策略。首先人機(jī)互動(dòng)的設(shè)定加滿油以后最長(zhǎng)能夠行使的 距離，然后輸入了各個(gè)站點(diǎn)之間的距離，在程序的設(shè)計(jì)中，首先檢查 了程序的可行性

3、。要是遇到當(dāng)某兩個(gè)站點(diǎn)之間的距離大于汽車一次加 油以后所能夠行使的最大距離時(shí)，我們認(rèn)為此問題是不可行的。這個(gè) 在實(shí)際情況中也是很容易理解的。 然后在滿足可行性條件下，依次采 用貪心算法對(duì)問題得以實(shí)現(xiàn)。采用S這個(gè)來保存現(xiàn)在車?yán)锩媪粝碌挠停?當(dāng)此時(shí)留下的有能夠行駛完這一站點(diǎn)到下一站點(diǎn)之間的距離是，在這一站點(diǎn)的時(shí)候就不加油。但是若不能行使完這一段路程的時(shí)候，就加滿油。核心算法如下：for(i=0,s=0;i Vn ;i+)s=s+ai;if(s>n)sum+;s=ai;(2)最少硬幣個(gè)數(shù)問題實(shí)驗(yàn)題目考慮下面的用最少硬幣個(gè)數(shù)找出 n分錢的問題：當(dāng)使用2角5分，1角，5分和1分四種硬幣面值時(shí)，設(shè)計(jì)

4、一個(gè)找 n 分錢的貪心算法，并證明算法能產(chǎn)生最優(yōu)解。過程設(shè)計(jì)貪心算法總是作出在當(dāng)前看來最好的選擇。 也就是說貪心算法并不從 整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。 當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。 雖然貪心算法 不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu) 解。比如說找最少硬幣個(gè)數(shù)的問題。在算法的實(shí)現(xiàn)過程中，當(dāng)剩余的 錢數(shù)大于2角5分時(shí)，我們?cè)谟涗浾?角5分硬幣的個(gè)數(shù)的變量里面 加一，同時(shí)把剩余所找的錢的總數(shù)目也減 2角5分。不斷重復(fù)這個(gè)過 程，直到剩余所需找的錢的數(shù)目小于 2角5分時(shí)，在記錄找1角硬幣 的個(gè)數(shù)的變量里面加一，同時(shí)把剩余所找

5、的錢的總數(shù)目也減 1角，不 斷重復(fù)這個(gè)過程，直到剩余所需找的錢的數(shù)目小于 1角。5分和1分 的硬幣實(shí)現(xiàn)過程同上述過程一樣，一直執(zhí)行到所剩的錢的數(shù)目為0，此時(shí)停止計(jì)算，得到最優(yōu)解。五、實(shí)驗(yàn)結(jié)果分析（1）最少加油次數(shù)當(dāng)加油后行駛的最大距離小于相鄰站點(diǎn)的最小值時(shí)，此時(shí)，可行，求 解結(jié)果如下：11-GA,M吉設(shè)計(jì)和分析憾荀更DdIJg4 J&赴心6工H-口 牛冃冃201234567 uxwciw12345166 s禺 - -In 一一 -?7 VTk 王:以I為 6 N之之之之、N之油y IM1站站站站站站站站加C 12345678 P 靜礦席4參至至至到到至l. a 由葫莎3占占占占占占占占

6、& S Q - S ? i - 20123456 7e7<L的的的的的的的C -:PJImTmi心日 一日 to當(dāng)加油后行駛的最大距離大于相鄰站點(diǎn)的最小值時(shí)，此時(shí)，沒用可行性，為邊沿情況，求解結(jié)果如下：設(shè) 并 分祈憶 1序gbug4-16"h肘 離 & 7巨 x 勺 o Wo N 和 虜 數(shù) 4行到 點(diǎn)以站 站為臺(tái) 的醫(yī)第 途點(diǎn)：_沿站一輸4 入專次 輸7途加一；y 2 643 TrXTrXTr 亠曷Iln = = = 一_ 一 o £ foK F “m m m JTTMm 一-CTr-(j到乙 占占占占占 1-i . 1234Si g.nS-.* =

7、b'elp'- y_Nato到到到JSB 6 -4 J占占占止 2 0 12 3 4 第(分析時(shí)空復(fù)雜性，設(shè)計(jì)測(cè)試用例及測(cè)試結(jié)果) 時(shí)間復(fù)雜性：該算法的時(shí)間復(fù)雜度為 O(n) 空間復(fù)雜性分析：該算法的空間復(fù)雜度為 0(1)(2)最少硬幣問題當(dāng)輸入的找零錢數(shù)為正常的時(shí)候的運(yùn)行情況如下:to COntinUe'G.R>設(shè)滬口分桁偉程序Cbugg-24心h也也1 1 0 e 緡有有有k 5 JBiB,B n .B 2 15 1 S JS P應(yīng)PI"5算法設(shè)計(jì)和分析¾Debug4*24.ee-當(dāng)輸入的找零錢數(shù)為不正常的時(shí)候(為負(fù))的運(yùn)行情況如下:0為

8、數(shù)fil O wt »J A 0 fse 蹲鬻有有k S- / V- m 反 5 Ifflff'ffFl <5®角八各歳2 1 5 IS wes 什鹵其苴其其Pr(分析時(shí)空復(fù)雜性，設(shè)計(jì)測(cè)試用例及測(cè)試結(jié)果)時(shí)間復(fù)雜性：該算法的時(shí)間復(fù)雜性為 O(n)空間復(fù)雜性分析：該算法的空間復(fù)雜性為 O(I)六、實(shí)驗(yàn)體會(huì)貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并 不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選 擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心 算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體 最優(yōu)解。如單源最短

9、路經(jīng)問題，最小生成樹問題，相容活動(dòng)安排問題等。這樣和采用動(dòng)態(tài)規(guī)劃的算法相比，算法的思想更加的簡(jiǎn)單，實(shí)現(xiàn)起來更加的容易。但是也要明確貪心算法和動(dòng)態(tài)規(guī)劃的主要區(qū)別。及0-1背包問題可以用動(dòng)態(tài)規(guī)劃算法求解，但是貪心選擇算法卻不能用動(dòng)態(tài)規(guī)劃算法求 解。因?yàn)樨澬乃惴o法最終將背包裝滿，部分閑置的背包空間使得每 公斤背包空間的價(jià)值降低了。七、附錄：(源代碼)(1)最少加油次數(shù)具體算法的實(shí)現(xiàn)如下：#i nclude<iostream.h>VOid mai n()int n,m,a100,i,s,sum=0,j;cout<<"請(qǐng)輸入沿途的站點(diǎn)數(shù)和每一次加油以后可以行使的路程數(shù)

10、"v<endl;cin>>n;cin>>m;cout<<"沿途的站點(diǎn)數(shù)為："<<n<<endl;cout<<"每加滿一次油可以行使的路程數(shù)為"<<m<<endl;cout<<"請(qǐng)一次輸入第零站到第N站之間的距離"v<endl;for(i=0;i<=n ;i+)cin> >ai;for( i=0;i<=n ;i+)cout<<"第"<<i&l

11、t;<"站到第"<<i+1<<"站之間的距離為"<<ai<<endl;for(j=0;j Vn ;j+)if(aj>m)Sum=-1;break;if(sum!=-1)for(i=0,s=0;i Vn ;i+)s=s+ai;if(s>n)sum+;s=ai;if(sum=-1)COutVv"沒有可行性"<<endl;elseCOUtVv"沿途的最少加油次數(shù)為"v<sum<<endl;(2)最少硬幣問題具體算法的實(shí)現(xiàn)如下：

12、#i nclude<iostream.h>mai n()double n,m,a,b,c,d,f;a=b=c=d=0;COUtV<"請(qǐng)輸入應(yīng)找的錢!"<<endl; cin>>n;if(n<=0)COUtV<"您輸入的數(shù)據(jù)有錯(cuò)!"v<endl;m=n;while(m>=2.5)a+;m=m-2.5;while(m>=1)b+;m=m-1;while(m>=0.5)c+; m=m-0.5;while(m>=0.1)d+;m=m-0.1;f=a+b+c+d;COutV<"應(yīng)找的最少的硬幣個(gè)數(shù)為："<<f<<endl; cout<v"其中 2 角 5 分的有"v<a<v"個(gè)"<<endl; COUtV