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

Question

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

示例：n = 6

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

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

Answer 1

我认为至少可以很容易地看到这个数字的增长。由 Binet / De-Moivre formula、

f_n = (φⁿ - ψⁿ) / 5

因为|ψ| < 1 < φ，则

f_n∼φⁿ / 5。

由此得出小于x的斐波那契数的数量增长为log_φ(5x) .

Answer 2

这是一个闭式 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 个斐波那契数，因此如果您想要严格小于 n 的斐波那契数的数量，您必须引入滞后。类似于：

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

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

Number of Fibonacci numbers smaller than number k. Sub O(n)