01有一种玻璃杯质量确定但未知,需要检测。
有一栋100层的大楼,该种玻璃杯从某一层楼扔下,刚好会碎。
现给你两个杯子,
方案一:二分法从50楼扔下,没碎的话,再扔75楼,再没碎我扔88楼,依次下去貌似很快就可以锁定楼层。不过,很不巧,第一次从50层楼扔下去就碎了,这个时候就只能从1层开始慢慢的的一层一层地扔,如果杯子的质量是刚好在49层碎掉的话,那么最差的情况是需要扔50次。方案二:分段查找区间法核心点:先分区间的扔,再慢慢地一层一层地扔。举个例子:先从第10楼扔,再从第20楼扔,依次下去,如果到某一层碎掉,比如60层碎掉了,我再从51楼开始扔,这样比前面的二分法更快,因为即使又很不巧,杯子的质量比较好,在99楼才会刚好碎掉。这样的话,在这种最差的情况下,也只需要扔19次就能找到目标楼层。方案三:基于数学方程的方法事实上,这算是一道趣味问题,可以从数学的角度进行分析。假设最少尝试次数为x,那么,第一个杯子必须要从第x层扔下,因为:如果碎了,前面还有x-1层楼可以尝试,如果没碎,后面还有x-1次机会。如果没碎,第一个杯子,第二次就可以从x+(x-1)层进行尝试,这里加上x-1,是因为当此时,第一个杯子碎了,第二个杯子还有可以从x+1到(x+(x-1)-1)层进行尝试,有x-2次机会。如果还没碎,那第一个杯子,第三次从x+(x-1)+(x-2)层尝试。不管杯子碎或者没碎,都有x-3次尝试机会,依次类推。那么经过x次的尝试可以确定最高的楼层为x+(x-1)+(x-2)+…+1=x(x+1)/2。那反过来,当最高楼层是100层,最少需要多少次呢?即x(x+1)/2>=100,得到x>=14,最少要尝试14次。
来自:SQL语句-排序相关