java 实现斐波纳契数列

斐波纳契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)。

以下是两种实现方式:

  1. import java.util.Scanner;   

  2. public class Fibonacci {  

  3.   

  4.     public static void main(String[] args) {  

  5.         Scanner scanner = new Scanner(System.in);  

  6.         System.out.println("Please input this fibonacci n:");  

  7.         int n = scanner.nextInt(); // 假设输入为大于零的整数  

  8.           

  9.         System.out.println(fibonacci(6) + ":" + fibonacciNormal(6));  

  10.           

  11.         int sum = 0;  

  12.         for(int i = 1; i <= n; i++){  

  13.             sum += fibonacci(i);  

  14.         }  

  15.         System.out.println(sum);  

  16.     }  

  17.       

  18.     // 递归实现方式  

  19.     public static int fibonacci(int n){  

  20.         if(n <= 2){  

  21.             return 1;  

  22.         }else{  

  23.             return fibonacci(n-1) + fibonacci(n-2);  

  24.         }  

  25.     }  

  26.       

  27.     // 递推实现方式  

  28.     public static int fibonacciNormal(int n){  

  29.         if(n <= 2){  

  30.             return 1;  

  31.         }  

  32.         int n1 = 1, n2 = 1, sn = 0;  

  33.         for(int i = 0; i < n - 2; i ++){  

  34.             sn = n1 + n2;  

  35.             n1 = n2;  

  36.             n2 = sn;  

  37.         }  

  38.         return sn;  

  39.     }  

  40. }