斐波那契数列解析优化

斐波那契数列（Fibonacci sequence），又称黄金分割数列、兔子数列，是数学家列昂纳多·斐波那契于1202年提出的数列。斐波那契数列为1、1、2、3、5、8、13、21、34……前两项都为1，递推公式为F(n)=F(n-1)+F(n-2)，n≥3，F(1)=1，F(2)=1。
这个数列从第3项开始，每一项都等于前两项之和。也是一道常见的面试题。
例题：求斐波那契数列第n项。

public static int fib(int n) {
 if (n == 1 || n == 2) { 
 return 1;
  } 
 return fib(n - 1) + fib(n - 2);
  }

当我们求 fib(30) 的时候发现, 程序执行速度极慢. 原因是进行了大量的重复运算.

class Test { 
 public static int count = 0; // 成员变量. 
 public static void main(String[] args) {
 System.out.println(fib(30)); 
 System.out.println(count); 
 } 
 public static int fib(int n) {
  if (n == 1 || n == 2) {
   return 1; 
   } 
   if (n == 3) { 
   count++; 
   }
  return fib(n - 1) + fib(n - 2);
   }
  } 
   // fib(3) 重复执行了 3 千万次. 

可以使用循环的方式来求斐波那契数列问题, 避免出现冗余运算.

 public static int fib(int n) { 
 int list2 = 1; int list1 = 1; int print = 0;
  for (int i = 3; i <= n; i++) {
   print = list1 + list2; 
   list2 = list1; 
   list1 = print;
   }
    return print;
 } 

此时程序的执行效率大大提高了.

本文地址：https://blog.csdn.net/JinxLin/article/details/107368363