《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)。
[輸 入]:鍵盤輸入文件名。
文件格式: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]