2010暑期算法講義修正版1VIP

1、學(xué)習(xí)之前的建議：熟練三種結(jié)構(gòu) 熟練三種循環(huán)熟練自定義函數(shù)、過(guò)程熟練一維數(shù)組操作熟練字符串包括相關(guān)函數(shù)與過(guò)程 了解字符串與一維數(shù)組之間的轉(zhuǎn)換關(guān)系了解文本文件操作其他： 1、程序閱讀能力打草稿 2、簡(jiǎn)單的推算 3、簡(jiǎn)單數(shù)學(xué)建模Pascal常用算法By阿默2021.8如何研究算法算法是指解決問(wèn)題的方法和步驟代碼！如何讓根本算法成竹于胸？不要背代碼如何學(xué)習(xí)別人寫的程序？讀程序打草稿多嘗試思維訓(xùn)練而非寫代碼草稿演算利用Fp調(diào)試功能來(lái)觀察數(shù)據(jù)變化F7+watch第一局部 數(shù)論算法素?cái)?shù)判定最大公約數(shù)最小公倍數(shù)素?cái)?shù)判定素?cái)?shù)定義：除了1和本身之外，沒(méi)有其它的約數(shù)。思路：給出任意數(shù)N分別用(2,sqrt(N)之間

2、的整除去除N，如果N被任意一個(gè)整除就說(shuō)明N不是素?cái)?shù)，否那么就是素?cái)?shù)大致算法flag:=true; 先假設(shè)N是素?cái)?shù)，設(shè)立布爾型標(biāo)志flag為true for i:=2 to trunc(sqrt(N) do if N mod i=0 then 如果N被i整除 beginflag:=false; N的標(biāo)志量置為false，說(shuō)明N不是素?cái)?shù)break; 可以立即跳出循環(huán)，不需要再循環(huán)了 end;writeln(flag); 輸出標(biāo)志量flag試除法判斷素?cái)?shù)算法將其設(shè)計(jì)成一個(gè)函數(shù)模塊function isprime(x:longint):boolean; var i:longint; flag:bool

3、ean; begin flag:=true; for i:=2 to trunc(sqrt(x) do if x mod i=0 then begin flag:=false; break; end; isprime:=flag; end; var n:longint;主程序開(kāi)始 begin readln(n); writeln(n,-,isprime(n) ; end./最簡(jiǎn)化寫法，此算法不兼容tpfunction isprime(x:longint):boolean;var i:longint;begin isprime:=true; for i:=2 to trunc(sqrt(x) d

4、o if x mod i=0 then exit(false); /fp下exit過(guò)程可以帶參數(shù)返回end;isprime.pas引在紙上寫一行數(shù)字，從2到24將2的倍數(shù)劃去，將3的倍數(shù)劃去。都不劃本身。你發(fā)現(xiàn)了什么？恭喜你！你已經(jīng)找出了24以內(nèi)的所有素?cái)?shù)。問(wèn)：如果要找出100以內(nèi)所有的素?cái)?shù)，劃幾次？篩法策略求某個(gè)區(qū)間的所有素?cái)?shù)var a:array2.1000000 of boolean; n,i,j:longint;begin readln(n); fillchar(a,sizeof(a),true); for i:=2 to trunc(sqrt(n) do if ai then for

5、 j:=2 to n div i do ai*j:=false;for i:=2 to n do if ai then write(i, );end.此句fillchar用法就相當(dāng)于把整個(gè)數(shù)組元素的值都改為TRUE。如果數(shù)組過(guò)大，仍需要花費(fèi)較多時(shí)間。怎么辦？我們?nèi)コ@個(gè)fillchar，稍微改寫一下程序，利用原來(lái)的默認(rèn)值就好了！/如果當(dāng)前下標(biāo)是素?cái)?shù)才去篩/從2倍開(kāi)始到n div i倍為止，否那么就要越界了/數(shù)值i的j倍這個(gè)數(shù)當(dāng)然不是素?cái)?shù)，就打上標(biāo)記shai.pas篩法是一個(gè)策略篩法不是一個(gè)具體的算法，而是一個(gè)策略，篩法最大的優(yōu)點(diǎn)就是時(shí)間！在1s內(nèi)求出2N之間的素?cái)?shù)時(shí)，用試除法的話N10萬(wàn)之后根

6、本就超時(shí)了，而用篩法N最大可以大到一千萬(wàn)左右。當(dāng)然，沒(méi)有絕對(duì)的優(yōu)勢(shì)，篩法的劣勢(shì)就在于需要用到大量的空間，本來(lái)篩法就是一個(gè)用空間換取時(shí)間的策略。請(qǐng)估算N=50000000的時(shí)候采用篩法求素?cái)?shù)是否會(huì)超過(guò)市賽中程序規(guī)定的內(nèi)存空間？布爾型按1字節(jié)計(jì)算。篩法策略其它典型問(wèn)題約數(shù)研究common.pas 小聯(lián)最近在研究和約數(shù)有關(guān)的問(wèn)題，每個(gè)正整數(shù)N2N5000000至少有兩個(gè)約數(shù)，最小的一個(gè)是1，但小聯(lián)并不關(guān)心它，因?yàn)樗姓麛?shù)最小約數(shù)都是1。小聯(lián)關(guān)心是正整數(shù)的第二小約數(shù)，并f(N)來(lái)表示，下表給出了一些f(N)的取值： N 2 3 4 5 f(N) 2 3 2 5現(xiàn)在小聯(lián)需要統(tǒng)計(jì)f(2) 到f(N)的累

7、加和M。樣例輸入：5樣例輸出：12 common.pas最大公約數(shù)算法文字描述：1m除以n得到的余數(shù)為r；2假設(shè) r=0 那么 算法結(jié)束，n為最大公約數(shù)3m=n，n=r，轉(zhuǎn) 1數(shù)字演算過(guò)程：MNR188118811891890function gcd(a,b:integer):integer; var t:integer;begin while a mod b 0 do begin t:=a mod b; a:=b; b:=t; end; gcd:=b;end;common.pas換種思路，精簡(jiǎn)一下function gcd(x,y:longint):longint;begin if x mod

8、 y=0 then gcd:=y else gcd:=gcd(y,x mod y);end;gcd2.pas換種思路，換種算法？有a，b兩數(shù)，設(shè)c=mina,b ，然后利用從c至1逐個(gè)去試除 a ，b兩數(shù)，一旦通過(guò)試除立即退出即得解。var a,b,c,i:longint;begin readln(a,b); if aaj then m:=j; t:=am;am:=ai;ai:=t; end; for i:=1 to 10 do write(ai, ); writeln;end.n個(gè)數(shù)的排序中，比較了多少次？交換了多少次？?jī)?yōu)化？xz.pas多路排序多路排序是信息學(xué)奧賽初學(xué)者必須掌握的內(nèi)容之一，

9、其大意是按照某一關(guān)鍵字進(jìn)行排序，當(dāng)這個(gè)關(guān)鍵字相同，那么按照第二關(guān)鍵字進(jìn)行排序，當(dāng)?shù)诙P(guān)鍵字再相同，就按照第三關(guān)鍵字排序，依此類推。解決這個(gè)問(wèn)題最普遍的方法是利用條件結(jié)構(gòu)進(jìn)行邏輯判斷，然后進(jìn)行多路選擇。練習(xí)輸入一組學(xué)生成績(jī)，按照成績(jī)從高到底進(jìn)行排序，如果成績(jī)相同，那么按照學(xué)號(hào)從小到大排。輸入：6100 60 80 81 60 100輸出：1 1006 1004 813 802 605 60設(shè)數(shù)組a保存成績(jī)，數(shù)組h保存學(xué)號(hào)，那么此題的比較條件為：(amhj)duolu.pas深入理解選擇排序多路排序： 在對(duì)數(shù)據(jù)進(jìn)行排序時(shí)，需要先后參照幾個(gè)條件進(jìn)行排序。經(jīng)過(guò)這兩個(gè)排序，你是否理解了選擇排序？?獎(jiǎng)學(xué)金

10、? - 排五個(gè)！?精挑細(xì)選?- 排一個(gè)！scholar.pasbest.pas冒泡排序冒泡排序的根本概念是：依次比較相鄰的兩個(gè)數(shù)，將小大數(shù)放在前面，小大數(shù)放在后面。數(shù)據(jù)演示：利用重的下沉思路初始 49 38 65 97 76 13 27 49第一趟結(jié)束 38 49 65 76 13 27 49 97第二趟結(jié)束 38 49 65 13 27 49 76 97第三趟結(jié)束 38 49 13 27 49 65 76 97第四趟結(jié)束 38 13 27 49 49 65 76 97第五趟結(jié)束 13 27 38 49 49 65 76 97第六趟結(jié)束 13 27 38 49 49 65 76 97第七趟結(jié)束

11、 13 27 38 49 49 65 76 97var a:Array1.1000 of longint; n,i,j,t:longint;begin randomize; readln(n); for i:=1 to n do begin ai:=random(100); write(ai, ); end; writeln; for i:=1 to n-1 do /冒泡開(kāi)始，一共經(jīng)歷n-1趟循環(huán) for j:=1 to n-i do if ajaj+1 then begin t:=aj;aj:=aj+1;aj+1:=t; end; for i:=1 to n do write(ai, );e

12、nd.當(dāng)n=10時(shí)，一共比較了多少次？最差的情況下需要交換多少次？數(shù)據(jù)演示：利用重的下沉思路初始 49 38 65 97 76 13 27 49第一趟結(jié)束 38 49 65 76 13 27 49 97第二趟結(jié)束 38 49 65 13 27 49 76 97第三趟結(jié)束 38 49 13 27 49 65 76 97第四趟結(jié)束 38 13 27 49 49 65 76 97第五趟結(jié)束 13 27 38 49 49 65 76 97第六趟結(jié)束 13 27 38 49 49 65 76 97第七趟結(jié)束 13 27 38 49 49 65 76 97觀察第六趟結(jié)束后，排序其實(shí)已經(jīng)完成了，那我們?nèi)绾闻?/p>

13、斷此時(shí)排序已經(jīng)結(jié)束？在一趟中沒(méi)有發(fā)生數(shù)據(jù)交換！var a:Array1.1000 of longint; n,i,j,t:longint; flag:boolean;begin randomize; readln(n); for i:=1 to n do begin ai:=random(100);write(ai, ); end; writeln; for i:=1 to n-1 do begin flag:=false; /一趟開(kāi)始，還沒(méi)有進(jìn)行交換 for j:=1 to n-i do if ajaj+1 then begin t:=aj;aj:=aj+1;aj+1:=t; flag:=t

14、rue;/執(zhí)行到此處，說(shuō)明發(fā)生了交換。 end; if not flag then break;/沒(méi)有交換，那么說(shuō)明已經(jīng)排序完成，直接跳出 end; for i:=1 to n do write(ai, );end.經(jīng)過(guò)優(yōu)化之后的冒泡排序，效率提高在什么地方？?jī)?yōu)化前后哪個(gè)量沒(méi)有變？maopao.pas深入理解冒泡在一個(gè)舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉(zhuǎn)。一個(gè)車站的職工發(fā)現(xiàn)橋的長(zhǎng)度最多能容納兩節(jié)車廂，如果將橋旋轉(zhuǎn)180度，那么可以把相鄰兩節(jié)車廂的位置交換，用這種方法可以重新排列車廂的順序。于是他就負(fù)責(zé)用這座橋?qū)⑦M(jìn)站的車廂按車廂號(hào)從小到大排列。他退休后，火車站決定將這一工作

15、自動(dòng)化，其中一項(xiàng)重要的工作是編一個(gè)程序，輸入初始的車廂順序，計(jì)算最少用多少步就能將車廂排序?！据斎敫袷健枯斎胛募袃尚袛?shù)據(jù)，第一行是車廂總數(shù)N不大于10000，第二行是N個(gè)不同的數(shù)表示初始的車廂順序。 【輸出格式】一個(gè)數(shù)據(jù)，是最少的旋轉(zhuǎn)次數(shù)。 【輸入樣例】4 4 3 2 1 【輸出樣例】 6train.pas插入排序插入排序的工作機(jī)理與很多人打牌時(shí)，整理手中牌時(shí)的做法差不多。在開(kāi)始摸牌時(shí)，左手是空的，牌面朝下放在桌上。接著，一次從桌上摸起一張牌，并將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置，要將它與手中已有的牌從右到左地進(jìn)行比較。無(wú)論什么時(shí)候，左手中的牌都是排好序的。插入排序

16、數(shù)據(jù)演示：待排數(shù)據(jù)8，1，2，11，12，3依次出現(xiàn)先把8直接放入數(shù)組第1個(gè)位置：8第二次：1 1 8 比較1次后，移動(dòng)1次，放入第三次：2 1 2 8 比較2次，移動(dòng)1次，放入第四次：11 1 2 8 11 比較1次，不需移動(dòng)，放入第五次：12 1 2 8 11 12 比較1次，不需移動(dòng)，放入第六次：3 1 2 3 8 11 12 比較4次，移動(dòng)3次，放入const maxN=10;var a:Array1.maxN of integer; x,i,j:integer;begin readln(a1); /第一個(gè)數(shù)直接放入數(shù)組最前位置 for i:=2 to maxN do begin re

17、adln(x); /讀入的數(shù)暫存在x中 j:=i-1; while (j0) and (x0) and (x0 do begin write(i, ); /輸出的是下標(biāo)，一共輸出ai次 ai:=ai-1; end;end.如果要針對(duì)字符進(jìn)行排序，我們需要把數(shù)組的下標(biāo)更改為字符，定義方式如：A:arraya.z of longint;最后輸出局部也需要更改:For c:=ato zdo 當(dāng)然，所有輸入數(shù)據(jù)的范圍不能超出數(shù)組定義的下標(biāo)的范圍。count.pas相關(guān)練習(xí)第三局部 高精度我們知道在計(jì)算機(jī)里面每一種數(shù)據(jù)類型都有自己的存儲(chǔ)量。由于存儲(chǔ)量的限制所以都有著各自的精度，下面是一些常用數(shù)據(jù)類型的精

18、度：以Pascal為例 整型的精度就是在該類型范圍內(nèi)所有的數(shù)。整型范圍Shortint -128 127Integer-32768 32767Longint-2147483648 2147483647Int64-9223372036854775808 9223372036854775807Byte0 255Word0 65535Cardinal 0 4294967295 但是在某些計(jì)算中，參與運(yùn)算的數(shù)的范圍大大超出了標(biāo)準(zhǔn)數(shù)據(jù)類型整型，實(shí)型能表示的范圍的運(yùn)算，例如求兩個(gè)100位數(shù)的和的精確值。如果用一個(gè)整型變量，無(wú)論如何也是存儲(chǔ)不了的，用實(shí)型那么會(huì)造成數(shù)據(jù)的不精確。 于是，我們想到了方法，將這個(gè)

19、數(shù)字拆開(kāi)，拆成一位一位的或者是四位四位的存儲(chǔ)到一個(gè)數(shù)組中，用一個(gè)數(shù)組去表示一個(gè)數(shù)字，這樣表示的數(shù)字就被稱為高精度數(shù)。 對(duì)于高精度數(shù)，也要像平常數(shù)一樣做加減乘除以及乘方的運(yùn)算，于是就有了高精度算法。數(shù)組下標(biāo)12345678910111213存儲(chǔ)數(shù)據(jù)21098765432100 比方將這個(gè)數(shù)存到數(shù)組中，我們需要反向存儲(chǔ)到數(shù)組中，即原來(lái)的個(gè)位存于a1，十位存于a2依次類推，為什么要用反存？因?yàn)閮蓴?shù)和差積等都是要右對(duì)齊，即個(gè)位與個(gè)位對(duì)齊，而數(shù)組間最容易處理的是第一個(gè)元素對(duì)齊，所以一般情況下我們都將數(shù)字反向存入到數(shù)組中。反存var a:array1.255 of integer; i,j,la:inte

20、ger; s:string; /如果輸入的數(shù)字串長(zhǎng)度超過(guò)255 就要用ansistringbegin readln(s); la:=length(s); /數(shù)字串s的長(zhǎng)度 for i:=1 to la do /把對(duì)應(yīng)位置的數(shù)字字符轉(zhuǎn)成數(shù)字 ai:=ord(sla-i+1)-ord(0); for i:=la downto 1 do write(ai);/反向輸出end.hprev.pas高精度加法5 5 9 8 7 5 6 + 1 2 3 4 5 6 7 8 9數(shù)組a數(shù)組b數(shù)組c151 5 141 4 151 5 151 5 151 5 101 0 921下標(biāo) 9 8 7 6 5 4 3 2

21、1 逐位相加，結(jié)果可先存入數(shù)組c中，立即進(jìn)位。演示計(jì)算過(guò)程中結(jié)果相加需要將c中原有的值也參加進(jìn)去。用語(yǔ)句表示為 ci:=ci+ai+bi而進(jìn)位可以用以下語(yǔ)句來(lái)表示。ci+1:=ci div 10;ci:=ci mod 10;另外，對(duì)應(yīng)相加的次數(shù)就是數(shù)組a，b中較長(zhǎng)的長(zhǎng)度。var a,b,c:array1.256 of integer; /a,b至多用255，c有可能需256位 i,j,la,lb,lc:integer; s:string;begin readln(s); la:=length(s); for i:=1 to la do ai:=ord(sla-i+1)-ord(0); /反存a

22、 readln(s); lb:=length(s); for i:=1 to lb do bi:=ord(slb-i+1)-ord(0); /反存b if lalb then lc:=la else lc:=lb; /lc為相加運(yùn)算的次數(shù) for i:=1 to lc do begin ci:=ci+ai+bi; /加1位 ci+1:=ci div 10; /進(jìn)位 ci:=ci mod 10; /去十 end; if clc+10 then lc:=lc+1; /判斷最高位是否發(fā)生進(jìn)位 for i:=lc downto 1 do write(ci); /反向輸出 writeln;end.hip

23、lus.pas高精度減法思路與加法類似，逐位相減。要點(diǎn)：保證大數(shù)放在被減數(shù)的位置，如果小數(shù)在前，做標(biāo)記，并交換兩數(shù)。如果當(dāng)前為需要退位，那么c的高位需要變成-1，那么逐位相減的語(yǔ)句就是：ci:=ai-bi+ci相減的結(jié)果會(huì)產(chǎn)生前導(dǎo)0，需要去除，也有可能結(jié)果為0，那就需要保存一個(gè)0。var a,b,c:array1.1000 of integer; i,la,lb,lc,t:integer; sa,sb,st:string; flag:boolean;begin readln(sa);la:=length(sa); readln(sb);lb:=length(sb); if (lalb) or

24、(la=lb) and (sasb) then begin /直接比較數(shù)字串a(chǎn)，b的大小 flag:=true; /設(shè)置結(jié)果為負(fù)數(shù)的標(biāo)記 st:=sa;sa:=sb;sb:=st; la:=length(sa);lb:=length(sb); end; lc:=la;/暫設(shè)結(jié)果長(zhǎng)度為la for i:=1 to la do ai:=ord(sala-i+1)-ord(0); for i:=1 to lb do bi:=ord(sblb-i+1)-ord(0); for i:=1 to lc do begin ci:=ci+ai-bi; if ci1) do dec(lc);/去除前導(dǎo)0，但總長(zhǎng)

25、要1 if flag then clc:=-clc; /write(-);輸出負(fù)號(hào) for i:=lc downto 1 do write(ci); writeln;end.hisub.pas高精度乘法從兩個(gè)數(shù)相乘的筆算式中，個(gè)位數(shù)乘上十位數(shù)的積的最末一位是在十位，所十位數(shù)乘上十位數(shù)那么是在百位。由此推出對(duì)于ai * bj這個(gè)結(jié)果應(yīng)該儲(chǔ)存在 ci + j - 1位上。 擺豎式ppt演示太難做了，略板書演示vara,b:array1.1000 of integer;c:array1.2000 of integer; /c的長(zhǎng)度可以計(jì)算出來(lái)嗎？la,lb,lc,x,i,j:integer;s:an

26、sistring;beginreadln(s);la:=length(s);for i:=1 to la do ai:=ord(sla-i+1) -ord(0);readln(s);lb:=length(s);for i:=1 to lb do bi:=ord(slb-i+1) -ord(0);for i:=1 to la do /一共要乘的次數(shù) begin x:=0; for j:=1 to lb do /逐位相乘 begin ci+j-1:=ci+j-1+ai*bj+x; /a的第i位和b的第j位相乘要放在c的i+j-1位，為什么？ x:=ci+j-1 div 10; /要進(jìn)位的數(shù)暫存在x

27、中 ci+j-1:=ci+j-1 mod 10; end; ci+j:=x; end;lc:=la+lb;while (clc=0) and (lc1) do dec(lc); /去除前導(dǎo)0，用while不用if的原因是什么？for i:=lc downto 1 do write(ci);writeln;end.HImul.pas高精度加減乘小小結(jié)一下我們用大寫A，B，C來(lái)表示高精度數(shù)，用小寫a，b，c來(lái)表示低精度數(shù)。上面的加減乘我們用字母來(lái)表示就可以標(biāo)記為：加法：C=AB減法：C=AB乘法：C=AB除此之外經(jīng)常會(huì)碰到一些變式如：A=A+B 高精度數(shù)據(jù)的某個(gè)低精度范圍的連加等A=A+b 斐波那

28、契數(shù)列第N項(xiàng)等A=A*b 求N！等 njc.pas這些都可以看作是高精度運(yùn)算的變式。局部注意點(diǎn)：1.A+B的結(jié)果長(zhǎng)度：maxla，lb或maxla，lb+1；2.A*B的結(jié)果長(zhǎng)度：la+lb或la+lb-1A，B皆不等于0；3.A*b計(jì)算中要考慮低精度數(shù)b與A中某位相乘得出結(jié)果的范圍。4.高精度運(yùn)算中可以考慮利用10000進(jìn)制即4位數(shù)字為一數(shù)組單元來(lái)提高運(yùn)算效率，但注意輸出時(shí)要注意每位可能有前導(dǎo)0出現(xiàn)。高精度求余(高精度mod低精度)1234 mod 11=？計(jì)算方法1 mod 11=11*10+2 mod 11=11*10 +3 mod 11=22*10+4 mod 11=2vars:ans

29、istring;m,i,x:integer;beginreadln(s);/s為高精度數(shù)readln(m); /m為低精度整數(shù)for i:=1 to length(s) do x:=(x*10+ord(si)-ord(0) mod m;writeln(x)end.mod.pas第四局部 策略窮舉貪心遞推歸納窮舉法窮舉法也稱為枚舉法是把討論的對(duì)象分成假設(shè)干種情況分類，然后對(duì)各種情況逐一討論，最終解決整個(gè)問(wèn)題。運(yùn)用枚舉法有時(shí)要進(jìn)行恰當(dāng)?shù)姆诸?，分類的原那么是不重不漏。正確的分類有助于暴露問(wèn)題的本質(zhì)，降低問(wèn)題的難度。摘自網(wǎng)絡(luò)簡(jiǎn)單窮舉求11000中所有能被88或173整除的數(shù)。百錢買百雞的問(wèn)題。求所有三

30、位數(shù)的水仙花數(shù)字。有些問(wèn)題無(wú)法簡(jiǎn)單窮舉01背包問(wèn)題裝載問(wèn)題有nn20個(gè)集裝箱要裝上一艘載重量為c的輪船，其中集裝箱i的重量為wi。找出一種最優(yōu)裝載方案，將輪船盡可能裝滿，即在裝載體積不受限制的情況下，將盡可能重的集裝箱裝上輪船。輸入5 10 /5代表一共有5個(gè)貨物n，10代表輪船的最大載重c7 2 6 5 4輸出10 /針對(duì)這5個(gè)貨物輪船最多可能裝載1001背包解析因?yàn)樨浳锏臄?shù)量不固定，所以我們不能簡(jiǎn)單的用多層循環(huán)嵌套來(lái)解決了，所以必須尋找其他思路。但方法的關(guān)鍵仍然是不能遺漏任何一種可能性。因?yàn)檫x和不選只有兩種狀態(tài)，所以在這里我們用數(shù)字0代表不選取該貨物，用1表示選取該貨物。7 2 6 5 4

31、0 0 0 0 0 表示一個(gè)也不選0 0 0 0 1 表示選擇重量為4的一個(gè)貨0 0 0 1 0 表示選擇重量為5的一個(gè)貨0 0 0 1 1 表示選擇重量為4和5的兩個(gè)貨1 1 1 1 1 表示選取所有貨物二進(jìn)制的累加器varb:array0.20 of integer; /一般最多可用到20位的01序列i,j,n,k:integer;begin readln(n); while b0=0 do /終止條件為b0=1，也就意味著溢出了。 begin for i:=1 to n do write(bi);writeln;/這里替換你的算法 i:=n; /找到最后位 while bi=1 do i

32、:=i-1;/找到第一個(gè)0的位置 bi:=1; /這個(gè)0變成1 for i:=i+1 to n do bi:=0; /從當(dāng)前位的后一位起都清0 end;end.bin.pas7 2 6 5 4 數(shù)組a0 0 0 0 0 0 0 0 0 10 0 0 1 0 數(shù)組b的某一個(gè)狀態(tài)0 0 0 1 11 1 1 1 1如何求出當(dāng)前取法下，一共選擇的貨物的重量呢？偽代碼如下：n=5for i1 to n do s=s+ai*bi現(xiàn)在的關(guān)鍵如何依次變化產(chǎn)生b數(shù)組中的值，其實(shí)b數(shù)組變化過(guò)程就是一個(gè)二進(jìn)制的累加器，從00000開(kāi)始一直到11111，不會(huì)遺漏任何一種可能性。01背包問(wèn)題關(guān)鍵在于一個(gè)物品的取或不取

33、，只有兩種狀態(tài)，某些情況下，某些問(wèn)題可能有三種或者更多狀態(tài)，因此，有時(shí)我們要把二進(jìn)制累加器擴(kuò)展到k進(jìn)制累加器。varb:array0.20 of integer;i,j,n,k:integer;begin readln(n,k);/n位，k進(jìn)制 while b0=0 do/b0為標(biāo)志位 begin for i:=1 to n do write(bi);writeln; /累加器樣例輸出，使用時(shí)在此處替換算法 i:=n; /定位 while bi=k-1 do i:=i-1;/逆向?qū)ふ易詈笠粋€(gè)不是K-1的數(shù) bi:=bi+1; /在當(dāng)前位加1，本質(zhì)就是進(jìn)位 for i:=i+1 to n do

34、bi:=0;/從i+1往后都清0 end;end.k.pas二進(jìn)制累加器終究是一種窮舉法，效率并不高，在二進(jìn)制累加器下一般物品個(gè)數(shù)即累加器長(zhǎng)度不應(yīng)超過(guò)20，否那么根本都要超時(shí)。應(yīng)用：01背包問(wèn)題 運(yùn)用二進(jìn)制累加器22屆市賽?等式問(wèn)題? 考慮到可填加號(hào)，減號(hào)或不填，一共三種狀態(tài)，所以應(yīng)該使用三進(jìn)制的窮舉累加器。貪心策略 貪心算法又稱貪婪算法是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。 貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。摘自網(wǎng)絡(luò)先來(lái)看個(gè)例

35、子數(shù)塔問(wèn)題有形如下圖的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，要求走到底層,找出一條路徑，使路徑上的值最大。 按照貪心原那么，每次都去找下方的數(shù)種較大的一個(gè)，那么得到結(jié)果為51，很明顯我們就發(fā)現(xiàn)51不是最大值，59才是最大值。所以此問(wèn)題解決不能用貪心策略。 同樣，在解決一般問(wèn)題中，如果你已經(jīng)有了算法，嘗試推舉反例，看看是否能夠否認(rèn)你的想法。so，在打草稿構(gòu)思算法的時(shí)候，就應(yīng)該開(kāi)始尋找反例，等你寫完代碼才發(fā)現(xiàn)，那就杯具了典型貪心問(wèn)題解析攔截導(dǎo)彈 某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，開(kāi)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮

36、彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來(lái)的高度雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)，計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。輸入樣例：389 207 155 300 299 170 158 65輸出樣例：2daodan.pas389 207 155 300 299 170 158 65現(xiàn)在我們來(lái)構(gòu)思一下算法：我們來(lái)嘗試找一個(gè)反例。68389 207 155 300 299 170 158 65這才是正確的方法，試驗(yàn)下剛剛舉的反例吧，通過(guò)了嗎？此題的局部最優(yōu)解是：用一套攔截系統(tǒng)攔截掉所有可以攔截的導(dǎo)彈。排隊(duì)接水有n個(gè)人在一個(gè)水龍頭前排隊(duì)接水，假設(shè)每個(gè)人接水的時(shí)間為