魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 2178625|回复: 99

两个鸡蛋和楼房高度问题 [复制链接]

Rank: 2

积分
274
帖子
164
精华
2
UID
63527
性别
发表于 2009-3-23 15:12:19 |显示全部楼层
有一栋高楼,高100层。现在你手里有2个质地完全相同的鸡蛋,要求你测出鸡蛋从哪一层楼扔下去之后恰好摔坏。
最笨的办法就是从第1层开始扔,没有碎,那再从第二层扔,没有碎,再上一层楼........,这样的话之多100次就得到答案。但是你若聪明一点,从第50层开始扔,如果碎了,那么用第二个鸡蛋从第一层开始测,这样的话,至多50次就可以得到答案。你还可以从第30层开始扔,等等方案。

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

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

Rank: 4

积分
1684
帖子
1332
精华
1
UID
77777
性别
保密

六年元老

发表于 2009-3-23 15:15:29 |显示全部楼层
随便试试:先从10楼开始试,每次隔10层,到摔坏的时候再退到未摔坏的10层先开始每次上一层试,这样的话最不幸的情况是要19次。

使用道具 举报

Rank: 4

积分
1524
帖子
1294
精华
0
UID
47365
性别
保密
发表于 2009-3-23 15:24:33 |显示全部楼层
不幸呀不幸,鸡蛋还能这样玩吗
无为而无不为。
开封魔方俱乐部:82185764

使用道具 举报

Rank: 3Rank: 3

积分
909
帖子
775
精华
0
UID
40315
性别
发表于 2009-3-23 15:25:30 |显示全部楼层
额,这么头痛!!没意思,顶了!
我结婚了,别打我主意

使用道具 举报

Rank: 2

积分
265
帖子
216
精华
0
UID
61592
性别
保密
发表于 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 编辑 ]

使用道具 举报

Rank: 4

积分
1684
帖子
1332
精华
1
UID
77777
性别
保密

六年元老

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

你的鸡蛋真多啊。。

使用道具 举报

红魔

耗子猪

Rank: 4

积分
1313
帖子
967
精华
1
UID
79032
性别
保密

四年元老

发表于 2009-3-23 15:28:19 |显示全部楼层
选择范围的二分之一层扔鸡蛋 例:开始50 ,假设不碎,范围是51~100 ,第二次选75,碎 范围是51~75 以此类推,最多需要七个鸡蛋。

使用道具 举报

Rank: 2

积分
249
帖子
204
精华
0
UID
37936
性别
发表于 2009-3-23 15:28:21 |显示全部楼层
告诉你们个秘密...其实鸡蛋从哪层楼仍下去..它都会碎...

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

使用道具 举报

Rank: 1

积分
144
帖子
96
精华
0
UID
68894
性别
保密
发表于 2009-3-23 15:29:00 |显示全部楼层
这个为题可以归结为折半查找。
先从50楼开始,如果没摔坏(哈哈,摔鸡蛋哪用那么高,从手上掉下去都碎),那从75楼摔,如果摔坏,那从
(50+75)/2取整后开始。如此是最理想的算法。次数=log2(N楼)。

使用道具 举报

Rank: 4

积分
1684
帖子
1332
精华
1
UID
77777
性别
保密

六年元老

发表于 2009-3-23 15:29:14 |显示全部楼层
难道就没有人认真看过题目再思考?

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2019-3-22 01:48

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部