我在求職面試中有以下問題：
“一個盒子里有很多巧克力，每次只能取出 1 個或 3 個。這個盒子有多少種方法可以倒空？”
起初，我嘗試用遞回來做，它奏效了。這是以下python代碼：
def numberOfWays(n):
if n <= 2:
return 1
else:
return numberOfWays(n - 3) numberOfWays(n - 1)
但是，該網站不允許使用遞回。我試過很多次了，就是不能把它變成一個迭代函式，因為在原來的函式上，我必須輸出兩個結果。
uj5u.com熱心網友回復：
這個問題與斐波那契非常相似，您可以創建一個比遞回解決方案性能更高的迭代解決方案。我稍微修改了遞回函式，因為通過閱讀問題，我將 n = 0 解釋為有 0 種方法可以通過洗掉 1 或 3 個專案來清空框。這是修改后的遞回函式。
def numberOfWays(n):
if n <= 0:
return 0
elif n in (2, 1):
return 1
elif n == 3:
return 2
else:
return numberOfWays(n - 3) numberOfWays(n - 1)
這是一個迭代解決方案，它將使用比 Michael 提供的記憶體更少的記憶體，因為它只存盤 3 個數字而不是系列中最多 n 個的每個數字：
def numberOfWays(n):
if n == 0:
return 0
elif n <= 2:
return 1
elif n == 3:
return 2
a, b, c, = 1, 1, 2
for i in range(n-3):
a, b, c, = b, c, c a
return c
我計算了迭代函式的回圈迭代次數和遞回函式的函式呼叫次數，以顯示它的性能有多好。
Iterative
n of 10 = 28 | Loop Iterations: 7
n of 9 = 19 | Loop Iterations: 6
n of 8 = 13 | Loop Iterations: 5
n of 7 = 9 | Loop Iterations: 4
n of 6 = 6 | Loop Iterations: 3
n of 5 = 4 | Loop Iterations: 2
n of 4 = 3 | Loop Iterations: 1
n of 3 = 2 | Loop Iterations: 0
n of 2 = 1 | Loop Iterations: 0
n of 1 = 1 | Loop Iterations: 0
n of 0 = 0 | Loop Iterations: 0
Recursive:
n of 10 = 28 | Function calls: 37
n of 9 = 19 | Function calls: 25
n of 8 = 13 | Function calls: 17
n of 7 = 9 | Function calls: 11
n of 6 = 6 | Function calls: 7
n of 5 = 4 | Function calls: 5
n of 4 = 3 | Function calls: 3
n of 3 = 2 | Function calls: 1
n of 2 = 1 | Function calls: 1
n of 1 = 1 | Function calls: 1
n of 0 = 0 | Function calls: 1
如果在軟體中使用此函式，無論底層實作如何，都將使用相同的引數多次呼叫該函式，快取/記憶結果會很好。但是，這可能無法幫助您通過在線編碼挑戰中的所有自動化測驗。
uj5u.com熱心網友回復：
將您的遞回演算法轉換為簡單的迭代解決方案仍將具有 O(2^n) 的運行時復雜度。
def NoW_iter(n):
if n <= 2: return 1
c = 2
l = [n-3, n-1]
while l:
i = l.pop()
if i > 2:
c = 1
l = [i-3, i-1]
return c
為您的演算法修復運行時問題的一種簡單方法是記憶中間結果
from functools import lru_cache
@lru_cache(maxsize=None)
def numberOfWays(n):
if n <= 2:
return 1
else:
return numberOfWays(n - 3) numberOfWays(n - 1)
這可以通過迭代方法以及 O(n) 的運行時復雜度來完成。
def NoW_memo(n):
d = {0: 1, 1: 1, 2: 1}
for i in range(3, n 1):
d[i] = d[i-3] d[i-1]
return d[n]
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/417792.html
標籤：
上一篇：遞回函式拼寫元素
下一篇：JS中的遞回函式