4
overhang 堆积木 - 能伸出桌面多远？
source link: https://zhiqiang.org/math/overhang-stacking-wood-how-far-can-extend-desktop.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
overhang 堆积木 - 能伸出桌面多远？
系列：数学之美
来自University of Warwick的Mike Paterson星期二在 Yao 的理论计算机课堂上给了一个非常有趣的小讲座。
n 个长度为 1 的砖块，叠起来能伸出桌面多远？（只考虑方块各平面都与桌面平行的情况）。
下面这种放法，很多人高中学物理的时候都见过吧？它用 N 个砖块伸出了大约(\ln(N)/2)。
上面这种叠放方法称为 Harmonic Stacks ，但它是最优的吗？下面这个例子可以看出，在 3 个砖块，我们就已经能做的更好了。
上面这个能继续往上堆么？很不幸
下面这个也不行
如果在上面再压很多砖块就可以了
下面是一种叠放方法，可以做到大约(O(lnN)).
但它也不是最优的，下面是 20 个和 30 个方块的最优叠放方法，它比上面的要好
下面是砖块数目比较少的时候的最优叠放方法。
不过说了这么多，上面的方法都只能做到 ln(N)的量级，而下面这个方法可以用 N 个砖块，往前伸出 N^(1/3)的长度。
而且，Mike Paterson及其合作者证明了，这种方法在量级上已经是最优的了！
Q. E. D.
系列： 数学之美 »
后一篇：
37% 原则约会策略的最优性证明
类似文章：
摸箱子问题以及应用 相似度: 0.151
以前提到过，理论计算机这门课会邀请一些正在这边访问的教授来讲课，由于是本科生，所以这些教授一般都是讲些有趣的东西，比如之前的overhang 堆积木 - 能伸出桌面多远？。今天这次课，来自 Aarhus 的Peter Bro Miltersen讲了一个很有趣的游戏问题。
前一篇：
最佳约会策略
后一篇：
一个算法面试题 & 面试题库
一个面试题，号称是微软的
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK