โปรแกรม Python สำหรับ Egg Dropping Puzzle (ปริศนาทิ้งไข่)

ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:

ข้อความปัญหา — สมมติว่าเราต้องการทราบว่าชั้นไหนในอาคาร 40 ชั้น ปลอดภัยที่จะทิ้งไข่ลงมา และชั้นไหนจะทำให้ไข่แตกเมื่อตกถึงพื้น ด้วยการใช้ไข่ เราต้องการแสดงจำนวนครั้งทดสอบ (trials) น้อยที่สุดเพื่อตรวจสอบชั้นต่างๆ

มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:

ตัวอย่างโค้ด

# Dynamic Programming
INT_MAX = 32767

# หาจำนวนครั้งทดสอบน้อยที่สุด
def eggDrop(n, k):
    # เริ่มต้น
    eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)]
    # กรณีฐาน
    for i in range(1, n + 1):
        eggFloor[i][1] = 1
        eggFloor[i][0] = 0
    # เราต้องการ j ครั้งเสมอ
    for j in range(1, k + 1):
        eggFloor[1][j] = j
    # เติมค่าส่วนที่เหลือ
    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]

# โปรแกรมหลัก
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

ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน

สรุป

ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python สำหรับ Egg Dropping Puzzle โดยใช้ Dynamic Programming