信息奧賽-窮舉

窮舉

OicqPassOver這個(gè)工具可以用來(lái)探測(cè)QQ的口令，它根據(jù)機(jī)器性能最高可以每秒測(cè)試20000個(gè)口令，如果口令簡(jiǎn)單，一分鐘內(nèi)，密碼就會(huì)遭到破譯。這些密碼破譯軟件通常就是用的窮舉算法。窮舉的策略應(yīng)該是直接基于計(jì)算機(jī)特點(diǎn)而使用的思維方法，在一時(shí)找不到解決問(wèn)題的更好途徑（比如數(shù)學(xué)公式或規(guī)律規(guī)則）時(shí)，可以根據(jù)問(wèn)題中的部分（約束）條件，將可能解的情況列舉出來(lái)，然后一一驗(yàn)證是否符合整個(gè)問(wèn)題的求解要求。

實(shí)例：編一個(gè)程序找出三位數(shù)到七位數(shù)中所有的阿姆斯特朗數(shù)。阿姆斯特朗數(shù)也叫水仙花數(shù),它的定義如下:若一個(gè)n位自然數(shù)的各位數(shù)字的n次方之和等于它本身,則稱這個(gè)自然數(shù)為阿姆斯特朗數(shù)。例如153(153=1*1*1+3*3*3+5*5*5)是一個(gè)三位數(shù)的阿姆斯特朗數(shù),8208則是一個(gè)四位數(shù)的阿姆斯特朗數(shù)。算法描述：forI:=100to9999999dobegin

驗(yàn)證是否是阿姆斯特朗數(shù)，若是則輸出；

end;鈔票換硬幣

把一元鈔票換成一分、二分、五分硬幣（每種至少一枚），有哪些種換法？461種

var

i,j,k,total:integer;begintotal:=0;{總數(shù)設(shè)為０}fori:=1to99do{i:二分硬幣最多99枚}forj:=1to49do{j:二分硬幣最多49枚}fork:=1to19do{k:五分硬幣最多19枚}ifi*1+j*2+k*5=100thenbeginwriteln(i:3,j:3,k:3);

inc(total);{總數(shù)加１}end;

writeln(total);

readln;end.百錢買百雞【題目】一只公雞值５元，一只母雞值３元，３只小雞值１元，現(xiàn)用一百元要買一百只雞。問(wèn)有什么方案？

這是一個(gè)古典數(shù)學(xué)問(wèn)題，設(shè)一百只雞中公雞、母雞、小雞分別為x，y，z，問(wèn)題化為三元一次方程組：

這里x,y,z為正整數(shù)，且z是3的倍數(shù)；由于雞和錢的總數(shù)都是100，可以確定x,y,z的取值范圍：

1)x的取值范圍為1～20

2)y的取值范圍為1～33

3)z的取值范圍為3～99，步長(zhǎng)為3

對(duì)于這個(gè)問(wèn)題我們可以用窮舉的方法，遍歷x,y,z的所有可能組合，最后得到問(wèn)題的解。

下式算式中不同的字母代表不同的數(shù)字，編程打印出下列算式A+BC+DEF=GHIJ可以確定d=9,g=1,h=0.分書問(wèn)題

有Ａ、Ｂ、Ｃ、Ｄ、Ｅ五本書，要分給張、王、劉、趙、錢五位同學(xué)，每人只能選一本,事先讓每人把自己喜愛(ài)的書法填于右表，編程找出讓每人都滿意的方案。

ABCDE張

√√

王√√

√劉

√√

趙√√

√

錢

√

√

張

王

劉

趙

錢

①Ｃ

Ａ

Ｂ

Ｄ

Ｅ

②Ｄ

Ａ

Ｃ

Ｂ

Ｅ

③Ｄ

Ｂ

Ｃ

Ａ

Ｅ

④

Ｄ

Ｅ

Ｃ

Ａ

Ｂ

var

z,w,l,zh,q,total:byte;procedureoutput;beginwriteln('zhang:',chr(z+64));writeln('wang:',chr(w+64));

writeln('liu:',chr(l+64));writeln('zhao:',chr(zh+64));writeln('qian:',chr(q+64));

writeln;

inc(total);end;

begintotal:=0;forz:=3to4doforw:=1to5doif(w<>3)and(w<>4)thenforl:=2to3doforzh:=1to4doifzh<>3thenforq:=2to5doif(q<>3)and(q<>4)thenbeginifz+w+l+zh+q=15thenifz*w*l*zh*q=120thenoutput;end;

write(total);end.

實(shí)例：砝碼稱重（NOIPT96-4）設(shè)有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重<=1000），輸出用這些砝碼能稱出的不同重量的個(gè)數(shù)，但不包括一個(gè)砝碼也不用的情況。算法分析：最容易想到的方法就是枚舉出有幾個(gè)1g，幾個(gè)2g，幾個(gè)3g……幾個(gè)20g，然后統(tǒng)計(jì)有幾種不同的重量。用數(shù)組w[1]~w[6]表示砝碼的重量，q[1]~q[6]表示選擇方案。{Total:array[0..1000]ofinteger;}fillchar(total,sizeof(total),0);forq[1]:=0toa1doforq[2]:=0toa2doforq[3]:=0toa3doforq[4]:=0toa4doforq[5]:=0toa5doforq[6]:=0toa6dobeginsum:=0;Fori:=1to6do

sum:=sum+q[i]*w[i];ifsum<=1000thentotal[sum]:=1;end;a1表示1g砝碼所能取到的最大個(gè)數(shù)a2表示2g砝碼所能取到的最大個(gè)數(shù)a3表示3g砝碼所能取到的最大個(gè)數(shù)……完全數(shù)

古希臘人認(rèn)為因子的和等于它本身的數(shù)是一個(gè)完全數(shù)（自身因子除外），例如28的因子是1、2、4、7、14，且1+2+4+7+14=28，則28是一個(gè)完全數(shù)，編寫一個(gè)程序求2～1000內(nèi)的所有完全數(shù)。Programp3_1;Vara,b,s:integer;

BeginFora:=2to1000doBeginS:=0;Forb:=1toa-1doIfamodb=0thens:=s+b;{分解因子并求和}Ifa=sthenbeginWrite(a,‘=’,1,);Forb:=2toa-1doIfamodb=0thenwrite(’+’,b);

Writeln;End;End;End.窮舉法的優(yōu)點(diǎn)：⑴由于窮舉算法一般是現(xiàn)實(shí)生活中問(wèn)題的“直譯”，因此比較直觀，易于理解；⑵由于窮舉算法建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)上，所以算法的正確性比較容易證明。窮舉法的缺點(diǎn)：窮舉算法的效率取決于窮舉狀態(tài)的數(shù)量以及單個(gè)狀態(tài)窮舉的代價(jià)，因此效率比較低。

實(shí)例：有形如：ax3+bx2+cx+d=0

這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)(a，b，c，d

均為實(shí)數(shù))，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕對(duì)值>=1。要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格)，并精確到小數(shù)點(diǎn)后2位。樣例輸入：1

-5

-4

20輸出：-2.00

2.00

5.00窮舉法應(yīng)用

本題是2001年全國(guó)信息學(xué)奧林匹克競(jìng)賽高中組復(fù)賽第一題，如果考慮解方程的話則比較麻煩。我們可以換個(gè)角度思考問(wèn)題，在-100到100之間找三個(gè)滿足方程的實(shí)數(shù)，由于窮舉時(shí)必須用整型變量，題目又要求保留兩位小數(shù)，我們只需將循環(huán)變量擴(kuò)大100倍即可順利窮舉，最后只要將所求結(jié)果再縮小100倍即可。Fori:=-10000To10000DoBeginx:=i/100;If

ThenIfi<x1Thenx1:=iElseIfi<x2Thenx2:=iElseIfi<x3Thenx3:=i;{確保x1<x2<x3}End;Writeln(x1/100:0:2,'',x2/100:0:2,'',x3/100:0:2);End.Abs(a*x*x*x+b*x*x+c*x+d)<0.000001篩法求素?cái)?shù)用篩選法實(shí)現(xiàn)求N以內(nèi)的所有素?cái)?shù)(就是質(zhì)數(shù))。并按每行10個(gè)數(shù)的形式打印出來(lái).n=25時(shí),用篩選法選素?cái)?shù)的過(guò)程如下:(1)2345678910111213141516171819202122232425(2)2345678910111213141516171819202122232425(3)2345678910111213141516171819202122232425(4)2345678910111213141516171819202122232425(5)2345678910111213141516171819202122232425(2)23456789101112131415161718192021222324

25(3)2345678

9

1011121314

15

1617181920

21

22232425(4)2345678

9

1011121314

15

1617181920

21

22232425(5)234

5

678

9

1011121314

15

1617181920

21

222324

25首先確定2是素?cái)?shù),接著把凡是2的倍數(shù)的那些數(shù)篩去,過(guò)程見(jiàn)步驟(2),其中帶有刪除線的數(shù)就是被篩去的數(shù).接著把凡是3的倍數(shù)的那些數(shù)篩去,過(guò)程見(jiàn)步驟(3).接著把凡是4的倍數(shù)的那些數(shù)篩去,過(guò)程見(jiàn)步驟(4).接著把凡是5的倍數(shù)的那些數(shù)篩去,過(guò)程見(jiàn)步驟(5).這時(shí)數(shù)列中剩下的未被篩去那些數(shù)就都是素?cái)?shù).篩選法找素?cái)?shù)的過(guò)程實(shí)際上是一個(gè)去合數(shù)的過(guò)程,顯然所有被去掉的數(shù)都是合數(shù),那么上述的篩選步驟到底

要做到第幾步才能保證沒(méi)有合數(shù)剩下來(lái)呢?沿用前面的質(zhì)數(shù)判斷定理,因?yàn)槿魏我粋€(gè)合數(shù)一定有一個(gè)因子的平方小于等于它本身,所以對(duì)任意的n,只要將所有的i(i*i<=n)的倍數(shù)篩去,就能保證沒(méi)有一個(gè)合數(shù)剩下來(lái).如n=25時(shí),篩去5的倍數(shù)后就不用再往下做了.為了實(shí)現(xiàn)以上算法我們首先可以把2到n這n-1個(gè)自然數(shù)放在一個(gè)數(shù)組中,可以用各種方法來(lái)表示數(shù)組元素中的值已被篩去,例如給數(shù)組元素置0或負(fù)數(shù).篩法求素?cái)?shù)constmaxn=1000;var

i,j,n:integer;

prime:array[2..maxn]ofinteger;begin

write('Inputn:');readln(n);fori:=2tomaxndoprime[i]:=1;i:=2;whilei*i<=ndobeginj:=i*2;whilej<=ndobeginprime[j]:=0;j:=j+iend;i:=i+1end;fori:=2tondoifprime[i]=1thenwrite(i:8);

writelnend.實(shí)例：4皇后問(wèn)題。問(wèn)題描述：在4×4的棋盤上安置4個(gè)皇后，要求任意兩個(gè)皇后不在同一行、不在同一列、不在同一對(duì)角線上，輸出所有的方案。實(shí)例三：4皇后問(wèn)題。問(wèn)題描述：在4×4的棋盤上安置4個(gè)皇后，要求任意兩個(gè)皇后不在同一行、不在同一列、不在同一對(duì)角線上，輸出所有的方案。S[1]:第一行皇后的列號(hào)S[2]:第二行皇后的列號(hào)……4皇后問(wèn)題Q2Q3Q1Q2Q3QQ3Q2Q1functioncheck:boolean;var

i,j:integer;beginfori:=1ton-1doforj:=i+1tondoif(s[i]=s[j])or(abs(i-j)=abs(s[i]-s[j]))thenbegincheck:=false;exit;end;check:=true;end;beginfori1:=1tondofori2:=1tondofori3:=1tondofori4:=1tondobegins[1]:=i1;s[2]:=i2;s[3]:=i3;s[4]:=i4;ifcheckthenprint;end;end.fori1:=1to4dofori2:=1to4doifi1<>i2thenfori3:=1to4doif(i1<>i3)and(i2<>i3)thenbegini4:=10-i1-i2-i3;ifcheckthenprint;end;情況分析123412431324134214231432213421432314234124132431312431423214324134123421412341324213423143124321所有可能的列號(hào)序列的情況：這就是1到4的全排列!排列輸入整數(shù)n，按字典序從小到大的順序輸出前n個(gè)數(shù)的所有全排列。兩個(gè)序列的字典序大小關(guān)系等價(jià)于從頭開(kāi)始的第一個(gè)不相同位置處的大小關(guān)系。例如(1,3,2)<(2,1,3),字典序最小的排列是（1，2，3，4，…，n），最大的排列是（n，n-1，n-2，…，1）。n=3時(shí)，所有排列的排序結(jié)果是：（1，2，3）、（1，3，2）、（2，1，3）（2，3，1）、（3，1，2）、（3，2，1）全排列的生成算法1~n個(gè)數(shù)全排列的總數(shù)為n！構(gòu)造法生成從123……n到n……321的全排列求12543的下一個(gè)排列：132451.從右到左找到一個(gè)數(shù)比右邊的數(shù)小，我們稱為A；(例?)2.從右到左找到第一個(gè)數(shù)比A大，我們成為B；(?)3.A和B交換；4.將原先A所在位置右邊的數(shù)倒序。全排列的生成算法fork:=1tototaldo{total為n！}beginFori:=1tondowrite(a[i]);writeln;i:=n-1;while(i>0)and(a[i]>a[i+1])doi:=i-1;j:=n;whilea[j]<a[i]doj:=j-1;temp:=a[i];a[i]:=a[j];a[j]:=temp;i:=i+1;j:=n;whilei<jdobegintemp:=a[i];a[i]:=a[j];a[j]:=temp;i:=i+1;j:=j-1;end;end;1234

例3-2.某班有M個(gè)同學(xué)，從中選出n個(gè)人參加文娛演出，沒(méi)有順序，請(qǐng)給出所有的情況。

思路是開(kāi)一個(gè)數(shù)組，其下標(biāo)表示1到m個(gè)數(shù)，數(shù)組元素的值為1表示其下標(biāo)代表的數(shù)被選中，為0則沒(méi)選中。

1.首先初始化，將數(shù)組前n個(gè)元素置1，表示第一個(gè)組合為前n個(gè)數(shù)。

2.然后從左到右掃描數(shù)組元素值的“10”組合，找到第一個(gè)“10”組合后將其變?yōu)椤?1”組合，同時(shí)將其左邊的所有“1”全部移動(dòng)到數(shù)組的最左端。

3.當(dāng)?shù)谝粋€(gè)“1”移動(dòng)到數(shù)組的m-n+1的位置，即n個(gè)“1”全部移動(dòng)到最右端時(shí)，就得到了最后一個(gè)組合。

例如求5中選3的組合：

11100//1,2,3

11010//1,2,4

10110//1,3,4

01110//2,3,4

11001//1,2,5

10101//1,3,5

01101//2,3,5

10011//1,4,5

01011//2,4,5

00111//3,4,5

窮舉法是基于計(jì)算機(jī)特點(diǎn)而進(jìn)行解題的思維方式。一般是在一時(shí)找不出解決問(wèn)題的更好途徑（即數(shù)學(xué)上找不到求解公式或規(guī)則）時(shí)，根據(jù)問(wèn)題中的部分條件（約束條件），將所有的可能解的情況列舉出來(lái)，然后一一驗(yàn)證是否符合整個(gè)問(wèn)題的求解要求，而得到問(wèn)題的解。窮舉法求解的問(wèn)題必須滿足兩個(gè)條件：

⑴可預(yù)先確定每個(gè)狀態(tài)的元素個(gè)數(shù)n；⑵狀態(tài)元素a1，a2，…，an的可能值為一個(gè)連續(xù)的值域。

設(shè)ai1—狀態(tài)元素ai的最小值；aik—狀態(tài)元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdo

foa2←a21toa2kdo……forai←ai1toaikdo……foran←an1toankdoif狀態(tài)(a1，…，ai，…，an)滿足檢驗(yàn)條件then輸出問(wèn)題的解；如何優(yōu)化窮舉算法提高窮舉效率的方法：1、根據(jù)問(wèn)題的實(shí)際需要，將反復(fù)操作部分預(yù)處理掉；2、根據(jù)問(wèn)題的實(shí)際的條件實(shí)施剪枝處理。實(shí)例：阿姆斯特朗數(shù)。問(wèn)題描述：編一個(gè)程序找出所有的三位數(shù)到七位數(shù)中的阿姆斯特朗數(shù)。阿姆斯特朗數(shù)也叫水仙花數(shù),它的定義如下:若一個(gè)n位自然數(shù)的各位數(shù)字的n次方之和等于它本身,則稱這個(gè)自然數(shù)為阿姆斯特朗數(shù)。例如153(153=1*1*1+3*3*3+5*5*5)是一個(gè)三位數(shù)的阿姆斯特朗數(shù),8208則是一個(gè)四位數(shù)的阿姆斯特朗數(shù)。算法分析：為了使得程序盡快運(yùn)行出正確結(jié)果,程序中使用了一個(gè)數(shù)組power存放所有數(shù)字的各次冪之值,power[i,j]等于i的j次方。變量currentnumber存放當(dāng)前要被驗(yàn)證的數(shù),數(shù)組digit存放當(dāng)前數(shù)的各位數(shù)字,開(kāi)始時(shí)digit[3]=1,其它元素均為0,此時(shí)表示當(dāng)前數(shù)為100。highest為當(dāng)前數(shù)的位數(shù)。程序：programex3(input,outoutp);constmaxlen=7;var

i,j,currentnumber,highest,sum,total:longint;

digit:array[0..maxlen+1]ofinteger;

power:array[0..9,0..maxlen]oflongint;begin

fori:=0to9dobeginpower[i,0]:=1;forj:=1tomaxlendo

power[i,j]:=power[i,j-1]*iend;

fori:=1tomaxlendodigit[i]:=0;digit[3]:=1;highest:=3;

currentnumber:=100;total:=0;whiledigit[maxlen+1]=0dobeginsum:=0;fori:=1tohighestdo

sum:=sum+power[digit[i],highest];ifsum=currentnumberthenbegintotal:=total+1;write(currentnumber:maxlen+5);iftotalmod6=0thenwritelnend;digit[1]:=digit[1]+1;

i:=1;whiledigit[i]=10dobegindigit[i+1]:=digit[i+1]+1;

digit[i]:=0;i:=i+1end;ifi>highestthenhighest:=i;

end;

writelnend.currentnumber:=currentnumber+1進(jìn)位

優(yōu)化思路：分解約束條件，將拆分的約束條件嵌套在相應(yīng)的循環(huán)體間，盡可能減少可行解的數(shù)目，也稱為“剪枝”，即把明顯不符合條件的可行解盡可能地剪去，減少窮舉的計(jì)算量。實(shí)例：巧妙填數(shù)。問(wèn)題描述：將1～9這九個(gè)數(shù)字填入九個(gè)空格中。每一橫行的三個(gè)數(shù)字組成一個(gè)三位數(shù)。如果要使第二行的三位數(shù)是第一行的兩倍，第三行的三位數(shù)是第一行的三倍，應(yīng)怎樣填數(shù)。如圖所示。192384576分析：本題目有9個(gè)格子，要求填數(shù)，如果不考慮問(wèn)題給出的條件，共有9！=362880種方案，在這些方案中符合問(wèn)題條件的即為解。因此可以采用窮舉法。但仔細(xì)分析問(wèn)題，顯然第一行的數(shù)不會(huì)超過(guò)400，實(shí)際上只要確定第一行的數(shù)就可以根據(jù)條件算出其他兩行的數(shù)了。這樣僅需窮舉400次。實(shí)例：數(shù)塔問(wèn)題問(wèn)題描述：有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)值的和最接近零。

數(shù)塔用二維數(shù)組記錄

向下嘗試有兩種可能，向左或向右；

用01序列表示路徑，0表示向左，1表示向右上圖的01序列為：01010右圖：路徑的列號(hào)為12233constn=4;typestack=array[0..n]ofinteger;var

i,j,k,sum,min:integer;

s:stack;a:array[1..n,1..n]ofinteger;beginfori:=0tondos[i]:=0;fori:=1tondoforj:=1toidobeginread(a[i,j]);end;min:=maxint;S數(shù)組記錄路徑方向；01序列

while

dobegink:=1;sum:=a[1,1];fori:=1tondobegin

;sum:=sum+a[I,k];end;ifabs(sum)<abs(min)thenmin:=sum;j:=n;while(s[j]=1)doj:=j-1;

;forI:=j+1tondo

;end;end.s[0]=0s[j]:=s[j]+1s[I]:=0k:=k+s[i]K？生成01序列S[0]為1，表示？城市通路在A，B兩個(gè)城市之間設(shè)有N個(gè)路站(如下圖中的S1，且N<100)，城市與路站之間、路站和路站之間各有若干條路段(各路段數(shù)≤20，且每條路段上的距離均為一個(gè)整數(shù))。A，B的一條通路是指：從A出發(fā)，可經(jīng)過(guò)任一路段到達(dá)S1，再?gòu)腟1出發(fā)經(jīng)過(guò)任一路段，…最后到達(dá)B。通路上路段距離之和稱為通路距離(最大距離≤1000)。當(dāng)所有的路段距離給出之后，求出所有不同距離的通路個(gè)數(shù)(相同距離僅記一次)。例如：下圖所示是當(dāng)N=1時(shí)的情況：programroad;

var

i,j,n,s:integer;

b:array[0..100]ofinteger;d:array[0..100,0..20]ofinteger;

g:array[0..1000]of0..1;

begin

readln(n);

fori:=1ton+1do

begin

readln(d[i,0]);

forj:=1tod[i,0]doreadln(d[i,j]);

end;

d[0,0]:=1;

fori:=1ton+1dob[i]:=1;

b[0]:=0;

fori:=0to1000dog[i]:=0;

while

b[0]=0

do

begins:=0;

fori:=1ton+1do

s:=s+d[i,b[i]];

g[s]:=1;j:=n+1;

while

b[j]=d[j,0]

doj:=j-1;

b[j]:=b[j]+1;

fori:=j+1ton+1dob[i]:=1;

end;

s:=0;

fori:=1to1000do

s:=s+g[i]

;

writeln(s);readln;end.不等進(jìn)位近年競(jìng)賽題分析火柴棒等式（noip2008)

問(wèn)題1：火柴棒等式【問(wèn)題描述】

給你n根火柴棍，你可以拼出多少個(gè)形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整數(shù)（若該數(shù)非零，則最高位不能是0）。用火柴棍拼數(shù)字0-9的拼法如圖所示：注意：1.加號(hào)與等號(hào)各自需要兩根火柴棍2.如果A≠B，則A+B=C與B+A=C視為不同的等式（A、B、C>=0）3.n根火柴棍必須全部用上?！据斎搿枯斎胛募atches.in共一行，又一個(gè)整數(shù)n（n<=24）。【輸出】輸出文件matches.out共一行，表示能拼成的不同等式的數(shù)目。問(wèn)題分析：本題選自noip