首页实现Fibonacci数列

实现Fibonacci数列

时间: 2024-09-28 15:04:55 浏览: 43

斐波那契数列是一个经典的数学序列，每个数字都是前两个数字之和。通常从0和1开始，后续每一项都等于前两项之和。例如：0, 1, 1, 2, 3, 5, 8, 13...以此类推。实现这个数列可以有多种编程方法，以下是几种常见的： 1. **递归** (Python): ```python def fibonacci(n): if n <= 1: return n else: return fibonacci(n - 1) + fibonacci(n - 2) ``` 2. **循环迭代** (Python): ```python def fibonacci(n): a, b = 0, 1 for _ in range(n): yield a a, b = b, a + b ``` 3. **动态规划** (Python): ```python def fibonacci(n): fib_sequence = [0, 1] while len(fib_sequence) < n: fib_sequence.append(fib_sequence[-1] + fib_sequence[-2]) return fib_sequence[n - 1] ``` 4. **矩阵快速幂** (适用于大数计算) (Python): ```python def matrix_power(matrix, n): if n == 1: return matrix half = matrix_power(matrix, n // 2) if n % 2 == 0: return half @ half else: return half @ half @ matrix def fibonacci(n): fib_matrix = [[1, 1], [1, 0]] result = matrix_power(fib_matrix, n - 1) return result[0][0] ```

阅读全文