两个鸡蛋和楼房高度问题

liuii

这不是去年某期程序员杂志的题目么？

yang_bigarm

这个是我一个同学去EMC参加面试的时候遇到的问题。

楼上 lulijie 的答案是正确的，分析的求和公式也很正确，但是这个问题跟数学归纳法没有什么关系，这个问题的主要实质是决策树的平衡，如果 lulijie 能把决策树也贴出来就很好了。

lulijie

决策树这个概念我可不懂，我该描述的都描述了，只差 程序的代码（ VB6.0）没公布，若大家对 其 感兴趣，我马上可以公布。

骰迷

LULIJIE是暴力解題的，不過要用樹的話，要嘗試好些時間才猜得出來

骰迷

如果第一次破了，那麼便要由頭試起，最少步>=第一次撞那個數
主要是讓右邊的態樹（第一次不破之後的動作）不要高過左邊

[ 本帖最后由 骰迷 于 2009-3-26 18:47 编辑 ]

lulijie

也不能说暴力。
应该说用递推方法求解，只不过把比较大小的过程交过了电脑而已。
先从S(1),推导出S(2),
再从S(1)、S(2)推导出S(3),
再从S(1)、S(2)、S(3)推导出S(4),
以此类推，直至推出S(100)。
跟暴力解法那是天壤之别。

骰迷

算我電腦知識差罷，本人是不太了解程序碼解題的

lulijie

我们把n层楼的最佳数列的第一项值，即最先扔鸡蛋的楼层  为 k
观察上述n=1-100  的k值，发现一个明显的规律：
以下把只有一个k值的列举如下，
n：k；
1：1；
2：1；
4：2；
7：3；
11：4；
16：5；
22：6；
29：7；
37：8；
46：9；
56：10；
67：11；
79：12；
92：13；
106：14；     这是我的推测
--------------------------
其他n，如70，从上表查它介于67和79之间，所以它的k值可取11或12。
所以只要记住上述表的值就可。
上述表有个很明显的规律。
第二行的n比第一行的多1，
第三行的n比第二行的多2，
第m行的n比上一行多m-1。
用通项表示  n(m)=1+m(m-1)/2       n(m)表示m行的n值。而k值等于m-1，（第一行除外）
所以不用记忆：只要记住
          n=1，                      k=1
          n=1+m(m-1)/2         k=m-1                          m>1
         介于两者之间的        k可以取两端的值。

解题过程：
    n=100
   因为    1+14*（14-1）/2=92           k=13
              1+15*（15-1）/2=106        k=14
  因为100介于上述两者之间，所以k可取13或14
不妨取14，    100-14=86                    即第一次楼层   14
              1+13*（13-1）/2=79      k=12
              1+14*（14-1）/2=92      k=13
      86介于上述两者之间，所以k可取12或13      
不妨取12，    86-12=74                        即第二次楼层  14+12=26
       。。。。。。。
       。。。。。。。
最后可得到金眼睛得出的数列：
   14、26、37、47、56、64、72、79、85、90、94、97、99、100
    知道了最佳数列，那么最少步数就举手可得。
---------------------------------------------------------
关键是我得出的上述蓝字部分的结论是不是对于所有的n都成立了？  n不仅仅限于100以内。

lulijie

S(n)的值也有明显的规律
1，
1+2，
1+2+3，1+2+3+3，
1+2+3+3+4，1+2+3+3+4+4，1+2+3+3+4+4+4，
1+2+3+3+4+4+4+5，。。。。。。

若m(m+1)/2 +2 <= n<= (m+1)(m+2)/2 +1，        那么  S(n)=S(n-1)+m+2。         
或者表示成以下递推公式：
      S(n)=S(n-1)+  int( sqr(2n-3.75)-0.5 ) +2              int是取整函数  ，sqr 是开根号。
      S(1)=1

ares_g

原帖由 东莞的8 于 2009-3-23 15:15 发表
随便试试：先从10楼开始试，每次隔10层，到摔坏的时候再退到未摔坏的10层先开始每次上一层试，这样的话最不幸的情况是要19次。

这个比较有道理，不过我觉得是18次，因为第100层是不用扔的。