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

ray

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

劉愷恩

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

複製代碼

李知易

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

複製代碼

劉愷鈞

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))

複製代碼

劉愷威

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

複製代碼