回 帖 发 新 帖 刷新版面

主题:方联邮票面值设计的难题

方联邮票面值设计的难题
如果有一組2*n的郵票,每张邮票面值可自訂。若要使這組邮票能支付1--R的邮资,且郵票不得分開。R最高為多少? 
範例1: 
1    2
4  6
能支付1--13的邮资。
範例2: 
1    2   15
4  6    8
能支付1--36的邮资。

回复列表 (共18个回复)

11 楼


  下面提供的算法和程序,仅供参考。
  设方联的每张邮票面值,按由小到大排列为: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 楼

我觉得时间效率上还需要加强,人们不可能用电脑来算N=3吧

所以我们应该从根本上来改变算法,这些剪枝的问题还是在找到一个高效的算法之后再来讨论吧

13 楼


提供一个完整的源程序:
' 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 楼

我没有学过数论,高等数学当时考了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 楼

改良了一下,时间很漫长:
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 楼


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 楼

类似的不是最大值的答案,要来没用.
如果按你的规律的话,答案就简单多了.
只是我不知道该用事实来验证命题呢
还是用公理来推论命题.
             +----+----\         +----+---\
    1    2   15   23   38  107  329  505  834 2387  ****
              +__/      +__/     +____/    +___/
              +  \      +  \     +    \    +   \
    4    6    8   23   69  107  176  505 1553 2387  ****
                        +---+---/          +----+----/

18 楼

如果定理成立的话,事情就变得简单了:
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

我来回复

您尚未登录,请登录后再回复。点此登录或注册