奧賽經(jīng)典題目講解

巧用數(shù)組下標輕松回避重復判斷

[作者：佚名轉貼自：網(wǎng)絡點擊數(shù)：68文章錄入：kknd]

在程序設計的某個環(huán)節(jié)中，需要統(tǒng)計不同數(shù)據(jù)的個數(shù)，按照常規(guī)思路的算法簡單描述如下：

①讀入下一個數(shù)；

②將該數(shù)與之前已讀入的數(shù)一一比較，如果都不同，則該數(shù)是新數(shù)，累加器加1;否則，表示該數(shù)是

舊數(shù)，有重復，直接退出比較的循環(huán)②。

③是否讀完所有數(shù)據(jù)，如果是，輸出累加器值，結束；否則，轉到①；

下面用一個實例說明。

例產(chǎn)生10個范圍為1—20的隨機整數(shù)，統(tǒng)計不同數(shù)的個數(shù)。

按照常規(guī)思路，得如下參考程序。

programtongji(input,output);

var

a:array[1..10]ofinteger;

i,j,t:integer;

begin

writeln。產(chǎn)生隨機數(shù):)；

randomize;

fori:=1to10do

begina[i]:=l+random(19);write(Jend;

t:=0;

fori:=1to10do

begin

j：=l；

while(j<i)and(a[i]Oa[j])doj:=j+1;

ifj=ithent:=t+l;

end;

writeln;writeln(，統(tǒng)計不同數(shù)據(jù)有個二)；

end.

由以上程序可知，完成數(shù)據(jù)統(tǒng)計需要兩重循環(huán)，時間復雜度為O(n2)。如果數(shù)據(jù)是正整數(shù)，那么試著

換另外一種思路：將數(shù)據(jù)作為數(shù)組的下標，進行一個賦值為1的標記操作。比如，現(xiàn)有數(shù)：2,6,2,

用數(shù)組b口輔助存儲，依次操作：b[2]:=1,b[6]:=1,接下來是2,已重復，在程序中無需特殊判斷，

執(zhí)行相同操作：b[2]:=1,這樣就可以有效回避重復判斷，最后只要累計b[]數(shù)組中值為1的個數(shù)，事

實上，數(shù)組中其他元素由于沒有進行賦值操作，保留了默認值0,因此累加操作也可以擴展到所有數(shù)

組元素的直接相加，為了更有效的累加，可以在執(zhí)行賦值操作時，加入數(shù)據(jù)范圍的上限、下限標識：

max和min,每讀入一個數(shù)后，更新數(shù)據(jù)范圍，最后只要將下標為上下限范圍的數(shù)組數(shù)據(jù)進行累加。

參考程序如下：

programtongji(input,output);

var

a:array[1..10]ofinteger;

b:array[1..20]ofinteger;

i,t,max,min:integer;

begin

wiitelnC產(chǎn)生隨機數(shù)

randomize;

fori:=1to10do｛產(chǎn)生10個(1-20)隨機數(shù)｝

begina[i]:=l+random(19);write,end;

t:=0;max:=0;min:=10000;｛設置統(tǒng)計時，數(shù)組范圍的上下標識｝

fori:=1to10do

begin

"a叩:=1；｛將數(shù)據(jù)以數(shù)組下標的形式寫入，避免判斷｝

ifa[i]>maxthenmax:=a[i];｛更新數(shù)組范圍的上下標識｝

ifa[i]<minthenmin:=a[i];

end;

fori:=mintomaxdot:=t+b[i];｛統(tǒng)計不同數(shù)據(jù)個數(shù)｝

writein;writeln。統(tǒng)計不同數(shù)據(jù)有X'個

end.

如果程序要求將個數(shù)統(tǒng)計結果分別顯示，如

輸入：262；

輸出：2:26:1

2

其中輸出第1行分別顯示每個數(shù)的統(tǒng)計情況，第2行統(tǒng)計數(shù)據(jù)有幾個。

要統(tǒng)計每個數(shù)的數(shù)量情況，在將數(shù)據(jù)以數(shù)組下標的形式寫入時，不能直接賦1操作，需執(zhí)行累加，

以為該數(shù)進行統(tǒng)計；這個操作對統(tǒng)計不同數(shù)據(jù)的總個數(shù)發(fā)生了變化，因此統(tǒng)計時將原來的直接累加,

變?yōu)榕袛喾?后，再累加1完成。改變部分的代碼如下：

t:=0;max:=O;min:=10000;｛設置統(tǒng)計時，數(shù)組范圍的上下標識｝

fori:=1to10do

begin

b[a[i]]:=b[a[i]]+l;

ifa[i]>maxthenmax:=a[i];

ifa[i]<minthenmin:=a[i];

end

fori:=mintomaxdo

ifb[i]<>0then

beginwrite(i,':',b[i]');t:=t+1;end;｛統(tǒng)計不同數(shù)據(jù)個數(shù)｝

writein;writeln(t);

時間復雜度由原來的0(n2)降低為0(n)?

編程時，不妨拋開傳統(tǒng)解題思路，嘗試著用其他方法解決，一個小小的數(shù)據(jù)統(tǒng)計程序，或許可以給

你些許啟迪，愿本文起到拋磚引玉的作用。

歷屆NOIP搜索算法全集

用動態(tài)規(guī)劃來解背包問題

在歷屆NOIP競賽中，有4道初賽題和5道復賽題均涉及到背包問題，所謂的背包問

題，可以描述如下：一個小偷打劫一個保險箱，發(fā)現(xiàn)柜子里有N類不同大小與價值

的物品，但小偷只有一個容積為M的背包來裝東西，背包問題就是要找出一個小偷

選擇所偷物品的組合，以使偷走的物品總價值最大。

如有4件物品，容積分別為：3458

對應的價值分別為：45710

小偷背包的載重量為：12

則取編號為123的物品，得到最大價值為16。

算法分析：如果采用貪心法，則先取價值最大的10,消耗了容積8,下面只能取容

積為4的物品，得到價值5,這樣總價值是15,這不是最優(yōu)解，因此貪心法是不正

確的。

采用窮舉法，用一個B數(shù)組來表示取數(shù)的標記，當時表示第i件物品不取，

當B=1時表示第i件物品已取，初始化全部取0,以下算法是從后面的物品開始取

起，通過B數(shù)組的取值把15種取法全部窮舉出來，價值MAX初始化為0o

B[0]B[l]B[2]B[3]B[4]

00000｛初始化｝

00001｛取第4件物品，容積為8,不超，價值為10,將MAX替換為10｝

00010｛取物品3,容積為5,不超，價值為7,不換｝

00011｛取物品3、4,容積為13,超｝

00100｛取物品2,容積為4,不超，價值為5,不換｝

00101

00110

00111

01110｛這是最佳方案｝

01111

10000｛當B(0)=1時停止，B10〕稱為哨兵｝

生成B數(shù)組中數(shù)據(jù)的方法如下：

fillchar(b,sizeof(b),0);

whileb[0]=0do

beginj:=n;

whileb[j]=ldodec(j);

b[j]:=1;

fori:=j+ltondo

b:=0;

end；

小結：以上每件物品只能取1件，所以取法只有0和1兩種情況，我們稱之為0、1

背包，算法的時間復雜度為0(2N),在1秒內N只能做到20。

例1：選數(shù)(N0IP2002初中組復賽第2題)

[問題描述]:已知n個整數(shù)xl,x2,…,xn,以及一個整數(shù)k(k<n)。從n個整數(shù)

中任選k個整數(shù)相加，可分別得到一系列的和。例如當n=4,k=3,4個整數(shù)分別

為3,7,12,19時，可得全部的組合與它們的和為：

3+7+12=223+7+19=297+12+19=383+12+19=34。

現(xiàn)在，要求你計算出和為素數(shù)共有多少種。

例如上例，只有一種的和為素數(shù)：3+7+19=29。

［輸入］:

鍵盤輸入，格式為：

n,k(K=n<=20,k<n)

xl,x2,xn(K=xi<=5000000)

n［輸出］：

屏幕輸出，格式為：

一個整數(shù)(滿足條件的種數(shù))。

［輸入輸出樣例］:

輸入：

43

371219

輸出：

1

［算法分析］:本題應用背包問題中取數(shù)的方法進行窮舉，在取數(shù)的過程中，當B數(shù)組

中有K個1的時候將對應的K個數(shù)相加，再判斷是不是素數(shù)。

主要程序段如下：

readln(n,k);sum:=0;

fori:=ltondoread(a);

fillchar(b,sizeof(b),0);

whileb［0］=0do

beginj:=n;

whileb［j］=ldodec(j);

b［j］:=1；

fori:=j+ltondob:=0;

m:=0;

fori:=ltondo

ifb=lthenm:=m+l;｛統(tǒng)計1的個數(shù)｝

ifm=kthen

begin計算此種取數(shù)方法得到的和S；

ifS是素數(shù)thensum:=sum+l;

end;

end;

例2：采藥（N0IP2005初中組復賽第3題）

【問題描述】

辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附

近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質，給他出了一個難題。醫(yī)師把他帶

到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采

每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時

間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥

的總價值最大?！?/p>

如果你是辰辰，你能完成這個任務嗎？

【輸入文件】

輸入文件medic.in的第一行有兩個整數(shù)T（1<=T<=1000）和M（1〈=M〈=100）,

用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞里的草藥的數(shù)目。接

下來的M行每行包括兩個在1至U100之間（包括1和100）的整數(shù)，分別表示采摘

某株草藥的時間和這株草藥的價值。

【輸出文件】

輸出文件medic,out包括一行，這一行只包含一個整數(shù)，表示在規(guī)定的時間內，可

以采到的草藥的最大總價值。

【樣例輸入】

703

71100

691

12

【樣例輸出】

3

【數(shù)據(jù)規(guī)?！?/p>

對于30%的數(shù)據(jù)，M<=10；

對于全部的數(shù)據(jù)，M<=100o

【算法分析】本題如果采用上述方法來解，只能將M算到20,而這里M<=100,所

以只能拿30%的分數(shù)，比較好的算法是采用動態(tài)規(guī)劃，為了能說清算法，現(xiàn)重新舉

一個例子，若輸入：

103

34

45

56

表示背包的容量是10,有3種物品。用一個數(shù)組用來表示背包容量與其最大價值的

關系，上例中設置一個數(shù)組count,用下標表示容量，初始化為0。然后按物品的順

序一一來統(tǒng)計此時的最大價值，每種藥品對應各種背包容量時得到的最大價值為：

對于是第i件物品，背包容量為j時的最大價值Cmax(j)=MAX(Cmaxj,Pi+余下空間

的最大價值Cmax(j-i物品所占的空間))，如上例中，根據(jù)物品的不斷增加，各容量

背包得到的最大價值不斷替換：

容量12345678910

價值

序號0000000000

10044444444

20045559999

30045669101111

［數(shù)據(jù)結構］time,price數(shù)組分別用來存入時間和價值，count來存入背包的價值。

var

time,price:array[1..100]oflongint;

t:longint;i,m,j:integer;

count:array[0..1000]oflongint;

begin

assign(input,?medic.in，);

assign(output,?medic.out，);

reset(input);

rewrite(output);

readln(t,m);

fori:=1tomdo

readln(time,price);

fillchar(count,sizeof(count),0);

fori:=1tomdo

forj:=tdownto1do

begin

if(j>=time)and(price+count[j-time]>count[j])then

count[j]:=price+count[j-time];

end;{j>=time表示當前的容量能放入背包，price+count[j-time]>count[j]表示

第i件物品的價值加上第i件物品對于背包容量為j時余下空間的最大價值大于當

前背包容量為j時的最大價值}

writein(count[t]);

close(input);

close(output);

end.

例3：開心的金明(N0IP2006初中組復賽第2題)

題目較長，省略，本題與例2相比，在比較時要先將價值乘以一個數(shù)，其余一樣，

但要注意的是：本題N的范圍是〈二26,如果用0、1背包窮舉法在1秒內只能過10

個點中的8個點。

總結：采用動態(tài)規(guī)劃的時間復雜度為O(n*m),范圍比窮舉法大多了，但也有弱點,

當數(shù)據(jù)不是整數(shù)時，就不可使用；如果還要求出具體的取法，那也相當麻煩。

競賽的高分的關鍵一測試

[作者：王亞峰轉貼自：河南大學附屬中學點擊數(shù)：54文章錄入：kknd]

競賽的高分的關鍵一測試

noip剛結束，很多同學認為題目很容易，但是自測時卻沒有得到理想的分數(shù)，

這主要是因為競賽時“測試”這個環(huán)節(jié)沒有做好，作為一個。i輔導老師，我

介紹一下一些經(jīng)驗，供大家分享。

信息學奧林匹克競賽中得高分的關鍵環(huán)節(jié)一一測試

河南大學附屬中學王亞峰

I、引言

中學生信息學奧林匹克競賽是中學生奧林匹克競賽的一個重要組成部分，和其他科目的奧林匹克競賽相比它在

競賽方式上和評分標準上有著很大不同。競賽實施的方式完全是上機編程序，實踐性很強，評分的唯一標準是

看通過測試數(shù)據(jù)的多少。通常競賽中編寫一個程序可以分為這樣幾個環(huán)節(jié)：分析題目一設計算法和數(shù)據(jù)結構一

編碼一調試一測試，設計測試數(shù)據(jù)的能力是競賽考察的重點之一。但是很多學習信息學奧林匹克競賽的學生和

一些教師常常只重視算法的學習，忽視了“測試”這個環(huán)節(jié)。有的同學在競賽中為了趕時間多做完一道題目，

沒有對已經(jīng)做過的題目進行充分的測試，認為設計測試數(shù)據(jù)是浪費時間，所以經(jīng)常會出現(xiàn)會做的題目不得分或

者得不了滿分的情況。那么怎么才能提高程序的正確率，在競賽中取得高分呢？

II、一些良好的習慣可以幫助提高編程正確率

眾所周知，要想提高學生編程的正確率必須要培養(yǎng)學生有一個良好的編程習慣。這些良好的習慣包括:

A、規(guī)范地書寫程序。我們書寫程序時要使用縮進格式，不同層次的語句向后縮進若干格，這樣可以保證程序

盡量少出語法錯誤。另外，命名變量名時應盡量有一定意義，增加程序的可讀性，調試程序時也方便。但是不

要把變量名起得太長，這樣會影響編程速度，可以使用一些簡短的漢語拼音或英文縮寫，只要自己好記就可以

了。

B、編程時要使用自頂向下分析的方法和模塊化的方法?？梢詫⒁恍┆毩⒌墓δ芾巛斎搿⑤敵龉δ苣K化，

這樣在調試的時候可以逐模塊地檢查排錯，將一個大規(guī)模問題分解成幾個小規(guī)模問題。但是也不能盲目地將程

序分割成太多模塊，信息學奧林匹克競賽中出的題目往往都不大，所以不必分成太多的模塊，分得太多反而會

成為累贅。模塊化的依據(jù)主要在于程序的內在邏輯。

C、使用全局變量時要特別小心。信息學奧林匹克競賽中的程序規(guī)模一般比較小，全局變量的使用會很頻繁，

有時全局變量可以簡化編程復雜度，但是全局變量的使用也會帶來危險，特別是在過程或函數(shù)中改變全局變量

的值可能會帶來不可預期的后果。例如，在深度優(yōu)先搜索中可以設一個全局的“?！眮泶鎯λ阉髦械臓顟B(tài)，但

是在遞歸過程中，進入遞歸時數(shù)據(jù)“進棧”，回溯時數(shù)據(jù)“出?！?。在這個過程中要對全局變量“?！焙汀皸?/p>

的指針”進行操作，在這個過程中非常容易出錯，出錯后很難檢查和調試。所以在教學中一定要給學生講清楚

全局變量和局部變量的區(qū)別，全局變量在過程或函數(shù)中被修改時對程序的影響，養(yǎng)成學生正確使用全局變量的

習慣。

III、測試是信息學奧林匹克競賽中得高分的關鍵

養(yǎng)成良好的習慣能避免編程中的很多錯誤，但是這還不足以能保證競賽中編寫的程序能通過所有的測試數(shù)據(jù)，

這是因為競賽評測時給的標準測試數(shù)據(jù)都是相當苛刻的，如果程序提交前沒有經(jīng)過充分的測試，很有可能不能

通過標準測試數(shù)據(jù)。學生在參加競賽時經(jīng)常會遇到這樣的情況：競賽完了以后感覺非常好，覺得題目不難，而

且?guī)椎李}自己都做完了，都通過了樣例數(shù)據(jù)，但是等成績出來以后卻和期望中的相差甚遠。使用標準測試數(shù)據(jù)

測試自己的程序后才發(fā)現(xiàn)，不是某些特殊情況沒有考慮到，就是犯了小錯誤，例如變量誤用，或者數(shù)組聲明地

太小。很多學生不止一次犯過類似這樣的錯誤，常常因為這樣的錯誤而懊悔不已，原本應該能夠拿到的分數(shù)卻

沒有拿到。大多數(shù)人把這種錯誤歸咎于粗心，其實出現(xiàn)錯誤是很正常的，無論多么擅長編程的人都不可能完全

避免出錯。那么能不能及時糾正這些由“粗心”引起的錯誤呢？在競賽中我們編寫完一個題目后自己應該設計

多組測試數(shù)據(jù)來測試自己的程序從而找到程序中隱藏的錯誤，測試是編程時的“把門將軍”，他可以將錯誤拒

之門外，測試進行得越充分，程序的正確率就越高，所以“測試”這一環(huán)節(jié)是競賽中得高分的關鍵。

程序結構組織的技巧

[作者：風清云淡轉貼自：網(wǎng)絡博客點擊數(shù)：28文章錄入：kknd]

1概述

1）自頂向下，逐步求精

意思就是，先寫主程序，需要用子程序的地方盡管調用（雖然子程序還沒有寫），

直至完成主程序的框架（頂）。下面再分別完成各各子程序。

這樣做的好處很明顯：思路連貫，清晰，從全局入手，不會被眾多小問題弄的

暈頭轉向。靜態(tài)查錯和調試也非常方便，程序可讀性也極強。

2）子程序的大小

學過一點軟件工程基本知識的同學應該知道，子程序因為起到了分割問題的作用

會降低編程復雜度，但過多的子程序會因為接口工作帶來額外的程序量。我不

想借用那種N行一個子程序的建議，只是希望大家注意，子程序不能太多。常用

的代碼寫成子程序就可以了。

3）子程序的相互依賴關系。

我不想深入展開，只是提醒大家，少用全局變量，減少依賴性，增加獨立性。這

會給調試帶來極大的方便。

4）競賽需要簡潔和清晰的統(tǒng)一

一般來說，競賽時更看中簡潔，因為涉及到編程復雜度和調試復雜度，所以過程不易太多。

[b]2美化你的程序

這是一個值得深入研究的問題。我在這里只是講一點皮毛，給初學者引引路，

幫你們找到“感覺”。

源程序是給人看的。

不只有你是人，因此程序要讓第二個人也能看懂

我知道你不想讓別人看到你的程序，但N年以后可能你自己都看不懂了...

所以，我給你一些建議：

a.縮進式。就是每個層次空兩格（也不一定是2格，看你的習慣了）。如：

fori:=1tondo

forj:=1tondo

ifi+j>5then

begin

i:=i+l;

j：=j-2;

end；

就寫成：

fori:=1tondo

forj:=1tondo

ifi+j>5then

begin

i:=i+1;

j：=j-2;

end；

這樣層次很清楚,也比較好看一點。

b.給變量取好記的名字。

如：i,j：循環(huán)變量

total:累加器

best:當前最優(yōu)值

等等。主要也是看你的習慣了。注意一定不要引起混淆。

例如一個變量叫num,一個叫number,就難免會用錯。

c.善用子程序。

例如：

begin

Init;

fori:=1tondo

begin

Analyse(i);

Process(i);

AddToResult(i);

end;

end.

程序的作用和結構很明顯，如果把init(),analyse0,process().addtoresult()代碼放在這里,

就會顯得非常臃腫，分不清哪些代碼是干什么的，而且很不利于單獨調試。

程序調試技巧

[作者：風清云淡轉貼自：網(wǎng)絡博客點擊數(shù)：28文章錄入：kknd]

1調試技巧

調試之前，先要靜態(tài)查錯。

1.看算法是否正確（其實應該是在編碼之前做的工作）

2.看有沒有筆誤（如i寫成j）

調試一般是分幾個步驟的。先把開關R,S,Q,I打開！

1.建立測試數(shù)據(jù)（技巧見后面的文章），可以