透過記憶化（Memoization）來加速計算過程

 使用遞迴和動態規劃的技術來計算一個遞迴函式 f(n) 的值，並且透過記憶化（Memoization）來加速計算過程。以下是詳細的解釋：

程式碼逐步解釋

1. t = [0] * 1000：

   t = [0] * 1000
   

   • 這行程式碼初始化了一個長度為 1000 的列表 t，每個元素都設為 0。
   • t 用來儲存計算過的 f(n) 值，這樣可以避免重複計算同一個數字，提升效率。

2. f(n) 函式：

   def f(n):
       if n < 3:
           return n
       if t[n] != 0:
           return t[n]
       t[n] = f(n - 1) + f(n - 2) + f(n - 3)
       return t[n]
   

   • 目標： 計算 f(n) 的值，根據題意的遞迴關係。
   • 遞迴終止條件： 當 n < 3 時，直接返回 n，因為這是已知的基礎情況。
   • 記憶化：
     • 如果 t[n] 不等於 0，表示 f(n) 之前已經計算過，直接返回 t[n]。
     • 否則，遞迴計算 f(n - 1) + f(n - 2) + f(n - 3)，將結果儲存在 t[n] 中，然後返回 t[n]。
   • 優點： 通過記憶化，避免了重複的遞迴計算，提升了效率。

3. 測試程式：

   for i in [1, 2, 3, 4, 5, 10, 100, 200, 300]:
       print(f'f({i})={f(i)}')
   

   • 對於給定的 n 值 [1, 2, 3, 4, 5, 10, 100, 200, 300]，逐一計算並印出 f(n) 的結果。
   • 這會測試函式在小值和極大值的情況下的表現。

運作機制

1. 遞迴關係：

   • 當 n >= 3 時，f(n) 由以下遞迴式表示：

     f(n) = f(n - 1) + f(n - 2) + f(n - 3)
     

   • 這表示每個 f(n) 都是 f(n-1), f(n-2), f(n-3) 的和。

2. 記憶化的作用：

   • 例如計算 f(10) 時，會計算 f(9), f(8), f(7)。計算 f(9) 時又需要 f(8), f(7), f(6)。
   • 若無記憶化，每次都要重新計算 f(8), f(7) 等值，導致大量重複計算。
   • 記憶化確保每個 f(n) 只計算一次並儲存在 t 中，後續只需查表即可。

輸出結果解釋

f(1)=1
f(2)=2
f(3)=3
f(4)=6
f(5)=11
f(10)=230
f(100)=151404293106684183601223222
f(200)=44165437642884416151601614150885951220530708429827492
f(300)=12883293083460111453027503171794640961947472198462694418305228298687155542667162

• 小值：
  • 當 n = 1 和 n = 2，直接返回 n，因此得到 f(1) = 1, f(2) = 2。
  • 當 n = 3，直接返回 n，因此 f(3) = 3。
• 大值：
  • 計算 f(10) 時，遞迴利用了先前已計算的 f(9), f(8), f(7) 等，最終得到 230。
  • 對於極大的值如 f(100), f(200), f(300)，因為使用了記憶化，能夠在合理時間內計算出結果，而不至於陷入大量重複的遞迴。

總結

• 遞迴： 函式利用遞迴來計算，但直接的遞迴方法在計算 f(n) 時會重複計算許多子問題。
• 記憶化： 運用了記憶化技術，將每個 f(n) 的結果儲存在列表 t 中，以避免重複計算，提升效率。
• 時間複雜度： 由於每個 f(n) 只計算一次，因此時間複雜度降為 O(n)。