100内,寻找一个集合A,元素全是自然数,得两两相加能表示2以上100以内所有的数？

无心人

显然 0, 1, 2是必须的 使用0, 1, 2能表示的是0, 1, 2, 3 第一个不能表示的是4，加入 然后可以表示4, 5, 6 同样道理加入7 可以证明 序列[3k + 1] + [0, 2]能达到要求

northwolves

原帖由 xiugakei 于 2008-12-25 19:36 发表 我的估算是100内,只需要20个（10*2）左右 推广之后是 n只需要1.5*√n~2*√n个。

理论上似乎是这样。但它是基于四进制的： 4^1 2个 4^2 6个 4^3 14个 4^4 30个 .... 4^k 2^(k+1)-2 个 令n=4^k n 内需要 2*sqrt(n)-2 个

无心人

同样道理 [4k+1] + [0, 2, 3]也能

northwolves

事实上，从1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, 42, 64, 65, 68, 69, 80, 81, 84, 85 任取两个相加可求出128以内任意整数

无心人

对m >= 3 得到 [mk + 1] + [0, 2, 3, ... m-1]能满足要求 此时总共需要的个数是 (N - 1) / m + (m - 1)

无心人

此时可证明 如果(N - 1) / m + m - 1最小 需要m = [sqrt(N-1)] 比如N = 100，则m = 9 此时需要99 / 9 + 9 - 1 = 11 + 8 = 19个

northwolves

原帖由 无心人 于 2008-12-25 20:58 发表 此时可证明 如果(N - 1) / m + m - 1最小 需要m = [sqrt(N-1)] 比如N = 100，则m = 9 此时需要99 / 9 + 9 - 1 = 11 + 8 = 19个

讲得很透彻，但问题是不让使用0

无心人

这时的序列是[0,1,2,3,4,5,6,7,8,10,19,28,37,46,55,64,73,82,91,100] 能表示的数字是 [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,3 0,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,100,101,102,103,104,105,106,107 ,108,110,119,128,137,146,155,164,173,182,191]

无心人

那都增加1就是了 呵呵 Prelude List> let c = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 20, 29, 38, 47, 56, 65, 74, 83, 92]

northwolves

哦，忘了，前两天有人提到，0 似乎算是自然数了，谁给个权威的连接？