斐波那契數(shù)列定義：From Wikipedia, the free encyclopedia

http://en.wikipedia.org/wiki/Fibonacci_number

In?mathematics, the?Fibonacci numbers?or?Fibonacci sequence?are the numbers in the following?integer sequence:^[2][3]

or (often, in modern usage):

?(sequence?A000045?in?OEIS).

By definition, the first two numbers in the Fibonacci sequence are 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

In mathematical terms, the sequence?F_n?of Fibonacci numbers is defined by the?recurrence relation

with seed values^[2][3]

or^[4]

本例以后一種為例：

最簡(jiǎn)單的一種：兩層遞歸

public static long fibonacci(int n){if(n==0) return 0;else if(n==1) return 1;else return fibonacci(n-1)+fibonacci(n-2);}

問題是：隨著n的數(shù)值逐漸增多，時(shí)間和空間耗費(fèi)太大，讀者可以自行實(shí)驗(yàn)。在我的機(jī)器上n=50時(shí)就不能忍受了。

考慮優(yōu)化：一層遞歸

public static void main(String[] args) {long tmp=0;// TODO Auto-generated method stubint n=10;Long start=System.currentTimeMillis();for(int i=0;i<n;i++){System.out.print(fibonacci(i)+" ");}System.out.println("-------------------------");System.out.println("耗時(shí)："+(System.currentTimeMillis()-start));} public static long fibonacci(int n) {long result = 0;if (n == 0) {result = 0;} else if (n == 1) {result = 1;tmp=result;} else {result = tmp+fibonacci(n - 2);tmp=result;}return result;}

遞歸時(shí)間減少了到不到50%

最好的方式，不使用遞歸的方式來(lái)做。

public static long fibonacci(int n){long before=0,behind=0;long result=0;for(int i=0;i<n;i++){if(i==0){result=0;before=0;behind=0;}else if(i==1){result=1;before=0;behind=result;}else{result=before+behind;before=behind;behind=result;}}return result;}

?

轉(zhuǎn)載于:https://www.cnblogs.com/davidwang456/p/4031167.html

總結(jié)

以上是生活随笔為你收集整理的斐波那契数列（fabnacci）java实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。