algorithm - 小于数 k 的斐波那契数的个数。子 O(n)

Question

面试题:有多少个斐波那契数小于给定数 k？你能找到一个关于 k 的函数，得到小于 k 的斐波那契数吗？

示例:n = 6

答案:6 为 (0, 1, 1, 2, 3, 5)

很简单，写一个循环或使用 Fibonacci 的递归定义。然而，这听起来太简单了……有没有办法使用封闭形式的定义来做到这一点？ (https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression)

Answer 1

这是一个封闭形式的 Python 解决方案，其复杂度为 O(1)。它使用 Binet 的公式(来自您链接到的维基百科文章):

>>> from math import sqrt,log
>>> def numFibs(n): return int(log(sqrt(5)*n)/log((1+sqrt(5))/2))

>>> numFibs(10)
6

哪些轨道有 1,1,2,3,5,8

关键是比奈公式中的第二项可以忽略不计，很容易反转忽略它的结果。

上面的公式统计了小于或者等于n的斐波那契数的个数。每个新的斐波那契数都跳 1。因此，例如，numFibs(12) = 6 和 numFibs(13) = 7。 13 是第 7 个 Fibonacci 数，因此如果您想要 严格 小于 n 的 Fibobacci 数，您必须引入滞后。像这样的东西:

def smallerFibs(n):
    if n <= 1:
        return 0
    else:
        return min(numFibs(n-1),numFibs(n))

现在 smallerFibs(13) 仍然是 6 但 smallerFibs(14) = 7. 这当然仍然是 O(1) .