题目
法一、递归
def fib (n):
if n==1 or n==2:
return 1
return fib(n-1)+fib(n-2)
n = int(input())
a=fib(n)
b=fib(n+1)
print("{:.8f}".format(a/b))
- 只通过了60%的测试
法二、迭代
#动态规划
# def fib (n):
# dp=[0]*(n+1)
# dp[1],dp[1]=1,1
# for i in range(3,n+1):
# dp[i]=dp[i-1]+dp[i-2]
# return dp[n]
#优化
def fib(n):
if(n==1 or n==2):
return 1
pre,cur=1,1
for i in range(3,n+1):
sum=pre+cur
pre=cur
cur=sum
return cur
n = int(input())
if n>20:
print(0.61803399)
else:
a=fib(n)
b=fib(n+1)
print("{:.8f}".format(a/b))