两个鸡蛋和楼房高度问题

don66

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

flwb

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

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

cfopsub5

好复杂啊，看了就头疼

lulijie

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

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

lulijie

假设这个鸡蛋硬度足够，不知道到底从几楼扔下刚好碎。设这层楼数值为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

看的迷糊,再学习一下

lulijie

修正一下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

方案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

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

lulijie

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 编辑 ]