Trong bài viết này, chúng ta sẽ tìm hiểu về giải pháp cho câu lệnh vấn đề được đưa ra bên dưới.
Tuyên bố sự cố - Giả sử chúng ta muốn biết câu chuyện nào trong một tòa nhà 40 tầng là an toàn để thả trứng xuống và câu chuyện nào sẽ khiến trứng bị hỏng trên đất liền với sự trợ giúp của trứng. Chúng tôi cần hiển thị số lượng đường mòn tối thiểu để kiểm tra các câu chuyện.
Bây giờ chúng ta hãy quan sát giải pháp trong việc triển khai bên dưới -
Ví dụ
# 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))) Đầu ra
Minimum number of trials in worst case scenario with 4 eggs and 40 floors is 6
Tất cả các biến được khai báo trong phạm vi cục bộ và các tham chiếu của chúng được hiển thị trong hình trên.
Kết luận
Trong bài viết này, chúng ta đã tìm hiểu về cách tạo Chương trình Python cho Câu đố thả trứng.