10、数据结构与算法 - 实战：斐波那契数列Fibonacci

Fibonacci数列特点

头两个元素都为1

从第三个元素起，当前元素数值为前两个元素的数值和

例如：1, 1, 2, 3, 5, 8, 13 .........

总结了四种方法生成Fibonacci数列 - 有3种是递归、有1种不使用递归

public class FibonacciUtil {
    // 返回斐波那契数列第index个位置的数字
    public static int fiboNum(int index) {
        if(index == 1 || index == 2) {
            return 1;
        }else {
            return fiboNum(index-1) + fiboNum(index-2);
        }
    }
    /**
     *
     * @param length   斐波那契数列的长度
     * @param fiboArr  保存到某个固定长度空数组中 - length与foboArr长度必须对应
     * @return  返回的还是形参fiboArr对象
     */
    public static  int[]  fibonacci(int length, int[] fiboArr) {
        if(length == 1 ) {
            fiboArr[0] = 1;
        }else if(length == 2 ) {
            fiboArr[0] = 1;
            fiboArr[1] = 1;
        }else {
            fiboArr[length-1] = fibonacci(length-1, fiboArr)[length-2] + fibonacci(length-2, fiboArr)[length-3];
        }
        return fiboArr;
    }
    /**
     *
     * @param length
     * @return 返回一个length长的fibonacci数组
     */
    public static int[] fibonacci2(int length) {
        int[] fibos = new int[length];
        for(int index = 0; index<length; index++) {
            fibos[index] = fiboNum(index+1);
        }
        return fibos;
    }
    /**
     *
     * @param maxValue 斐波那契数列最后一个元素 大于 等于该元素
     * @return
     */
    public static Integer[] fibonacci3(int maxValue) {
        List<Integer> fiboList = new ArrayList<>();
        int length = 1;
        while(true)  {
            int fiboNum = fiboNum(length);
            fiboList.add(fiboNum);
            if(fiboNum >= maxValue)
                break;
            length++;
        }
        Integer[] fiboNums = new Integer[fiboList.size()];
        return fiboList.toArray(fiboNums);
    }
    /**
     * 不使用递归
     * @param length
     * @return 返回一个length长的fibonacci数组
     */
    public static int[] fibonacci4(int length) {
        int[] fiboNums = new int[length];
        if(length > 0) {
            fiboNums[0] = 1;
        }
        if(length > 1) {
            fiboNums[1] = 1;
        }
        if(length > 2) {
            int index = 2;
            while(true) {
                fiboNums[index] = fiboNums[index-1] + fiboNums[index-2];
                if(index+1 == length)
                    break;
                index++;
            }
        }
        return fiboNums;
    }
    public static void main(String[] args) {
        int[] fibonacci = fibonacci(10, new int[10]);
        System.out.println(Arrays.toString(fibonacci));
        int[] fibonacci2 = fibonacci2(10);
        System.out.println(Arrays.toString(fibonacci2));
        Integer[] fibonacci3 =  fibonacci3(100);
        System.out.println(Arrays.toString(fibonacci3));
        int[] fibonacci4 = fibonacci4(10);
        System.out.println(Arrays.toString(fibonacci4));
    }
}