信息奧林匹克競(jìng)賽之貪心算法-共29頁(yè)課件

1、武松打老虎問(wèn)題描述：曾經(jīng)因打虎而文明的武松在x年后接到了景陽(yáng)岡動(dòng)物園的求助信，信上說(shuō)：最近我們動(dòng)物園逃跑了幾只老虎，請(qǐng)您把它們抓回來(lái)，thank you！武松接到信后立刻上了山。正當(dāng)他到半山腰是，suddenly！跳出n只猛虎來(lái)。每只老虎都有一塊虎牌，牌上寫(xiě)著的是每一只虎最大擁有的體力，當(dāng)武松與老虎PK時(shí)，若老虎的體力先用完，那么老虎over，否則武松over。求武松在over之前最多能干掉幾只老虎？（注：老虎是一只只上的）輸入文件：第一行兩個(gè)數(shù)字n(nb+a，就把a(bǔ)排在b的前面，反之則把a(bǔ)排在b的后面。如：12 123因?yàn)椋?212312312所以：123在12之前如：12 121因?yàn)椋?2

2、11212121所以：12在121之前代碼框架int cmp(char *s1,char *s2) 比較函數(shù) int main()scanf(%d,&n); for(i=1;i 從 取 3 張牌放到 （9 11 10 10）- 從 取 1 張牌放到（10 10 10 10）。輸入描述： 第一行N（N 堆紙牌，1 = N = 100） 第二行A1 A2 An （N 堆紙牌，每堆紙牌初始數(shù)，l= Ai =10000）輸出描述：輸出至屏幕。格式為：所有堆均達(dá)到相等時(shí)的最少移動(dòng)次數(shù)。樣例輸入49 8 17 6樣例輸出：3分析設(shè)ai為第i堆紙牌的張數(shù)（0=i=n），v為均分后每堆紙牌的張數(shù)，s為最小移到

3、次數(shù)。按照從左到右的順序移動(dòng)紙牌。如第i堆(0iv，則將ai-v張紙牌從第I堆移動(dòng)到第I+1堆；（2） 若aiv，則將v -ai張紙牌從第I+1堆移動(dòng)到第I堆；為了設(shè)計(jì)的方便，我們把這兩種情況統(tǒng)一看作是將aI-v張牌從第I堆移動(dòng)到第I+1堆；移動(dòng)后有：aI:=v；aI+1:=aI+1+aI-v；貪心選擇：分析我們繼續(xù)按規(guī)則分析移牌過(guò)程，從第二堆移出9張到第一堆后，第一堆有10張紙牌，第二堆剩下-7張紙牌，再?gòu)牡谌岩苿?dòng)17張到第二堆，剛好三堆紙牌數(shù)都是10，最后結(jié)果是對(duì)的，從第二堆移出的牌都可以從第三堆得到。我們?cè)谝苿?dòng)過(guò)程中，只是改變了移動(dòng)的順序，而移動(dòng)的次數(shù)不變，因此此題使用貪心法是可行的。

4、在從第i+1堆中取出紙牌補(bǔ)充第i堆的過(guò)程中，可能會(huì)出現(xiàn)第i+1堆的紙牌數(shù)小于零(ai+1+ai-v0 )的情況。如n=3，三堆紙牌數(shù)為（1，2，27）這時(shí)v=10，為了使第一堆數(shù)為10，要從第二堆移9張紙牌到第一堆，而第二堆只有2張紙牌可移，這是不是意味著剛才使用的貪心法是錯(cuò)誤的呢？當(dāng)不具備貪心選擇性質(zhì)時(shí)：得到較優(yōu)解。數(shù)字三角如圖所示的數(shù)字三角形，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或得向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。貪心法：7+8+1+7+5=28更優(yōu)方案：貪心法：更優(yōu)方案：7+3+8+7+5=30策略：從第一層開(kāi)始選，每次選擇可選的數(shù)字中最大的數(shù)字第二層選擇小些的數(shù)目能達(dá)到更優(yōu)解不符合貪心選擇性質(zhì)分析當(dāng)不能100%確定一個(gè)貪心算法正確時(shí)，在使用之前，就應(yīng)該嘗試證明它的不正確性。要證明其不正確，一種最簡(jiǎn)單的方法就