flwb
发表于 2009-3-24 00:10:45
原帖由 lulijie 于 2009-3-23 23:50 发表 http://bbs.mf8-china.com/images/common/back.gif
最佳方案是: 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楼的:L :L
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 发表 http://bbs.mf8-china.com/images/common/back.gif
假设这个鸡蛋硬度足够,不知道到底从几楼扔下刚好碎。设这层楼数值为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 编辑 ]
页:
1
2
3
[4]
5
6
7
8
9
10
11