数学研发论坛

 找回密码
 欢迎注册
查看: 753|回复: 6

[提问] 求可得到的最大正整数

[复制链接]
发表于 2018-8-1 20:09:57 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
`A`、`B`是两个有限数集,定义`A+B`为遍历`A`、`B`所得二元和之集。

构造含有`k`个不同正整数的集`S=\{0, s_1, s_2, …,s_k\}`,使得`S+S+S`可覆盖尽可能长的自然数前段`\{1, 2, 3, …,n\}`。

当`k=10`时,求最大的的正整数`n`.


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-8-3 00:56:48 | 显示全部楼层
如果k=3,按3位2进数最大能覆盖到7。
如果k=4,可以写程序(用的python,请自行脑补缩进)

  1. for i1 in range(15):
  2.   for i2 in range(i1,15):
  3.    for i3 in range(i2,15):
  4.     for i4 in range(i3,15):
  5.      if set([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])<set([i1,i2,i3,i4,i1+i2,i1+i3,i1+i4,i2+i3,i2+i4,i3+i4,i1+i2+i3,i1+i2+i4,i1+i3+i4,i2+i3+i4]):
  6.       print([i1,i2,i3,i4])
复制代码

没结果,而[1,2,4,8]可以覆盖到14
于是可以构造出[1,2,4,8,15,23,30,37,44,51],这一列数能覆盖到57
当然57应该是可以改进的

暴力搜索可以得到:
[1,2,4,7,14]可以覆盖到23
[1, 2, 3, 6, 10, 20]
[1, 2, 4, 7, 14, 24]这两组都可以覆盖到33

然后,用后面那个解法我们可以拿[1,2,4,7,14,24,34,44,54,64]覆盖到73
不确定73是否可以改进,大概率可以
比如用[1, 2, 3, 6, 10, 20,34,...]

或许[1,2,3,6,10,16,26,40,54,74]可以覆盖到87
[1, 2, 3, 6, 10, 20,34,48,62,76]可以覆盖到89
[1,2,3,6,10,14,28,46,64,82]可以覆盖到99
python:

  1. res=[0]
  2. a=[1,2,3,6,10,14,28,46,64,82]
  3. for i in a:
  4.   for j in a:
  5.    for k in a:
  6.     if i<j<k:
  7.      res+=[i,j,k,i+j,i+k,j+k,i+j+k]

  8. for k in range(1+len(set(res))):
  9.   if not (set(range(k+1))<=set(res)):
  10.    print(k)
  11.    break
复制代码
用贪心算法凑出来的都不是最好的,反而是在前面稍微减一点之后,在后面会得到一个更大的结果

无论如何,坑已挖好,就等大神了:)

点评

谢谢.·.·. !  发表于 2018-8-4 22:17
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-8-4 20:08:20 | 显示全部楼层
M10验证
  1. Plus @@@ Subsets[{1, 2, 3, 6, 10, 14, 28, 46, 64, 82}, {1, 3}] // Union
  2. LengthWhile[%, %[[#]] == # &]
复制代码

输出:
Out[1]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87,88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 102, 106, 110, 111, 112, 113, 116, 120, 124, 128, 129, 130, 131, 134, 138, 142, 146, 147, 148, 149, 152, 156, 160, 174, 192}
Out[2]=99

点评

谢谢hujunhua!  发表于 2018-8-4 22:16
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-8-9 13:27:48 | 显示全部楼层

点评

谢谢mathe!  发表于 2018-8-9 13:44
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-6-27 07:52 , Processed in 0.066214 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表