两个鸡蛋和楼房高度问题

yang_bigarm

有一栋高楼，高100层。现在你手里有2个质地完全相同的鸡蛋，要求你测出鸡蛋从哪一层楼扔下去之后恰好摔坏。
最笨的办法就是从第1层开始扔，没有碎，那再从第二层扔，没有碎，再上一层楼........，这样的话之多100次就得到答案。但是你若聪明一点，从第50层开始扔，如果碎了，那么用第二个鸡蛋从第一层开始测，这样的话，至多50次就可以得到答案。你还可以从第30层开始扔，等等方案。

现在问题是让你安排一种扔鸡蛋的方案，使得扔的次数尽可能的少就能测出答案来。

注意，是方案，也就是要回答
第一次从第xxx楼扔，如果碎了，下一次从xxx楼开始，如果没有碎，再选择从第xxx楼开始等等，是一系列的描述。

东莞的8

随便试试：先从10楼开始试，每次隔10层，到摔坏的时候再退到未摔坏的10层先开始每次上一层试，这样的话最不幸的情况是要19次。

无为子

不幸呀不幸，鸡蛋还能这样玩吗

cfmake

额，这么头痛！！没意思，顶了！

leaders

括号里面是没碎的情况，情况里面会再有碎或者不碎的情况，我只列举尝试次数最多的两系列情况，思路写在最后
先从50层开始，碎了就到25层（没碎就到75层），然后再到12层（再到88层），然后再到6层（再到94层），然后再到3层（再到97层），再到2层（再到99层），再到1层（再到100层）。（最多7次）
思路是二分法，先从中间开始，失败就向上或向下移动剩下的一半，一直循环下去

[ 本帖最后由 leaders 于 2009-3-23 15:31 编辑 ]

东莞的8

原帖由 leaders 于 2009-3-23 15:25 发表
先从50层开始，碎了就到25层，然后再到12层，然后再到6层，然后再到3层，再到2层，再到1层。（最多7次）
思路是二分法，先从中间开始，失败就向上或向下移动剩下的一半，一直循环下去

你的鸡蛋真多啊。。

朱智浩

选择范围的二分之一层扔鸡蛋 例：开始50 ，假设不碎，范围是51～100 ，第二次选75，碎 范围是51～75 以此类推，最多需要七个鸡蛋。

qazwsxpy

告诉你们个秘密...其实鸡蛋从哪层楼仍下去..它都会碎...

[ 本帖最后由 qazwsxpy 于 2009-3-23 15:30 编辑 ]

ppowers

这个为题可以归结为折半查找。
先从50楼开始，如果没摔坏（哈哈，摔鸡蛋哪用那么高，从手上掉下去都碎），那从75楼摔，如果摔坏，那从
（50+75)/2取整后开始。如此是最理想的算法。次数=log2(N楼)。

东莞的8

难道就没有人认真看过题目再思考？