Overhang 堆积木 – 能伸出桌面多远?

n个长度为1的砖块,叠起来能伸出桌面多远?(只考虑方块各平面都与桌面平行的情况)。
下面这种放法,很多人高中学物理的时候都见过吧?它用N个砖块伸出了大约1/2ln(N)。

上面这种叠放方法称为Harmonic Stacks,但它是最优的吗?

下面这个例子可以看出,在3个砖块,我们就已经能做的更好了。

上面这个能继续往上堆么?很不幸

如果在上面再压很多砖块就可以了

下面是一种叠放方法,可以做到大约O(lnN).

但它也不是最优的,下面是20个和30个方块的最优叠放方法,它比上面的要好

下面是砖块数目比较少的时候的最优叠放方法。

不过说了这么多,上面的方法都只能做到ln(N)的量级,而下面这个方法可以用N个砖块,往前伸出 N^(1/3)的长度。

而且,Mike Paterson及其合作者证明了,这种方法在量级上已经是最优的了!

文章转自:阅微堂
http://zhiqiang.org/blog/posts/overhang-stacking-wood-how-far-can-extend-desktop.html#new331

发表评论

电子邮件地址不会被公开。 必填项已用*标注