斐波那契数列是指具备如下特征的数列:
前两个数的值分别为 0 、1 或者 1、1;
序列中从第 3 个数字开始,它的值是通过前两个数字相加得到的,即 F(n) = F(n-1) + F(n-2)。
例如,下面的数列就是一个斐波那契数列:
1、1、2、3、5、8、13、21、34、......
下面的动画给您描述了斐波那契数列的生成过程:
图 1 斐波那契数列的生成过程
接下来,我们研究如何设计算法生成斐波那契数列。
斐波那契数列的生成
斐波那契数列的生成方法有很多,本节我们主要研究如何用递归算法生成该数列。
如下为递归实现斐波那契数列的伪代码:
fibonacci(n): // n 表示求数列中第 n 个位置上的数的值
if n == 1: // 设置结束递归的限制条件
return 1
if n == 2: // 设置结束递归的限制条件
return 1
return fibonacci(n-1) + fibonacci(n-2) // F(n) = F(n-1) + F(n-2)
输入 n // 输入 n 的值
for i<-1 to n: // 输出前 n 个数
print fibonacci(i)
如下为递归输出斐波那契数列的 C 语言程序:
#include <stdio.h>// n 表示求数列中第 n 个位置上的数的值int fibonacci(int n) {// 设置结束递归的限制条件if (n == 1 || n == 2) {return 1;}// F(n) = F(n-1) + F(n-2)return fibonacci(n - 1) + fibonacci(n - 2);}int main(){int i;// 输出前 9 个数for (i = 1; i <= 9; i++) {printf("%d ", fibonacci(i));}return 0;}
如下为递归输出斐波那契数列的 Java 程序:
public class Demo {// n 表示求数列中第 n 个位置上的数的值public static int fibonacci(int n) {// 设置结束递归的限制条件if (n == 1 || n == 2) {return 1;}// F(n) = F(n-1) + F(n-2)return fibonacci(n - 1) + fibonacci(n - 2);}public static void main(String[] args) {// 输出前 9 个数for (int i = 1; i <= 9; i++) {System.out.print(fibonacci(i) + " ");}}}
如下为递归输出斐波那契数列的 Python 程序:
# n 表示求数列中第 n 个位置上的数的值def fibonacci(n):# 设置结束递归的限制条件if n == 1 or n == 2:return 1# F(n) = F(n-1) + F(n-2)return fibonacci(n-1) + fibonacci(n-2)# 输出前 n 个数for i in range(1,9):print(fibonacci(i),end=" ")
以上程序的输出结果均为:
1 1 2 3 5 8 13 21