算法案例(1)------ 斐波那契数列

傷城~ 2021-12-11 04:51 177阅读 0赞

# 一、简介 #

斐波那契数列：给定开始的俩个值，后面的值是前面俩个值的叠加，求第n个数的值；

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

# 二、实现方式 #

## 2.1 数组遍历方式 ##

public class Fbnq {
    
    
        /**
         * 获取斐波那契数列第n个数的值
         * @param first 第一个数值
         * @param second 第二个数值
         * @param n 第n个数
         * @return 第n个数的值
         */
        public static int getFbnqNumber(int first, int second, int n) {
    
            int[] arr = new int[1000];
            arr[0] = first;
            arr[1] = second;
    
            if (n < 2) {
                return arr[n];
            }
            for (int i = 2; i < n; i++) {
                arr[i] = arr[i - 2] + arr[i - 1];
            }
            return arr[n - 1];
        }
    
        public static void main(String[] args) {
    
            System.out.println(getFbnqNumber(1, 1, 12));
    
        }
    
    
    }

## 2.2 三个变量方式 ##

public class Fbnq {
    
    
        /**
         * 获取斐波那契数列第n个数的值
         *
         * @param first  第一个数值
         * @param second 第二个数值
         * @param n      第n个数
         * @return 第n个数的值
         */
        public static int getFbnqNumber(int first, int second, int n) {
    
            if (n == 1) {
                return first;
            } else if (n == 2) {
                return second;
            }
    
            int a = first, b = second, c = 0;
            for (int i = 3; i <= n; i++) {
                c = a + b;
                a = b;
                b = c;
            }
            return c;
        }
    
        public static void main(String[] args) {
    
            System.out.println(getFbnqNumber(1, 1, 12));
    
        }
    
    
    }

## 2.3 递归方式 ##

public class Fbnq {
    
    
        /**
         * 获取斐波那契数列第n个数的值
         *
         * @param first  第一个数值
         * @param second 第二个数值
         * @param n      第n个数
         * @return 第n个数的值
         */
        public static int getFbnqNumber(int first, int second, int n) {
    
            if (n == 1) {
                return first;
            } else if (n == 2) {
                return second;
            }
    
    
            return getFbnqNumber(first, second, n - 2) + getFbnqNumber(first, second, n - 1);
        }
    
        public static void main(String[] args) {
    
            System.out.println(getFbnqNumber(1, 1, 12));
    
        }
    
    
    }