两个鸡蛋和楼房高度问题

flwb

原帖由 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

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

lulijie

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

东莞的8

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

lulijie

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

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

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

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

骰迷

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

金眼睛

好题！！不过与常理不符，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

金眼睛的数列，用我的算法计算平均值跟我的数列一样。
其实计算这个就是用倒推法。                                         就按照金眼睛的方法，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

因为求最小值时求得的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 编辑 ]