2019年-fibonacci数列与黄金分割

• 题目
• 法一、递归
• 法二、迭代

题目

法一、递归

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))