大家都知道斐波那契数列,现在要求输入一个正整数 n ,请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 的数列
数据范围:
要求:空间复杂度 ,时间复杂度 ,本题也有时间复杂度 的解法
仅输入一个正整数 n。
输出斐波那契数列中第 n 个数。
4
3
根据斐波那契数列的定义可知,fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3,所以答案为3。
1
1
2
1
n = int(input()) l = [1,1] if n <=2 : print(1) else: for i in range(3,n+1): c = l[-1]+l[-2] l.append(c) print(l[-1])
def fob(n): if n <= 2: return 1 dp = [0] * n dp[0] = 1 dp[1] = 1 for i in range(2,n): dp[i]= dp[i-1] + dp[i-2] return dp[n-1] n = int(input()) print(fob(n))
n= int(input()) if n==1: print(1) elif n==2: print(1) elif n>=3: fis=[0 for i in range(n+1)] fis[1]=1 fis[2]=1 for i in range(3,n+1): fis[i]=fis[i-1]+fis[i-2] print(fis[n])
while True: try: s = int(input()) s1, s2, s3 = 1, 0, 0 for i in range(1, s): s3 = s3 + s2 s2 = s1 s1 = s3 print(s1 + s2 + s3) except EOFError: break
n=int(input()) dp=[1]*2 switch=0 for i in range(3,n+1): dp[switch]=dp[0]+dp[1] switch=(switch+1)%2 print(dp[(switch+1)%2])