計算公式給出的序列的第 n 個成員
a[2 * n] = a[n] 1
a[2 * n 2] = a[2 * n 1] - a[n]
a[0] = a[1] = 1
n > 0
我嘗試了很多變體，但我找不到正確的變體。
n = int(input())
a = [0 for i in range(n 3)]
a[0] = a[1] = 1
i = 1
while i * 2 2 < n 3:
a[2 * i] = a[i] 1;
a[2 * i 1] = a[2 * i 2] a[i]
a[2 * i 2] = a[2 * i 1] - a[i]
i = 1
print(a[n])
uj5u.com熱心網友回復：
我們應該首先計算前幾個數字的預期輸出，讓我們首先了解序列是什么樣的，
a[0] = a[1] = 1
在第一個遞回關系中替換 n = 1 給出 a[2] = a[1] 1 = 2
在第二個遞回關系中替換 n = 1 給出 a[4] = a[3] - a[1]
但是根據第一個遞推關系a[4] = a[2] 1 = 3，所以3 = a[3] - 1，得到a[3] = 4
我們有a = {1, 1, 2, 4, 3, ... }
你的程式給a = {1, 1, 2, 1, 3, ...}
你的程式出了什么問題？
我們注意到，當 i = 1 時，該行的a[2 * i 1] = a[2 * i 2] a[i]計算結果為a[3] = a[4] a[1]。但是，當時還沒有評估 a[4]，導致輸出不正確。
因此，問題在于如何在 while 回圈中對陳述句進行排序。確保回圈中的陳述句只使用以后不會更改的值。
我們應該怎么做？
如果我們如下操作第二個遞回關系：
a[2 * i 2] = a[2 * i 1] - a[i]
a[2 * i 1] = a[2 * (i 1)] a[i]
使用第一個遞回關系，我們有
a[2 * i 1] = a[i 1] 1 a[i]
這應該解決問題，因為 2 * n 1 > n 1 對于所有正 n。
修改第二條陳述句后，檢查a是否計算了每個元素，并且應該完成。
筆記
還有一點需要注意的是，第三個陳述句是多余的，因為第一個陳述句a已經涵蓋了所有偶數元素。
事實上，如果您只需要計算序列的第 n 個成員，則存在更有效的方法，特別是對數解。
uj5u.com熱心網友回復：
我找到了決定
n = int(input())
k = n if n % 2 == 0 else n 1
a = [None for i in range(k 1)]
a[0] = a[1] = 1
def fill_list(a):
while None in a:
i = 1
while i * 2 <= k:
if a[i] != None:
a[2 * i] = a[i] 1
i = 1
i = 1
while i * 2 2 <= k:
if a[i * 2 2] != None and a[i] != None:
a[i * 2 1] = a[i * 2 2] a[i]
i = 1
fill_list(a)
print(a[n])
uj5u.com熱心網友回復：
你的第二個公式給出a[2n 2] = a[2n 1] - a[n]。這可以重寫：a[2n 1] = a[2n 2] a[n]這是a[n 1] a[n] 1從第一個公式。
我們可以使用它來撰寫一個在線性時間內運行的簡單動態規劃演算法：
def A(n):
a = [1] * (n 1)
for i in range(2, n 1):
if i%2 == 0:
a[i] = a[i//2] 1
else:
a[i] = a[i//2] a[i//2 1] 1
return a[n]
但是，我們可以注意到我們可以在對數時間內解決這個問題，因為我們可以計算a[n]和a[n 1]和。a[n//2]a[n//2 1]
如果n是偶數，那么a[n]=a[n//2] 1和a[n 1]=a[n//2] a[n//2 1] 1。如果n是奇數，那么a[n]=a[n//2] a[n//2 1] 1和a[n 1]=a[n//2 1] 1。這些只是我們已有公式的應用。
這給了我們這個解決方案：
def A2(n):
if n == 0:
return 1, 1
if n == 1:
return 1, 2
a, b = A2(n//2)
if n % 2 == 0:
return a 1, a b 1
else:
return a b 1, b 1
請注意，這將回傳 2 個值，但對于所有n, A(n) == A2(n)[0]。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/529171.html
標籤：Python算法
下一篇：二叉搜索樹懶洗掉Python