日前在网上看到道面试题颇有意思也细细研究番现将该题发布于此和各位交流下

　　某幢大楼有100层你手里有两颗模样玻璃珠当你拿着玻璃珠在某层往下扔时候定会有两个结果玻璃珠碎了或者没碎这幢大楼有个临界楼层低于它楼层往下扔玻璃珠玻璃珠不会碎等于或高于它楼层扔下玻璃珠玻璃珠定会碎玻璃珠碎了就不能再扔现在让你设计种方式使得在该方式下最坏情况扔次数比其他任何方式最坏次数都少也就是设计种最有效方式

　　例如:有这样种方式第次选择在60层扔若碎了介绍说明临界点在60层及以下楼层这时只有颗珠子剩下只能是从第层层层往上实验最坏情况要实验59次加上的前第次共60次若没碎则只要从61层往上试即可最多只要试40次加上的前共需41次两种情况取最多那种故这种方式最坏情况要试60次

　　那该如何设计方式呢？

　　仔细分析下关键是第次选择假设在第N层如果第次扔时候就碎了那么第 2颗珠子只能是从第1层开始层层往上试此时最坏情况为N-1次加上第次则共为N层那如果不碎呢第 2颗珠子会从N+1层开始试吗？很显然不会此时大楼还剩100-N层问题就转化为100-N2颗珠子请设计最有效方式

　　哦等等想到什么？呵呵我想到递归

　　定义个F(N)表示N层楼最有效方式最坏情况次数

　　通过上面分析有

　　F(N)=Min(Max(11+F(N-1))Max(21+F(N-2))……Max(N-11+F(1)))

　　F(1)=1

　　本面试题就是求F(100)

　　下面把解法代码赋予其后用是VB2005

　　

1 Dim F(100) AsInteger, i AsInteger, j AsInteger 2 Dim tC AsInteger 3 F(0) =0 4 F(1) =1 5 6 For i =2To100 7 F(i) =100 8 For j = i To1 Step -1 9 tC = IIf(j >1+ F(i - j), i, 1+ F(i - j))10 If tC < F(i) Then F(i) = tC11 Next12 Next13 14 For i =1To10015 16 Debug.Pr(F(i))17 Next