【分享】費氏數列

[johnroyer 10]

之前教授提供一個費氏數列的網站

覺得不錯

與大家分享

網址：http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html

另外

費氏數列的遞迴 ( C Language )是

int fib(int n)

{

if( n==0 ) return 0;

if( n==1 ) return 1;

if( n>1 ) return fib(n-2)+fib(n1);

}

執行效益不高

有另一種演算法提供給大家 供參考 ^^~

long fib(int n) {

if (n==0) return(1);

if (n==1) return(1);

if (n==2) return(2);

if (n % 2 == 0) {

return (fib(n/2+1)* fib(n/2)- fib(n/2-1)* fib(n/2-2));

}

else {

return (fib(n/2+1)* fib(n/2)+ fib(n/2)* fib(n/2-1));

}

}

[電腦狂 10]

我覺得之前3行不要用if會比較好~因為前3項是固定的

直接輸入像fib(1)=1;fib(2)=1;fib(3)=2;這樣應該會比較快吧?

畢竟判斷式比較花時間

[johnroyer 10]

判斷跟遞回

遞回花的時間比判斷來的多

[wensmart 10]

遞迴花的時間非常龐大。

參考看看~!

int fib(int n)

{

int n1=0,n2=0,sum=1,i;

if((n==1) || (n==0))

return n;

else

{

for(i=2;i<=n;i++)

{

n1=sum;

sum=sum+n2;

n2=n1;

}

return sum;

}

}

[weiye 10]

來個 Lisp 語言 遞迴版本的

(defun fib (n)
	"this function returns the n-th term of Fibonacci sequence."
	(if (or (= n 1) (= n 2))
		1
		(+ (fib (- n 1)) (fib (- n 2)))
	)
)

雖然沒有蝦咪新意~ XD