卵を投げる(ガラス玉や碁)

1875 ワード


テーマ:100階建てのビルで、あなたの手には同じ卵(ガラス玉や囲碁)が2つあります.このビルのある階から卵(ガラス玉や碁))を投げると割れてしまい、あなたの手の中のこの2つの卵(ガラス玉や碁)で、その臨界レベルを知るのに最適な戦略を見つけます.
分析:この問題の比較的直観的な考えは二分で探すが、二分の解法は最適ではないはずだ.ここでは,動的計画の構想によって解くことを議論する.ここでの最適戦略とは、この戦略の下でどの臨界レベルが何層目であっても、テストの回数が最も少ないことを意味する.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")を仮定すると,2つのケースが発生する.
  • (1)ガラス球は砕けて、第1から第r層のビルの中で必ず1層が臨界層であることを説明して、問題は1つのサブ問題に転化します:F(r,k-1)
  • を求めます
  • (2)ガラス球は砕けないで、臨界層が第r+1層から第n層のこのn-r層のビルの中で、問題はサブ問題に転化することを説明します:F(n-r,k)
  • を求めます
    最悪の場合の投球戦略に必要な試験回数の最小値を考慮したので,この2つの場合の大きな値をとり,可能なrごとに遍歴し,その最小値をとるとF(n,k)が得られる.実装コードは次のとおりです.
     
    #include<iostream>
    using namespace std;
    
    #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 = 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)
    }
    
    int main()
    {
    	int floor=100;
    	int ball=2;
    	cout<<dp(floor,ball);
    }