費氏數列(fibonacci sequence)是程式語言中常見的遞迴範例
他的每一項分別是：
A0=0
A1=1
AN=A(N-1)+A(N-2)
也就是A2以後，每一項的值就是前兩項的值相加
使用遞迴的方法可以把費式數列的值做出來
以下是遞迴的範例
public class FibonacciTest {
public static void main(String[] args) {
System.out.println(fibonacci(50));
}
public static long fibonacci(int x){
if(x==1||x==2){
return 1;
}else {
return fibonacci(x-1)+fibonacci(x-2);
}
}
}
但是使用遞迴的效能很差
所以如果有人提出這個問題
又沒有特別規定要用遞迴做出來的話
建議使用一般的迴圈來解決這個問題
效能會有明顯的改善
以下是範例
public class FibonacciDemo {
public static void main(String[] args) {
FibonacciDemo demo = new FibonacciDemo();
System.out.println(demo.fibonacci(50));
}
public long fibonacci(int n){
if(n==0){
return 0;
} else {
long x_1 = 0;
long x_2 = 1;
for(int i=0;i<n;i++){
if(i>0){
x_2 = x_2 + x_1;
x_1 = x_2 - x_1;
}
}
return x_2;
}
}
}
全站熱搜
留言列表
