貪心算法的應(yīng)用.doc

貪心算法的應(yīng)用.doc

ID:48833267

大?。?2.51 KB

頁(yè)數(shù):15頁(yè)

時(shí)間:2020-01-31

貪心算法的應(yīng)用.doc_第1頁(yè)
貪心算法的應(yīng)用.doc_第2頁(yè)
貪心算法的應(yīng)用.doc_第3頁(yè)
貪心算法的應(yīng)用.doc_第4頁(yè)
貪心算法的應(yīng)用.doc_第5頁(yè)
資源描述:

《貪心算法的應(yīng)用.doc》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、在求最優(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)解。我們看看下面的例子例1均分紙牌(NOIP2002tg)[問(wèn)題描述] 有N堆紙牌,編號(hào)分別為1,2,…,N。每堆上有若干張,但紙牌總數(shù)必為N的倍數(shù)。可以在任一堆上取若干張紙牌,然后移動(dòng)。移牌規(guī)則為:在編號(hào)為1堆上取的

2、紙牌,只能移到編號(hào)為2的堆上;在編號(hào)為N的堆上取的紙牌,只能移到編號(hào)為N-1的堆上;其他堆上取的紙牌,可以移到相鄰左邊或右邊的堆上?,F(xiàn)在要求找出一種移動(dòng)方法,用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多。例如N=4,4堆紙牌數(shù)分別為: ?、佟??、凇??、邸?7 ④ 6移動(dòng)3次可達(dá)到目的:  從③取4張牌放到④(981310)->從③取3張牌放到②(9111010)->從②取1張牌放到①(10101010)。[輸入]:鍵盤輸入文件名。文件格式:N(N堆紙牌,1<=N<=100)  A1A2…An(N堆紙牌,每堆紙牌初始數(shù),l<=Ai

3、<=10000)[輸出]:輸出至屏幕。格式為:所有堆均達(dá)到相等時(shí)的最少移動(dòng)次數(shù)。[輸入輸出樣例]a.in: 4 98176屏慕顯示:3算法分析:設(shè)a[i]為第i堆紙牌的張數(shù)(0<=i<=n),v為均分后每堆紙牌的張數(shù),s為最小移到次數(shù)。我們用貪心法,按照從左到右的順序移動(dòng)紙牌。如第i堆(0v,則將a[i]-v張紙牌從第I堆移動(dòng)到第I+1堆;(2)???若a[i]

4、方便,我們把這兩種情況統(tǒng)一看作是將a[I]-v張牌從第I堆移動(dòng)到第I+1堆;移動(dòng)后有:a[I]:=v;a[I+1]:=a[I+1]+a[I]-v;在從第i+1堆中取出紙牌補(bǔ)充第i堆的過(guò)程中,可能會(huì)出現(xiàn)第i+1堆的紙牌數(shù)小于零(a[i+1]+a[i]-v<0)的情況。如n=3,三堆紙牌數(shù)為(1,2,27)這時(shí)v=10,為了使第一堆數(shù)為10,要從第二堆移9張紙牌到第一堆,而第二堆只有2張紙牌可移,這是不是意味著剛才使用的貪心法是錯(cuò)誤的呢?我們繼續(xù)按規(guī)則分析移牌過(guò)程,從第二堆移出9張到第一堆后,第一堆有10張紙牌,第二堆剩下-7張紙

5、牌,再?gòu)牡谌岩苿?dòng)17張到第二堆,剛好三堆紙牌數(shù)都是10,最后結(jié)果是對(duì)的,從第二堆移出的牌都可以從第三堆得到。我們?cè)谝苿?dòng)過(guò)程中,只是改變了移動(dòng)的順序,而移動(dòng)的次數(shù)不變,因此此題使用貪心法是可行的。源程序:vari,n,s:integer;v:longint;?a:array[1..100]oflongint;?f:text;fil:string;begin?readln(fil);assign(f,fil);reset(f);?readln(f,n);v:=0;?fori:=1tondobegin???read(f,a[i])

6、;inc(v,a[i]);?end;?v:=vdivn;{每堆牌的平均數(shù)}?fori:=1ton-1doifa[i]<>vthen{貪心選擇}begin?????inc(s);{移牌步數(shù)計(jì)數(shù)}?????a[i+1]:=a[i+1]+a[i]-v;{使第i堆牌數(shù)為v}???end;{then}?writeln(s);end.利用貪心算法解題,需要解決兩個(gè)問(wèn)題:一是問(wèn)題是否適合用貪心法求解。我們看一個(gè)找?guī)诺睦?如果一個(gè)貨幣系統(tǒng)有3種幣值,面值分別為一角、五分和一分,求最小找?guī)艛?shù)時(shí),可以用貪心法求解;如果將這三種幣值改為一角一分、

7、五分和一分,就不能使用貪心法求解。用貪心法解題很方便,但它的適用范圍很小,判斷一個(gè)問(wèn)題是否適合用貪心法求解,目前還沒(méi)有一個(gè)通用的方法,在信息學(xué)競(jìng)賽中,需要憑個(gè)人的經(jīng)驗(yàn)來(lái)判斷何時(shí)該使用貪心算法。二是確定了可以用貪心算法之后,如何選擇一個(gè)貪心標(biāo)準(zhǔn),才能保證得到問(wèn)題的最優(yōu)解。在選擇貪心標(biāo)準(zhǔn)時(shí),我們要對(duì)所選的貪心標(biāo)準(zhǔn)進(jìn)行驗(yàn)證才能使用,不要被表面上看似正確的貪心標(biāo)準(zhǔn)所迷惑,如下面的列子。例2(NOIP1998tg)設(shè)有n個(gè)正整數(shù),將他們連接成一排,組成一個(gè)最大的多位整數(shù)。例如:n=3時(shí),3個(gè)整數(shù)13,312,343,連成的最大整數(shù)為:3

8、4331213又如:n=4時(shí),4個(gè)整數(shù)7,13,4,246連接成的最大整數(shù)為7424613輸入:NN個(gè)數(shù)輸出:連接成的多位數(shù)算法分析:此題很容易想到使用貪心法,在考試時(shí)有很多同學(xué)把整數(shù)按從大到小的順序連接起來(lái),測(cè)試題目的例子也都符合,但最后測(cè)試的結(jié)果卻不全對(duì)。按這種貪心標(biāo)準(zhǔn),

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。