数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 程序：查找吃 N 个橙子所需的最少天数
假设我们有一个数字 n。因此，假设厨房里有 n 个橙子，我们每天吃掉一些橙子，并遵循以下规则：1. 吃一个橙子。2. 如果 n 是偶数，则吃 n/2 个橙子。3. 如果 n 可以被 3 整除，则可以吃 2*(n/3) 个橙子。我们每天只能选择一个选项。我们必须找到吃掉 n 个橙子所需的最少天数。
因此，如果输入类似 n = 10，则输出将为 4，因为
第一天吃 1 个橙子，10 - 1 = 9。
第二天吃 6 个橙子，9 - 2*(9/3) = 9 - 6 = 3。
第三天吃 2 个橙子，3 - 2*(3/3) = 3 - 2 = 1。
第四天吃掉最后一个橙子 1 - 1 = 0。
为了解决这个问题，我们将遵循以下步骤 -
定义一个函数 fun()。它将接收 n
如果 n 在 memo 中，则
返回 memo[n]
如果 n<=2，则
返回 n
memo[n]:= 1 + (n mod 2+ fun(n/2 的商)) 和 (n mod 3 + fun(n/3 的商)) 的最小值
返回 memo[n]
从主方法中，执行以下操作
memo:= 一个新的映射
返回 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))输入
7, [5,1,4,3]
输出
4
更新于: 2021年10月6日
238 次查看
广告