斐波那契数列

        斐波那契数列又称 黄金分割 数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“ 兔子数列 ”;

* 指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
* 其规律是从第3个数开始，每个数都等于它前两个数的和。

java代码实现

1. 用递归的方法实现:

package com;

import java.util.Arrays;

//1.递归方法
public class test2 {
    //1.用递归方法
    public static void main(String[] args) {
        for (int counter = 0; counter <= 10; counter++){
            System.out.printf("Fibonacci of %d is: %d\n", counter, fibonacci(counter));
        }
    }
    public static long fibonacci(long number) {
        if ((number == 0) || (number == 1))
            return number;
        else
            return fibonacci(number - 1) + fibonacci(number - 2);
    }
}

 2. 用循环方法实现:

public class test3{
    public static void main(String[] args) {
        //1.定义三个变量,用来存放第一个第二第三个斐波那契数
        int a1 = 1;
        int a2 = 1;
        int a3 ;
        System.out.print("斐波那契数列前十个是:");
        System.out.print(a1+","+a2);
        for (int i = 3; i <=10;i++) {
            //2.根据前两个数算出第三个数
            a3=a2+a1;
            //3.更新第一第二个数
            a1=a2;
            a2=a3;
            System.out.print(","+a3);
        }
    }
}

3. 用数组+循环来实现:

public class test4{
    public static void main(String[] args) {
        //创建一个用来装斐波那契数列的数组,假设只获取前十个数
        int [] arr = new int[10];
        //先将前两个放入数组
        arr[0] = 1;
        arr[1] = 1;
        //循环获得剩下斐波那契数
        for (int i = 2; i <arr.length; i++) {
            arr[i]=arr[i-1]+arr[i-2];
        }
        //输出这十个数
        String s = Arrays.toString(arr);
        System.out.println("前十个斐波那契数是:"+s);
    }
}

 斐波那契数列：指的是这样的数列：0，1，1，2，3，5，8，21，34..., 这个数列从第三项开始，每一项都等于前两项之和。

案例代码：

/**
 * 递归求解斐波那契数列
 * 步骤解释：
 * n=5 foo(4)+foo(3)
 * =foo(3)+foo(2)+foo(2)+1
 * =3foo(2) +1+1
 * =3+2
 * =5
 *
 * @param n
 * @return
 */
private static Integer foo(int n) {
    if (n < 2)
        return n;
    return foo(n - 1) + foo(n - 2);
}

 循环、递归代码实现斐波那契数列

package top.chenxiky.courseware.sort;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: chenxiky
 * @Date: 2022/03/11/13:28
 * @Description: 斐波那契数列
 * 斐波那契数列：指的是这样的数列：0，1，1，2，3，5，8，21，34...,
 * 这个数列从第三项开始，每一项都等于前两项之和
 */
public class FibonacciLoop {
    public static void main(String[] args) {
        // 笔试题
        System.out.println("答案:" + foo(5));
        // 循环实现斐波那契数列
        fibonacci_loop(5);
        // 打印空行
        System.out.println();
        // 递归实现斐波那契数列
        fibonacci_recursion(1);
    }

    /**
     * 递归求解斐波那契数列
     * 步骤解释：
     * n=5 foo(4)+foo(3)
     * =foo(3)+foo(2)+foo(2)+1
     * =3foo(2) +1+1
     * =3+2
     * =5
     *
     * @param n
     * @return
     */
    private static Integer foo(int n) {
        if (n < 2)
            return n;
        return foo(n - 1) + foo(n - 2);
    }

    /**
     * 用循环实现斐波那契数列
     *
     * @return
     */
    public static void fibonacci_loop(int num) {

        // num如果小于1直接结束该方法
        if (num < 1) {
            return;
        }
        // 设置一个变量输出数据的个数
        int n = 0;
        // 初始化第一个数
        int a = 0;
        // 初始化第二个数
        int b = 1;
        // 第三个数 斐波那契数列第一项等于前两项之和(初始化为0)
        int c = 0;

        // do while至少循环一次
        do {
            n++;
            if (n == 1) {
                System.out.print("循环实现：" + 0 + "\t");
                System.out.print(1 + "\t");
            }
            // 第三个数是前两个数之和
            c = a + b;
            System.out.print(c + "\t");
            // 原来的第一个数变为第二个数
            a = b;
            // 原来的第二个数变为第三个数
            b = c;
        } while (n < num);
        return;
    }


    /**
     * 递归实现斐波那契数列
     *
     * @param num
     */
    public static void fibonacci_recursion(int num) {
        // 边界值判断
        if (num < 1) {
            return;
        }
        // 调用递归方法
        fibonacci_recursion_handler(1, num, 0, 1);

    }

    /**
     * 在私有的方法里递归调用
     *
     * @param index // 数据的序号
     * @param num   //  数列数据的个数
     * @param one   //   第一个数
     * @param two   //    第二个数
     */
    private static void fibonacci_recursion_handler(int index, int num, int one, int two) {

        // 程序的出口
        if (index <= num) {
            if (index == 1) {
                System.out.print("递归实现：" + one + "\t");
                System.out.print(two + "\t");
            }
            // 第三个数是前两个数之和
            System.out.print(one + two + "\t");
            // 递归 原来的第一个数变成第er个数 原来的第二个数变成第三个数
            fibonacci_recursion_handler(++index, num, two, one + two);
        }


//        // 程序的出口
//        if (index > num) {
//            // 终止递归
//            return;
//        } else {
//            if (index == 1) {
//                System.out.println(0);
//                System.out.println(1);
//            }
//            // 第三个数是前两个数之和
//            System.out.println(one + two);
//            // 原来的第一个数变成第er个数 原来的第二个数变成第三个数
//            fibonacci_recursion_handler(++index, num, two, one + two);
//        }

    }

}