โปรแกรมหาจำนวนวันขั้นต่ำในการกิน N ส้มใน Python

สมมติว่าเรามีตัวเลข n ดังนั้น ให้พิจารณาว่าไม่มีส้มในครัว และเรากินส้มเหล่านี้ทุกวันโดยรักษากฎเหล่านี้:1. กินส้มลูกเดียว 2. ถ้า n เป็นเลขคู่ ให้กินส้ม n/2 ผล 3. ถ้า n หารด้วย 3 ลงตัวสามารถกินส้ม 2*(n/3) ได้ เราสามารถเลือกได้เพียงตัวเลือกเดียวในแต่ละวัน เราต้องหาจำนวนวันขั้นต่ำที่จะกินส้มได้

ดังนั้นหากอินพุตเท่ากับ n =10 เอาต์พุตจะเป็น 4 เพราะ

• ในวันที่ 1 กินส้ม 1 ผล 10 - 1 =9

• วันที่ 2 กินส้ม 6 ผล 9 - 2*(9/3) =9 - 6 =3.

• วันที่ 3 กินส้ม 2 ผล 3 - 2*(3/3) =3 - 2 =1.

• วันที่ 4 กินส้มสุดท้าย 1 - 1 =0

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน fun() นี่จะใช้เวลา n

• ถ้า n อยู่ในบันทึกแล้ว

  • บันทึกช่วยจำ[n]

• ถ้า n<=2 แล้ว

  • กลับ n

• memo[n]:=1 + ขั้นต่ำของ (n mod 2+ fun(quotient of n/2)) และ (n mod 3 + fun(quotient of n/3))

• บันทึกช่วยจำ[n]

• จากวิธีหลัก ให้ทำดังนี้

• บันทึก:=แผนที่ใหม่

• คืนความสนุก(n)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

def solve(n):
   def fun(n):
      if n in memo:
         return memo[n]
      if n<=2:
         return n
      memo[n]=1+min(n%2+fun(n//2),n%3+fun(n//3))
      return memo[n]
   memo={}
   return fun(n)

n = 12
print(solve(n))

อินพุต

7, [5,1,4,3]

ผลลัพธ์

4