楼层扔鸡蛋问题

楼层扔鸡蛋问题 

题目

　　“两个软硬程度一样但未知的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置，可以摔碎两个鸡蛋。”

 

分析

     这是典型的动态规划问题。假设f[n]表示从n层楼找到摔鸡蛋不碎安全位置的最少判断次数。假设第一个鸡蛋第一次从第i层扔下，如果碎了，就剩一个鸡蛋，为确定下面楼层中的安全位置，必须从第一层挨着试，还需要i-1次；如果不碎的话，上面还有n-i层，剩下两个鸡蛋，还需要f[n-i]次（子问题，实体n层楼的上n-i层需要的最少判断次数和实体n-i层楼需要的最少判断次数其实是一样的）。因此，最坏情况下还需要判断max(i-1,f[n-i])次。

　　状态转移方程：f[n] = min{ 1+max(i-1,f[n-i]) | i=1..n }   初始条件: f[0]=0（或f[1]=1）

 

解法

　　实际上，两个鸡蛋的情况用数学方程就可以解决，前提是你知道该怎么扔：

　　一种想法是第一个鸡蛋折半搜索，如100层的楼，先从50层扔下去，如果碎了则第二个鸡蛋在1~49层楼中自底向上线性搜索；如果没碎则第一个鸡蛋再从75层扔。如果这次碎了则第二个鸡蛋在51~74层楼中自底向上线性搜索；如果还没碎则第一个鸡蛋再从88层扔，依此类推。这种方法不是最优，因为最坏情况下安全位置恰好是49层，需要尝试50次。

　　正确的方法是先假设最少判断次数为x，则第一个鸡蛋第一次从第x层扔（不管碎没碎，还有x-1次尝试机会）。如果碎了，则第二个鸡蛋在1～x-1层中线性搜索，最多x-1次；如果没碎，则第一个鸡蛋第二次从x+(x-1)层扔（现在还剩x-2次尝试机会）。如果这次碎了，则第二个鸡蛋在x+1～x+(x-1)-1层中线性搜索，最多x-2次；如果还没碎第一个鸡蛋再从x+(x-1)+(x-2)层扔，依此类推。x次尝试所能确定的最高楼层数为x+(x-1)+(x-2)+...+1=x(x+1)/2。

　　比如100层的楼，只要让x(x+1)/2>=100，得x>=14，最少判断14次。具体地说，100层的楼，第一次从14层开始扔。碎了好说，从第1层开始试。不碎的话还有13次机会，再从14+13=27层开始扔。依此类推，各次尝试的楼层依次为:

　　14，  27 = 14 + 13，  39 = 27 + 12 ， ...  ， 99 = 95 + 4，  100

 

推广

　　现在推广成n层楼，m个鸡蛋：

　　还是动态规划。假设f[n,m]表示n层楼、m个鸡蛋时找到摔鸡蛋不碎的最少判断次数。则一个鸡蛋从第i层扔下，如果碎了，还剩m-1个鸡蛋，为确定下面楼层中的安全位置，还需要f[i-1,m-1]次（子问题）；不碎的话，上面还有n-i层，还需要f[n-i,m]次（子问题，实体n层楼的上n-i层需要的最少判断次数和实体n-i层楼需要的最少判断次数其实是一样的）。 

　　状态转移方程：f[n,m] = min{ 1+max(f[i-1,m-1], f[n-i,m]) | i＝1..n }  初始条件：f[i,0]=0（或f[i,1]=i），对所有i 

 

代码

解法一

#include <iostream>  
#include <cstdio> 

using namespace std;  

#define M 100  
#define N 100  

int dp[101][101];  

int main ()  
{
    int i,j,k,m,n;   

    memset(dp,0,sizeof(dp));  

    for(i = 1; i <= N; i++)      
        dp[1][i] = i;    

    for(j = 2; j <= M; j++)  
    {
        for(k = 1; k <= N; k++)  
        {  
            dp[j][k] = 1 + max(dp[j-1][0], dp[j][k-1]);   
            for(i = 2; i <= k; i++)           
                dp[j][k] = min(dp[j][k], 1 + max(dp[j-1][i-1], dp[j][k-i])); 
        }    
    }

    while(scanf("%d %d", &m, &n) != EOF)    
        printf("%d
", dp[m][n]);  

    return 0; 
}  

解法2

/*
 *
 * m个球，n层楼，最少几次（假设为最坏情况下的最少次数，不是平均次数） 
 * 能判断从哪层楼开始扔球会坏掉，假设球摔坏的概率与楼层高度无关且每层相等, 
 * 并且不一定肯定有一层能摔坏
 * 递推公式：
 * b(m,n) = min{ max{ b(m-1,k-1)+1, b(m,n-k)+1 } } 
 *
 *
 */
#include <stdio.h>

int max(const int &a, const int &b){
    return a>b ? a : b;
}

int min(const int &a, const int &b){
    return a>b ? b : a;
}

//b(m,n) = min{ max{ b(m-1,k-1)+1, b(m,n-k)+1 } }
//n>=1,m>=2,1<=k<=n
//For convenience, we handle m=1, n=0 separately
void mball_nfloor(int m, int n){
    if(m<=0 || n<=0)
        return;
    int result[m+1][n+1];
    int temp_min = n+1;
    int temp_max = 0;
    //for n==0 and n==1
    for(int i=0;i<=m;i++){
        result[i][0] = 0;
        result[i][1] = 1;
    }
    //for m==0 and m==1
    for(int i=0;i<=n;i++){
        result[1][i] = i;
        result[0][i] = 0;
    }
    if(m>1 && n>1){
        //start from 2 balls
        for(int a=2;a<=m;a++){
            //start from 1 floors
            for(int i=1;i<=n;i++){
                for(int k=1;k<=i;k++){
                     temp_max = max(result[a-1][k-1]+1, result[a][i-k]+1);
                    temp_min = min(temp_min, temp_max);
                }
                result[a][i] = temp_min;
                temp_min = n+1;
            }
        }
    }
    for(int i=1;i<=m;i++){
        fprintf(stdout, "
======%d个球，%d层，每种楼层各种丢球方法中最坏情况下的最少丢球次数======
", i, n);
        for(int j=1;j<=n;j++){
            fprintf(stdout, "%d	", result[i][j]);
        }
        fprintf(stdout, "
");
    }
}

int main(int argc, char **argv)
{
    mball_nfloor(2, 100);
    
    return 0;
}

ref：http://blog.163.com/ty_sky0908/blog/static/133360335201101155853282/