算法設(shè)計(jì)與分析課程設(shè)計(jì)

1、.算法設(shè)計(jì)與分析課程設(shè)計(jì)一、 課程題目零錢問(wèn)題貪心算法實(shí)現(xiàn)二、課程摘要1）題目描述使用貪心算法設(shè)計(jì)思想設(shè)計(jì)算法實(shí)現(xiàn)找零錢問(wèn)題。例題13-4 一個(gè)小孩買了價(jià)值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次加入一個(gè)硬幣。選擇硬幣時(shí)所采用的貪婪準(zhǔn)則如下：每一次選擇應(yīng)使零錢數(shù)盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數(shù)），所選擇的硬幣不應(yīng)使零錢總數(shù)超過(guò)最終所需的數(shù)目。1）在給定錢幣面值的前提下，實(shí)現(xiàn)找回盡量少硬幣的輸出方案2）分析算法性能2）貪心算

2、法簡(jiǎn)述在求最優(yōu)解問(wèn)題的過(guò)程中，依據(jù)某種貪心標(biāo)準(zhǔn)，從問(wèn)題的初始狀態(tài)出發(fā)，直接去求每一步的最優(yōu)解，通過(guò)若干次的貪心選擇，最終得出整個(gè)問(wèn)題的最優(yōu)解，這種求解方法就是貪心算法。從貪心算法的定義可以看出，貪心法并不是從整體上考慮問(wèn)題，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而由問(wèn)題自身的特性決定了該題運(yùn)用貪心算法可以得到最優(yōu)解。貪心算法所作的選擇可以依賴于以往所作過(guò)的選擇，但決不依賴于將來(lái)的選擇，也不依賴于子問(wèn)題的解，因此貪心算法與其它算法相比具有一定的速度優(yōu)勢(shì)。如果一個(gè)問(wèn)題可以同時(shí)用幾種方法解決，貪心算法應(yīng)該是最好的選擇之一。本文講述了貪心算法的含義、基本思路及實(shí)現(xiàn)過(guò)程，貪心算法的核心、基本性質(zhì)、

3、特點(diǎn)及其存在的問(wèn)題。并通過(guò)貪心算法的特點(diǎn)舉例列出了以往研究過(guò)的幾個(gè)經(jīng)典問(wèn)題，對(duì)于實(shí)際應(yīng)用中的問(wèn)題，也希望通過(guò)貪心算法的特點(diǎn)來(lái)解決。三、課程引言首先，證明找零錢問(wèn)題的貪婪算法總能產(chǎn)生具有最少硬幣數(shù)的零錢。證明：（1）找零錢問(wèn)題的最優(yōu)解必以一個(gè)貪心選擇開始，當(dāng)總金額為N,硬幣面值為25，10，5，1時(shí)。 設(shè)最大容許的硬幣面值為m,最優(yōu)解必包含一個(gè)面值為m的硬幣: 設(shè)A是一個(gè)最優(yōu)解，且A中的第i個(gè)硬幣面值為f(i)。 當(dāng)f(1)=m（此處為25）,得證； 若f(1)1)之和1時(shí)，若jTn,即第n種錢幣面值比所兌換零錢數(shù)小,因此有。當(dāng)k為時(shí)，C(n,j)達(dá)到最小值，有P(T(k0),j)=P(T()，

4、j-T()+1若j=Tn，即用n種錢幣兌換零錢，第n種錢幣面值與兌換零錢數(shù)j相等，此時(shí)有C(n,j)=C(n,Tn)=1；若jTn，即第n種錢幣面值比所兌換零錢數(shù)大，因此兌換零錢只需考慮前n-1種錢幣即可，故有C(n,j)=C(n-1,j)，且P(T(n-1),j)=0。從以上討論可知該問(wèn)題具有重疊子問(wèn)題性質(zhì)。（1） 根據(jù)分析建立正確的遞歸關(guān)系。答： （2） 分析利用你的想法解決該問(wèn)題可能會(huì)有怎樣的時(shí)空復(fù)雜度。答：算法的時(shí)間復(fù)雜度主要取決于程序的兩個(gè)循環(huán)，所以算法的時(shí)間復(fù)雜度為；算法執(zhí)行過(guò)程中引入了一個(gè)二維數(shù)組，隨著輸入規(guī)模的增大，所需要的空間復(fù)雜度為：考慮例1 3 - 4的找零錢問(wèn)題，假設(shè)售

5、貨員只有有限的2 5美分， 1 0美分， 5美分和1美分的硬幣，給出一種找零錢的貪婪算法。這種方法總能找出具有最少硬幣數(shù)的零錢嗎？證明結(jié)論。源代碼如下：# include using namespace std;const int C=33; const int M=100; /小孩給的錢數(shù)const int twentyfnum=3; /25美分硬幣const int tennum=3; /10美分硬幣const int fivenum=3; /5美分硬幣const int onenum=3; /1美分硬幣 const int tnum=twentyfnum+tennum+fivenum+o

6、nenum; /硬幣的總數(shù)量int main()int atnum,i; /數(shù)組初始化,數(shù)組中的元素由大到小排列int *p=a;for(i=0;itwentyfnum;i+) *p+=25;for(i=0;itennum;i+) *p+=10;for(i=0;ifivenum;i+) *p+=5;for(i=0;ionenum;i+) *p+=1;bool btnum; q,int n,int c);if(findmoney(a,b,tnum,M-C) int c4=0; /存放應(yīng)找個(gè)各面值硬幣的數(shù)量 bool findmoney(int *p,bool *for(i=0;itnum;i+)

7、if(bi=true)switch(ai)case 25: c0+;break;case 10: c1+;break;case 5: c2+;break;case 1: c3+;break; cout找錢方案:endl; cout25美分:c0枚,10美分:c1枚,5美分:c2枚,1美分:c0枚endl;else cout零錢不夠;system(pause); return 0;bool findmoney(int *p,bool *q,int n,int c) for(int i=0;in;i+) if(pi=c&c!=0) qi=true; c-=pi; if(c=0) break; if

8、(c=0) return true;else return false;在此程序中，程序沒(méi)有實(shí)現(xiàn)輸入和輸出的模塊，但是具有了找零錢問(wèn)題的貪心算法解決模塊，所以需要在此程序的基礎(chǔ)上進(jìn)一步優(yōu)化，改進(jìn)后的代碼如下：#include using namespace std; void Zl(double num) int leave=0; double a8; leave = (int)(num*10)%10; a1 = leave/5; a0 = (leave%5)/1; a7 = num/50; a6 = (int)num%50)/20; a5 = (int)num%50)%20)/10; a4

9、= (int)num%50)%20)%10)/5; a3 = (int)num%50)%20)%10)%5)/2; a2 = (int)num%50)%20)%10)%5)%2)/1; if(a0!=0) cout需要找的0.1元個(gè)數(shù)為：a0endl; if(a1!=0) cout需要找的0.5元個(gè)數(shù)為：a1endl; if(a2!=0) cout需要找的1元個(gè)數(shù)為：a2endl; if(a3!=0) cout需要找的2元個(gè)數(shù)為：a3endl; if(a4!=0) cout需要找的5元個(gè)數(shù)為：a4endl; if(a5!=0) cout需要找的10元個(gè)數(shù)為：a5endl; if(a6!=0)

10、cout需要找的20元個(gè)數(shù)為：a6endl; if(a7!=0) cout需要找的50元個(gè)數(shù)為：a7endl; int main() double num; cout請(qǐng)輸入你需要找的零錢數(shù)：num; Zl(num); coutendl; return 0;2）實(shí)驗(yàn)結(jié)果比較上一步驟中兩個(gè)源代碼運(yùn)行結(jié)果分別如下：第一個(gè)的運(yùn)行結(jié)果第二個(gè)運(yùn)行結(jié)果比較上面兩個(gè)算法，第二個(gè)算法在第一個(gè)的基礎(chǔ)上增加了輸入輸出功能，方便得到任意數(shù)值零錢問(wèn)題的最優(yōu)解。五、結(jié)論與展望（1）算法實(shí)現(xiàn)的復(fù)雜度在問(wèn)題規(guī)模很大時(shí)可以接受嗎？答：可以接受，因?yàn)樨澬乃惴ㄓ泻芎玫男?，所以?dāng)問(wèn)題復(fù)雜度很大時(shí)，就不會(huì)對(duì)算法的運(yùn)行時(shí)間有太大的影響

11、，可以控制在用戶可以接受的范圍內(nèi)。（2）如果不用貪心算法方法還能想到其他的解決方式嗎？和貪心算法相比會(huì)有更好的效率嗎？答：對(duì)于找硬幣問(wèn)題，有時(shí)候動(dòng)態(tài)規(guī)劃也能解決，前面也有敘述，動(dòng)態(tài)規(guī)劃求解要比貪心算法求解有效率，所以采用動(dòng)態(tài)規(guī)劃方法也是一個(gè)很好的選擇。（3）所選用的數(shù)據(jù)結(jié)構(gòu)合適嗎？答：采用了數(shù)組的數(shù)據(jù)結(jié)構(gòu)，合適，因?yàn)樵摂?shù)據(jù)結(jié)構(gòu)能夠支持對(duì)于數(shù)組中的元素的隨機(jī)訪問(wèn)，而且方便查詢。（4）該算法都存在哪幾類可能出現(xiàn)的情況，你的測(cè)試完全覆蓋了你所想到的這些情況嗎，測(cè)試結(jié)果如何？答：基本上覆蓋了所有可能的測(cè)試結(jié)果，但不排除結(jié)果出現(xiàn)錯(cuò)誤的可能。（5）通過(guò)實(shí)驗(yàn)對(duì)貪心算法的理解及總結(jié)*貪心算法的特點(diǎn)從全局來(lái)看，運(yùn)用貪心策略解決的問(wèn)題在程序的運(yùn)行過(guò)程中無(wú)回溯過(guò)程，后面的每一步都是當(dāng)前看似