資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告