2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 貪心法

《2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 貪心法》由會(huì)員分享，可在線閱讀，更多相關(guān)《2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 貪心法（3頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(liá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)解。 我們看看下面的例子 貪心法應(yīng)用 例1 均分紙牌（NOIPxxtg） [問(wèn)題描述]　有 N 堆紙牌，編號(hào)分別為 1，2，…, N。每堆上有若干張，但紙牌總數(shù)必為 N 的倍數(shù)?？梢栽谌我欢焉先∪舾蓮埣埮?，然后移

2、動(dòng)。移牌規(guī)則為：在編號(hào)為 1 堆上取的紙牌，只能移到編號(hào)為 2 的堆上；在編號(hào)為 N 的堆上取的紙牌，只能移到編號(hào)為 N-1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多。例如 N=4，4 堆紙牌數(shù)分別為： 　?、佟??、凇??、邸?7?、堋? 移動(dòng)3次可達(dá)到目的： 　　從 ③ 取 4 張牌放到 ④ （9 8 13 10） -> 從 ③ 取 3 張牌放到 ②（9 11 10 10）-> 從 ② 取 1 張牌放到①（10 10 10 10）。 [輸 入]：鍵盤(pán)輸入文件名。 文件格式：N（N 堆紙牌，1 <= N

3、 <= 100） 　　A1 A2 … An （N 堆紙牌，每堆紙牌初始數(shù)，l<= Ai <=10000） [輸 出]：輸出至屏幕。格式為：所有堆均達(dá)到相等時(shí)的最少移動(dòng)次數(shù)。 [輸入輸出樣例] a.in： 　4 　9 8 17 6 屏慕顯示：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、v，則將v -a[i]張紙牌從第I+1堆移動(dòng)到第I堆； 為了設(shè)計(jì)的方便，我們把這兩種情況統(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張紙牌，第二

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

6、d(f,a[i]); inc(v,a[i]); end; v:=v div n; {每堆牌的平均數(shù)} for i:=1 to n-1 do if a[i]<>v then {貪心選擇} 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 （NOIPxxtg）設(shè)有n個(gè)正整數(shù)，將他們連接成一排，組成一個(gè)最大的多位整數(shù)。例如:n=3時(shí)，3個(gè)整數(shù)13,312,343,連成的最大整數(shù)為:34331213 又如:n

8、=4時(shí),4個(gè)整數(shù)7,13,4,246連接成的最大整數(shù)為7424613 輸入：N N個(gè)數(shù) 輸出:連接成的多位數(shù) 算法分析：此題很容易想到使用貪心法，在考試時(shí)有很多同學(xué)把整數(shù)按從大到小的順序連接起來(lái)，測(cè)試題目的例子也都符合，但最后測(cè)試的結(jié)果卻不全對(duì)。按這種貪心標(biāo)準(zhǔn)，我們很容易找到反例：12，121 應(yīng)該組成12121而非12112,那么是不是相互包含的時(shí)候就從小到大呢？也不一定，如：12，123 就是12312而非12112,這樣情況就有很多種了。是不是此題不能用貪心法呢？ 其實(shí)此題是可以用貪心法來(lái)求解，只是剛才的貪心標(biāo)準(zhǔn)不對(duì)，正確的貪心標(biāo)準(zhǔn)是：先把整數(shù)化成字符串，然后再比較a+b和b

9、+a，如果a+b>b+a，就把a(bǔ)排在b的前面，反之則把a(bǔ)排在b的后面。 源程序： var s:array[1..20] of string; t:string;i,j,k,n:longint; begin readln(n); for i:=1 to n do begin read(k); str(k,s[i]); end; for i:=1 to n-1 do for j:=i+1 to n do if s[i]+s[j]