b022: 費氏數列

b022: 費氏數列

"""
費波那西數列(Fibonacci Sequence)簡稱費氏數列，
它的定義如下：

F0=0
F1=1
Fn=Fn-1+Fn-2

也就是說，它以 0,1 開頭，接下來的每一項

都是前兩項的和，它的前10項為：0,1,1,2,3,5,8,13,21,34。

費氏數列是許多人接觸遞迴函數時的第一個例子，
但事實上它不是一個適合使用遞迴的例子，
因為隨著 N 的增加，底層函數的呼叫將會接近指數成長
而導致效能過低，

現在給你一個 N，請你以遞迴方式計算出 Fn的值，
並統計執行了幾次函數的呼叫。

輸入說明：
輸入一個正整數 N (2<=N<=35)。
輸出說明：

請輸出 Fn 的值，以及執行了幾次函數的呼叫。
範例輸入：

輸入1:
4

輸入2:
10
範例輸出 ：

輸出1:
3 9

輸出2:
55 177

"""
array = [0,1]
cnt=0
print("=====方式1 ===")
n=int(input("input a number "))
print("0,1",end=',')
for i in range(n-1):
   global cnt
   cnt+=1
   x = array[0]+array[1]   
   print(x,end=',')
   array[0] = array[1]
   array[1] = x
print()
print("計算次數",cnt)
print("\n\n")


print("=====方式2 ===")
cnt=0
def fib(i):
    global cnt
    cnt+=1
    if i <= 1:   # 當 i <= 1 時,
       return i  #  就結束 fib() 函式的遞迴呼叫.
    else: # 繼續遞迴呼叫 fib() 函式.
       return fib(i - 1) + fib(i - 2)

for i in range(n+1): # 利用迴圈印出 1~10 的費式數列.
   print ("fibonacci(" + str(i) + ")=" + str(fib(i)))
print()
print("計算次數",cnt)


====================== RESTART: F:/Python_APSC/b022.py ======================
=====方式1 ===
input a number 4
0,1,1,2,3,
計算次數 3



=====方式2 ===
fibonacci(0)=0
fibonacci(1)=1
fibonacci(2)=1
fibonacci(3)=2
fibonacci(4)=3

計算次數 19
>>>