斐波纳奇数列(Fibonacci)

斐波那契数列简介

斐波那契数列(Fibonacci sequence)，又称黄金分割数列、指的是这样一个数列：1、1、2、3、5、8、13、21、34、……即从第3项起，后一项总是等于前两项之和。

在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）。

1. 使用数组实现Fibonacci数列

/**
 * 使用数组实现Fibonacci数列
 */
public void fibonacciArray(int n) {
    int[] fibonacci = new int[n];
    fibonacci[0] = 1;
    fibonacci[1] = 1;
    for (int i = 2; i < n; i++) {
        fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
    }
    System.out.println(Arrays.toString(fibonacci));
}

2. 使用栈实现Fibonacci数列

/**
 * 使用栈实现Fibonacci数列
 */
public void fibonacciStack(int n) {
    Stack<Integer> stack = new Stack<>();
    stack.push(1);
    stack.push(1);
    while (stack.size() < n) {
        Integer numTop1 = stack.pop();
        Integer numTop2 = stack.peek();
        stack.push(numTop1);
        stack.push(numTop1 + numTop2);
    }
    System.out.println(stack);
}

3. 使用递归求Fibonacci第n项的值

/**
 * 使用递归求Fibonacci第n项的值
 */
public int fibonacciRecursion(int n) {
    if (n == 1) return 1;
    if (n == 2) return 1;
    return fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2);
}