建表查表應用例

 通過遞推的方法計算一組數列，並將結果儲存在列表 f 中。這裡使用了一個類似於動態規劃的技巧，來生成數列中的每一個值。以下是詳細的解釋：

程式碼逐步解釋

1. 初始化列表 f：

   f = [0, 1, 2]
   

   • 初始化列表 f，設置了前三個已知的數值：f[0] = 0, f[1] = 1, f[2] = 2。

2. 遞推生成數列：

   for n in range(3, 101):
       f.append(sum(f[-3:]))
   

   • 使用 for 迴圈從 n = 3 開始，一直到 n = 100。
   • 每次迴圈執行時，會計算 f[-3:] 的總和，也就是列表中最後三個數的和，並將這個和添加到 f 中。
     • f[-3:] 會取列表中最後三個數值，例如在 n = 3 時會取 f[0], f[1], f[2] 的總和。
     • 因此，f[n] = f[n-1] + f[n-2] + f[n-3]，這是一個遞推關係。

3. 輸出指定數值：

   for i in [0, 1, 2, 3, 4, 5, 10, 20, 50, 90, 100]:
       print(f'f[{i}]={f[i]}')
   

   • 使用 for 迴圈輸出列表 f 中指定索引的數值。
   • 這裡會打印出 f[0], f[1], ..., f[100] 中的幾個特定值。

運作機制

1. 遞推公式：

   • 從 f[3] 開始，每一個 f[n] 都是 f[n-1] + f[n-2] + f[n-3] 的和。
   • 這表示每一個數都是前面三個數字相加的結果。

2. 初始值的重要性：

   • 初始值 f[0], f[1], f[2] 設定為 0, 1, 2，這確定了整個數列的生成規則。
   • 每個後續的值都基於這三個初始值進行遞推計算。

輸出結果解釋

f[0]=0
f[1]=1
f[2]=2
f[3]=3     # f[3] = f[2] + f[1] + f[0] = 2 + 1 + 0 = 3
f[4]=6     # f[4] = f[3] + f[2] + f[1] = 3 + 2 + 1 = 6
f[5]=11    # f[5] = f[4] + f[3] + f[2] = 6 + 3 + 2 = 11
f[10]=230  # 計算到第 10 項，結果是 230
f[20]=101902  # 計算到第 20 項，結果是 101902
f[50]=8864740270458  # 計算到第 50 項，結果是 8864740270458
f[90]=341699037144358680988654  # 計算到第 90 項
f[100]=151404293106684183601223222  # 計算到第 100 項

程式運作流程

1. 生成數列：

   • 程式先初始化前三個數值，然後通過遞推公式生成後面的數字，直到 f[100] 為止。
   • 由於每次只需要訪問最後三個數字，因此計算的效率很高。

2. 輸出結果：

   • 在生成 f[0] 到 f[100] 之後，程式根據指定索引印出對應的數值。

總結

• 動態規劃的概念： 利用遞推公式逐步生成數列，並且利用已經計算過的結果來計算新的值，避免了重複計算。
• 時間複雜度： 每次生成 f[n] 只需做常數次的加法操作，因此時間複雜度為 O(n)。
• 應用場景： 這種模式適合用於 Fibonacci 數列、樓梯問題等其他需要遞推計算的情境。