b024: 指南宮的階梯

b024: 指南宮的階梯
"""
指南宮有階梯，據說有1000多階。
小明的步伐比較大，一次最多可以爬兩階，
他希望每次爬上去的走法都不一樣，
例如四階的情況就有：
1-1-1-1、
1-1-2、
1-2-1、
2-1-1、
2-2等5種方式。

現在想請你幫他計算，
當階梯有 N 階時，總共有幾種走法。

輸入說明：
輸入一個正整數 N (1<=N<=90)。
輸出說明：
假設 N 階的階段，每次走一或二階，
總共有 K 種走法，
請輸出 N 階 以及   K%N 階 各有幾種走法。

範例輸入： 
輸入1:
4
輸入2:
10
範例輸出 ：

輸出1:
5 1

輸出2:
89 55
""


# f(n)=f(n−1)+f(n−2)， f(0)=1，f(1)=1  直接求解。


def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

n=int(input("請輸入 正整數 --> "))

print("總共有",fib(n)," 種走法")

====================== RESTART: F:/Python_APSC/b024.py ======================

請輸入 正整數 --> 4

總共有 5  種走法

>>> 

====================== RESTART: F:/Python_APSC/b024.py ======================

請輸入 正整數 --> 10

總共有 89  種走法

>>> 

f(n)=f(n−1)+f(n−2)，
f(0)=1，f(1)=1  直接求解。
0	1
1	1
2	2
3	3
4	5
5	8
6	13
7	21
8	34
9	55
10	89
11	144
12	233
13	377
14	610
15	987
16	1597
17	2584
18	4181
19	6765
20	10946
21	17711
22	28657