《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 貪心法二.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 貪心法二.doc（14頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 貪心法二
課題：貪心法
目標(biāo)：
知識(shí)目標(biāo)：貪心的原理遞與貪心的實(shí)現(xiàn)
能力目標(biāo)：貪心的原理
重點(diǎn)：貪心算法的應(yīng)用
難點(diǎn)：貪心的理解
板書示意：
1） 貪心的引入（例24）
2） 貪心的應(yīng)用（例25、例26、例27、例28）
授課過(guò)程：
若在求解一個(gè)問(wèn)題時(shí)，能根據(jù)每次所得到的局部最優(yōu)解，推導(dǎo)出全局最優(yōu)或最優(yōu)目標(biāo)。那么，我們可以根據(jù)這個(gè)策略，每次得到局部最優(yōu)解答，逐步而推導(dǎo)出問(wèn)題，這種策略稱為貪心法。
下面我們看一些簡(jiǎn)單例題。
例24：在N行M列的正整數(shù)矩陣中，要求從每行中選出1個(gè)數(shù)，使得選出的總共N個(gè)數(shù)的和最大。
分析：要使總和最大，則每個(gè)數(shù)要盡可能大，自然應(yīng)該選每行中最大的那個(gè)數(shù)。因此，我們?cè)O(shè)計(jì)出如下算法:
讀入N, M,矩陣數(shù)據(jù)；
Total := 0;
For I := 1 to N do begin {對(duì)N行進(jìn)行選擇}
選擇第I行最大的數(shù),記為K；
Total := Total + K；
End；
輸出最大總和Total；
從上例中我們可以看出，和遞推法相仿，貪心法也是從問(wèn)題的某一個(gè)初始解出發(fā)，向給定的目標(biāo)遞推。但不同的是，推進(jìn)的每一步不是依據(jù)某一固定的遞推式，而是做一個(gè)局部的最優(yōu)選擇，即貪心選擇（在例中，這種貪心選擇表現(xiàn)為選擇一行中的最大整數(shù)），這樣，不斷的將問(wèn)題歸納為若干相似的子問(wèn)題，最終產(chǎn)生出一個(gè)全局最優(yōu)解。
特別注意的是是，局部貪心的選擇是否可以得出全局最優(yōu)是能否采用貪心法的關(guān)鍵所在。對(duì)于能否使用貪心策略，應(yīng)從理論上予以證明。下面我們看看另一個(gè)問(wèn)題。
例25：部分背包問(wèn)題
給定一個(gè)最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價(jià)值為Vi元/公斤，編程確定一個(gè)裝貨方案，使得裝入卡車中的所有物品總價(jià)值最大。
分析：因?yàn)槊恳粋€(gè)物品都可以分割成單位塊，單位塊的利益越大顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答，方法如下：先將單位塊收益按從大到小進(jìn)行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解。
因此我們非常容易設(shè)計(jì)出如下算法：
問(wèn)題初始化； {讀入數(shù)據(jù)}
按Vi從大到小將商品排序；
I := 1;
repeat
if M = 0 then Break; {如果卡車滿載則跳出循環(huán)}
M := M - Wi;
if M >= 0 then 將第I種商品全部裝入卡車
else
將(M + Wi)重量的物品I裝入卡車;
I := I + 1; {選擇下一種商品}
until (M <= 0) OR (I >= N)
在解決上述問(wèn)題的過(guò)程中，首先根據(jù)題設(shè)條件，找到了貪心選擇標(biāo)準(zhǔn)(Vi)，并依據(jù)這個(gè)標(biāo)準(zhǔn)直接逐步去求最優(yōu)解，這種解題策略被稱為貪心法。
Program Exam25;
Const Finp=Input.Txt;
Fout=Output.Txt;
Var N,M :Longint;
S :Real;
P,W :Array[1..100] Of Integer;
Procedure Init; {輸出}
Var I :Integer;
Begin
Assign(Input,Finp); Reset(Input);
Readln(M,N);
For I:=1 To N Do Readln(W[I],P[I]);
Close(Input);
End;
Procedure Sort(L,R:Integer); {按收益值從大到小排序}
Var I,J,Y :Integer;
X :Real;
Begin
I:=L; J:=R;
X:=P[(L+R) Div 2]/W[(L+R) Div 2];
Repeat
While (I
=X) Do Inc(I);
While (P[J]/W[J]<=X)And(J>L) Do Dec(J);
If I<=J Then
Begin
Y:=P[I]; P[I]:=P[J]; P[J]:=Y;
Y:=W[I]; W[I]:=W[J]; W[J]:=Y;
Inc(I); Dec(J);
End;
Until I>J;
If I=W[I] Then {如果全部可取，則全取}
Begin
S:=S+P[I]; M:=M-W[I];
End
Else {否則取一部分}
Begin
S:=S+M*(P[I]/W[I]); Break;
End;
End;
Procedure Out; {輸出}
Begin
Assign(Output,Fout); Rewrite(Output);
Writeln(S:0:0);
Close(Output);
End;
Begin {主程序}
Init;
Work;
Out;
End.
因此，利用貪心策略解題，需要解決兩個(gè)問(wèn)題：
首先，確定問(wèn)題是否能用貪心策略求解；一般來(lái)說(shuō)，適用于貪心策略求解的問(wèn)題具有以下特點(diǎn)：
① 可通過(guò)局部的貪心選擇來(lái)達(dá)到問(wèn)題的全局最優(yōu)解。運(yùn)用貪心策略解題，一般來(lái)說(shuō)需要一步步的進(jìn)行多次的貪心選擇。在經(jīng)過(guò)一次貪心選擇之后，原問(wèn)題將變成一個(gè)相似的，但規(guī)模更小的問(wèn)題，而后的每一步都是當(dāng)前看似最佳的選擇，且每一個(gè)選擇都僅做一次。
② 原問(wèn)題的最優(yōu)解包含子問(wèn)題的最優(yōu)解，即問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。在背包問(wèn)題中，第一次選擇單位質(zhì)量最大的貨物，它是第一個(gè)子問(wèn)題的最優(yōu)解，第二次選擇剩下的貨物中單位重量?jī)r(jià)值最大的貨物，同樣是第二個(gè)子問(wèn)題的最優(yōu)解，依次類推。
其次，如何選擇一個(gè)貪心標(biāo)準(zhǔn)？正確的貪心標(biāo)準(zhǔn)可以得到問(wèn)題的最優(yōu)解，在確定采用貪心策略解決問(wèn)題時(shí)，不能隨意的判斷貪心標(biāo)準(zhǔn)是否正確，尤其不要被表面上看似正確的貪心標(biāo)準(zhǔn)所迷惑。在得出貪心標(biāo)準(zhǔn)之后應(yīng)給予嚴(yán)格的數(shù)學(xué)證明。
下面來(lái)看看0-1背包問(wèn)題。
給定一個(gè)最大載重量為M的卡車和N種動(dòng)物。已知第i種動(dòng)物的重量為Wi，其最大價(jià)值為Vi，設(shè)定M，Wi，Vi均為整數(shù)，編程確定一個(gè)裝貨方案，使得裝入卡車中的所有動(dòng)物總價(jià)值最大。
分析：對(duì)于N種動(dòng)物，要么被裝，要么不裝，也就是說(shuō)在滿足卡車載重的條件下，如何選擇動(dòng)物，使得動(dòng)物價(jià)值最大的問(wèn)題。
即確定一組X1，X2，…，Xn， Xi∈{0,1}
f(x)=max(∑Xi*Vi) 其中，∑(Xi*Wi)≦W
從直觀上來(lái)看，我們可以按照上例一樣選擇那些價(jià)值大，而重量輕的動(dòng)物。也就是可以按價(jià)值質(zhì)量比（Vi/Wi）的大小來(lái)進(jìn)行選擇。可以看出，每做一次選擇，都是從剩下的動(dòng)物中選擇那些Vi/Wi最大的，這種局部最優(yōu)的選擇是否能滿足全局最優(yōu)呢？我們來(lái)看看一個(gè)簡(jiǎn)單的例子：
設(shè)N=3，卡車最大載重量是100，三種動(dòng)物A、B、C的重量分別是40，50，70，其對(duì)應(yīng)的總價(jià)值分別是80、100、150。
情況A：按照上述思路，三種動(dòng)物的Vi/Wi分別為2,2,2.14。顯然，我們首先選擇動(dòng)物C，得到價(jià)值150，然后任意選擇A或B，由于卡車最大載重為100，因此卡車不能裝載其他動(dòng)物。
情況B：不按上述約束條件，直接選擇A和B。可以得到價(jià)值80+100=180，卡車裝載的重量為40+50=90。沒(méi)有超過(guò)卡車的實(shí)際載重，因此也是一種可行解，顯然，這種解比上一種解要優(yōu)化。
問(wèn)題出現(xiàn)在什么地方呢？我們看看圖2-18
圖23 卡車裝載貨物情況分析
從圖23中明顯可以看出，情況A，卡車的空載率比情況B高。也就是說(shuō)，上面的分析，只考慮了貨物的價(jià)值質(zhì)量比，而沒(méi)有考慮到卡車的運(yùn)營(yíng)效率，因此，局部的最優(yōu)化，不能導(dǎo)致全局的最優(yōu)化。
因此，貪心不能簡(jiǎn)單進(jìn)行，而需要全面的考慮，最后得到證明。
例26排隊(duì)打水問(wèn)題
有N個(gè)人排隊(duì)到R個(gè)水龍頭去打水，他們裝滿水桶的時(shí)間為T1，T2，…，Tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們花費(fèi)的時(shí)間最少？
分析：由于排隊(duì)時(shí)，越靠前面的計(jì)算的次數(shù)越多，顯然越小的排在越前面得出的結(jié)果越?。梢杂脭?shù)學(xué)方法簡(jiǎn)單證明，這里就不再贅述），所以這道題可以用貪心法解答，基本步驟：
(1) 將輸入的時(shí)間按從小到大排序；
(2) 將排序后的時(shí)間按順序依次放入每個(gè)水龍頭的隊(duì)列中；
(3) 統(tǒng)計(jì)，輸出答案。
參考程序：
Program Exam26;
Const Finp=Input.Txt;
Fout=Output.Txt;
Var A :Array[1..100] Of Integer;
S :Array[1..100] Of Longint;
N,M :Integer;
Min :Longint;
Procedure Init; {讀入數(shù)據(jù)}
Var I :Integer;
Begin
Assign(Input,Finp); Reset(Input);
Readln(N,M);
For I:=1 To N Do Read(A[I]);
Close(Input);
End;
Procedure Sort(L,R:Integer); {將時(shí)間從小到大排序}
Var I,J,X,Y :Integer;
Begin
I:=L; J:=R; X:=A[(L+R) Div 2];
Repeat
While (A[I]<=X)And(I=X)And(J>L) Do Dec(J);
If I<=J Then
Begin
Y:=A[I]; A[I]:=A[J]; A[J]:=Y;
Inc(I); Dec(J);
End;
Until I>J;
If LI Then Sort(I,R);
End;
Procedure Work;
Var I,J,K :Integer;
Begin
Fillchar(S,Sizeof(S),0);
J:=0; Min:=0;
For I:=1 To N Do {用貪心法求解}
Begin
Inc(J);
If J=M+1 Then J:=1;
S[J]:=S[J]+A[I];
Min:=Min+S[J];
End;
Assign(Output,Fout); Rewrite(Output); {輸出解答}
Writeln(Min);
Close(Output);
End;
Begin {主程序}
Init;
Sort(1,N);
Work;
End.
例27：旅行家的預(yù)算（NOI99分區(qū)聯(lián)賽第3題）
一個(gè)旅行家想駕駛汽車以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（假設(shè)出發(fā)時(shí)油箱時(shí)空的）。給定兩個(gè)城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發(fā)點(diǎn)每升汽油價(jià)格P和沿途加油站數(shù)N（N可以為零），油站i離出發(fā)點(diǎn)的距離Di、每升汽油價(jià)格Pi（i=1，2，……，N）。
計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。
如果無(wú)法到達(dá)目的地，則輸出“No Solution”。
樣例：
Input
D1=275.6 C=11.9 D2=27.4 P=2.8 N=2
油站號(hào)I
離出發(fā)點(diǎn)的距離Di
每升汽油價(jià)格Pi
1
102.0
2.9
2
220.0
2.2
Output
26.95（該數(shù)據(jù)表示最小費(fèi)用）
分析：需要考慮如下問(wèn)題：
1） 出發(fā)前汽車的油箱是空的，故汽車必須在起點(diǎn)（1號(hào)站）處加油。加多少油？
2） 汽車行程到第幾站開(kāi)始加油，加多少油？
可以看出，原問(wèn)題需要解決的是在哪些油站加油和加多少油的問(wèn)題。對(duì)于某個(gè)油站，汽車加油后到達(dá)下一加油站，可以歸結(jié)為原問(wèn)題的子問(wèn)題。因此，原問(wèn)題關(guān)鍵在于如何確定下一個(gè)加油站。通過(guò)分析，我們可以選擇這樣的貪心標(biāo)準(zhǔn)：
對(duì)于加油站I，下一個(gè)加油站J可能第一個(gè)是比油站I油價(jià)便宜的油站，若不能到達(dá)這樣的油站，則至少需要到達(dá)下一個(gè)油站后，繼續(xù)進(jìn)行考慮。
對(duì)于第一種情況，則油箱需要（d（j）-d（i））/m加侖汽油。對(duì)于第二種情況，則需將油箱加滿。
貪心算法證明如下：
設(shè)定如下變量：
Value[i]：第i個(gè)加油站的油價(jià)；
Over[i]：在第i站時(shí)的剩油；
Way[i]：起點(diǎn)到油站i的距離；
X[I]：X記錄問(wèn)題的最優(yōu)解，X[I]記錄油站I的實(shí)際加油量。
首先，X[1]≠0，Over[1]=0。
假設(shè)第I站加的X[I]一直開(kāi)到第K站。則有，X[I]..x[k-1]都為0，而X[K]≠0。
① 若Value[I]>Value[k]，則按貪心方案，第I站應(yīng)加油為
T=（Way[k]-Way[I]）/M-Over[I]。
若TX[I], 則預(yù)示著，汽車開(kāi)到油站K，仍然有油剩余。假設(shè)剩余W加侖汽油，則須費(fèi)用Value[I]*W，如果W加侖汽油在油站K加，則須費(fèi)用Value[K]*W，顯然Value[K]*WX[I]，則表示在第I站的不加滿油，而將一部分油留待第K站加，而Value[I] MaxWay) then begin
init:= False;
Exit;
end;
init := True;
end;
procedure Buy(I: Integer; Miles: Real);;
{在I加油站購(gòu)買Miles/D2加侖汽油}
begin
Cost:= Cost + Miles / D2 * Oil[I]^.Value;
{將買汽油所需的費(fèi)用加到Cost變量中}
end;
procedure Solve;
var
I, J: Integer;
S: Real;
begin
I := 1; {汽車在起點(diǎn)}
repeat
S := 0.0;
{在MaxWay范圍以內(nèi)，找第一個(gè)油價(jià)比I站便宜的加油站J}
while (S <= MaxWay+zero) and (J <= N – 1)
and (Oil[I]^.Value <= Oil[J]^.Value) do
begin
Inc(J);
S := S + Oil[J]^.Way – Oil[J – 1]^.Way;
end;
if S <= MaxWay+zero then {如果找到J站或可以直達(dá)終點(diǎn)}
{如果剩油足夠到達(dá)J站，則無(wú)需購(gòu)油，并計(jì)算到達(dá)J站時(shí)汽車的剩油}
if (Oil[I]^.Over + Zero >=Oil[J]^.Way – Oil[I]^.Way) then
Oil[J]^.Over:=Oil[I]^.Over–Oil[J]^.Way+Oil[I]^.Way
else begin
{在I站購(gòu)買恰好能到達(dá)J站的油量}
Buy(I,Oil[J]^.Way – Oil[I]^.Way – Oil[I]^.Over);
Oil[J]^.Over := 0.0;
end
else begin {附近無(wú)比I站便宜的加油站J}
Buy(I, MaxWay – Oil[I]^.Over); {在I站加滿油}
J := I + 1; {行駛到下一站}
Oil[J]^.Over:= MaxWay – (Oil[J]^.Way – Oil[I]^.Way);
end;
I := J; {汽車直達(dá)J站}
until I = N; {汽車到達(dá)終點(diǎn)}
end;
begin {主程序}
Cost := 0;
Assign(Input, Inp);
Reset(Input);
Assign(Output, Outp);
Rewrite(Output);
if init then begin {如果有解}
Solve; {求解}
Writeln(Cost:0 :2); {輸出最少費(fèi)用}
end else
Writeln(‘No Solution’); {輸出無(wú)解}
Close(Input);
Close(Output);
end.
例28：兩機(jī)器加工問(wèn)題
有n個(gè)部件需在A，B機(jī)器上加工，每個(gè)工件都必須經(jīng)過(guò)先A后B兩道工序。
已知：部件i在A、B機(jī)器上的加工時(shí)間分別為ai，bi。
問(wèn)：如何安排n個(gè)工件的加工順序，才能使得總加工時(shí)間最短？
輸入示例：
N = 5
工件I
1
2
3
4
5
ai
3
5
8
7
10
bi
6
2
1
4
9
輸出示例：
34 （最少時(shí)間）
1 5 4 2 3 （最優(yōu)加工順序）
分析：
本題求一個(gè)加工順序使得加工總時(shí)間最短，要使時(shí)間最短，則就是讓機(jī)器的空閑時(shí)間最短。一旦A機(jī)器開(kāi)始加工，則A機(jī)器將會(huì)不停的進(jìn)行作業(yè)，關(guān)鍵是B機(jī)器在加工過(guò)程中，有可能要等待A機(jī)器。很明顯第一個(gè)部件在A機(jī)器上加工時(shí)，B機(jī)器必須等待，最后一個(gè)部件在B機(jī)器上加工，A機(jī)器也在等待B機(jī)器的完工。
可以大膽猜想，要使總的空閑的最少，就要把在A機(jī)器上加工時(shí)間最短的部件最先加工，這樣使得B機(jī)器能以最快的速度開(kāi)始加工；把在B機(jī)器上加工時(shí)間最短的部件放在最后加工。這樣使得A機(jī)器能盡快的等待B機(jī)器完工。于是我們可以設(shè)計(jì)出這樣的貪心法：
設(shè)Mi=min{ai, bi}
將M按照從小到大的順序排序。然后從第1個(gè)開(kāi)始處理，若Mi=ai，則將它排在從頭開(kāi)始的已經(jīng)作業(yè)后面，若Mi=bi，則將它排在從尾開(kāi)始的作業(yè)前面。
例如：N=5
（a1，a2，a3，a4，a5）=（3，5，8，7，10）
（b1，b2，b3，b4，b5）=（6，2，1，4，9）
則（m1，m2，m3，m4，m5）=（3，2，1，4，9）
排序之后為（m3，m2，m1，m4，m5）
處理m3：∵m3=b3 ∴m3排在后面；加入m3之后的加工順序?yàn)椋?， ， ， ，3）；
處理m2：∵m2=b2 ∴m2排在后面；加入m2之后的加工順序?yàn)椋?， ， ，2，3）；
處理m1：∵m3=a1 ∴m1排在前面；加入m1之后的加工順序?yàn)椋?， ， ，2，3）；
處理m4：∵m4=b4 ∴m4排在后面；加入m4之后的加工順序?yàn)椋?， ，4，2，3）；
處理m5：∵m5=b5 ∴m5排在后面；加入m5之后的加工順序?yàn)椋?，5，4，2，3）；
則最優(yōu)加工順序就是（1，5，4，2，3），最短時(shí)間為34。顯然這是最優(yōu)解。
問(wèn)題是這種貪心策略是否正確呢？還需證明。
證明過(guò)程如下：
設(shè)S={J1，J2，……，Jn}，為待加工部件的作業(yè)排序，若A機(jī)器開(kāi)始加工S中的部件時(shí)，B機(jī)器還在加工其它部件，t時(shí)刻后再可利用，在這樣的條件下，加工S中任務(wù)所需的最短時(shí)間T（S，t）= min{ai+T(S-{Ji},bi+max{t-ai,0})} 其中，Ji∈S。
圖24 機(jī)器加工作業(yè)示意圖
從圖24可以看出，（a）為作業(yè)I等待機(jī)器B的情況，（b）為機(jī)器B等待作業(yè)I在機(jī)器A上完成的情形。
假設(shè)最佳的方案中，先加工作業(yè)Ji，然后加工作業(yè)Jj，則有：
T(S,t)=ai+T(S-{Ji},bi+Max{t-ai,0})
=ai+aj+T(S-{Ji,Jj},bj+max{bi+max{t-ai,0}-aj,0})
=ai+aj+T(S-{Ji,Jj},Tij)
Tij=bj+max{bi+max{t-ai,0}-aj,0}
=bj+bi-aj+max{max{t-ai,0},aj-bi}
=bi+bj-aj+max{t-ai,aj-bi,0}
=bi+bj-ai-aj+max{t,ai,ai+aj-bi}
若max{t,ai,ai+aj-bi}=t
若max{t,ai,ai+aj-bi}=ai
若max{t,ai,ai+aj-bi}=ai+aj-bi
若將作業(yè)Ji和作業(yè)Jj的加工順序，則有：
T’(S,t)=ai+aj+T(S-(Ji,Jj),Tji)，其中
Tji=bi+bj-ai-aj+max{t,aj,ai+aj-bj}
按假設(shè)，因?yàn)門<=T’,所以有:
max{t,ai+aj-bi,ai}<=max{t,ai+aj-bj,aj}
……………… ①
于是有：
ai+aj+max{-bi,-aj}<=ai+aj+max{-bj,-ai}
即
Min{bj,ai}<=min{bi,aj}
……………… ②
②式便是Johnson公式。也就是說(shuō)②式成立的條件下，任務(wù)Ji安排在任務(wù)Jj之前加工可以得到最優(yōu)解。也就是說(shuō)在A機(jī)器上加工時(shí)間短的任務(wù)應(yīng)優(yōu)先，而在B機(jī)器上加工時(shí)間短的任務(wù)應(yīng)排在后面。因此，論證了開(kāi)始設(shè)計(jì)的貪心算法是正確的。
算法流程如下：
for I := 1 to N do {求M數(shù)組}
if A[I] < B[I] then
M[I] := A[I]
else
M[I] := B[I]；
將M從小到大排序；
S := 1; T := N; {首位指針初始化}
for I := 1 to N do
if 對(duì)于第I小的工序J，若A[J] < B[J] then begin
Order[S] := J; {將工序J插在加工序列的前面}
S := S + 1;
end else begin
Order[T] := J; {將工序J插在加工序列的后面}
T := T - 1;
end;
程序如下：
program Machine;
const
Inp = input.txt;
Outp = output.txt;
MaxN = 100; {最多部件數(shù)}
var
N, Min: Integer;
A, B, M,
O, {O用來(lái)記錄從小到大排序后部件的編號(hào)}
Order: array [1 .. MaxN] of Integer; {Order用來(lái)記錄加工順序}
procedure Init; {讀入數(shù)據(jù)}
var
I: Integer;
begin
Assign(Input, Inp); Reset(Input);
Readln(N);
for I := 1 to N do
Read(A[I]);
Readln;
for I := 1 to N do
Read(B[I]);
Close(Input);
end;
procedure Main;
var
I, J, Z, S, T, T1, T2: Integer;
begin
FillChar(M, Sizeof(M), 0); {求M數(shù)組的值}
for I := 1 to N do
if A[I] < B[I] then M[I] := A[I] else M[I] := B[I];
for I := 1 to N do O[I] := I;
for I := 1 to N - 1 do {從小到大排序}
for J := I + 1 to N do
if M[O[I]] > M[O[J]] then begin
Z := O[I]; O[I] :=O[J]; O[J] := Z;
end;
FillChar(Order, Sizeof(Order), 0);
S := 1; T := N;
for I := 1 to N do
if M[O[I]] = A[O[I]] then begin
{若A[O[I]]
下載提示(請(qǐng)認(rèn)真閱讀)
- 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
9.9
積分
- 配套講稿：
如PPT文件的首頁(yè)顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制：
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
-
2019-2020年高中信息技術(shù)
全國(guó)青少年奧林匹克聯(lián)賽教案
貪心法二
2019
2020
年高
信息技術(shù)
全國(guó)青少年
奧林匹克
聯(lián)賽
教案
貪心
- 溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請(qǐng)勿作他用。
2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 貪心法二.doc
鏈接地址：http://www.820124.com/p-2613326.html