Chương trình tìm số ngày tối thiểu để ăn N quả cam bằng Python

Giả sử chúng ta có một số n. Vì vậy, hãy xem xét có n quả cam trong nhà bếp và chúng ta ăn một số quả cam này mỗi ngày, duy trì các quy tắc sau:1. Ăn một quả cam. 2. Nếu n chẵn thì ăn n / 2 quả cam. 3. Nếu n chia hết cho 3 có thể ăn 2 * (n / 3) quả cam. Chúng tôi chỉ có thể chọn một tùy chọn mỗi ngày. Chúng ta phải tìm số ngày tối thiểu để ăn n quả cam.

Vì vậy, nếu đầu vào là n =10, thì đầu ra sẽ là 4 vì

• Vào ngày 1 ăn 1 quả cam, 10 - 1 =9.

• Ngày thứ hai ăn 6 quả cam, 9 - 2 * (9/3) =9 - 6 =3.

• Ngày thứ 3 ăn 2 quả cam, 3 - 2 * (3/3) =3 - 2 =1.

• Vào ngày thứ 4 ăn quả cam cuối cùng 1 - 1 =0.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm fun (). Điều này sẽ mất n

• nếu n có trong bản ghi nhớ, thì

  • trả lại thư báo [n]

• nếu n <=2, thì

  • trả lại n

• memo [n]:=1 + tối thiểu (n mod 2+ fun (thương của n / 2)) và (n mod 3 + fun (thương của n / 3))

• trả lại thư báo [n]

• Từ phương thức chính, hãy thực hiện như sau

• memo:=a new map

• trả lại niềm vui (n)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơ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))

Đầu vào

7, [5,1,4,3]

Đầu ra

4