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

xiugakei

100内,寻找一个集合A,元素全是自然数,得两两相加能表示2以上100以内所有的数？ 比如1,2,4,5,.... 2=1+1 3=1+2 4=2+2 5=1+4...... 求A的数量上最小的集合。 最好推广到1000,10000

litaoye

是不是费伯纳妾的问题?

无心人

A = [1..50]可以么？

gxqcn

改成相减就是最少刻度尺问题。 感觉楼主这个问题也蛮有实际意义的。

northwolves

原帖由 litaoye 于 2008-12-25 12:30 发表 是不是费伯纳妾的问题?

又见老朋友，还欧拉娶妻呢

northwolves

手工推算了一个，不知是否最少的那个： 1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, 42, 64, 65, 68, 69, 80, 81, 84, 85

northwolves

应该与二进制或四进制有关： 1 0000001 2 0000010 4 0000100 5 0000101 8 0001000 10 0001010 16 0010000 17 0010001 20 0010100 21 0010101 32 0100000 34 0100010 40 0101000 42 0101010 64 1000000 65 1000001 68 1000100 69 1000101 80 1010000 81 1010001 84 1010100 85 1010101

northwolves

竟然搜到了这个序列： A126684

xiugakei

高手!这道题我心里还没底,我算了50的,100的还在推。我还想推广到无穷。 1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, 42, 64, 65, 68, 69, 80, 81, 84, 85肯定大了,最大的数不需要超过70（估算的）

xiugakei

我的估算是100内,只需要20个（10*2）左右 推广之后是 n只需要1.5*√n~2*√n个。