关于这个问题,俺写的帖子一共有这么多,

直到去baidu面试,回来再仔细思考后,发现那些帖子的回答都不严谨。

在这片文章里,经典仍鸡蛋问题,今天在baidu面试时被问了,俺还在思考到底是那个面试官的提示有道理,还是俺前面的某篇帖子有道理?

经过再次思考,发现前面的回答都不严谨,正确的答案在这里。(老实说,第一次接触这个题时的第一反应,在这个答案里都能得到解决)
要弄清什么是最坏情况?即该算法应用于小球临界值取尽所有值(这里是1-300)的状况下,能得到的最大尝试次数;
而最坏情况所试次数最少即该算法的最大尝试次数在所有算法中最小。

首先,假设临界点P的定义是,P不碎,<=(P-1)全碎,那么递归式为

minmaxegg

其次,该递归式可以用java表示为Main.java

再次,运行这个程序,它告诉我们f(100,3)= 9。

思考从一开始就要把变量x和i正确识别出来啊;

使用特殊推导一般的手段有时是危险的,比如这里用解f(m,2)的方法(每次仍一个球)来解f(m,3)就不成立;

  • 第一种人能做到这点,一般—>特殊;是天才
  • 第二种人能做到这点,所有特殊—>一般;是地才
  • 第三种人能做到这点,某些高阶特殊;是人才
  • 第四种人能做到这点,某些低阶特殊;是庸才

以上关于天才,地才,人才和庸才的结论纯开玩笑,哈哈。

Advertisements