# noip讲义7-穷举法

var x,y:integer; 枚举所有可能的除数 begin for x:=10 to 99 do begin y:=（ 809*x+1 ）; {计算出被除数} if y>9999 then break;｛优化语句｝ 验证 if （ (y>=1000) and (8*x<=99) and (9*x>=100) then writeln(y,' ',x); end; end. 运行结果： 9709 12

var i,j,s:integer; 枚举123到329之 a:array[1..9] of 0..1; {标记数字j有没有出现} 间的所有三位数 begin for i:=123 to 329 do begin for j:=1 to 9 do a[j]:=0; a[i div 100]:=1; a[i div 10 mod 10]:=1; a[i mod 10]:=1; 分别找出组 a[2*i div 100]:=1; 成这三个三 a[2*i div 10 mod 10]:=1; 位数的9个 a[2*i mod 10]:=1; a[3*i div 100]:=1; 数字。 a[3*i div 10 mod 10]:=1; a[3*i mod 10]:=1; s:=0; for j:=1 to 9 do s:=s+a[j]; 验证 if s=9 then writeln(i:4,2*i:4,3*i:4); end; end.

b1 b2 b5 b3 b6 b4 b7

b8

const link:array[1..6,1..2] of integer=((1,2),(1,4),(2,5),(4,7),(5,8),(7,8)); var b:array[1..8] of integer;{存放摆放方案} procedure print; {输出一种满足条件的放法} begin writeln(b[1]:4); writeln(b[2]:2,b[3]:2,b[4]:2); writeln(b[5]:2,b[6]:2,b[7]:2); writeln(b[8]:4); writeln; end; function choose:boolean; {检验当前放法是否符合要求} var i:integer; begin choose:=false; for i:=1 to 6 do if abs( b[link[i,1]] - b[link[i,2]] )=1 then exit; choose:=true; end;

procedure try; begin for b[2]:=3 to 6 do {枚举b[2]，b[4]，b[5]，计算b[7]} for b[4]:=3 to 6 do if b[2]<>b[4] then for b[5]:=3 to 6 do if (b[5]<>b[2])and(b[5]<>b[4]) then begin b[7]:=18-b[2]-b[4]-b[5]; if choose then print; end; end; begin b[1]:=2; b[3]:=8; b[6]:=1; b[8]:=7;{情况一} try； b[1]:=7; b[3]:=1; b[6]:=8; b[8]:=2;{情况二} try； readln; end.

var a,b,c,d,e,f,g,h,i,p,ans:integer; s:set of 1..9;{s是一个集合类型变量} begin readln(p); ans:=0; for a:=1 to 7 do {枚举a、 f，计算i} for f:=a+1 to 8 do begin s:=[1..9]; i:=3*p-45-a-f; if i>f then begin s:=s-[a,f,i]; for b:=1 to 8 do if ( b in s ) and (( p-a-b-f ) in s ) and ( p-a-b-f>b ) then for g:=1 to 8 do if ( g in s ) and (( p-f-g-i ) in s ) and ( p-f-g-i>g ) then for c:=1 to 8 do if ( c in s ) and (( p-a-c-i ) in s ) and ( p-a-c-i>c )

then begin 输入：20 d:=p-a-b-f; 输出：6 h:=p-f-g-i; e:=p-a-c-i; s:=s-[b,d,g,h,e,c]; 验证 if s=[] then ans:=ans+1; s:=[1..9]-[a,f,i]; end; end; end; writeln(ans);{输出方案总数} end.

var i,m,n,r,s:longint; a:array[1..100] of longint;{保存-R进制数} begin readln(n,r); r:=-r; m:=1;{记录位数} for i:=1 to 100 do a[i]:=0; a[1]:=-1; repeat a[1]:=a[1]+1 ;{从0开始逐一穷举-R进制数} i:=1; {处理进位} while a[i]=r do begin a[i]:=0; i:=i+1; a[i]:=a[i]+1 end; if i>=m then m:=i;{修正位数} s:=0; for i:=m downto 1 do s:=s*(-r)+a[i]{算出对应的十进制数} until n=s; for i:=m downto 1 do if a[i]<=9 then write(a[i]) else write(chr(a[i]+55)); end.

const maxn=64; var a:array[1..maxn,1..maxn] of boolean; b:array[1..maxn] of boolean; n,d,i,j:integer; begin readln(n); n:=round(exp(ln(2)*n)); {求2n} fillchar(a,sizeof(a),0); for d:=1 to n-1 do {枚举每一天} begin fillchar(b,sizeof(b),0); write(‘(’,d,‘)’);｛输出天数｝ for i:=1 to n do ｛枚举每一球队｝ if not b[i] then begin｛若在第d天还未安排比赛｝ b[i]:=true; {则为其安排比赛} write(i); 在这天还未参加比赛过的其它球队 for j:=1 to n do 中找一个还未曾与i比赛过的球队j if not b[j] and not a[i,j] then break; write(‘==’,j,‘ ’);{i与j比赛} b[j]:=true; a[i,j]:=true; a[j,i]:=true end; writeln end end.

8 6 b[0] 0 0 0 0 0 0 0 0 0 0 0 0 1 b[1] 1 1 1 1 1 1 2 2 2 2 2 2 1

4 5 7 b[2] 1 1 2 2 3 3 1 1 2 2 3 3 1

3 4

D[1，0]=2, D[1，1]=8, D[1，2]=6 D[2，0]=3, D[2，1]=4, D[2，2]=5，D[2，3]=7 D[3，0]=2, D[3，1]=3, D[3，2]=4

b[3] 1 2 1 2 1 2 1 2 1 2 1 2 1

8+4+3=15 8+4+4=16 8+5+3=16 8+5+4=17 8+7+3=18 8+7+4=19 6+4+3=13 6+4+4=14 6+5+3=14 6+5+4=15 6+7+3=16 6+7+4=17 穷举结束

g[15]=1 g[16]=1 g[16]=1 g[17]=1 g[18]=1 g[19]=1 g[13]=1 g[14]=1 g[14]=1 g[15]=1 g[16]=1 g[17]=1

var 穷举用 i,j,n,s:integer; while( b[0]<>1)do 求当前通 路的距离 b:array[0..100] of integer; begin d:array[0..100,0..20] of integer; s:=0; g:array[0..1000] of 0..1; for i:=1 to n+1 do begin s:=( s+d[ i , b[i] ] ); readln(n); g[s]:=1; 产生一种 作记录 for i:=1 to n+1 do j:=n+1; 新的方案 begin while( b[j]=d[j,0] )do j:=j-1; readln(d[i,0]); b[j]:=b[j]+1; for j:=1 to d[i,0] do for i:=j+1 to n+1 do b[i]:=1; read(d[i,j]); end; end; s:=0; 循环开关 d[0,0]:=1; for i:=1 to 1000 do( s:=s+g[i] ); for i:=1 to n+1 do b[i]:=1; writeln(s); 统计不同的 b[0]:=0; readln; 通路条数 for i:=1 to 1000 do g[i]:=0; end.

0 0 0 0 0 a[6]

a[27] 1 1 1 1 1

1000000000000000000000 1000000000000000000001 1000000000000000000010 1000000000000000000011 1000000000000000000100 1000000000000000000101 1000000000000000000110 1000000000000000000111 1000000000000000001000 1000000000000000001001 1000000000000000001010

while ( p=1 ) do var begin a:array[1..36] of 0..1; 循环开关 j:=27 b:array[0..31] of integer; while a[j]=1 do j:=j-1; i,j,k,s,p:integer; 产生一种 ( a[j]:=1 ) begin 新的方案 for i:=j+1 to 27 do ( a[i]:=0 ) for i:=1 to 36 do a[i]:=0; for i:=0 to 31 do b[i]:=0; for i:=28 to 32 do a[i]:=1; for i:=1 to 32 do 转化为10 p:=1; begin a[6]:=1; 进制数 ( s:=0 ) S=0*2+1=1 for k:=i to i+4 do S=1*2+1=3

11011

S=3*2+0=6 S=6*2+1=13 S=13*2+1=27

for i:=1 to 32 do for j:=i to i+4 do write(a[j]); writeln end.

s:=s*2+a[k]; 作记录 ( b[s]:=1 ) end; 统计个数 s:=0; for i:=0 to 31 do s:=s+b[i]; if ( s=32 ) then p:=0 end;

P=(S1-S2)2+(S1一S3)2+……+(S1-Sk)2+(s2-s3)2+……+(Sk-1-Sk)2

var i,j,n,k : integer; 打擂台 a :array [1..100] of integer; b,d:array [0..100] of integer; s :array[1..30] of integer; begin readln(n,k); for i:=1 to n do read(a[i]); 分组初 始化 for i:=0 to n do b[i]:=1; cmin:=1000000; 循环开关 while (b[0]=1) do begin for i:=1 to k do ( s[i]:=0 );
for i:=1 to n do( s[b[i]]:=s[b[i]]+a[i] );

if( cmin>sum )then

begin
cmin:=sum;
for i:=1 to n do d[i]:=b[i];

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

while( b[j]=k )j:=j-1;
for i:=j+1 to n do( b[i]:=1) end; writeln(cmin); for i:=1 to n write(d[i]:40);

sum:=0; for i:=1 to k-1 do for j:=( i+1 to k do )
sum:=sum+(s[i]-s[j])*(s[i]-s[j]);

end.

a[1..k,1..n]记录k个地区对物品的要求,其中: a[i,j]=1表示第i个地区对第j种物品是需要的 a[i,j]=0表示第i个地区对第j种物品是无所谓的 a[i,j]=-1表示第i个地区对第j种物品是不需要的

var
i, j ,k, n :integer; p:boolean;

while( p and (b[0]=0) )do

begin
j:=n; while b[j]=1 do j:=j-1;

b :array [0..20] of 0..1;
a :array[1..20,1..10]d integer; begin

( b[j]:=1 ); for i:=j+1 to n do b[i]:=0; p:=false ); ( for i:=1 to k do

readln(n,k);
begin

for j :=1 to n do (a[i,j]=-1)and(b[j]=1) if(a[i,j]=1)and(b[j]=0)or( )
then p:=true;

for j:=1 to n do read(a[i,j]);
readln;

end; if( p )then writeln('找不到!‘)
else for i:=1 to n do if (b[i]=1) then writeln('物质',i,’需要') else writeln('物质',i,'不需要'); end.

end;
for i:=0 to n do b[i]:=0; p:=true;

a[0] 0 0 0 0 1

a[1] 1 1 1 2 2

a[2] 2 2 3 3 3

a[3] 3 4 4 4 4

12 19 12 19

②判断一个整数是否为素数 判断一个整数s是否为素数最简单的方法就是试除法。即 y=trunc(sqrt(s))，然后用2,3,…,y去试除,当有一个除尽时，即非素数， 否则为素数。由于在此题中1<=xi<=5000000，n<=20，所以有些数据在运行 时可能会超时。 如何加快速度？可以从判断素数这个地方着手。 我们可以预先将2…10000之间的素数（共1229个）全部计算出来，存储 到数组中。然后看其中是否存在一个素数a(<=sqrt(s))是s的约数，如果不存 在，该数就为素数。此法可大大加快速度。

var n,k,j,i:integer;

sum,total:longint;
x:array[1 .. 20] of longint;{存储原始数列} a:array[0 .. 20] of integer;{记录各组合中各数在原数列中的位置 }

p:array[1 .. 1229] of integer;{存储10000以内的素数，共1229个}

procedure get_prime； var i,j,s:integer; f:array[1..10000] of 0..1; begin s:=0; f[1]:=0; for i:= 2 to 10000 do f[i]:=1; for i:= 2 to 100 do if f[i]=1 then begin s:=s+1; p[s]:=i; j:=2*i; while j<=10000 do begin f[j]:=0; j:=j+i; end; end;

function fit(sum:longint):boolean; {判断k个整数之和是否为素数} var max,m:integer; begin max:=trunc(sqrt(sum))+1; m:=1;
while(sum mod p[m]<>0)and(p[m]<max) do

m:=m+1; if p[m]>=max then fit:=true else fit:=false; end;

function tj(n,k:integer):longint; var total:longint; 产生第一种组合, begin a[0]=0是循环开关 total:=0; for i:=0 to k do a[i]:=i; while( a[0]=0 )do begin sum:=0; for i:=1 to k do sum:=( sum+x[a[i]] ); if( fit(sum) )then total:=total+1; 产生 j:=k; 一种 while( a[j]=n-k+j )do j:=j-1; 新的 a[j]:=a[j]+1; 组合 for i:=j+1 to k do( a[i]:=a[i-1]+1 ); end; tj:=total; end; begin get_prime; {用筛选法建立10000以内的素数集合} readln(n,k); for i:=1 to n do read(x[i]); total:=tj(n,k); writeln(total); end.

【问题描述】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自 己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间 需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今 天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限 定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5 表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数 元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价 格与重要度的乘积的总和最大。 设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编 号依次为j1，j2，……，jk，则所求的总和为： v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk] 请你帮助金明设计一个满足要求的购物单。

【输入文件】 输入文件happy.in 的第1行，为两个正整数，用一个空格隔开： N m（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。） 从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有 2个非负整数v p（其中v表示该物品的价格(v<=10000)，p表示该物品的重 要度(1~5)） 【输出文件】 输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与 重要度乘积的总和的最大值（<100000000）。 【输入样例】 1000 5 800 2 400 5 300 5 400 3 200 2 【输出样例】 3900

var v,p:array[1..25] of integer; b:array[0..25] of 0..1; n,m,i,j,max,s,yu,l:longint; begin readln(n,m); for i:=1 to m do readln(v[i],p[i]); for i:=0 to m do b[i]:=0; while b[0]=0 do begin j:=m; while b[j]=1 do j:=j-1; b[j]:=1;
for l:= j+1 to m do b[l]:=0;

s:=0; yu:=0; for i:=1 to m do if (b[i]=1) then begin yu:=yu+v[i]; s:=s+v[i]*p[i]; end; if (yu<=n)and (s>max) then max:=s; end; writeln(max); end.

noip讲义7-穷举法_图文.ppt
noip讲义7-穷举法 - 穷举法 在程序设计中, 在程序设计中,我们经常需要根
NOIP培训1.ppt
7页 免费 noip讲义5-递归法 20页 免费 noip讲义7-穷举法 33页
noip讲义6-回溯法.ppt
noip讲义4-递推法 noip讲义5-递归法 noip讲义7-穷举法 noip
noip讲义2-归纳法.ppt
noip讲义4-递推法 noip讲义5-递归法 noip讲义6-回溯法 noip讲义7-穷举法 noip...归纳法归纳法是由一系列有限的特殊事例得出一般规律的推理方法。 例如、求前n个...
noip讲义2递推法_图文.ppt
noip讲义2递推法 - 递推法 所谓递推,是指从已知的初始条件出发,依据某种递

NOIP普及组复赛辅导-枚举专题.doc

NOIP名校讲义.doc
NOIP名校讲义 - 程序设计资料(一) 数据类型:定义运算符函数 整型数:in
noip讲义4-递推法.ppt(小学程度)_图文.ppt
noip讲义4-递推法.ppt(小学程度) - 递推法 所谓递推,是指从已知的初

noip高精度运算讲义_图文.ppt
noip高精度运算讲义 - 高精度运算 由于待处理的数据超过了任何一种数据类型所

Lazarus讲义7(数组二).doc
Lazarus讲义7(数组二) - 第七课 数组(二) 7.2 二维数组: 一、
noip讲义5-递归法(小学程度)_图文.ppt
noip讲义5-递归法(小学程度) - 递归 如果函数体或过程体中出现调用其自
noip讲义2-归纳法_图文.ppt
noip讲义2-归纳法 - 归纳法 归纳法是由一系列有限的特殊事例得出一般规律的

NOIP初赛复习14基本算法思想.doc
NOIP 初赛复习 14 基本算法思想一个程序往往要包含...枚举枚举法,又称穷举法,或称为暴力破解法,是一种...6、预处理找到大体搜索翻译; 7、改写成 IDA*算法。...
day1数学方法-曹立国-noip培训_图文.ppt

NOIP复赛题集.doc