โปรแกรมหาจำนวนขวดน้ำสูงสุดที่ดื่มได้ใน Python

ภาพรวม

มีขวดน้ำเต็ม n ขวด สามารถแลกขวดว่าง m ขวด ได้ 1 ขวดเต็ม ดื่มขวดเต็มจะกลายเป็นขวดว่าง ต้องการหาจำนวนขวดสูงสุดที่ดื่มได้

ตัวอย่าง

n = 9, m = 3

ดื่ม 9 ขวด → ได้ 9 ขวดว่าง → แลก 3 ขวดเต็ม → ดื่ม 3 ขวด → ได้ 3 ขวดว่าง → แลก 1 ขวดเต็ม → ดื่ม 1 ขวด

รวม: 9 + 3 + 1 = 13 ขวด

ขั้นตอนการแก้ปัญหา

1. ตั้งค่า x = n (ขวดว่างปัจจุบัน), s = 0 (ขวดเพิ่มที่ดื่มได้), k = 0 (เศษขวดว่าง)
2. วนลูป while x >= m:
   • k = x % m (เศษขวดว่างที่แลกไม่ได้)
   • x = x // m (ขวดเต็มใหม่ที่แลกได้)
   • s += x (สะสมขวดที่ดื่มเพิ่ม)
   • x = x + k (ขวดว่างรอบถัดไป = ขวดเต็มใหม่ที่ดื่มแล้ว + เศษ)
3. คืนค่า n + s

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

def solve(n, m):
    x = n
    s = 0
    k = 0
    while x >= m:
        k = x % m
        x = x // m
        s += x
        x = x + k
    return n + s

n = 9
m = 3
print(solve(n, m))

อินพุต

9, 3

เอาต์พุต

13

ความซับซ้อน

• เวลา: O(log_m n)
• พื้นที่: O(1)