1. 问题
    300层楼,3个一样的小球,设计一个策略,得到小球摔碎的临界层数,并且要求最坏情况下所试次数最少。
  2. 理解问题
    题目显然有个隐含的假设,即如果小球在第n层摔碎,那么在第n+k层也摔碎,其中k>=1;
    还要注意的一点是,小球的临界层数在实验前是不可知的。
    什么是最坏情况? 
  3. 思路
    变量有3,(m,n,k),m是最底层数,n是最高层数,k是手头拥有的球数,假设F(m,n,k)是采取该策略所试次数
    当有3个小球时,情况稍微complex,可取的方法是由简入繁

    • 先考虑1个球的情况。
      因为仅有一个球,那么只能从低往高试,试到的第一个摔碎的层数,我们假设是p,那么F(1,300,1)=p
      最坏情况下,p=300,即最坏情况下要试300
    • 再考虑有2个球的情况
      此时F(1,300,2),可以先从(m+n)/2层扔,我们取下限,即(1+300)/2=150;有两种可能性,表格表示如下

      可能性 (m+n)/2  代价
      1 1
      2 不碎 1
      • 如果没碎,我们仍然有2个球,此时F(1,300,2)等价于求F(151,300,2)+1,抽象为F(下限((m+n)/2)+1,n,2)+1
        而F(151,300,2)的下一个试点是225,碎的情况包含了此时最坏的情况,此时最坏是(224-151+1)+2=76次
      • 如果碎了,我们仅剩1球,此时F(1,300,2)等价于求F(1,149,1)+1,抽象为F(m,下限((m+n)/2)-1,1)+1
        此时最坏情况是试150次

      按照这种策略扔,在有两个球的情况下,不但能得到临界层数,而且最坏情况是试150次。

    • 如果是3个球呢
      此时F(1,300,3),可以有两种策略

      • 先从(m+n)/2层扔,我们取下限,即(1+300)/2=150;有两种可能性,
        可以看得出来,按照这种策略,最坏情况是试76

        • 如果没碎,我们仍然有3个球,此时等价于求F(151,300,3)+1,抽象为F(下限((m+n)/2)+1,n,k)
          此时最坏情况是F(151,224,2)+1+1=37+2=39次
        • 如果碎了,此时手头还有两球,此时等价于求F(1,149,2)+1,抽象为F(m,下限((m+n)/2-1),k-1)
          此时最坏情况是试75+1=76次
      • 用两球分别在(m+n)/3和(m+n)*2/3层扔,我们取下限,有三种可能性,表格表示如下
        可以看得出来,按照这种策略,最坏情况是52

        可能性 (m+n)/3  第一次 (m+n)*2/3  第二次 代价
        1 1
        2 不碎 不碎 2
        3 不碎 2
        • 对于情况1,等价于求F(m,下限((m+n)/3)-1,2)+1,即F(1,100,2)+1=51次
        • 对于情况2,等价于求F(下限((m+n)*2/3)+1,n,3)+2,即F(201,300,3)+2
          F(201,300,3)等价于F(1,100,3) ,而F(1,100,3)肯定比52要小。。。。。
        • 对于情况3,等价于求F(下限((m+n)/3)+1,下限((m+n)*2/3)-1,2)+2,即F(101,199,2)+2=50+2=52次
        • 额外思路
          要是能让F(n,300,3)等于F(1,n,2)如此还能让最坏情况比52更小。。。。。
  4. 结论和直观图示
    根据3的思路分析,答案就很明显了,用递归公式表示如下
    image
  5. 后记
    F(1,n,1)=n
    F(m,n,k)=F(1,n-m+1,k),所以F(m,n,1)=F(1,n-m+1,1)=n-m+1
    F(m,m,k)=1
    F(1,n,2)=(1+n)/2取下限
Advertisements