减小
增大
默认

护眼
夜间
默认

斐波那契数列

上一节
斐波那契数列是指具备如下特征的数列：
  • 前两个数的值分别为 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

上一节