经典算法详解（1）斐波那契数列的n项

斐波那契数列是一个常识性的知识，它指的是这样的一个数列，它的第一项是1，第二项是1，后面每一项都是它前面两项的和，如：1,1,2,3,5,8,13,21,34,55,89,144,233……

说明：由于通过递推方式效率低，系统开销大，空间复杂度高，故不考虑。

/*斐波那契数列：第一项和第二项为1，后面各项是其前面两项之和*/
/*编写一个函数，输入整数n，求该项的值*/

#include<iostream>

using namespace std;

int fibonacci(int n) {
    if (n < 0){
        return -1;
    }
    if ((n == 1 )||( n ==2)) {
        return 1;
    }
    else {
        int fib_1 = 1,fib_2=1,fib_3;
        for (int i = 3; i <= n; i++) {
            fib_3 = fib_1 + fib_2;
            fib_1 = fib_2;
            fib_2 = fib_3;
        }
        return fib_3;
    }
}

int main(int argc, char *argv[]) {
    cout << "please input n" << endl;
    int n;
    cin >> n;
    cout << "The reslut: " << fibonacci(n) << endl;

    getchar();
    getchar();
    return 0;
}