Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

계란 던지기 퍼즐을 위한 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 프로그램

모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.

결론

이 기사에서 우리는 계란 던지기 퍼즐을 위한 Python 프로그램을 만드는 방법에 대해 배웠습니다.