卵を落とすパズルのためのPythonプログラム

この記事では、以下に示す問題ステートメントの解決策について学習します。

問題の説明 − 40階建ての建物のどの階から卵を落とすのが安全で、どれが卵の助けを借りて着陸時に卵を損傷させるのかを知りたいとします。ストーリーを確認するには、最小数のトレイルを表示する必要があります。

次に、以下の実装のソリューションを見てみましょう-

例

# dynamic programming
INT_MAX = 32767
# to get minimum trials
def eggDrop(n, k):
   # intialization
   eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)]
   # base case
   for i in range(1, n + 1):
      eggFloor[i][1] = 1
      eggFloor[i][0] = 0
   # We always need j trials
   for j in range(1, k + 1):
      eggFloor[1][j] = j
   # Fill rest of the entries
   for i in range(2, n + 1):
      for j in range(2, k + 1):
         eggFloor[i][j] = INT_MAX
         for x in range(1, j + 1):
            res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x])
            if res < eggFloor[i][j]:
               eggFloor[i][j] = res
   return eggFloor[n][k]
# main
n = 4
k = 40
print("Minimum number of trials in worst case scenario with " + str(n) + " eggs and "+ str(k) + " floors is " + str(eggDrop(n, k)))

出力

Minimum number of trials in worst case scenario with 4 eggs and 40 floors is 6

すべての変数はローカルスコープで宣言されており、それらの参照は上の図に示されています。

結論

この記事では、卵を落とすパズル用のPythonプログラムを作成する方法について学びました。