题目描述

Fibonacci数列求和
0, 1, 1, 2, 3, 5, 8, 13
规律：前两位分别是0、1，后面每一位是前面两位的和。

代码块

  1. package com.yue.season1.class01;
  3. import com.yue.util.TimeUtil;
  5. /**
  6.  * Fibonacci数列求和
  7.  * 0, 1, 1, 2, 3, 5, 8, 13
  8.  * 规律：前两位分别是0、1，后面每一位是前面两位的和。
  9.  */
  10. public class Fibonacci {
  12.     public static long basicFibonacci(int num) {
  13.         if (num <= 1) {
  14.             return num;
  15.         }
  16.         return basicFibonacci(num - 1) + basicFibonacci(num - 2);
  17.     }
  19.     public static long improvedFibonacci(int num) {
  20.         if (num <= 1) {
  21.             return num;
  22.         }
  23.         long first = 0;
  24.         long second = 1;
  25.         long sum = num;
  26.         for (int i = 0; i < num - 1; i ++) {
  27.             sum = first + second;
  28.             first = second;
  29.             second = sum;
  30.         }
  31.         return sum;
  32.     }
  34.     public static void main(String[] args) {
  36.         int num = 40;
  38.         TimeUtil.check("basicFibonacci", new TimeUtil.Task() {
  39.             @Override
  40.             public void execute() {
  41.                 System.out.println(basicFibonacci(num));
  42.             }
  43.         });
  45.         TimeUtil.check("improvedFibonacci", new TimeUtil.Task() {
  46.             @Override
  47.             public void execute() {
  48.                 System.out.println(improvedFibonacci(num));
  49.             }
  50.         });
  52.     }
  54. }

运行结果

[basicFibonacci] 开始：2021-07-08T00:22:10.007873600 102334155 结束：2021-07-08T00:22:10.915445500

耗时：0.896秒

[improvedFibonacci] 开始：2021-07-08T00:22:10.923448900 102334155 结束：2021-07-08T00:22:10.923448900

耗时：0.0秒