穷举法2.docx
《穷举法2.docx》由会员分享，可在线阅读，更多相关《穷举法2.docx（10页珍藏版）》请在冰点文库上搜索。
穷举法2
穷举法（排列组合）
1、四人分书
把23本书分给甲、乙、丙、丁4人，要求这四人得到的书的数量分别不得超过9本、8本、7本、6本，问有多少种不同的分法？
并找出每种具体的分法。
（115种）
var
i,j,k,p,s:
longint;
begin
fori:
=1to9do
forj:
=1to8do
fork:
=1to7do
begin
p:
=23-i-j-k;
if（p<=6）and（p>=1）thenbeginwriteln（i,'',j,'',k,'',p）;s:
=s+1;end;
end;
writeln（s）;
end.
2、填数字
将1-6这六个数字分别填到下图中，使三角形每条边上的三个数之和相等，一共有多少种答案，编程打印出来。
（24种）
A
B C
D E F
var
a,b,c,d,e,f,s:
longint;
begin
fora:
=1to6do
forb:
=1to6do
begin
ifa<>bthenbegin
forc:
=1to6do
begin
if（a<>c）and（b<>c）thenbegin
ford:
=1to6do
begin
if（a<>d）and（b<>d）and（c<>d）thenbeginfore:
=1to6do
begin
if（a<>e）and（b<>e）and（c<>e）and（d<>e）thenbegin
f:
=21-a-b-c-d-e;
if（（f<>a）and（f<>b）and（f<>c）and（f<>d）and（f<>e））and（a+c+f=d+e+f）and（d+e+f=a+b+d）and（a+b+d=a+c+f）thens:
=s+1;
end;
end;
end;
end;
end;
end;
end;
end;
writeln（s）;
end.
3、在下列的（）中填上加号或减号，使等式成立，共有多少种填法？
把种填法的式子打印出来？
（11种）
1（）2（）3（）4（）5（）6（）7（）8（）9=9
标程1
var
i,t,s,j:
longint;
b:
array[0..1000]oflongint;
begin
fori:
=0to8do
b[i]:
=0;
whileb[0]=0do
begin
t:
=1;
fori:
=1to8do
begin
ifb[i]=1thent:
=t+i+1;
ifb[i]=0thent:
=t-i-1;
end;
ift=9thens:
=s+1;
j:
=8;
whileb[j]=1do
begin
j:
=j-1;
end;
b[j]:
=1;
fori:
=j+1to8do
b[i]:
=0;
end;
writeln（s）;
end.
标程2
var
ss,s,k,i,ii,j:
longint;
begin
s:
=0;
fori:
=0to255do
begin
ii:
=i;
s:
=1;
forj:
=1to8do
begin
k:
=iishr（j-1）;
ifkmod2=1then
s:
=s-（j+1）
else
s:
=s+（j+1）;
end;
ifs=9thenss:
=ss+1;
end;
writeln（ss）;
end.
4、下式算式中不同的字母代表不同的数字，编程打印出下列算式
A+BC+DEF=GHIJ
varans,s,a,b,c,d,e,f,g,h,i,j,pas:
integer;
v:
array[-10..100]ofinteger;
begin
ans:
=0;
ford:
=8to9do
fore:
=0to9do
forf:
=0to9do
forb:
=0to9do
forc:
=0to9do
fora:
=0to9do
begin
s:
=a+b*10+c+f+e*10+d*100;
ifs>1000then
begin
fori:
=0to9do
v[i]:
=0;
g:
=sdiv1000;
h:
=sdiv100-g*10;
i:
=（sdiv10）mod10;
j:
=smod10;
v[a]:
=1;
v[b]:
=1;
v[c]:
=1;
v[d]:
=1;
v[e]:
=1;
v[f]:
=1;
v[g]:
=1;
v[h]:
=1;
v[i]:
=1;
v[j]:
=1;
s:
=0;
forpas:
=0to9do
s:
=s+v[pas];
ifs=10thenwriteln（a,'+',b,c,'+',d,e,f,'=',g,h,i,j）;
end;
end;
end.
路径二题：
第5题：
如下图所示的数字三角形，请编写一个程序计算从顶到底的某处的一条路径，使该路径的数字和最大，输出路径和最大值。
数据从键盘输入，首先输入总行数（小于20），再按照每行进行数据输入。
如下图的三角形，按如下方式录入：
5，7，3，8，8，1，0，2，7，4，4，4，5，2，6，5。
输出为，路径：
7-3-8-7-5，最大值：
30
7
38
810
2744
45265
var
i,t,s,j,k,m,n,max:
longint;
a:
array[0..120,0..120]oflongint;
b:
array[0..10000]oflongint;
begin
read（n）;
fori:
=1tondo
forj:
=1toido
read（a[i,j]）;
fori:
=0tondo
b[i]:
=0;
max:
=0;
whileb[0]=0do
begin
t:
=a[1,1];j:
=1;
fori:
=1tondo
begin
ifb[i]=1thenj:
=j+1;
ifj>n+1thenj:
=n+1;
ifj<1thenj:
=1;
t:
=t+a[i+1,j];
end;
ift>maxthenmax:
=t;
j:
=n-1;
whileb[j]=1do
begin
j:
=j-1;
end;
b[j]:
=1;
fori:
=j+1tondo
b[i]:
=0;
end;
writeln（max）;
end.
第6题：
一个数字宝塔，从第N层到第M层（最顶层为0，次顶为1，。
。
。
。
，最底层为8），每次只能走到下一层其左边或右边的数字，输入n，M（M<9）,k，求出
1、走到第M层的所有数字和为k的路径
2、一条走到第M层的数字之和最大的途径
输入：
（n，M，k）
0,3,23
输出：
NO1 7-4-6-6
NO2 7-4-9-3
NO3 7-6-3-7
LONG：
7
46
693
6371
25328
594732
6418563
39768415
257357842
var
i,t,s,j,k,m,n,max:
longint;
a:
array[0..120,0..120]oflongint;
b:
array[0..10000]oflongint;
begin
read（m,n,k）;
fori:
=1ton+1do
forj:
=1toido
read（a[i,j]）;
fori:
=0tondo
b[i]:
=0;
max:
=0;
whileb[m]=0do
begin
t:
=a[m+1,1];j:
=1;
fori:
=m+1tondo
begin
ifb[i]=1thenj:
=j+1;
ifj>n+1thenj:
=n+1;
ifj<1thenj:
=1;
t:
=t+a[i+1,j];
end;
ift=kthenbegin
s:
=s+1;
write（'NO',s,''）;
j:
=1;
fori:
=mton-1do
begin
ifb[i]=1thenj:
=j+1;
ifj>n+1thenj:
=n+1;
ifj<1thenj:
=1;
write（a[i+1,j],'-'）;
end;
ifb[n]=1thenj:
=j+1;
ifj>n+1thenj:
=n+1;
ifj<1thenj:
=1;
writeln（a[n+1,j]）;
end;
j:
=n-1;
whileb[j]=1do
begin
j:
=j-1;
end;
b[j]:
=1;
fori:
=j+1tondo
b[i]:
=0;
end;
end.
7.问题描述:
将n个整数分成k组（k≤n,要求每组不能为空）,显然这k个部分均可得到一个各自的和s1,s2,……sk,定义整数P为:
P=（S1-S2）2+（S1一S3）2+……+（S1-Sk）2+（s2-s3）2+……+（Sk-1-Sk）2
问题求解:
求出一种分法,使P为最小（若有多种方案仅记一种〉
升级会员 