直尺刻度问题
有一个问题，可能大家以前也了解过：一把长为L的直尺，上面的刻度都是整数，即0,1,2,3，。。。L，如果其中某些刻度被抹去了，这时这把尺子仍然可以量出一些长度，如果要求能够一次性量出从1到L的所有整数长度，那么最少需要几个刻度？这些刻度应该是哪些呢？比如：L=6，那么最少需要4个刻度，分别是0,1,4,6
现在的问题是：设长为L时的最少刻度数是f(L)，有没有算法，可以很快的计算出f(L)，并且能够给出所有可能的刻度？
我们容易知道：必须有\(f(L)*(f(L)-1)/2\geqslant L\);解得: \(f(L) \geqslant \frac{1}{2} + \sqrt{2L + \frac{1}{4}}\)
现在考虑L是平方数的情况，即 \(L=m^2\)，考虑如下刻度：0,1,2,3...m,2m,3m,4m...m*m；这时这些刻度将能够满足条件（因为从1到\(m^2\)的所有长度都可以写成\(km+r\)的形式）。因为此时有2m个刻度，所以此时有：\
显然，\(f(L)\leqslant f(L+1)\leqslant f(L)+1\)，所以当L不是平方数的时候，设N是第一个比L大的平方数，则有\(f(L) \leqslant f(N)=2\sqrt{N}\)，所以：\(f(L)\leqslant2\sqrt{L}+1\)
通过上述讨论，将f(L)限制在一个范围内，缩小了我们需要考虑的范围，可以看到，当L很大的时候，f(L)处于\(\sqrt{2L}\)到\(2\sqrt{L}\)之间，那么还有一个问题：\(\frac {f(L)}{\sqrt{L}}\)当L趋向无穷大的时候有没有极限，有的话是多少呢？ 还有一个类似的问题：哥隆尺问题，但是侧重点不同。
页:
[1]