关于堆砖块的一篇blog

Categories: Uncategorized
Tags: No Tags
Comments: 3 Comments
Published on: 2008/12/28

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

3 Comments - Leave a comment
  1. lonnie says:

    当时听这个老头讲的时候,一来觉得很有趣,二来觉得英国人真闲得慌……

  2. yumuzi says:

    哇!我完全不能理解啊……
    不过我觉得:
    物理学家不研究这个!!!

    发达资本主义国家的学者们会研究很多您看起来闲得慌得东西的……

  3. lonnie says:

    orz 这个是搞计算理论的人研究着玩的……

Leave a comment

Your email address will not be published. Required fields are marked *


Welcome , today is Wednesday, 2018/02/21