魔方吧·中文魔方俱乐部

标题: 两个鸡蛋和楼房高度问题 [打印本页]

作者: 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 发表
先从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

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

作者: zhy3729 时间: 2009-3-23 15:31:12

不会。。。。。。。。。。。。。。

作者: leaders 时间: 2009-3-23 15:34:02

如果只有两个鸡蛋可以让你扔的话，那这个题目就没有思考的余地了。答案只能是1楼或2楼（结合常识来扔鸡蛋）。
我想，楼主的意思应该是假设每次所扔下的鸡蛋都是完全相同的。

原帖由 东莞的8 于 2009-3-23 15:29 发表
难道就没有人认真看过题目再思考？

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

作者: azlpub 时间: 2009-3-23 15:53:39

其实只需要一个鸡蛋。
从一层扔。
啪！

作者: migl 时间: 2009-3-23 16:16:45

鸡蛋没啥意义啊~~~~~~~~先入为主了~~

换成石头才有讨论的意义啊~~

要不换成恐龙蛋魔方的也好。

作者: Vicki 时间: 2009-3-23 16:23:10

两个鸡蛋嘛~最少一次~最多两次~

如果LZ题目没有错的话那后面那些就是误导人的~

作者: AMOAMO 时间: 2009-3-23 16:24:51

这里的鸡蛋是鸡生的还是人造的啊
鸡蛋如果是人造的，就用黄金分割法，从38楼开始扔

作者: 东莞的8 时间: 2009-3-23 16:24:54

无言了。等楼主出来吧。我发现很难跟楼上N人沟通。

作者: strawberry 时间: 2009-3-23 16:39:11

能找出从1楼掉下去还不碎的鸡蛋再说吧！！！

作者: don66 时间: 2009-3-23 16:43:14

其实很简单,,,楼主说只有两个蛋,,那就说明只有两次机会可以试,,每一次从二楼开始,,
设蛋碎等于1 ,,没事等于0,,,可以做很简单的条件循环,,楼层数为F (floor)  初始值为2
因为要看留个蛋,,试一楼仍是否也不行(设蛋A和蛋B)  实际上B蛋是在A蛋的楼下扔
F=2
if  A=0  then  F=F+2
else  (if B=0  then F=F-1
      else F=F-2)
就看结果了,,如果F=0,说明在一楼扔出也不行...

这种不是问题的问题用最最小儿科的逻辑分析就得了
楼主比较有想法,,事实上在哪仍蛋到地面都会碎,,,为什么不换成其它东西,,,
我比较喜欢鸡蛋吃到肚子里,,这样比较正常!!!

[ 本帖最后由 don66 于 2009-3-24 00:15 编辑 ]

作者: flwb 时间: 2009-3-23 17:22:25

10,20,30,40,50,60,70,80,90,共九次,如果第九次碎了,用第二个鸡蛋,81至89,,如果第九次还没碎,继续93,96,99,如果最后一次99碎了,用第二个蛋97,98,如果99没碎,那就只剩100了,这样最多18次。

[ 本帖最后由 flwb 于 2009-3-23 17:24 编辑 ]

作者: don66 时间: 2009-3-23 17:46:03

好奇怪啊,,两个鸡蛋能有几次机会碎啊,,十次还是二十次???不就是两次吗

作者: flwb 时间: 2009-3-23 17:49:03

前面没想清楚，原来是这样的,最多14次,第一次14.然后是27,39,50,60,69,77,84,90,95,99。

[ 本帖最后由 flwb 于 2009-3-23 17:50 编辑 ]

作者: cfopsub5 时间: 2009-3-23 17:57:19

好复杂啊，看了就头疼

作者: lulijie 时间: 2009-3-23 19:08:43

我来换一种提法，免得大家臭鸡蛋乱丢。

有一个小于100的奇数，不知道具体数值，
现在让你报数，每次只能报偶数，对方会告诉你所报的数大了还是小了，
你可以一直进行下去，直到你报的数有两次大了为止。
最后要求你说出奇数的具体数值。
设计一个方案，使得你能准确地说出奇数的具体数值而报数的次数尽可能少。

作者: lulijie 时间: 2009-3-23 19:56:06

假设这个鸡蛋硬度足够，不知道到底从几楼扔下刚好碎。设这层楼数值为n。
1楼就是地面，假设肯定不碎，那么1<n。

那么对于不同的n，各种方案的步数都不同。
方案A：从3楼开始扔，假如不碎，就加2层再试，再不碎再加2层，直到碎了（碎了的楼层为m）。那么接着m-1层扔，不碎，n=m，碎了，n=m-1。这种方案所需的步数=[n/2] +1                   [  ]  为取整。
99层不碎，接着只能扔100层，没有101层。
显然n越大，所需的步数约多。  由于n是不确定的，只能计算平均值=2599/99=26.2525步。
即方案A的步数期望值=26.2525步。
方案B：先从50楼扔，不碎，按照A方案两层两层加；碎了从2楼开始，一层一层加，
   结果 n<=50 步数 n
            n>50    步数 [(n-49)/2] +2
   方案B的步数期望值=（（2+50）* 49/2  +    (3+27)*25 ）/99=2024/99=20.4444
显然，方案B比方案A好。
方案C：先从K楼扔，不碎，按照A方案两层两层加；碎了从2楼开始，一层一层加。
   K取多少，才能使该系列方案的步数期望值最小呢？

作者: kexin_xiao 时间: 2009-3-23 20:16:21

看的迷糊,再学习一下

作者: lulijie 时间: 2009-3-23 20:30:25

修正一下25#的结果的错误
   方案A的步数期望值=2598/99=26.2424步。
   方案B的步数期望值=2023/99=20.4343步。
   方案C中的K取35 时步数期望值最小=1846/99=18.6464步。
所以在同系列方案中，以下方案最佳：
   从35楼开始扔，若碎了，那么从2楼开始扔第二个鸡蛋，一层一层往上扔，直到碎了为止。
                           若不碎，那么在37楼扔，只要不碎就增加两层楼再扔，直到第一个鸡蛋碎了，那么就在碎了的那层楼的
                                 下面那层扔第二个鸡蛋。
   该方案的得出结果的步数期望值是1846/99=18.6464步。

作者: lulijie 时间: 2009-3-23 21:59:29

方案D系列：
有m个整数从小到大排列，第i个数表示为 a(i)。 a(0)=1,表示从第一楼扔，肯定没碎。
先从a(1) 楼开始扔第一个鸡蛋，若碎了，  从2楼开始，一层一层往上扔第二个鸡蛋。
         若没碎，从a(2)楼扔，还没碎，再从a(3)楼扔，(只要没碎就按照上述的数列往上升。）
                     直到第一个鸡蛋碎了，  那么第二个鸡蛋就从最高的没碎的那层一层一层往上扔。
--------------------------------------------------------------------------------------------------------------------
所有的方案，都可以表述成上述的形式。比如方案C系列的k=35，就是以下的数列
         1，35，37，39，41，43，……97,99,100
----------------------------------------------------------------
所以本贴的解答，就是找到一个数列，
      a0,a1,a2,…ai…,100                ( a0=1)
按照该数列递增顺序扔第一个鸡蛋，直到第一个鸡蛋碎了，
那么第二个鸡蛋从没碎的最大的ai 加1开始扔，以后每次加1，直到第二个鸡蛋也碎了为止。

作者: lulijie 时间: 2009-3-23 23:50:51

最佳方案是： 14 26 37 47 56 64 71 78 84 89 93 96 98 99 100
步数期望值=1016/99=10.2626步。最多步数15步，最少2步。

作者: lulijie 时间: 2009-3-24 00:01:59

22楼的方案也不错，最多步数14次，但步数的期望值（平均值）=1020/99=10.3030，比29楼的方案稍大些。
22楼的方案若把后面稍微修该一下：
14 27 39 50 60 69 77 84 90 93 96 98 99 100
步数的期望值（平均值）=1017/99=10.2727 ，比原先提高了一点，比29楼的方案还是稍大些。

[ 本帖最后由 lulijie 于 2009-3-24 00:11 编辑 ]

作者: flwb 时间: 2009-3-24 00:10:45

原帖由 lulijie 于 2009-3-23 23:50 发表
最佳方案是： 14 26 37 47 56 64 71 78 84 89 93 96 98 99 100
步数期望值=1016/99=10.2626步。最多步数15步，最少2步。

你可真是高手,最少2步

[ 本帖最后由 flwb 于 2011-8-25 08:57 编辑 ]

作者: 东莞的8 时间: 2009-3-24 00:15:19

29楼的方法很好！但如果按这个来做的话似乎下面一组是不是更优？
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100。
期望值好像更低。还是我对该计算方法不够理解的缘故？请指教

作者: lulijie 时间: 2009-3-24 00:17:00

比如这个鸡蛋从2楼掉下会碎，那么按照方案 14 26 37 47 56 64 71 78 84 89 93 96 98 99 100
先从14楼扔鸡蛋，碎了，再从2楼扔鸡蛋，碎了。花两步就找到了鸡蛋从2楼掉下刚好摔碎。 1楼是地面，不用试。

作者: 东莞的8 时间: 2009-3-24 00:17:02

晕。回贴的时候还在30楼的

作者: lulijie 时间: 2009-3-24 00:28:29

方案    14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100
  假设鸡蛋从n楼掉下刚好碎了：
   n=2 步数=2  ； n=3 步数=3 ；  n=4 步数=4  ； ........  n=12 步数=12  ； n=13 步数=13 ；  n=14 步数=13
   n=15 步数=3  ； n=16 步数=4 ；  n=17 步数=5  ； ........  n=25 步数=13 ； n=26 步数=14 ；  n=27 步数=14
   ..................
   n=96 步数=12  ； n=97 步数=13 ；  n=98 步数=14 ；  n=99 步数=14
   n=100 步数=12
---------------------------------------
以上全部步数相加除以99=1020/99=10.3030

作者: don66 时间: 2009-3-24 12:21:39

原帖由 lulijie 于 2009-3-23 19:56 发表
假设这个鸡蛋硬度足够，不知道到底从几楼扔下刚好碎。设这层楼数值为n。
1楼就是地面，假设肯定不碎，那么1

您用的方案A和我的方法相同,,我先提出来的..呵呵,,
但您明显是个机会主义者,,不考虑全部可能性的.不会想合理与否..如果是在49楼或者说40楼以上,,按你提出的方案B要多少步呢,,多A方法多了去吧..
明显方案B是不好的...从全部各种概率平均出现的角度上说...这不是在赌运气,,,是在分析问题...

[ 本帖最后由 don66 于 2009-3-24 12:24 编辑 ]

作者: 骰迷 时间: 2009-3-24 18:15:35

樓上還在說方案B，跟社會脫節了

作者: 金眼睛 时间: 2009-3-24 22:04:31

好题！！不过与常理不符，100cm的地面扔鸡蛋还差不多，o(∩_∩)o...

先说一下假设及对原题的理解，当然假设不同也可以计算，只是结果有点差异：
1：1楼扔可能碎，100楼扔可能不碎，这样100楼必须试一次。
2：每隔10层的方案显然不妥，90后直接试100比较浪费，可见间隔层数越往后越小。
3：以间隔10层为例，30没碎，40碎了，第二个鸡蛋从31开始往上试，试到39为止，因为40试过了。

解题方法：数学归纳法。
从100层开始计算，计算在某层不碎的情况下，还需要进行试验的平均次数，这里要用到概率。
举例：如果求90层不碎之后的平均次数，需要依次求出90层后试91、92……100层各自的平均次数，以最小平均次数作为90层不碎之后的平均次数。这样就可以递推出各层不碎的一个选择数列。在选择数列附近进行试算，找出一个最佳方案。

结果如下：14、26、37、47、56、64、72、79、85、90、94、97、99、100。平均试验次数10.3465次。

作者: lulijie 时间: 2009-3-25 00:32:06

金眼睛的数列，用我的算法计算平均值跟我的数列一样。
其实计算这个就是用倒推法。                                        就按照金眼睛的方法，1楼也要试。
假设只有1层楼，那么最少步数的总和 1 记作  S(1)=1
2层楼，最少步数的总和 3 （方案 1，2  最佳） S(2)=3
一共n层楼，最佳方案的最少步数的总和记作 S(n)
         假设先从k层扔鸡蛋的方案最佳，那么 S(n)=(k+3)*k/2  -1 +  (n-k)  +  S(n-k)  =（k+2)*(k-1)/2  +n +S(n-k)
               红字部分为鸡蛋在k层以下包括k层刚好碎的所有步数的和，
               蓝字部分为k层以上刚好碎的所有步数的和。
   假设n-1以下的所有S(i) 值都知道，那么计算S(n)值就是让k从1到n，上述公式求得的值中的最小值就是所求的S(n)值。
这样，从S(1)开始（或 S(1)、S(2)开始），按照递推公式依次求的得S(2),S(3),........,以致S(100), 让电脑计算很快。
最后平均值就等于S(100)/100。
1楼不算，平均值=S(99)/99。
-----------------------------------------------------------------------------------------------------
从S(1),至S(100)的值如下：
1，3，6，9，13，17，21，26，31，36，41，47，53，59，65，71，78，85，92，99，106，113，121，129，
137，145，153，161，169，178，187，196，205，214，223，232，241，251，261，271，281，291，301，
311，321，331，342，353，364，375，386，397，408，419，430，441，453，465，477，489，501，513，
525，537，549，561，573，586，599，612，625，638，651，664，677，690，703，716，729，743，757，
771，785，799，813，827，841，855，869，883，897，911，926，941，956，971，986，1001，1016，1031，
------------------------------------------------------------------------------------------
以下就是最少步数的解法，冒号前面的是总楼层数，冒号后面的数字是最先在哪个楼层扔鸡蛋。
  1：1； 2：1；    3：2；    4：2；    5：2；    6：2；    7：3；    8：3；    9：3； 10：3；
11：4；  12：4； 13：4； 14：4； 15：4； 16：5； 17：5； 18：5； 19：5； 20：5；
  21：5；  22：6； 23：6； 24：6； 25：6； 26：6； 27：6； 28：6； 29：7； 30：7；
  31：7；  32：7； 33：7； 34：7； 35：7； 36：7； 37：8； 38：8； 39：8； 40：8；
  41：8；  42：8； 43：8； 44：8； 45：8； 46：9； 47：9； 48：9；    49：9； 50：9；
51：9； 52：9；    53：9； 54：9； 55：9； 56：10；  57：10；  58：10；  59：10；  60：10；
61：10；  62：10；  63：10；  64：10；  65：10；  66：10；  67：11；  68：11；  69：11；  70：11；
71：11；  72：11；  73：11；  74：11；  75：11；  76：11；  77：11；  78：11；  79：12； 80：12；
81：12；  82：12；  83：12；  84：12；  85：12；  86：12；  87：12；  88：12；  89：12；  90：12；
  91：12；  92：13；  93：13；  94：13；  95：13；  96：13；  97：13；  98：13；  99：13；  100：13；
---------------------------------------------
比如一共100层楼，第一层也要试，从上述找到100，后面的是13，剩下的还有100-13=87，找到87后面的数字是12，下一步就是从剩下的87层的12楼即13+12=25楼，依次类推得出数列就为最优数列，
      13，25，36，46，55，63，71，78，84，89，93，96，98，99，100
--------------------------------------------------------------------------
第一层不算，实际只有99层楼，同样的方法找出数列后，把值全部加上1即可。
      13，25，36，46，55，63，70，77，83，88，92，95，97，98，99             全部加上1就得到我的那个数列
      14，26，37，47，56，64，71，78，84，89，93，96，98，99，100

作者: lulijie 时间: 2009-3-25 00:49:37

因为求最小值时求得的k值不只一个，所以造成求的的最佳数列不只一个答案。
具体如下： or 表示前面和后面的值都可以。
1：1；  2：1；  3：1or2；  4：2；  5：2or3；  6：2or3；  7：3；  8：3or4；  9：3or4；  10：3or4；  11：4；
12：4or5；  13：4or5；  14：4or5；  15：4or5；  16：5；  17：5or6；  18：5or6；  19：5or6；  20：5or6；
21：5or6；  22：6；  23：6or7；  24：6or7；  25：6or7；  26：6or7；  27：6or7；  28：6or7；  29：7；
30：7or8；  31：7or8；  32：7or8；  33：7or8；  34：7or8；  35：7or8；  36：7or8；  37：8；  38：8or9；
39：8or9；  40：8or9；  41：8or9；  42：8or9；  43：8or9；  44：8or9；  45：8or9；  46：9；  47：9or10；
48：9or10；  49：9or10；  50：9or10；  51：9or10；  52：9or10；  53：9or10；  54：9or10；  55：9or10；  56：10；
57：10or11；  58：10or11；  59：10or11；  60：10or11；  61：10or11；  62：10or11；  63：10or11；  64：10or11；
65：10or11；  66：10or11；  67：11；  68：11or12；  69：11or12；  70：11or12；  71：11or12；
72：11or12；  73：11or12；  74：11or12；  75：11or12；  76：11or12；  77：11or12；  78：11or12；  79：12；
80：12or13；  81：12or13；  82：12or13；  83：12or13；  84：12or13；  85：12or13；  86：12or13；
87：12or13；  88：12or13；  89：12or13；  90：12or13；  91：12or13；  92：13；  93：13or14；  94：13or14；
  95：13or14；  96：13or14；  97：13or14；  98：13or14；  99：13or14；  100：13or14；

[ 本帖最后由 lulijie 于 2009-3-25 00:52 编辑 ]

作者: liuii 时间: 2009-3-25 11:38:39

这不是去年某期程序员杂志的题目么？

作者: yang_bigarm 时间: 2009-3-26 17:48:03

这个是我一个同学去EMC参加面试的时候遇到的问题。

楼上 lulijie 的答案是正确的，分析的求和公式也很正确，但是这个问题跟数学归纳法没有什么关系，这个问题的主要实质是决策树的平衡，如果 lulijie 能把决策树也贴出来就很好了。

作者: lulijie 时间: 2009-3-26 18:19:20

决策树这个概念我可不懂，我该描述的都描述了，只差程序的代码（ VB6.0）没公布，若大家对其感兴趣，我马上可以公布。

作者: 骰迷 时间: 2009-3-26 18:21:59

LULIJIE是暴力解題的，不過要用樹的話，要嘗試好些時間才猜得出來

作者: 骰迷 时间: 2009-3-26 18:45:41

如果第一次破了，那麼便要由頭試起，最少步>=第一次撞那個數
主要是讓右邊的態樹（第一次不破之後的動作）不要高過左邊

[ 本帖最后由骰迷于 2009-3-26 18:47 编辑 ]

作者: lulijie 时间: 2009-3-26 18:56:32

也不能说暴力。
应该说用递推方法求解，只不过把比较大小的过程交过了电脑而已。
先从S(1),推导出S(2),
再从S(1)、S(2)推导出S(3),
再从S(1)、S(2)、S(3)推导出S(4),
以此类推，直至推出S(100)。
跟暴力解法那是天壤之别。

作者: 骰迷 时间: 2009-3-26 22:47:28

算我電腦知識差罷，本人是不太了解程序碼解題的

作者: lulijie 时间: 2009-3-27 00:31:24

我们把n层楼的最佳数列的第一项值，即最先扔鸡蛋的楼层  为 k
观察上述n=1-100  的k值，发现一个明显的规律：
以下把只有一个k值的列举如下，
n：k；
1：1；
2：1；
4：2；
7：3；
11：4；
16：5；
22：6；
29：7；
37：8；
46：9；
56：10；
67：11；
79：12；
92：13；
106：14；    这是我的推测
--------------------------
其他n，如70，从上表查它介于67和79之间，所以它的k值可取11或12。
所以只要记住上述表的值就可。
上述表有个很明显的规律。
第二行的n比第一行的多1，
第三行的n比第二行的多2，
第m行的n比上一行多m-1。
用通项表示  n(m)=1+m(m-1)/2    n(m)表示m行的n值。而k值等于m-1，（第一行除外）
所以不用记忆：只要记住
      n=1，                   k=1
      n=1+m(m-1)/2       k=m-1                         m>1
      介于两者之间的       k可以取两端的值。

解题过程：
n=100
因为 1+14*（14-1）/2=92          k=13
            1+15*（15-1）/2=106       k=14
  因为100介于上述两者之间，所以k可取13或14
不妨取14， 100-14=86                   即第一次楼层 14
            1+13*（13-1）/2=79    k=12
            1+14*（14-1）/2=92    k=13
   86介于上述两者之间，所以k可取12或13
不妨取12， 86-12=74                      即第二次楼层  14+12=26
   。。。。。。。
   。。。。。。。
最后可得到金眼睛得出的数列：
14、26、37、47、56、64、72、79、85、90、94、97、99、100
知道了最佳数列，那么最少步数就举手可得。
---------------------------------------------------------
关键是我得出的上述蓝字部分的结论是不是对于所有的n都成立了？  n不仅仅限于100以内。

作者: lulijie 时间: 2009-3-27 18:30:05

S(n)的值也有明显的规律
1，
1+2，
1+2+3，1+2+3+3，
1+2+3+3+4，1+2+3+3+4+4，1+2+3+3+4+4+4，
1+2+3+3+4+4+4+5，。。。。。。

若m(m+1)/2 +2 <= n<= (m+1)(m+2)/2 +1，       那么  S(n)=S(n-1)+m+2。
或者表示成以下递推公式：
   S(n)=S(n-1)+  int( sqr(2n-3.75)-0.5 ) +2             int是取整函数  ，sqr 是开根号。
   S(1)=1

作者: ares_g 时间: 2009-3-28 18:20:54

原帖由 东莞的8 于 2009-3-23 15:15 发表
随便试试：先从10楼开始试，每次隔10层，到摔坏的时候再退到未摔坏的10层先开始每次上一层试，这样的话最不幸的情况是要19次。

这个比较有道理，不过我觉得是18次，因为第100层是不用扔的。

作者: fallenjoker 时间: 2010-11-14 18:08:38

如果在一楼也不一定破。

扔2次的方法最多只可以坚定3楼
1+2＝3
方法：2（1）；3

扔3次的方法最多只可以坚定6楼
1+2+3＝6
方法：3（1，2）；5 (4)；6

扔7次的方法最多只可以坚定28楼
7+6+5+4+3+2+1＝28
方法：7（1，2，3，4，5，6）；13 (8，9，10，11，12)；18（14，15，16，17）；22（19，20，21）；25（23，24）；27（28）；29

（n）为第一粒蛋破了后的选择。

1+2+3+4.......+14=105
扔14次可以最多坚定105楼。

＝=================
改题目：
如果你打工，老板给了每个员工3个样本球，叫员工在这100楼测试它的耐度，要你坚定样本球是在那一楼刚好破的。
球的耐度与它在撞击地面的速度成正比，并不是楼的高度。
v^2=2as
a=10
v=速度

作者: tm__xk 时间: 2010-11-14 19:20:43

这题目比我上课时善良..
我当时的题目是差遣一堆人去跳楼....=_=||

并且人数(蛋数)和层数都是变量..

作者: 相思常青 时间: 2010-11-27 14:35:47

我智商是比较低，楼上的回答我都看不懂

我想的是：
如果鸡蛋碎了就往左边试，没有碎就往右边
                                          50

               25                                                          75

   13                   38                                  63                88

7    19                32 44                         56 69                   82 94
到这一步以后就可以挨着试了。
最多需要试12次

作者: 黄龙 时间: 2010-11-27 14:52:53

玩蛋蛋 …………

作者: 喝着牛奶数星星 时间: 2010-11-27 14:55:34

得需要好好思考思考……

作者: kukufeicong 时间: 2011-1-26 11:01:23

最多六次就可以了：50楼，碎，再75楼，不碎，则25楼（下同）。即50楼、25楼、13楼、7楼、4楼、2楼。

作者: 好没意思了 时间: 2011-1-26 11:54:48

感觉这个题目让人很无语……

作者: gdwf 时间: 2011-1-27 17:37:08

34;12;4;2;1,,5ci

作者: 529160821 时间: 2011-2-19 17:05:20

复杂问题简单化！毛主席教导我们说，要实事求是，所以，不用试，从一楼扔下去就已经烂了！呵呵……

作者: 八目阿修罗 时间: 2011-2-27 06:21:47

原帖由 相思常青 于 2010-11-27 14:35 发表
我智商是比较低，楼上的回答我都看不懂
我想的是：
如果鸡蛋碎了就往左边试，没有碎就往右边
50

25 ...

还是你的方法看起来比较容易理解

作者: zhudapigu 时间: 2011-3-12 13:14:46

这个用二分法好还是用黄金分割法好呢？用黄金分割法好像六次就可以了。

作者: jiajia007 时间: 2011-5-3 16:26:57

二分发。。。。。。。。。。。。

作者: aubell 时间: 2011-6-6 21:21:20

用线扯住，就不碎了。

作者: 龚永明魔方 时间: 2011-6-30 13:25:03

在1层使劲往下扔，结果呢？

作者: 240321asd 时间: 2011-6-30 13:31:14

脑筋急转弯么???　　

作者: 司马殇 时间: 2011-6-30 13:40:57

有点意思拿一个鸡蛋从10楼向下扔碎则另一个从1楼分次测试！不碎则到20楼向下扔碎则从11楼分次测试！不碎上30楼再扔这样最多测试19次最少测试11就能知道了

[ 本帖最后由司马殇于 2011-6-30 13:42 编辑 ]

作者: fhw 时间: 2011-7-1 21:16:20

最后答案是“9”！！！！！！！！！！！！

作者: 克克 时间: 2011-7-20 20:43:40 标题: 很简单

从第一层仍，必碎。不信者可以实践验证

作者: ZZY7417 时间: 2011-9-3 00:36:13

0.618法可以么。。。
第一只鸡蛋：
1 2 3 5 8 13 21 34 55 89 100
记录摔破时的楼层和它前面那个楼层
第二只鸡蛋。。。
在这两层之间每一楼摔一次。。

作者: huangfu142857 时间: 2011-9-23 10:39:50

利用0.618法，先从61层开始扔，如果碎了（一定会碎），再取61的0.618，继续扔，以此类推，就能最少次数得到你要的了。

作者: 黑丝的咏叹 时间: 2011-10-14 10:41:02

25？？？吧吧吧。。。

作者: lsx 时间: 2012-2-1 23:36:36

“2”次根号“100”等于10，所以楼主说的方案应该是最佳的了。
但要有一个假设：我们生活中的常识在这里是不适用的，1-100层扔下鸡蛋，鸡蛋都有可能碎或者不碎。

作者: lsx 时间: 2012-2-1 23:38:52

内容“2”次根号“100”等于10，所以楼主说的方案应该是最佳的了。
但要有一个假设：我们生活中的常识在这里是不适用的，1-100层扔下鸡蛋，鸡蛋都有可能碎或者不碎。

作者: kattokid 时间: 2012-2-2 00:11:47

原帖由 kukufeicong 于 2011-1-26 11:01 发表
最多六次就可以了：50楼，碎，再75楼，不碎，则25楼（下同）。即50楼、25楼、13楼、7楼、4楼、2楼。

我觉得有必要重新看下题目，因为题中只有两个鸡蛋，按阁下的方案，假如在25楼第二次鸡蛋也碎了，那么你会发现这个题目你将无法完成，也许你得重新去买蛋，但是买蛋并不是题目所许可的。。。

个人的解法是假如第N层摔蛋不碎，那么数学公式可以表示为求x+[100/x]的最小值

[ 本帖最后由 kattokid 于 2012-2-2 00:14 编辑 ]

作者: theobagwell 时间: 2012-6-13 14:52:33

二分法！可是只有2个鸡蛋，很明显不够啊

作者: 魔方minister 时间: 2012-6-14 22:55:32

高数里求零点的思路。就是总数除以二减去上面的数。有负值时结束

作者: 793855337 时间: 2012-7-22 14:29:37

不是一共只有两个鸡蛋吗。。。找出答案最多只能碎两次啊？你们这么扔得碎多少个

作者: 孤山一片云 时间: 2012-8-2 17:29:06

问题不难，但是看到很多人理解错了，我是这样想的，如果一层一层的试，先一层再二层再三层……，最多需要100次；如果2层2层的试，先二层再四层再六层……，最多需要50+1=51次；如果3层3层的试，先3层再6层再9层，最多需要33+2=35次；同理4层25+3=28次；5层20+4=24次；6层16+5=21次；7层14+6=20次；8层12+7=19次；9层11+8=19次；10层10+9=19次；11层9+10=19次；12层8+11=19次；13层7+12=19次；14层7+13=20次……………………………………，所以可以得到19次是最优方案！！

作者: 我是潇洒哥 时间: 2012-8-11 00:02:05

你家鸡蛋真结实……

作者: 武杰610206738 时间: 2012-9-21 22:22:51

纯粹的物理问题"求在某楼的地方掉下去的力""再和鸡蛋破的临界比较"只要零次欧

作者: 小鸿99 时间: 2012-10-20 22:58:38

楼上用的方法都不是最优
应该这样：
第一次：64层，有两种情况：碎或没碎
第二次：若碎了，即“64-64/2”；若没碎，即“64+64/2”
然后再分（以上一次碎了为例，没碎就是以下的步骤反过来，具体的自己思考），第三次没碎，则“64+64/2-64/4”，碎了，则“64+64/2+64/4”
总之就是设最高上限为128（2的7次幂），每次碎了就减“2^（8-本次次数）”，没碎就加“2^（8-本次次数）”，最终一定7次求出，此为最科学、最精简的方法
（PS：累死我了……）

作者: 小鸿99 时间: 2012-11-2 19:39:10

两个鸡蛋的话……见下：
从2楼开始，扔下去，没碎就捡起来，到四楼，还没碎，再捡起来，上六楼……以此类推
碎了的话，就下一层楼，扔另一个，看看碎没碎
至多51次（好像也不少）

作者: 小菲姑 时间: 2012-11-19 14:49:09

qazwsxpy 发表于 2009-3-23 15:28
告诉你们个秘密...其实鸡蛋从哪层楼仍下去..它都会碎...

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

我也想说。。。

作者: Fenz 时间: 2012-11-21 16:53:58

我在一楼摔了一下，碎了，，从50楼开始才是傻瓜呢

作者: youyang1985 时间: 2012-12-5 12:50:22

一共就俩鸡蛋，你们都得瑟什么数学知识啊？
要铺张的话，每层一个人一个鸡蛋试试不就完了么？时间比鸡蛋重要吧！

作者: 无言的季末 时间: 2012-12-21 15:08:12

qazwsxpy 发表于 2009-3-23 15:28
告诉你们个秘密...其实鸡蛋从哪层楼仍下去..它都会碎...

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

哈哈，不错，所以，只要一次就够了

作者: 地·摊·魔·方 时间: 2013-2-4 00:44:42

在信息学奥赛中的题目吧....其实随便一道动态规划都能做死没做过递推题的人....

作者: 小飞人1175 时间: 2013-2-4 11:48:43

本帖最后由小飞人1175 于 2013-2-5 12:31 编辑

[伪]靠谱方法

：
先把一个鸡蛋送给开发商，让他告诉你一层楼有多高，然后测出另一个鸡蛋重量，并用硬度计测出使另一个鸡蛋破碎需要最少多大的力，再代入物理公式得出鸡蛋自由落体破碎所需最低高度，除以一层楼高度，有余数则进一，即为所求层数。

作者: H白尼B 时间: 2013-10-18 14:11:30

每十层扔一次吧，如果层数小于90的时候就碎了，就在前一个十层一层层尝试；如果90层没碎，就可以从95层尝试，不碎就继续二分法，碎了就一层层凑

作者: 日天者 时间: 2015-8-5 10:19:41

目前找到的最好方案：第一次从15层扔，碎了就从1层到14层，没碎就去29（15+14）层；从29层往下扔，碎了就从16层到18层，没碎就去42（29+13）层；从42层往下扔......以此类推，最多需要15次就能找出最终答案。

作者: 大大大魔方 时间: 2016-1-24 17:40:40

认真了，答案也是7个？！

作者: wangjh0710 时间: 2016-1-28 11:57:41

我的思路是开平方，比如100，第一次从10开始，碎了，就从1楼，然后从1-9（至多10次）；没有碎，根号90约等于10，即从20楼开始，碎了从11-19，没碎根号80约等于9,即从29开始，碎了从21-28，没碎根号71约等于9，依次下去，最多约为16次。

作者: wangjh0710 时间: 2016-1-28 12:42:50

我来终结此帖：当层数为N时，K*（K+1）/2≥N的最小整数K，如100层K*（K+1）/2≥100的最大整数为15，因此至多15次。

作者: a471791142 时间: 2016-3-23 20:19:17

wangjh0710 发表于 2016-1-28 12:42
我来终结此帖：当层数为N时，K*（K+1）/2≥N的最小整数K，如100层K*（K+1）/2≥100的最大整数为15，因此至多 ...

你确定是15不是14？我读书少不要骗我

作者: 嗨皮！兔油 时间: 2016-3-26 22:08:28

首先，从50楼开始如果鸡蛋碎了就从25开始在扔如果没碎就从75楼开始每次取中间的楼从即可最短

作者: fgmN 时间: 2016-4-25 19:07:09

不是说只有两个蛋么按照生活实际在1楼和3楼试下就可以了

作者: Bobson 时间: 2017-1-31 21:40:49

鸡蛋从手中摔下来正常都会碎的吧

作者: 一目了然 时间: 2017-7-20 17:45:58

为合情理，此题应换一种表述：我在心中记住了自然数1——100中的一个数，你来猜。猜错了我会告诉你大了或是小了，猜小了可以继续猜，猜大了也可以继续猜但不许再猜大。也就是说可以猜大一次，猜小不限次数。问，在最不利的情况下最少多少次可以猜出此数？
此题不涉及概率问题。应该是14次。14,27,39,50,60,69,77,84,90。最不利的情况是第9次猜90，猜大了，然后从85逐一猜5次。第9次之前不管是哪一次猜大了，然后从上一次猜小了的数逐一往大猜，也是14次。
此题涉及自然数前n项之和的数列：1,3,6,10,15,21,28,36,45,55,66,78,91,105,120......n大于91，小于等于105就是14次。大于105小于等于120就是15次......以此类推。

作者: 魔方lover 时间: 2017-7-21 20:39:15

qazwsxpy 发表于 2009-3-23 15:28
告诉你们个秘密...其实鸡蛋从哪层楼仍下去..它都会碎...

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

有道理哦~~~

作者: History 时间: 2017-8-27 15:31:18

这不科学，鸡蛋是椭圆体，鸡蛋受力不均匀，鸡蛋在做加速运动……啊，鸡蛋，若你这么想不开，我愿陪你against the earth。欧，蛋蛋。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)