老青菜

剑指offer-斐波那契数列

2017-01-20

题目

写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。

分析

斐波那契数列(Fibonacci sequence),又称黄金分割数列,数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”
函数定义:

F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3)

比如这样的数列:1、1、2、3、5、8、13、21、34……

实现

long fibonacci(long n) {
    if (n<=0) {
        return 0;
    }
    if (n == 1 || n == 2) {
        return 1;
    }
    //记录前两个(第n-2个)的Fibonacci数
    long prePre = 1;
    //记录前两个(第n-1个)的Fibonacci数
    long pre = 1;
    //记录前两个(第n个)的Fibonacci数
    long result = 0;
    //求解第n个的fibonacci数的值
    //当然这里也可以使用递归
    for (int i=3; i<=n; i++) {
        //求第i个的Fibonacci数
        result = prePre + pre;
        //把 i-1 赋值给 i-2
        prePre = pre;
        //把 i 赋值给 i-1
        pre = result;
    }
    return result;
}
//测试代码
printf("%ld,", fibonacci(0));
printf("%ld,", fibonacci(1));
printf("%ld,", fibonacci(2));
printf("%ld,", fibonacci(3));
printf("%ld,", fibonacci(4));
printf("%ld,", fibonacci(5));
printf("%ld,", fibonacci(6));
printf("%ld,", fibonacci(7));

//输出结果
0,1,1,2,3,5,8,13,

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章