抛玻璃算法方法介绍

网上闲逛,看到一算法题大体如下:

有一幢100层高的大楼，给你两个完全相同的玻璃棋子。
假设从某一层开始，丢下玻璃棋子就会破碎。那么怎么利用手中的两颗棋子，
用一种什么样的最优策略，知道这个临界的层高呢？

大致想了下... 得出的第一个算法是33 66 99

IF( 既第一个Q从33楼扔,如果碎了. 就从第一层向33层枚举..)

{

假设最糟糕的情况是32楼是临界点.

33楼 + 1 + 2 +3 ....... +32 = 33次... 嗯...上下楼33,累死了...

}

else

IF(33楼扔下去没碎,那么从66楼往下扔)

最糟糕的情况又发生了 =.=! 65层才是临界点.那么...

33层 + 66层 + (34---65) =33次 ..............!!!

如果66没碎... 99也没碎.. 那么就是 33 + 66 + 99 + (67--98) = 34次..

脑袋里反映出来的第一个算法,, 最糟糕的情况要扔 33或者34次..效率显然不高..

看了下回帖,有个叫IToa什么的同志... 贴出了他的算法..

第一次从15层往下扔..碎了的话,, 最糟糕 15 + (1-13) = 14次.

没碎继续: 第二次从(15-1)+15 = 29 层往下扔. 碎了为: 15 + 29 + (16 ---28)= 14次

第三次 (14 - 1) + 29 = 42 碎了的话最多也是跑上14次而已...

该算法最糟糕的情况为14次或者13次就能得出临界点,,效率显然比我高的多..

毕竟.我是菜鸟.. 哈哈哈哈

还有的人的算法是 以10为单位扔玻璃球... 那么结果是:10,10, 11 .12.13.14.15.16.17.18.

显然,,15-1的这种算法比较均衡,从头到位都是13或者14... 而以10为单位的这种算法前期比较有效...

但在临界点==99层的情况,,要测18次才行..

而前一种算法则无论临界点在那层..都只要14次就能完成............

仔细思考后,,发现第一种算法仍然不是最有效的...

10 23(10+15-2) 35(23+15-3)............ 100

该算法扔玻璃球的效率为 10 13 13 13.........12

既

int n,s,L ;

L = 100 ; //楼层

n=sqrt(L) ; //给该楼开方==10 =.=!

s=n+sqrt(n); // 继续开方得到计算差值

while(n<=L)

{n = n + (n+s--); // 循环计算直到开关为假, >楼层数

................ //设置好临界点,满足临界点后标记然,退出循环; }

到网络上搜索了一下..有段不知出处的C++代码.

里面用暴力穷举出的最佳点是:9 22 34 45 55 64 72 79 85 90 94 97 99 100

9为开端,偶的是10为开端... 其后都是15-(2++)

第一部比偶的快了一点点.. 哈哈哈哈 次数是: 9 13 13 13..........12

但偶的算法适用于各种高度的楼层..只是两次开方,循环计算<sqrt(楼层高度)

对方的是暴力破解... 如果楼层过高...嗯嗯,家用计算机可能需要数年才能计算出来

没有最高效,只有更高效....继续学习ing..........