一道腾讯面试题:厉害了我的杯
问题分析
-
2 个杯子的脆弱程度是一样的
-
如果杯子从 N 楼扔下来没有碎,那么它从小于 N 楼扔下来,也不会碎
-
如果杯子从 N 楼扔下来碎了,那么它从大于 N 楼扔下来,也一定会碎
-
一个扔出去但没有碎的杯子,可以继续被用于试验
-
碎了的杯子将无法再继续试验。
举个栗子:
如果从 x 楼扔下,没碎,在 x+1 楼扔下,碎掉了,即证明找到了 x+1 是刚好碎掉的楼层。
那么问题来了:怎样才能最快速的找到这个楼层?
问题的解决有很多种方案,注意点就是找到的最佳方案是能在各种情况下都能快速地找到目标楼层。
总结一下:我们的终极目的是要找出连续的两层楼 x 与 x + 1 ,在楼层 x 杯子没有摔碎,在楼层 x + 1 杯子碎了,问题的关键之处在于,测试之前,并不知道杯子会在哪一层摔碎,需要找到的是一种测试方案,这种测试方案,无论杯子会在哪层被摔碎,都至多只需要 m 次测试,在所有这些测试方案中, m 的值最小。
------------------------------一条思考的分界线------------------------------
题目:成功率跟运气有关运气,尝试次数可能情况1、2、3······100
目的:最差情况尝试次数最小
思想:均分次数(类似五笔把汉字均分到26个字母)
方法:划分最小区间
解:设最小区间大小为X
能判定的最大范围 res = X + (X-1) + (X-2) + ··· + 2
由题意得:res >= 100
解的 X = 14
最差情况14次 期望值9次多 平均次数10次