【python练习】python斐波那契数列超时问题

计算斐波那契数列第n项的数字
Description

计算斐波那契数列第n项的数字，其中f(1)=f(2)=1,f(n)=f(n-1)+f(n-2)，如1，1，2，3，5,......


Input
正整数n(n<100)


Output
一个整数f(n)


Sample Input 1 

8
Sample Output 1

21
Source

中学生可以这样学Python，P187例8-19
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

一、使用递归，出现超时

n=int(input())
def f(n):
    if n==1 or n==2:
        return 1
    else:
        return f(n-1)+f(n-2)
print(f(n))
1
2
3
4
5
6
7

二、使用列表，通过

n=int(input())
a=[1,1]
if n==1 or n==2:
    print(1)
else:
    for i in range(2,n):
        a.append(a[i-2]+a[i-1])
print(a[n-1])
1
2
3
4
5
6
7
8