主题:什么叫穷举!
hmx0979
[专家分:160] 发布于 2006-02-15 13:18:00
什么叫穷举?怎么用?举个例子讲解一下,谢谢了
回复列表 (共21个回复)
沙发
为啥学编程 [专家分:150] 发布于 2006-02-15 18:35:00
n := 9;
for i := 0 to n do
for j := 0 to n do
for k := 0 to n do
if (i<>j) and (i<>k) then
write(i,j,k);
三位0-9数字密码字典
这就是穷举~~~~
板凳
hmx0979 [专家分:160] 发布于 2006-02-15 19:06:00
这个是简单的穷举,复杂一点的呢
3 楼
lmj9201 [专家分:1400] 发布于 2006-02-15 21:45:00
1、穷举搜索法
从可能的集合A中一一列举各元素,找出能使命题成立的即为其解的集合B。
适用对象:是一种虽繁琐却极为有效的方法。
它的循环次数一定不能成指数增长。(注:例如 2^n当n---n+1时,次数增加了2^n次。)
特点:方法简单,工作量很大。
4 楼
lmj9201 [专家分:1400] 发布于 2006-02-15 21:45:00
例1:百鸡问题:公鸡每只5元钱,母鸡每只3元钱,小鸡3只1元钱。用100元钱买100只鸡,问公鸡、母鸡和小鸡各几只?
Pascal程序:
program chick;
var x,y,z:integer;
begin for x:=1 to 19 do
for y:=1 to 32 do
begin
z:=100-x-y;
if 5*x+3*y+z/3=100 then
writeln('x=',x,' y=',y,' z=',z);
end;
end.
这个程序看似简单,但是其中还是有值得考虑的地方。应该把公鸡的数目放在循环的最外层,即循环次数少的放在外层,多的放在内层。最后小鸡的数目用 100-公鸡数-母鸡数 得到。另外还可以设置一些砍枝条件,如公鸡数只可能是1-19,不可能超过19,这样循环次数就可以减少,提高效率。枚举法的适用范围很广,程序很容易编,如果配合一些适宜的砍枝条件,也不失为一种解决问题的好方法。
例2:有4个学生,上地理课时提出我国四大淡水湖的排序如下:
甲:洞庭湖最大,洪泽湖最小,鄱阳湖第三;
乙:洪泽湖最大,洞庭湖最小,鄱阳湖第二,太湖第三;
丙:洪泽湖最小,洞庭湖第三;
丁:鄱阳湖最大,太湖最小,洪泽湖第三,洞庭湖第三;
对于各个湖泊应处的地位,每个人只说对了一个。
根据以上情况,编一个程序,让计算机判断各个湖泊应处在第几位。
Pascal程序:
program lake;
var
k,d,h,b,t:integer;
begin
k:=0;
for d:=1 to 4 do
for h:=1 to 4 do
begin
if h<>d then for b:=1 to 4 do
begin
if ((b<>h) and (b<>d)) then
begin
t:=10-d-h-b;
if ord(d=1)+ord(h=4)+ord(b=3)=1 then
begin
if ord(h=1)+ord(d=4)+ord(b=2)+ord(t=3)=1 then
if ord(h=4)+ord(d=3)=1 then
if ord(b=1)+ord(t=4)+ord(h=2)+ord(d=3)=1 then
begin
writeln('dth=',d);
writeln('hzh=',h);
writeln('byh=',b);
writeln('th=',t);
end;
end
else writeln('false');
end;
end;
end;
end.
编这种题目的程序主要就是用n层循环。这类题目的难点是如何把已知的条件转化成计算机能理解的逻辑表达式。
5 楼
lmj9201 [专家分:1400] 发布于 2006-02-15 21:46:00
别处贴来的,加个分,谢了
6 楼
hmx0979 [专家分:160] 发布于 2006-02-15 22:05:00
谢谢你
7 楼
贺天行宝 [专家分:2300] 发布于 2006-02-16 20:22:00
我。。。。。。
穷举又叫深搜吧?
例1-1-1 有A、B、C、D、E五个人,安排值周一、周二、周三、周四、周五的班,每人值一天,共有多少种不同的安排,编程打印输出各种安排。(排列问题)
var
a,b,c,d,e : byte;
n : word;
begin
n := 0;
for a := 1 to 5 do
for b := 1 to 5 do
if a <> b then
for c := 1 to 5 do
if (a <> c) and (b <> c) then
for d := 1 to 5 do
if (a <> d) and (b <> d) and (c <> d) then begin
e := 15-a-b-c-d;
n := n+1;
writeln('No.',n:2,' :',' A : ',a,' B : ',b,' C : ',c,
' D : ',d,' E : ',e);
if n mod 24 = 0 then readln;
end;
end.
例1-1-2 在 红、黄、蓝、黑、白 五种颜色的五个彩球中,取出三个彩球的各种取法共有多少种,编程打印输出各种取法。(组合问题)
const
s : array[1..5] of string = ('Red ','Yellow','Blue ','Black ','White ');
var
i,j,k,n : byte;
begin
n := 0;
for i := 1 to 3 do
for j := i+1 to 4 do
for k := j+1 to 5 do begin
n := n+1;
writeln('No.',n:2,' : ',s[i]:8,s[j]:8,s[k]:8);
end;
readln;
end.
例1-1-3 在如图所示的圆圈中,不重复地填入数字1、2、3、4、5、6。要求每条边上三个数之和都相同,编程打印输出各种填法。(排列问题)
var
s,n,a,b,c,d,e,f : integer;
begin
n := 0;
for a := 1 to 6 do
for b := 1 to 6 do
if b <> a then
for c := 1 to 6 do
if (c <> a) and (c <> b) then
for d := 1 to 6 do
if (d <> a) and (d <> b) and (d <> c) then
for e := 1 to 6 do
if (e <> a) and (e <> b) and (e <> c) and (e <> d) then
begin
f := 21-a-b-c-d-e;
s := a+b+c;
if (c+d+e = s) and (a+f+e = s) then begin
n := n+1;
writeln('No.',n:2,' : ',a:4);
writeln(b:10,f:4);
writeln(c:8,d:4,e:4);
readln;
end;
end;
end.
呵呵,看看教程把
8 楼
lmj9201 [专家分:1400] 发布于 2006-02-16 22:08:00
贺天行宝
你敲这么道例题不累啊
9 楼
贺天行宝 [专家分:2300] 发布于 2006-02-17 20:08:00
不累,我复制的,那老师才敲得累......
10 楼
lmj9201 [专家分:1400] 发布于 2006-02-18 09:16:00
晕
我来回复