Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:
Đề bài – Muốn biết tầng nào trong tòa 40 tầng an toàn để rổ trứng, tầng nào làm vỡ trứng. Cần số lần thử tối thiểu trong trường hợp xấu nhất.
Hãy quan sát giải pháp trong triển khai dưới đây:
Ví dụ
# quy hoạch động
INT_MAX = 32767
# lấy số lần thử tối thiểu
def eggDrop(n, k):
# khởi tạo
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
# 1 trứng cần j lần
for j in range(1, k + 1):
eggFloor[1][j] = j
# điền bảng
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("Số lần thử tối thiểu worst-case với", n, "trứng và", k, "tầng là", eggDrop(n, k))
Kết quả
Số lần thử tối thiểu worst-case với 4 trứng và 40 tầng là 6
Kết luận
Trong bài này, chúng ta đã học cách làm chương trình Python bài toán rổ trứng.