返回列表 發帖

2022/01/02 利用遞迴+動態規劃計算費式數列

使用global來存取一個全域的解答陣列
大幅降低重複計算的次數

本帖最後由 劉愷威 於 2022-1-2 15:02 編輯
  1. import time
  2. s = [-1]*100

  3. def f(n):
  4.     global s
  5.     if s[n] == -1:
  6.         if n < 2:
  7.             s[n] = n
  8.             return s[n]
  9.         s[n] = f(n-2) + f(n-1)
  10.         return s[n]
  11.     else:
  12.         return s[n]

  13. try:
  14.     while True:
  15.         x = int(input())
  16.         start = time.time()
  17.         print(f(x))
  18.         end = time.time()
  19.         print(end-start)
  20. except EOFError:
  21.     pass
複製代碼

TOP

  1. s=[1]*50
  2. def f(n):
  3.     global s
  4.     if s[n] == 1:
  5.         if n < 2:
  6.             s[n] == n
  7.             return s[n]
  8.         s[n]=f(n-2)+f(n-1)
  9.         return s[n]
  10.     else:
  11.         return s[n]
  12. a=int(input())
  13. print(f(a))
複製代碼

TOP

  1. import time
  2. s = [-1]*50

  3. def x(n):
  4.     global s
  5.     if s[n] == -1:
  6.         if n < 2:
  7.             s[n] = n
  8.             return s[n]
  9.         s[n] = x(n-1) + x(n-2)
  10.         return s[n]
  11.     else:
  12.         return s[n]
  13. try:
  14.     while True:
  15.         a = int(input())
  16.         start = time.time()
  17.         print(x(a))
  18.         end = time.time()
  19.         print(end - start)
  20. except:
  21.     pass
複製代碼

TOP

  1. s=[-1]*50
  2. def f(n):
  3.     global s
  4.     if s[n]==-1:
  5.         if n<2:
  6.             s[n]=n
  7.             return s[n]
  8.         else:
  9.             s[n]=f(n-2)+f(n-1)
  10.             return s[n]
  11.     else:
  12.         return s[n]
  13. try:
  14.     while True:
  15.         a=int(input())
  16.         print(f(a))
  17. except:
  18.     pass
複製代碼

TOP

返回列表