[合集] 问一个玻璃球和100层楼的问题# JobHunting - 待字闺中
h*g
1 楼
☆─────────────────────────────────────☆
laoyan (tom) 于 (Fri Oct 27 02:46:54 2006) 提到:
n个玻璃球,怎么样试出哪层楼玻璃球会摔碎,问最坏情况的最优解?
一直没见到标准答案,我的分析如下,不知对不对?
n=1,一层一层从下往上试,所以要100次;
n=2,两层两层从下往上试,所以要51次;
n=3,4层4层从下往上试,所以要27次;
n=4,8层8层从下往上试,所以要15次;
...
大概的公式是:m+n-1,m=取整(100/(2^(n-1)))>0
以此类推
n=5,10次
n=6,8次
n=7,7次
n>7,7次,球多了也是浪费.
☆─────────────────────────────────────☆
ThinkBook (think) 于 (Fri Oct 27 03:27:01 2006) 提到:
n=2开始就不用从1楼开始试了, 从n楼开始试,这样会不会节省一点点?
☆─────────────────────────────────────☆
laoyan
laoyan (tom) 于 (Fri Oct 27 02:46:54 2006) 提到:
n个玻璃球,怎么样试出哪层楼玻璃球会摔碎,问最坏情况的最优解?
一直没见到标准答案,我的分析如下,不知对不对?
n=1,一层一层从下往上试,所以要100次;
n=2,两层两层从下往上试,所以要51次;
n=3,4层4层从下往上试,所以要27次;
n=4,8层8层从下往上试,所以要15次;
...
大概的公式是:m+n-1,m=取整(100/(2^(n-1)))>0
以此类推
n=5,10次
n=6,8次
n=7,7次
n>7,7次,球多了也是浪费.
☆─────────────────────────────────────☆
ThinkBook (think) 于 (Fri Oct 27 03:27:01 2006) 提到:
n=2开始就不用从1楼开始试了, 从n楼开始试,这样会不会节省一点点?
☆─────────────────────────────────────☆
laoyan