魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: yang_bigarm

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

Rank: 2

积分
519
帖子
467
精华
0
UID
22856
性别
发表于 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 编辑 ]

使用道具 举报

Rank: 4

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

六年元老

发表于 2009-3-24 00:15:19 |显示全部楼层
29楼的方法很好!但如果按这个来做的话似乎下面一组是不是更优?
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100。
期望值好像更低。还是我对该计算方法不够理解的缘故?请指教

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 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楼是地面,不用试。

使用道具 举报

Rank: 4

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

六年元老

发表于 2009-3-24 00:17:02 |显示全部楼层
晕。回贴的时候还在30楼的

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 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

使用道具 举报

Rank: 2

积分
235
帖子
178
精华
0
UID
47362
性别
发表于 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 编辑 ]
潜水单手盲拧五阶!

使用道具 举报

红魔

All Blue

Rank: 4

积分
1196
帖子
999
精华
2
UID
38845
性别
发表于 2009-3-24 18:15:35 |显示全部楼层
樓上還在說方案B,跟社會脫節了

使用道具 举报

Rank: 2

积分
421
帖子
233
精华
2
UID
25681
性别
保密
发表于 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次。

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 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

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 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 编辑 ]

使用道具 举报

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

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

GMT+8, 2019-1-19 14:46

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部