Python实现婓波那契数列（Fibonacci sequence）

一、斐波那契数列（Fibonacci sequence）

斐波那契数列（Fibonacci sequence）是一个非常神奇和有趣的数列，又被称为黄金分割数列或兔子数列。

在数学上，斐波那契数列定义为：第一项F(1)=0，第二项F(2)=1，而后续每一项都是前两项的和，即F(n)=F(n-1)+F(n-2)（n≥3），因此，斐波那契数列的前几个数字是：0、1、1、2、3、5、8、13、21、34、……

此外，斐波那契数列也有通项公式，它可以使用无理数和幂次的形式表示数列中的任意一项。这个通项公式相对复杂，涉及黄金分割比（φ = (1+√5)/2）及其共轭（ψ = (1-√5)/2）。对于第n项，通项公式可以写作：F(n) = (φ^n - ψ^n) / √5

在这里，φ和ψ分别是黄金分割比及其共轭，√5表示5的平方根。需要注意的是，虽然φ和ψ是无理数，但斐波那契数列的每一项都是整数。

二、用Python实现婓波那契函数

使用函数递归或非递归的方式都可以方便地计算斐波那契函数：F(1)=0，F(2)=1, F(n)=F(n – 1)+F(n – 2)（n ≥ 3）

1、递归方法：

def fibonacci_recursive(n):
    if n <= 0:
        return "输入错误，请输入正整数"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

if __name__ == '__main__':
    n = int(input())
    print(fibonacci_recursive(n))

2、迭代方法：

def fibonacci_iterative(n):
    if n <= 0:
        return "输入错误，请输入正整数"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        a, b = 0, 1
        # 这个循环的作用是从第2项开始，迭代计算斐波那契数列中的每一项，直到达到第 n 项为止。
        for _ in range(2, n):  # 循环变量 _ 是一个常用的占位符，表示我们在循环中不打算使用这个变量的值。
            a, b = b, a + b  # 在每次循环迭代中，a 和 b 的值会更新为下一对斐波那契数列中的两个连续数字。具体来说，a 会更新为 b，而 b 会更新为 a + b。
        return b  # 循环结束后，变量 b 的值就是斐波那契数列中的第 n 项

if __name__ == '__main__':
    n = int(input())
    print(fibonacci_iterative(n))

以上两种方法中，递归方法虽然简洁，但是效率较低，因为有很多重复的计算。在实际应用中，我们更倾向于使用迭代方法，因为它避免了重复计算，提高了效率。

3、公式法：

对于第n项的斐波那契数列，可以使用通项公式进行计算。例如，对于第10项的斐波那契数列，可以使用以下公式进行计算：
F(10) = (φ^10 - ψ^10) / √5
其中，φ和ψ分别是黄金分割比及其共轭，√5表示5的平方根。

def fibonacci_formula(n):
    if n <= 0:
        return "输入错误，请输入正整数"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return (pow((1+5**0.5)/2, n) - pow((1-5**0.5)/2, n)) / 5**0.5

if __name__ == '__main__':
    n = int(input())
    print(fibonacci_formula(n))

这段代码是计算斐波那契数列的一种方法，具体来说，它是通过使用黄金分割比φ=(1+√5)/2来快速计算第n个斐波那契数。下面是对这段代码的逐步解释：

因此，这段代码通过利用数学公式和技巧，有效地计算了斐波那契数列中的第n个数。

4、矩阵快速幂法：

def fibonacci_matrix(n):  
    if n <= 0:  
        return "输入错误，请输入正整数"  
    elif n == 1:  
        return 0  
    elif n == 2:  
        return 1  
    else:  
        phi = (1+5**0.5)/2  
        psi = (1-5**0.5)/2  
        a = psi/phi**0.5  
        b = phi**n - a**n * psi**n / phi**n  
        return int(b * phi**0.5)
        
if __name__ == '__main__':
    n = int(input())
    print(fibonacci_matrix(n))

这个函数使用矩阵快速幂方法来高效地计算斐波那契数列中的第n项。这种方法利用了矩阵的幂运算的性质，避免了传统的递归或迭代方法中的重复计算，从而大大提高了计算效率。

5、动态规划法：

动态规划是一种通过将问题分解为更小的子问题并存储子问题的解决方案，以便在解决更大的问题时重复使用它们的方法。

def fibonacci_dynamic_programming(n):  
    if n <= 0:  
        return "输入错误，请输入正整数"  
    # 如果n等于1，则返回斐波那契数列的第一项0。
    elif n == 1:  
        return 0  
    # 如果n等于2，则返回斐波那契数列的第二项1。
    elif n == 2:  
        return 1  
    else: 
    		 # 初始化一个长度为n的列表dp，其中前两项0和1是已知的斐波那契数列的前两项，其余项初始化为0。
        dp = [0, 1] + [0] * (n-2)  
        for i in range(2, n):  # 从第三项开始循环计算斐波那契数列的每一项。
            dp[i] = dp[i-1] + dp[i-2]  # 根据斐波那契数列的定义，当前项等于前两项之和。
        return dp[n-1]  # 返回计算得到的斐波那契数列的第n项的值。
if __name__ == '__main__':
    n = int(input())
    print(fibonacci_dynamic_programming(n))

对于斐波那契数列，我们可以将其视为一个递归问题，其中每个数是前两个数的和。
为了解决这个问题，我们可以使用动态规划来避免递归的重复计算。

6、缓存法：

缓存法，是一种使用记忆化（也称为缓存）技术。记忆化是一种优化技术，用于存储已经计算过的子问题的结果，以便在后续需要时重复使用，而不是重新计算。
使用记忆化技术的主要优势是避免了大量的重复计算。在递归计算斐波那契数列时，对于每个索引 n，都需要计算 fibonacci(n-1) 和 fibonacci(n-2)。如果没有缓存，这将导致大量的重复计算。通过使用缓存，我们可以存储已经计算过的斐波那契数，并在需要时直接从缓存中获取它们，从而提高计算效率。

def fibonacci_cache(n):  
    # 这是一个字典，用于存储已经计算过的斐波那契数列的值。其键是计算斐波那契数的索引，值是对应的斐波那契数。
    cache = {}  
    # 这个函数用于计算斐波那契数列的第 n 项。
    def fibonacci(n):  
        if n in cache:  
            return cache[n] 
        elif n <= 0:  # 添加此条件检查
            raise ValueError("输入的数字应为正整数")  # 当n为负数时引发异常 
        elif n == 1:  
            result = 0  
        elif n == 2:  
            result = 1  
        # 对于其他 n，使用递归的方式计算斐波那契数列的第 n 项。
        # 递归地调用 fibonacci(n-1) 和 fibonacci(n-2)，并将它们的和存储在 result 中。
        else:  
            result = fibonacci(n-1) + fibonacci(n-2)  
        cache[n] = result  # 将计算得到的 result 作为键 n 的值存储在 cache 中，以便下次可以直接从缓存中获取该值。
        return result  
    return fibonacci(n)
    
if __name__ == '__main__':
    n = int(input())
    print(fibonacci_cache(n))