数列相关算法

本文主要收集一些常见的数列的算法实现。

斐波那契数列

现实例子

• 一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

• 有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法?

数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。

数学定义:

int fib( int n )
{
    if( n <= 2 )
        return 1;

    int fn;         // n 项
    int fn_1 = 1;   // n - 1 项
    int fn_2 = 1;   // n - 2 项

    for( int i = 2; i < n; i++ )
    {
        fn = fn_1 + fn_2;
        fn_2 = fn_1;
        fn_1 = fn;
    }

    return fn;
}