信息奥赛-穷举

穷举

OicqPassOver这个工具可以用来探测QQ的口令，它根据机器性能最高可以每秒测试20000个口令，如果口令简单，一分钟内，密码就会遭到破译。这些密码破译软件通常就是用的穷举算法。穷举的策略应该是直接基于计算机特点而使用的思维方法，在一时找不到解决问题的更好途径（比如数学公式或规律规则）时，可以根据问题中的部分（约束）条件，将可能解的情况列举出来，然后一一验证是否符合整个问题的求解要求。

实例：编一个程序找出三位数到七位数中所有的阿姆斯特朗数。阿姆斯特朗数也叫水仙花数,它的定义如下:若一个n位自然数的各位数字的n次方之和等于它本身,则称这个自然数为阿姆斯特朗数。例如153(153=1*1*1+3*3*3+5*5*5)是一个三位数的阿姆斯特朗数,8208则是一个四位数的阿姆斯特朗数。算法描述：forI:=100to9999999dobegin

验证是否是阿姆斯特朗数，若是则输出；

end;钞票换硬币

把一元钞票换成一分、二分、五分硬币（每种至少一枚），有哪些种换法？461种

var

i,j,k,total:integer;begintotal:=0;{总数设为０}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);{总数加１}end;

writeln(total);

readln;end.百钱买百鸡【题目】一只公鸡值５元，一只母鸡值３元，３只小鸡值１元，现用一百元要买一百只鸡。问有什么方案？

这是一个古典数学问题，设一百只鸡中公鸡、母鸡、小鸡分别为x，y，z，问题化为三元一次方程组：

这里x,y,z为正整数，且z是3的倍数；由于鸡和钱的总数都是100，可以确定x,y,z的取值范围：

1)x的取值范围为1～20

2)y的取值范围为1～33

3)z的取值范围为3～99，步长为3

对于这个问题我们可以用穷举的方法，遍历x,y,z的所有可能组合，最后得到问题的解。

下式算式中不同的字母代表不同的数字，编程打印出下列算式A+BC+DEF=GHIJ可以确定d=9,g=1,h=0.分书问题

有Ａ、Ｂ、Ｃ、Ｄ、Ｅ五本书，要分给张、王、刘、赵、钱五位同学，每人只能选一本,事先让每人把自己喜爱的书法填于右表，编程找出让每人都满意的方案。

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.

实例：砝码称重（NOIPT96-4）设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），输出用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。算法分析：最容易想到的方法就是枚举出有几个1g，几个2g，几个3g……几个20g，然后统计有几种不同的重量。用数组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砝码所能取到的最大个数a2表示2g砝码所能取到的最大个数a3表示3g砝码所能取到的最大个数……完全数

古希腊人认为因子的和等于它本身的数是一个完全数（自身因子除外），例如28的因子是1、2、4、7、14，且1+2+4+7+14=28，则28是一个完全数，编写一个程序求2～1000内的所有完全数。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.穷举法的优点：⑴由于穷举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；⑵由于穷举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。穷举法的缺点：穷举算法的效率取决于穷举状态的数量以及单个状态穷举的代价，因此效率比较低。

实例：有形如：ax3+bx2+cx+d=0

这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d

均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。样例输入：1

-5

-4

20输出：-2.00

2.00

5.00穷举法应用

本题是2001年全国信息学奥林匹克竞赛高中组复赛第一题，如果考虑解方程的话则比较麻烦。我们可以换个角度思考问题，在-100到100之间找三个满足方程的实数，由于穷举时必须用整型变量，题目又要求保留两位小数，我们只需将循环变量扩大100倍即可顺利穷举，最后只要将所求结果再缩小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筛法求素数用筛选法实现求N以内的所有素数(就是质数)。并按每行10个数的形式打印出来.n=25时,用筛选法选素数的过程如下:(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是素数,接着把凡是2的倍数的那些数筛去,过程见步骤(2),其中带有删除线的数就是被筛去的数.接着把凡是3的倍数的那些数筛去,过程见步骤(3).接着把凡是4的倍数的那些数筛去,过程见步骤(4).接着把凡是5的倍数的那些数筛去,过程见步骤(5).这时数列中剩下的未被筛去那些数就都是素数.筛选法找素数的过程实际上是一个去合数的过程,显然所有被去掉的数都是合数,那么上述的筛选步骤到底

要做到第几步才能保证没有合数剩下来呢?沿用前面的质数判断定理,因为任何一个合数一定有一个因子的平方小于等于它本身,所以对任意的n,只要将所有的i(i*i<=n)的倍数筛去,就能保证没有一个合数剩下来.如n=25时,筛去5的倍数后就不用再往下做了.为了实现以上算法我们首先可以把2到n这n-1个自然数放在一个数组中,可以用各种方法来表示数组元素中的值已被筛去,例如给数组元素置0或负数.筛法求素数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.实例：4皇后问题。问题描述：在4×4的棋盘上安置4个皇后，要求任意两个皇后不在同一行、不在同一列、不在同一对角线上，输出所有的方案。实例三：4皇后问题。问题描述：在4×4的棋盘上安置4个皇后，要求任意两个皇后不在同一行、不在同一列、不在同一对角线上，输出所有的方案。S[1]:第一行皇后的列号S[2]:第二行皇后的列号……4皇后问题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所有可能的列号序列的情况：这就是1到4的全排列!排列输入整数n，按字典序从小到大的顺序输出前n个数的所有全排列。两个序列的字典序大小关系等价于从头开始的第一个不相同位置处的大小关系。例如(1,3,2)<(2,1,3),字典序最小的排列是（1，2，3，4，…，n），最大的排列是（n，n-1，n-2，…，1）。n=3时，所有排列的排序结果是：（1，2，3）、（1，3，2）、（2，1，3）（2，3，1）、（3，1，2）、（3，2，1）全排列的生成算法1~n个数全排列的总数为n！构造法生成从123……n到n……321的全排列求12543的下一个排列：132451.从右到左找到一个数比右边的数小，我们称为A；(例?)2.从右到左找到第一个数比A大，我们成为B；(?)3.A和B交换；4.将原先A所在位置右边的数倒序。全排列的生成算法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个同学，从中选出n个人参加文娱演出，没有顺序，请给出所有的情况。

思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标代表的数被选中，为0则没选中。

1.首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。

2.然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。

3.当第一个“1”移动到数组的m-n+1的位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。

例如求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

穷举法是基于计算机特点而进行解题的思维方式。一般是在一时找不出解决问题的更好途径（即数学上找不到求解公式或规则）时，根据问题中的部分条件（约束条件），将所有的可能解的情况列举出来，然后一一验证是否符合整个问题的求解要求，而得到问题的解。穷举法求解的问题必须满足两个条件：

⑴可预先确定每个状态的元素个数n；⑵状态元素a1，a2，…，an的可能值为一个连续的值域。

设ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdo

foa2←a21toa2kdo……forai←ai1toaikdo……foran←an1toankdoif状态(a1，…，ai，…，an)满足检验条件then输出问题的解；如何优化穷举算法提高穷举效率的方法：1、根据问题的实际需要，将反复操作部分预处理掉；2、根据问题的实际的条件实施剪枝处理。实例：阿姆斯特朗数。问题描述：编一个程序找出所有的三位数到七位数中的阿姆斯特朗数。阿姆斯特朗数也叫水仙花数,它的定义如下:若一个n位自然数的各位数字的n次方之和等于它本身,则称这个自然数为阿姆斯特朗数。例如153(153=1*1*1+3*3*3+5*5*5)是一个三位数的阿姆斯特朗数,8208则是一个四位数的阿姆斯特朗数。算法分析：为了使得程序尽快运行出正确结果,程序中使用了一个数组power存放所有数字的各次幂之值,power[i,j]等于i的j次方。变量currentnumber存放当前要被验证的数,数组digit存放当前数的各位数字,开始时digit[3]=1,其它元素均为0,此时表示当前数为100。highest为当前数的位数。程序：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进位

优化思路：分解约束条件，将拆分的约束条件嵌套在相应的循环体间，尽可能减少可行解的数目，也称为“剪枝”，即把明显不符合条件的可行解尽可能地剪去，减少穷举的计算量。实例：巧妙填数。问题描述：将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍，第三行的三位数是第一行的三倍，应怎样填数。如图所示。192384576分析：本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用穷举法。但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需穷举400次。实例：数塔问题问题描述：有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值的和最接近零。

数塔用二维数组记录

向下尝试有两种可能，向左或向右；

用01序列表示路径，0表示向左，1表示向右上图的01序列为：01010右图：路径的列号为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数组记录路径方向；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两个城市之间设有N个路站(如下图中的S1，且N<100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20，且每条路段上的距离均为一个整数)。A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，…最后到达B。通路上路段距离之和称为通路距离(最大距离≤1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。例如：下图所示是当N=1时的情况：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.不等进位近年竞赛题分析火柴棒等式（noip2008)

问题1：火柴棒等式【问题描述】

给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：注意：1.加号与等号各自需要两根火柴棍2.如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）3.n根火柴棍必须全部用上。【输入】输入文件matches.in共一行，又一个整数n（n<=24）。【输出】输出文件matches.out共一行，表示能拼成的不同等式的数目。问题分析：本题选自noip