一道有趣的数字题目

northwolves

男生女生各1000人，分别编号1-1000.现从1-1000中选取20个数字，比如：

1,2,3,4,5,6,7,14,21,28,35,42,49,56,63,70,77,84,91,98

选出以上编号的男生女生，异性之间的任两人号码相加，可得到400个有重复的数字。在这些数字中，连续数字最多可有多少？如本例最大可得到2-105共104个连续数字。

求选择这20个数字的最佳方案

northwolves

不难推算，

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110---------->可得到  120个l连续数字

有没有更优的方案？

paciguard

留个脚印。。。

yeminqiang

过来围观一下

香川群子

选定20个数之后，检查连续数列这个比较容易一点。

所以，问题核心就在于如何选定20个数的间隔分布。

初步设想，先从较小的数（x<m）中取较少的n个数，模拟后检查是否存在浪费。（多余的数）
扣除多余的数，然后增加一个新的数字，使得该组合得到的连续数列最长……

如此递增计算。

但，这么做的前提是，之前的组合效果可以遗传。

如果最佳效果不能遗传，那么问题就成了需要穷举遍历所有Combin(1000,20)的组合了，
这个是做不到的。

northwolves

香川群子 发表于 2017-7-5 18:43
选定20个数之后，检查连续数列这个比较容易一点。

所以，问题核心就在于如何选定20个数的间隔分布。

我也不确定。最初以为2^n序列要好一些，或者与斐波那契数列http://oeis.org/A000045
或者Rohrbach's problem http://oeis.org/A123509  有关

today0427

不明真相的打酱油群众路过一下……

northwolves

baigangliao 发表于 2017-7-5 19:22
1 2
1 3
1 4

？？？
需要结果中从某数开始的连续数字最长，如本例可得到120个数字：2-121

香川群子

在1楼数列的基础上，检查优化得到最大连续个数=117【2 - 118】

1楼数列：1,2,3,4,5,6,7,14,21,28,35,42,49,56,63,70,77,84,91,98
  优化后：1,2,3,4,5,6,7,14,21,28,35,42,49,56,62,68,74,80,86,92

1. Sub test() 'by kagawa 2017/7/5
   
2.     Dim a&(), b, i&, i2&, k&, n&, n1&, t&, t2&
   
3.     b = [{1,2,3,4,5,6,7,14,21,28,35,42,49,56,63,70,77,84,91,98}] '原始模板
   
4.     For n1 = 2 To 20 '从第2个数开始检查替换
   
5.         ReDim a(1 To 20) '重置数组a
   
6.         For i = 1 To n1
   
7.             a(i) = b(i) '根据模板填写前n1个数
   
8.         Next
   
9. 
   
10.         For n = n1 To 20 '循环检查填后面的数
    
11.             t2 = f(a, n - 1): k = 0 '计算当前最大连续数t 以及没有变化的计数k归零
    
12.             For i = a(n - 1) + 1 To 1000 '以前一个数+1开始检查替换
    
13.                 a(n) = i: t = f(a, n) '替换 并统计最大连续个数
    
14.                 If t > t2 Then t2 = t: i2 = i Else k = k + 1: If k > 5 Then Exit For
    
15.                 '更新连续个数的最大值t2 如果此值不能增大则连续5个数都不增大则提前结束
    
16.             Next
    
17.             a(n) = i2 '更新为第一个有效最大值时的数字
    
18.         Next
    
19.         Cells(n1, 1) = t2 '输出连续最大个数
    
20.         Cells(n1, 2).Resize(, n - 1) = a '输出这一组数
    
21.     Next
    
22. End Sub
    
23. 
    
24. Function f&(a, n&) '统计最大连续个数的自定义函数 解释略
    
25.     Dim i&, i2&, k&, k2&, n1&, n2&, t&
    
26.     n1 = a(1) + a(1): n2 = a(n) + a(n)
    
27.     ReDim b(n1 To n2) As Boolean
    
28.     For i = 1 To n
    
29.         t = a(i)
    
30.         For i2 = 1 To n
    
31.             b(t + a(i2)) = True
    
32.         Next
    
33.     Next
    
34.     For i = n1 To n2
    
35.         If b(i) Then k = k + 1 Else If k > k2 Then k2 = k: k = 0
    
36.     Next
    
37.     If k > k2 Then k2 = k
    
38.     f = k2
    
39. End Function

复制代码