主题:帮我解出这个题,加分30哦!!!
zhaoren
[专家分:420] 发布于 2005-08-07 11:07:00
[em18]邮票问题:
在一个信封上,最多可贴3张邮票,要你设计4种面值不同的邮票,要能贴出1到R的连续值;
并使R的值达到最大。
[em18][em18][em18][em10][em10][em10]
回复列表 (共6个回复)
沙发
闪电123 [专家分:470] 发布于 2005-08-07 11:28:00
给你个通用的。。。
第一个输入的数是M张,
第二个输入的数是N种。
程序如下:
var
a:array [1..100] of integer;
money:array [1..2550] of integer;
total,n,m,i:integer;
procedure search(k,n,x:integer);
var i:integer;
begin
if (n=0)or(k=0) then exit;
for i:=n downto 0 do
begin
x:=x+a[k]*i;
n:=n-i;
money[x]:=money[x]+1;
search(k-1,n,x);
x:=x-a[k]*i;
n:=n+i;
end
end;
function maxlong:integer;
var j,total,max:integer;
begin
j:=n*a[m];
max:=0;
repeat
while (money[j]=0)and(j>0) do
j:=j-1;
total:=0;
while (money[j]>0)and(j>0) do
begin total:=total+1;j:=j-1 end;
if max<total then max:=total ;
until j<=0;
maxlong:=max
end;
begin
readln(m,n);
for i:=1 to m do read(a[i]);
total:=0;
search(m,n,0);
writeln(maxlong)
end.
回溯算法。。。
板凳
口口and枕头 [专家分:1550] 发布于 2005-08-07 16:14:00
分析:显然,只有4种邮票面值互不相同,才有可能得到最大的R值.
设4种邮票的面值为a<b<c<d.显然a只能取1;b的可能取值在a+1到3a+1之间;c的可能取值在b+1到3b+1之间;d的可能取值在c+1到3c+1之间.
对a,b,c,d的每一种组合,分别计算满足题目要求的R值,其中使R取最大值的那一种组合,即是所求的结果.
可以通过一个四重循环来确定由某个组合a,b,c,d可能得到的R值.设面值为a的邮票可以贴n1张(0<=n1<=3),面值为b的邮票可以贴n2张(0<=n2<=3-n1),面值为c的邮票可以贴n3张(0<=n3<=3-n1-n2),面值为d的邮票可以贴n4张(0<=n4<=3-n1-n2-n3).对满足条件
n1+n2+n3+n4<=3
的每一组n1,n2,n3,n4,计算积之和
sum=n1*a+n2*b+n3*c+n4*d
并将sum加入到集合S中(s初始值为空集).最后,检测1,2,3,...,n是否在集合s中,若n在s中,而n+1不在s中,则R=n.
program ch64;
const m=3; {信封上最多可贴m张邮票}
var a,b,c,d:integer;
R,Q,x1,x2,x3,x4:integer;
function number(a,b,c,d:integer):integer; {确定由面值为a,b,c,d的4种邮票可得到的R值}
var n1,n2,n3,n4,sum,n:integer;
s:set of 1..100;
begin
s:=[ ];
for n1:=0 to m do
for n2:=0 to m-n1 do
for n3:=0 to m-n1-n2 do
for n4:=0 to m-n1-n2-n3 do
if n1+n2+n3+n4<=m {不超过m张}
then begin
sum:=n1*a+n2*b+n3*c+n4*d; {得到一种邮资}
s:=s+[sum]; {放入s集合}
end;
n:=1;
while n in s do n:n+1;
number:=n-1; {返回最大的R值}
end;
begin
a:=1; R:=0;
for b:=a+1 to m*a+1 do
for c:=b+1 to m*b+1 do
for d:=c+1 to m*c+1 do
begin
Q:=number(a,b,c,d);
if Q>R then
begin
R:=Q;
x1:=a;x2:=b;x3:=c;x4:=d;
end;
end;
writeln;
write('4种票面值为:',x1:4,x3:4,x3:4,x4:4);
end.
3 楼
口口and枕头 [专家分:1550] 发布于 2005-08-07 16:14:00
不好意思~这是我以前贴过的~
4 楼
zhaoren [专家分:420] 发布于 2005-08-07 17:12:00
太谢谢了,真是感谢啊,我是新手,做7天做不出,想不到有人一下做出来了,高手啊啊啊
5 楼
口口and枕头 [专家分:1550] 发布于 2005-08-07 18:08:00
这 是书上的例题~呵呵~~
6 楼
zhaoren [专家分:420] 发布于 2005-08-08 18:59:00
晕~[em08]
我来回复