首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 其他相关 >

【转】投鸡蛋(玻璃球或围棋)

2012-09-07 
【转】抛鸡蛋(玻璃球或围棋)?题目:一个100层的大厦,你手中有两个相同的鸡蛋(玻璃球或围棋)。从这个大厦的某一

【转】抛鸡蛋(玻璃球或围棋)

?

题目:一个100层的大厦,你手中有两个相同的鸡蛋(玻璃球或围棋)。从这个大厦的某一层扔下鸡蛋((玻璃球或围棋))就会碎,用你手中的这两个鸡蛋(玻璃球或围棋),找出一个最优的策略,来得知那个临界层面。

分析:这道题比较直观的想法是通过二分来寻找,但是二分的解法应该不是最优的。这里讨论通过动态规划的思路来求解。这里的最优策略指的是在这种策略下无论哪个临界层面在第几层,测试的次数都最少。设F(n,k)为用k个玻璃球来测试n层大厦的临界层的最少次数,状态转移方程如下:
F(n,k)=min{max{F(r,k-1), F(n-r,k)}+1, 1<=r<=n},边界条件:F(n,1)=n-1, F(1,k)=F(0,k)=0
状态转移方程可以这样来考虑,假设在n层楼中的第r层抛一次(对应方程中的"+1"),会有两种情况发生:

  • (1)玻璃球碎,说明在第1到第r层楼中必有一层为临界层,问题转化为一个子问题:求F(r,k-1)
  • (2)玻璃球不碎,说明临界层在第r+1层到第n层这n-r层楼中,问题转化为子问题:求F(n-r,k)

    因为考虑的是最坏情况下抛球策略的所需测试次数的最小值,所以取这两种情况中的较大值,并遍历每一个可能的r,取其最小值即得到F(n,k)。实现代码如下:

    ?

    #define MAX_FLOOR 512  #define MAX_BALL  100    int dp(int n, int k)  {      if(k<1 || n<1) return -1;            if(k==1) return n-1;      if(n==1) return 0;        int M[MAX_BALL][MAX_FLOOR];      int i,j,r;      int temp, min;        for(i=0;i<=k;i++) M[i][0]=M[i][1]=0;    //F(1,k)=F(0,k)=0      for(j=2;j<=n;j++) M[1][j]=j-1;            //F(n,1)=n-1        /*         状态转移方程:         F(n,k)=min{max{F(r,k-1)+1, F(n-r,k)+1}, 1<=r<=n}     */      for(i=2;i<=k;i++)          for(j=2;j<=n;j++)          {              min = numeric_limits<int>::max();              for(r=1;r<=j;r++)              {                  temp = max(M[i-1][r], M[i][j-r])+1;                  if(temp<min)                      min = temp;              }              M[i][j] = min;          }        return M[k][n];//F(n,k)  }  

    ?

    ?

    ?转载自程序员面试之家

    ?

    ?

热点排行