从伽利略丢铁球联想到的题目。 - 辕门射虎


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#1

发表于 2007-1-12 09:44 资料主页短消息看全部作者

从伽利略丢铁球联想到的题目。

你有两个玻璃球和一个１００层的大高楼，你想测出最低在那一层将玻璃球丢下，玻璃球便会破碎。用什么样的战术可以确保得到结果（i.e. 你的战术不能出现两个球都碎了，还找不到答案的情况），并且总共丢球的次数最小化？

如果你有 N 个玻璃球，你的战术会是什么？

[广告] 《精忠报国岳飞传完整版》火热发布


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#2

发表于 2007-1-12 11:09 资料主页短消息看全部作者

周瑜：N = 2 的 case 你还没有达到最小。

岱瀛：你这个方法也。。。如果32层没碎，64层碎了。剩下的一个球，岂非要从 33, 34, 35, ... 一个一个往上来？

给个提示：当 N > log_2 (100) 的时候，二分法的确是正确的。当 N = 1 的时候，一层率一次是正确的。当 N 不大不小的时候，你们想法把这两个 case 折衷一下吧。

[ 本帖最后由天宫公主于 2007-1-12 11:11 编辑 ]

[广告] 《精忠报国岳飞传完整版》火热发布


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#3

发表于 2007-1-15 05:37 资料主页短消息看全部作者

reynolds + 周瑜的答案正确。其实周瑜的那个 algorithm 仔细分析一下，不难给出一个严密的证明。

whws: 我的题目是 worst case optimization, 本来也可以出 average case optimization 的，但我们对实验失败（全部球都碎了，还是没有找到答案）给什么样的惩罚算最合理呢？

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！