信息奧林匹克競賽之貪心算法-共29頁課件

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

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）輸出描述：輸出至屏幕。格式為：所有堆均達到相等時的最少移動次數(shù)。樣例輸入49 8 17 6樣例輸出：3分析設(shè)ai為第i堆紙牌的張數(shù)（0=i=n），v為均分后每堆紙牌的張數(shù)，s為最小移到

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

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