快速斐波那契使用遞歸

我在Scala中實現了一個斐波那契函數，它工作正常，但是當我輸入50時需要很長的時間來計算它，因爲它必須每次計算2個前面的整數。我發現了一個保留前兩個數字的函數。然而，有人可以告訴我如何編寫這個函數來讓它接受2個整數而不是3個，並返回最後2個數字來計算特定索引x處的斐波那契數。謝謝！快速斐波那契使用遞歸

def fastFib(x: Long): Long = { 
     def fast(x:Long , a:Long, b:Long):Long = 
     if (x<=0) a+b 
     else fast(x-1,b,a+b) 
     if (x<2) 1 
     else fast(x-2,0,1) 
    }

來源

2013-11-02 user2947615

請首先嚐試搜索。 http://stackoverflow.com/questions/7388416/what-is-the-fastest-way-to-write-fibonacci-function-in-scala – psisoyev

哦，好吧，就像在發佈的鏈接中，你可以使用明確的公式不需要以前的結果 –

我不明白那個.. – user2947615

可以緩存中間結果，那麼你永遠不會重新計算相同的結果兩次

下面是代碼

//this supposed to contains all the value when initialized 
//initialized with 0 for all value 
val cache = Array [Int] (101);//0 to 100 
cache(1)==1;//initial value 
cache(2)=1;//initial value 

def fibonacciCache(n:Int) : Int = { 
    if (n>100) 
    { 
     println("error"); 
     return -1; 
    } 

    if (cache(n)!=0)//means value has been calculated 
    return cache(n); 
    else 
    { 
    cache(n)=fibonacciCache(n-1)+fibonacciCache(n-2); 
    return cache(n);  
    } 
}

希望幫助

來源

2014-11-22 22:13:52 Gabriel

快速斐波那契使用遞歸

回答

相關問題