斐波那契公式没有正确输出第 N 个值

Question

我正在尝试解决这个问题：

Hi, here's your problem today. This problem was recently asked by LinkedIn:

You are given a positive integer N which represents the number of steps in a staircase. You can either climb 1 or 2 steps at a time. Write a function that returns the number of unique ways to climb the stairs.

这道题实际上产生了斐波那契数列：

1 step =1 way,
2 steps =2 ways,
3 steps =3 ways,
4 steps =5 ways,
5 steps =8 ways, 
6 steps =13 ways
7 steps =21 ways
8 steps =34 ways
9 steps =55 ways
10 steps =89 ways
11 steps =144 ways
12 steps =233 ways
13 steps =377 ways

所以为了在没有 for 循环或递归的情况下解决这个问题，我决定为第 n 项编写斐波那契公式：

import math

def staircase(n):
  # Fill this in.
  term_a = ((1 + math.sqrt(5))/2) ** n
  term_b = ((1 - math.sqrt(5))/2) ** n

  numerator = term_a - term_b
  denominator = math.sqrt(5)

  return int(numerator/denominator)
  
print(staircase(4))
# 3
print(staircase(5))
# 5

对于 4 和 5，我应该得到 5 和 8。相反，我得到 3 和 5。我做错了什么？

Answer 1

正如上面评论中提到的，您的程序完成了它的工作并完美地描述了斐波那契数列。我在这里实现了递归版本，然后将结果与您的实现（显式）进行比较。

import math

def staircase(n):

    term_a = ((1 + math.sqrt(5)) / 2) ** n
    term_b = ((1 - math.sqrt(5)) / 2) ** n

    numerator = term_a - term_b
    denominator = math.sqrt(5)

    return int(numerator / denominator)


def fibo_rec(n):
    # initial conditions
    if n == 0: return 0
    if n == 1: return 1
    # recursive relationship
    return fibo_rec(n-1) + fibo_rec(n-2)

n = 20
test = [fibo_rec(i) for i in range(n)] == [staircase(i) for i in range(n)]
print(test)

输出

True

斐波那契公式没有正确输出第 N 个值

The Fibonacci formula does not correctly output the Nth value

python

fibonacci