Python程序：如何检查给定的数字是否为斐波那契数？

斐波那契数列是一个非常经典的数列，其中每个数都是前两个数之和。比如，1, 1, 2, 3, 5, 8, 13, 21, …… 依此类推。

在本文中，我们将探讨如何用 Python 程序检查给定的数字是否为斐波那契数。

方法一：直接根据斐波那契数列实现

我们可以直接用 Python 程序实现斐波那契数列，然后判断给定的数字是否在该数列中出现。

例如，下面的代码定义了一个函数 is_fibonacci()，由于该数列是无限的，我们需要设定一个上限来限定检索的范围。此处我们设定上限为最大值，即 $2^{32}$ ，当然，如果你需要检查的数字更大，可以根据需要调整上限。

def is_fibonacci(n):
    """
    判断数值 n 是否为斐波那契数。
    """
    a, b = 0, 1
    while b <= n:
        if b == n:
            return True
        a, b = b, a + b
    return False

# 测试用例
print(is_fibonacci(3))    # True
print(is_fibonacci(13))   # True
print(is_fibonacci(15))   # False

方法二：数学方法判断

另一种方法是借助斐波那契数列的数学特性，即判断给定的数字是否是斐波那契数列中前两项之和的形式。如果是，则该数字为斐波那契数。

下面定义一个函数 is_fibonacci_math() 来实现这个数学方法。

def is_fibonacci_math(n):
    """
    判断数值 n 是否为斐波那契数，使用数学方法。
    """
    return (is_perfect_square(5 * n * n + 4)) or (is_perfect_square(5 * n * n - 4))


def is_perfect_square(n):
    """
    辅助函数：判断一个数是否为完全平方数。
    """
    if n <= 0:
        return False
    root = int(n ** 0.5)
    return root * root == n

# 测试用例
print(is_fibonacci_math(3))    # True
print(is_fibonacci_math(13))   # True
print(is_fibonacci_math(15))   # False

方法三：使用生成器实现优化的方法

第二种方法已经比第一种方法快了很多。但还有更好的方法——使用生成器。

下面的代码实现了一个生成斐波那契数列的生成器函数 fibonacci()。该函数可以生成从 0 开始的无限斐波那契数列，但根据需要它也可以生成有限的数列。在该函数使用的 while 循环中，在两个变量（”a” 和 “b”）之间切换，它们的值分别为：0 和 1，然后对它们进行相加，来产生下一个数。

利用此函数，我们可以实现一个更快速的算法来检查给定的数字是否是斐波那契数。简单来说，我们只需在斐波那契数列中按顺序检查，直到达到或超过该数字的值。如果该数字与当前斐波那契数列的末尾匹配，则该数字为斐波那契数。

def fibonacci():
    """
    以生成器的方式产生斐波那契数列，由于数列是无限的，因此未定义上限，需要在使用时注意。
    """
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

def is_fibonacci_optimized(n):
    """
    判断数值 n 是否为斐波那契数，使用优化的方法。
    """
    for fib in fibonacci():
        if fib == n:
            return True
        elif fib > n:
            return False

# 测试用例
print(is_fibonacci_optimized(3))    # True
print(is_fibonacci_optimized(13))   # True
print(is_fibonacci_optimized(15))   # False