查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指：

  • 前2个数是 0 和 1 。
  • 第 i 个数是第 i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

像这样的题，看到肯定想到递归算法来做，这是一种很重要的思想（虽然递归实现效率低，但是简洁的代码就能达到该有的功能），

下面上源码。

递归算法：

public int fibonacci(int n) {
        // write your code here
        if(n == 1)
            return 0;
        else if(n == 2)
            return 1;
        return  fibonacci(n-2)+fibonacci(n-1);
    }

非递归：

public int fibonacci(int n) {
        // write your code here
        int a = 0;
        int b = 1;
        int result = 0;
        if(n == 1)
            return 0;
        else if(n == 2)
            return 1;
        for(int i = 3;i<n+1;i++){
            result = a +b;
            a = b;
            b = result;
        }
        return result;
    }

 

版权声明：本文为Allen-T原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Allen-T/p/7744717.html