yang_bigarm 发表于 2009-3-23 15:12:19

两个鸡蛋和楼房高度问题

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

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

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

东莞的8 发表于 2009-3-23 15:15:29

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

无为子 发表于 2009-3-23 15:24:33

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

cfmake 发表于 2009-3-23 15:25:30

额,这么头痛!!没意思,顶了!

leaders 发表于 2009-3-23 15:25:47

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

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

东莞的8 发表于 2009-3-23 15:27:08

原帖由 leaders 于 2009-3-23 15:25 发表 http://bbs.mf8-china.com/images/common/back.gif
先从50层开始,碎了就到25层,然后再到12层,然后再到6层,然后再到3层,再到2层,再到1层。(最多7次)
思路是二分法,先从中间开始,失败就向上或向下移动剩下的一半,一直循环下去
你的鸡蛋真多啊。。

朱智浩 发表于 2009-3-23 15:28:19

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

qazwsxpy 发表于 2009-3-23 15:28:21

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

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

ppowers 发表于 2009-3-23 15:29:00

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

东莞的8 发表于 2009-3-23 15:29:14

难道就没有人认真看过题目再思考?
页: [1] 2 3 4 5 6 7 8 9 10
查看完整版本: 两个鸡蛋和楼房高度问题