斐波那契数列两种算法

2019-11-14 16:22:04

字体：大中小

来源：转载

供稿：网友

斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）

①、递归

public static int Fibonacci(int num){    if (num > 0 && num <= 2)        return 1;    return Fibonacci(num - 1) + Fibonacci(num - 2);}

②、迭代

public int Fibonacci(int num){    if (num > 0 && num <= 2)        return 1;    // 设定f1代表第num-2个数，f2代表第num-1; current代表第num个斐波那契队列所对应的数。    int f1 = 1, f2 = 1, current = 0;    for (int i = 3; i <= num; i++)    {        current = f1 + f2;        f1 = f2;        f2 = current;    }    return current;}