どのようにプログラムで2つのガラス球のパズルを解決するには？

Question

人気のpuzzleは約100階建ての建物と2つのガラス球です。私は解決策を見て、今私は困惑を解決することができるのだろうかプログラムによって。

簡略プログラムの解決策は完全な検索です（バックトラッキングを使用してコードすることができます）。プログラムによりが良いですか？解決方法私は動的プログラミングを使ってパズルを解くことができますか？

Answer 1

これは、卵落としパズルに似ています。私はあなたに動的プログラミングの基本戦略を教えてあげます。これをあなたの質問と密接に関連させてください。

# include <stdio.h> 
# include <limits.h> 

// A utility function to get maximum of two integers 
int max(int a, int b) { return (a > b)? a: b; } 

/* Function to get minimum number of trails needed in worst 
case with n eggs and k floors */ 
int eggDrop(int n, int k) 
{ 
/* A 2D table where entery eggFloor[i][j] will represent minimum 
    number of trials needed for i eggs and j floors. */ 
int eggFloor[n+1][k+1]; 
int res; 
int i, j, x; 

// We need one trial for one floor and0 trials for 0 floors 
for (i = 1; i <= n; i++) 
{ 
    eggFloor[i][1] = 1; 
    eggFloor[i][0] = 0; 
} 

// We always need j trials for one egg and j floors. 
for (j = 1; j <= k; j++) 
    eggFloor[1][j] = j; 

// Fill rest of the entries in table using optimal substructure 
// property 
for (i = 2; i <= n; i++) 
{ 
    for (j = 2; j <= k; j++) 
    { 
     eggFloor[i][j] = INT_MAX; 
     for (x = 1; x <= j; x++) 
     { 
      res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]); 
      if (res < eggFloor[i][j]) 
       eggFloor[i][j] = res; 
     } 
    } 
} 

// eggFloor[n][k] holds the result 
return eggFloor[n][k]; 
} 

/* Driver program to test to pront printDups*/ 
int main() 
{ 
    int n = 2, k = 36; 
    printf ("\nMinimum number of trials in worst case with %d eggs and %d floors is %d \n", n, k, eggDrop(n, k)); 
    return 0; 
} 

出力：卵2個と36階と最悪の場合、試験の 最小数は、私は申し訳ありませんが、前の答えはちょうどこの質問には何も正義もしない8

Answer 2

です。最善の時間はNのsqrtです。誰かがlognでこれを反論しようとしますが、申し訳ありません。

// my prentend breaking function 
function itBreaks(level) { 
    return level > 36; 
} 

function search(maxLevel) { 
    var sqrtN = Math.floor(Math.sqrt(maxLevel)); 
    var i = 0; 
    for (;i < maxLevel; i += sqrtN) { 
     if (itBreaks(i)) { 
      break; 
     } 
    } 

    for (i -= sqrtN; i < maxLevel; i++) { 
     if (itBreaks(i)) { 
      return i - 1; 
     } 
    } 
}