主题:方联邮票面值设计的难题
ric500
[专家分:0] 发布于 2006-09-23 15:05:00
方联邮票面值设计的难题
如果有一組2*n的郵票,每张邮票面值可自訂。若要使這組邮票能支付1--R的邮资,且郵票不得分開。R最高為多少?
範例1:
1 2
4 6
能支付1--13的邮资。
範例2:
1 2 15
4 6 8
能支付1--36的邮资。
回复列表 (共18个回复)
11 楼
ric500 [专家分:0] 发布于 2006-10-05 21:37:00
下面提供的算法和程序,仅供参考。
设方联的每张邮票面值,按由小到大排列为:1=v(1)<=v(2)<=…<=v(2n),
依次搜索确定面值v(d), d=1,2,…,2n,
其中v(d+1) 搜索区间的下限取为前一个面值v(d),
上限取为由前d个已选定面值的邮票组成的方联(未选定面值视为零)
所给出的最大连续邮资+1。
与按方联的邮票位置顺序来确定每张邮票面值的方法相比,
上述算法充分考虑了方联中各张邮票面值和位置的相关性,从而可以大幅度地减少搜索的次数。
源程序:自动求解1*2,2*2和2*3三种方联邮票的面值
' a Block of Stamps [2*n]
DECLARE SUB work (d%)
DECLARE SUB minmax (n%, a%(), mins%, maxs%)
DEFINT A-Z
DIM SHARED n, a(2, 9), max, ns, nr
DATA 1, 2, 3
DATA 0
DO
READ n: IF n = 0 THEN EXIT DO
PRINT : PRINT "Input: n="; n
FOR i = 1 TO 2: FOR j = 1 TO n: a(i, j) = 0: NEXT j, i
‘ 方联邮票面值清零
ns = 0: nr = 0: max = n * 2
CALL work(1)
PRINT "[total]="; ns; " [maxV]="; max; " [Nrun]="; nr
‘ 输出解的个数、最大连续邮资以及调用子程序work的次数
key$ = INPUT$(1) ‘ 按任意键后继续执行
LOOP
END
(1) 子程序work采用DFS法,依次确定方联的每张邮票面值(由小到大排列)
SUB work (d)
DIM i, j, k, mins, maxs
nr = nr + 1
CALL minmax(n, a(), mins, maxs)
IF d - 1 = n * 2 THEN
IF maxs - 1 >= max THEN
IF maxs - 1 = max THEN ns = ns + 1 ELSE ns = 1
max = maxs - 1
PRINT "max="; max; " a(1:2,1:n)=";
FOR i = 1 TO 2: FOR j = 1 TO n: PRINT a(i, j); : NEXT j, i: PRINT
END IF
ELSE
FOR i = 1 TO 2: FOR j = 1 TO n
IF a(i, j) = 0 THEN
FOR k = mins TO maxs
a(i, j) = k
CALL work(d + 1)
a(i, j) = 0
NEXT k
END IF
NEXT j, i
END IF
END SUB
(2) 子程序minmax(略)
SUB minmax (n, a(), mins, maxs)
入口参数n和 a(1 to 2, 1 to n) 分别表示方联的列数和方联的每张邮票面值。
出口参数mins和maxs 分别表示方联a() 的单张邮票最大面值和方联所不能给出的最小邮资。这里允许邮票面值为零。
例如:当n=3, a()=1,2,0, 4,6,8时,mins=8和maxs=15
当n=3, a()=1,2,15, 4,6,8时,mins=15和maxs=37
END SUB
12 楼
hs3180 [专家分:530] 发布于 2006-10-06 19:36:00
我觉得时间效率上还需要加强,人们不可能用电脑来算N=3吧
所以我们应该从根本上来改变算法,这些剪枝的问题还是在找到一个高效的算法之后再来讨论吧
13 楼
ric500 [专家分:0] 发布于 2006-10-10 10:08:00
提供一个完整的源程序:
' a Block of Stamps [2*n]
DECLARE SUB work (d%)
DECLARE SUB minmax (n%, a%(), mins%, maxs%)
DECLARE SUB count (n%, a%(), maxs%)
DEFINT A-Z
DIM SHARED n, a(2, 9), max, ns
DATA 1, 2, 3
DATA 0
DO
READ n: IF n = 0 THEN EXIT DO
PRINT : PRINT "Input: n="; n
FOR i = 1 TO 2: FOR j = 1 TO n: a(i, j) = 0: NEXT j, i
' 方联邮票面值清零, a(1 to 2, 1 to n)表示方联的各张邮票面值
ns = 0: max = n * 2
CALL work(1)
PRINT "[total]="; ns; " [maxV]="; max
' 输出解的个数ns、最大连续邮资max
key$ = INPUT$(1) ' 按任意键后继续执行
LOOP
END
'(1) 子程序work采用DFS法,依次确定方联的每张邮票面值(由小到大排列)
SUB work (d)
DIM i, j, k, mins, maxs
CALL minmax(n, a(), mins, maxs)
IF d - 1 = n * 2 THEN
IF maxs - 1 >= max THEN
IF maxs - 1 = max THEN ns = ns + 1 ELSE ns = 1
max = maxs - 1
PRINT "max="; max; " a(1:2,1:n)=";
FOR i = 1 TO 2: FOR j = 1 TO n: PRINT a(i, j); : NEXT j, i: PRINT
END IF
ELSE
FOR i = 1 TO 2: FOR j = 1 TO n
IF a(i, j) = 0 THEN
FOR k = mins TO maxs
a(i, j) = k
CALL work(d + 1)
a(i, j) = 0
NEXT k
END IF
NEXT j, i
END IF
END SUB
'(2) 子程序minmax出口参数mins和maxs分别表示方联a()的单张邮票最大面值和
' 方联所不能给出的最小邮资, 这里允许邮票面值为零
SUB minmax (n, a(), mins, maxs)
DIM i, j
mins = 1
FOR i = 1 TO 2: FOR j = 1 TO n
IF a(i, j) > mins THEN mins = a(i, j)
NEXT j, i
CALL count(n, a(), maxs)
END SUB
'(3) 子程序count按递推方式计算一个2*n方联所不能给出的最小邮资
' (即最大连续邮资R+1)
SUB count (n, a(), maxs)
DIM dep, i, j, k, l, s, t(3), old(3), new(3), c(0 TO 1000)
DIM uv(3, 0 TO 1000), uv1(3, 0 TO 1000)
FOR i = 0 TO 1000: c(i) = 0: NEXT i
uv(1, 0) = 0: uv(2, 0) = 0: uv(3, 0) = 0
FOR dep = 1 TO n
t(1) = a(1, dep): t(2) = a(2, dep): t(3) = t(1) + t(2)
FOR i = 1 TO 3: old(i) = uv(i, 0): NEXT i
FOR i = 1 TO 3: FOR j = 1 TO old(i): uv1(i, j) = uv(i, j): NEXT j, i
FOR i = 1 TO 3
l = 0
l = l + 1: uv(i, l) = t(i)
IF i < 3 THEN l = l + 1: uv(i, l) = t(3)
FOR k = 1 TO 3
IF i + k <> 3 THEN
FOR j = 1 TO old(k): l = l + 1: uv(i, l) = t(i) + uv1(k, j): NEXT j
END IF
NEXT k
new(i) = l
NEXT i
FOR i = 1 TO 3: uv(i, 0) = new(i): NEXT i
FOR i = 1 TO 3: FOR j = 1 TO uv(i, 0)
s = uv(i, j): IF s <= 1000 THEN c(s) = 1
NEXT j, i
NEXT dep
FOR i = 1 TO 1000
IF c(i) = 0 THEN maxs = i: EXIT FOR
NEXT i
END SUB
计算结果如下:
Input: n= 1
......
max= 3 a(1:2,1:n)= 1 2
max= 3 a(1:2,1:n)= 2 1
[total]= 2 [maxV]= 3
Input: n= 2
......
max= 13 a(1:2,1:n)= 1 2 4 6
max= 13 a(1:2,1:n)= 1 4 2 6
max= 13 a(1:2,1:n)= 1 3 7 2
max= 13 a(1:2,1:n)= 1 7 3 2
max= 13 a(1:2,1:n)= 2 1 6 4
max= 13 a(1:2,1:n)= 3 1 2 7
max= 13 a(1:2,1:n)= 7 1 2 3
max= 13 a(1:2,1:n)= 4 1 6 2
max= 13 a(1:2,1:n)= 2 6 1 4
max= 13 a(1:2,1:n)= 3 2 1 7
max= 13 a(1:2,1:n)= 7 2 1 3
max= 13 a(1:2,1:n)= 4 6 1 2
max= 13 a(1:2,1:n)= 2 3 7 1
max= 13 a(1:2,1:n)= 2 7 3 1
max= 13 a(1:2,1:n)= 6 2 4 1
max= 13 a(1:2,1:n)= 6 4 2 1
[total]= 16 [maxV]= 13
Input: n= 3
......
max= 36 a(1:2,1:n)= 1 2 15 4 6 8
max= 36 a(1:2,1:n)= 1 3 17 8 2 5
max= 36 a(1:2,1:n)= 15 2 1 8 6 4
max= 36 a(1:2,1:n)= 17 3 1 5 2 8
max= 36 a(1:2,1:n)= 8 2 5 1 3 17
max= 36 a(1:2,1:n)= 4 6 8 1 2 15
max= 36 a(1:2,1:n)= 5 2 8 17 3 1
max= 36 a(1:2,1:n)= 8 6 4 15 2 1
[total]= 8 [maxV]= 36
说明:
1.本程序没有考虑更多的剪枝和优化技巧,也没有考虑解的对称性。
2.类似求解“连续邮资”问题那样,关键在于寻求一种“确定已知面值的邮票方联最大连续邮资R”的高效算法。
3.欢迎对本问题有兴趣的网友,作进一步的探讨。
14 楼
moz [专家分:37620] 发布于 2006-10-21 13:51:00
我没有学过数论,高等数学当时考了60分,但现在已经一点印象都没有了,
也不懂什么叫DFS,不知道什么叫深度搜索,也不明白图树枝的概念,
感觉上应该是一些高等的数学技术一窍不通.
大家别以为我在炫耀,刚好相反,感觉对很多问题力不从心.
明明在你们眼里很简单的技术问题,偏偏我无法凭空想像.
但我已经了无生趣了,在这里也只不过是消消我消极的心情,
这已经是我唯一能做的事情了.
这个问题我作了一个假设(其实这个假设很不安全,经不起验证)
我假设这个数列是固定的,唯一的,可延伸的
然后我就从1426开始延伸下去,
这只是一个模型,其实是可以简单的修改一下,足可以应付n比较小的情况
得数列
1, 2, 15, 23, 38, 107, 329
4, 6, 8, 23, 69, 107, 176
13, 36, 82, 189, 403, 908
程序如下:
declare sub add1 (a%(), b%, c%())
declare sub add2 (l%(), r%(), x%, y%, ll%(), rr%())
declare sub addds (a%(), b%(), c%())
declare sub asks (l%(), r%(), m1%)
declare function locates% (a%(), x%)
defint a-z
dim shared m3, m3l, m3r, m2l, m2r
m3 = 13
m = 100
dim shared l(m), r(m)
for i = 1 to 4: read s(i): next
data 1,4,2,6
for i = 0 to 7: read l(i): next
data 7,2,3,7,8,9,12,13
for i = 0 to 7: read r(i): next
data 7,6,8,9,10,11,12,13
cls
print 1, 4
print 2, 6, 13
do
m2l = 0
m2r = 0
asks l(), r(), m3
print m3l, m3r, m3
add2 l(), r(), m3l, m3r, l(), r()
loop
sub add1 (a(), b, c())
if b = 0 then j = 0 else j = 1
for i = a(0) to 1 step -1
c(i + j) = a(i) + b
next
c(j) = b
c(0) = a(0) + j
end sub
sub add2 (l(), r(), x, y, ll(), rr())
dim l2(l(0) + 1), r2(r(0) + 1), llrr(l(0) + r(0) + 2)
if x > 0 then add1 l(), x + y, l2() else add1 l(), 0, ll()
if y > 0 then add1 r(), x + y, r2() else add1 r(), 0, rr()
addds r2(), l2(), llrr()
add1 l(), x, l2()
add1 r(), y, r2()
if x > 0 then addds l2(), llrr(), ll()
if y > 0 then addds r2(), llrr(), rr()
end sub
sub addds (a(), b(), c()) '三个数组不能同地址调用
i = 1
j = 1
do
if i > a(0) then
for j = j to b(0)
k = k + 1
c(k) = b(j)
next
exit do
elseif j > b(0) then
for i = i to a(0)
k = k + 1
c(k) = a(i)
next
exit do
end if
k = k + 1
if a(i) > b(j) then
c(k) = b(j)
j = j + 1
elseif a(i) < b(j) then
c(k) = a(i)
i = i + 1
elseif a(i) = b(j) then
c(k) = a(i)
i = i + 1
j = j + 1
end if
loop
c(0) = k
end sub
sub asks (l(), r(), m1)
dim z(l(0) * 3 + r(0) * 3 + 6), l2(l(0) * 2 + r(0) + 3), r2(r(0) * 2 + l(0) + 3)
add2 l(), r(), m2l, m2r, l2(), r2()
addds l2(), r2(), z()
m2 = m1
for i1 = 1 to z(0)
if m2 = z(i1) then m2 = m2 + 1 else if m2 < z(i1) then exit for
next
if m2 >= m3 + 1 then
m3 = m2 - 1
m3l = m2l
m3r = m2r
end if
if m2l = 0 then
m2l = m2
asks l(), r(), m2
for i2l = 1 to l(0)
m2l = m2 - l(i2l)
if m2l < 0 then exit for
asks l(), r(), m2 '递归一次
next
m2l = 0
end if
if m2r = 0 then
m2r = m2
asks l(), r(), m2
for i2r = 1 to r(0)
m2r = m2 - r(i2r)
if m2r < 0 then
m2r = 0
exit for
end if
asks l(), r(), m2 '递归一次
next
m2r = 0
end if
'递归返回
end sub
15 楼
moz [专家分:37620] 发布于 2006-10-21 18:00:00
改良了一下,时间很漫长:
1, 2, 15, 23, 38, 107, 329, 505, 834 2387
4, 6, 8, 23, 69, 107, 176, 505, 1553 2387
13, 36, 82, 189, 403, 908, 1918, 4305, 9079
如果有机会的话,还想把数组压缩来加快速度.
DECLARE SUB add1 (a%(), b%, c%())
DECLARE SUB add2 (l%(), r%(), x%, y%, ll%(), rr%())
DECLARE SUB addds (a%(), b%(), c%())
DECLARE SUB Asks (l%(), r%(), m1%)
DEFINT A-Z
DIM SHARED m3, m3l, m3r, m2l, m2r, m4
m3 = 13
m = 10000
DIM SHARED l(m), r(m)
FOR i = 1 TO 4: READ s(i): NEXT
DATA 1,4,2,6
FOR i = 0 TO 7: READ l(i): NEXT
DATA 7,2,3,7,8,9,12,13
FOR i = 0 TO 7: READ r(i): NEXT
DATA 7,6,8,9,10,11,12,13
CLS
PRINT 1, 4
PRINT 2, 6, 13
DO
timer1# = TIMER
m2l = 0
m2r = 0
m4 = m3
Asks l(), r(), m3
LOCATE , 1
PRINT m3l, m3r, m3, TIMER - timer1#
add2 l(), r(), m3l, m3r, l(), r()
LOOP
SUB add1 (a(), b, c())
IF b = 0 THEN j = 0 ELSE j = 1
FOR i = a(0) TO 1 STEP -1
c(i + j) = a(i) + b
NEXT
c(j) = b
c(0) = a(0) + j
END SUB
SUB add2 (l(), r(), x, y, ll(), rr())
DIM l2(l(0) + 1), r2(r(0) + 1), llrr(l(0) + r(0) + 2)
IF x > 0 THEN add1 l(), x + y, l2() ELSE add1 l(), 0, ll()
IF y > 0 THEN add1 r(), x + y, r2() ELSE add1 r(), 0, rr()
addds r2(), l2(), llrr()
add1 l(), x, l2()
add1 r(), y, r2()
IF x > 0 THEN addds l2(), llrr(), ll()
IF y > 0 THEN addds r2(), llrr(), rr()
END SUB
SUB addds (a(), b(), c()) '三个数组不能同地址调用
i = 1
j = 1
DO UNTIL i > a(0) OR j > b(0)
k = k + 1
IF a(i) > b(j) THEN
c(k) = b(j)
j = j + 1
ELSEIF a(i) < b(j) THEN
c(k) = a(i)
i = i + 1
ELSEIF a(i) = b(j) THEN
c(k) = a(i)
i = i + 1
j = j + 1
END IF
LOOP
FOR j = j TO b(0)
k = k + 1
c(k) = b(j)
NEXT
FOR i = i TO a(0)
k = k + 1
c(k) = a(i)
NEXT
c(0) = k
END SUB
SUB Asks (l(), r(), m1)
DIM z(l(0) * 3 + r(0) * 3 + 6), l2(l(0) * 2 + r(0) + 3), r2(r(0) * 2 + l(0) + 3)
add2 l(), r(), m2l, m2r, l2(), r2()
addds l2(), r2(), z()
m2 = m1
FOR i1 = 1 TO z(0)
IF m2 = z(i1) THEN m2 = m2 + 1 ELSE IF m2 < z(i1) THEN EXIT FOR
NEXT
IF m2 >= m3 + 1 THEN
m3 = m2 - 1
m3l = m2l
m3r = m2r
PRINT m3,
END IF
IF m2l = 0 THEN
m2l = m2
DO UNTIL m2l <= 0 OR (m2l > 0 AND m2r > 0 AND m2l + m2r + m4 < m3)
Asks l(), r(), m2
i2l = i2l + 1
IF i2l > l(0) THEN EXIT DO
m2l = m2 - l(i2l)
LOOP
m2l = 0
END IF
IF m2r = 0 THEN
m2r = m2
DO UNTIL m2r <= 0 OR (m2l > 0 AND m2r > 0 AND m2l + m2r + m4 < m3)
Asks l(), r(), m2
i2r = i2r + 1
IF i2r > r(0) THEN EXIT DO
m2r = m2 - r(i2r)
LOOP
m2r = 0
END IF
IF INKEY$ = CHR$(27) THEN SYSTEM
LOCATE , 1
PRINT m2l, m2r,
END SUB
16 楼
ric500 [专家分:0] 发布于 2006-10-25 15:30:00
Moz的计算很精彩!
1, 2, 15, 23, 38, 107, 329, 505, …
4, 6, 8, 23, 69, 107, 176, 505, …
13, 36, 82, 189, 403, 908,1918, …
规律:23=15+8,38=15+23,107=38+69,176=69+107,505=329+176,…
类似的还有:
1, 4, 10, 30, 46, 76, 218, 670, …
2, 6, 10, 16, 46, 142, 218, 360, …
13, 33, 79, 171, 389, 825,1855, …
规律:16=6+10,46=30+16,76=30+46,218=76+142,360=142+218,…
17 楼
moz [专家分:37620] 发布于 2006-10-25 16:13:00
类似的不是最大值的答案,要来没用.
如果按你的规律的话,答案就简单多了.
只是我不知道该用事实来验证命题呢
还是用公理来推论命题.
+----+----\ +----+---\
1 2 15 23 38 107 329 505 834 2387 ****
+__/ +__/ +____/ +___/
+ \ + \ + \ + \
4 6 8 23 69 107 176 505 1553 2387 ****
+---+---/ +----+----/
18 楼
moz [专家分:37620] 发布于 2006-10-25 18:40:00
如果定理成立的话,事情就变得简单了:
n=100
m = n*2
dim s(m) as double
s(1) = 1
s(2) = 4
s(3) = 2
s(4) = 6
s(5) = 15
s(6) = 8
s(0) = 36
for i = 7 to m step 2
if i mod 4 = 3 then
s(i) = s(i - 2) + s(i - 1)
s(i + 1) = s(i)
else
if i mod 8 = 1 then
j1 = i
j2 = i + 1
else
j1 = i + 1
j2 = i
end if
s(j1) = s(j1 - 2) + s(j1 - 4)
s(j2) = s(j1) + s(i - 6) + s(i - 5) + s(i - 4) + s(i - 3)
end if
s(0)=s(0)+s(i)+s(i+1)
print s(i),s(i+1),s(0)
next
我来回复