用 Python 编写程序，找出吃 N 个橙子的最少天数

pythonserver side programmingprogramming更新于 2025/12/1 23:08:17

假设我们有一个数字 n。假设厨房里有 n 个橙子，我们每天吃一些橙子，遵循以下规则:1. 只吃一个橙子。2. 如果 n 是偶数，则吃 n/2 个橙子。3. 如果 n 能被 3 整除，则可以吃 2*(n/3) 个橙子。我们每天只能选择一个选项。我们必须找到吃 n 个橙子的最少天数。

因此，如果输入为 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 在 memo 中，则
- 返回 memo[n]
如果 n<=2，则
- 返回 n
memo[n]:= 1 + (n mod 2+ fun(quotient of n/2)) 和 (n mod 3 + fun(quotient of n/3)) 的最小值
返回 memo[n]
从 main 方法，执行以下操作
memo:= a new map
返回 fun(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))