如何遞歸檢查數字是否是斐波那契數字？

我需要編寫一個遞歸檢查一個數字是否是斐波那契數的程序;反覆做同樣的任務很容易;也很容易遞歸地找到第n個斐波納契數，但我被困在如何使用遞歸檢查數字是否是斐波納契數。這裏是找到第n個fib的代碼。編號：如何遞歸檢查數字是否是斐波那契數字？

int fib(int n){ 
    if (n <= 1){ 
     return n; 
    }else { 
     return (fib(n-1) + fib (n-2)); 
    } 
}

我不知道該怎麼辦是如何修改上面的代碼來檢查給定的數字是否是斐波那契？

來源

2012-11-21 EasyQuestions

您需要在函數本身進行實際測試，然後您需要將其傳遞。你有適當的功能，你只需要向自己陳述你的問題，並寫下你將如何做到這一點，它會來找你。 – sean

這是功課嗎？因爲沒有任何遞歸需要更簡單的方法 – SingerOfTheFall

我知道你迭代迭代或使用數學證明更容易，但它必須遞歸地完成 – EasyQuestions

傳統的方法是使用Gessel的測試。 Ñ是Fibonacci數當且僅當^{5N 2} + 4或^{5N 2} - 4是平方數。這在this SO question和this SO question中討論。你也可以找到例子here，但是這個頁面上有Python代碼（雖然很容易理解）。現在

，如果你被要求專門使用遞歸......好吧一個辦法就是這麼開始產生斐波那契數，直到生成的數字變得更或等於要測試的數量。如果匹配，測試的數字屬於斐波那契數列。如果沒有匹配，並且生成的數字大於測試的數字，則測試的數字不是斐波那契數。

這是一個基本的（和醜陋的），例如你：

bool isFibonacci(int testedNumber, int a = 1, int b = 1) 
{ 
    if(testedNumber == 0 || testedNumber == 1) 
     return true;//returning true for 0 and 1 right away. 
    int nextFib = a + b;//getting the next number in the sequence 
    if(nextFib > testedNumber) 
     return false;//if we have passed the tested number, it's not in the sequence 
    else if(nextFib == testedNumber) 
     return true;//if we have a perfect match, the tested number is in the sequence 
    else 
     isFibonacci(testedNumber, b, nextFib);//otherwise, get the next fibonacci number and repeat. 
}

使用它就像isFibonacci(the_number_you_want_to_test);

注意，斐波那契數可以O(log n)時間計算，如this SO question例如描述。

來源

2012-11-21 06:10:29 SingerOfTheFall

它必須遞歸地完成，我想我的麻煩是如何在每次遞歸調用時存儲結果，因爲在遞歸中，直到它結束纔會計算結果已達到基本情況。 – EasyQuestions

@Easy，我已經更新了答案，請看看 – SingerOfTheFall

完美，謝謝！ – EasyQuestions

Determining whether a number is a Fibonacci number看起來一樣的東西，但在Java - 你很可能得到你要找的內容有。

來源

2012-11-21 06:05:42 Krease

檢查不是遞歸地完成，這就是問題 – EasyQuestions

這感覺有點笨重給我，但你可以嘗試：

bool isFib(int numToCheck int twoPrev = 0, int prev = 1) { 
    if (numToCheck == twoPrev || numToCheck == prev) 
     return true; 

    int currentFibNumber = twoPrev + prev; 
    if (currentFibNumber == numToCheck) 
     return true; 
    else if (currentFibNumber > numToCheck) 
     return false; 

    return isFib(numToCheck, prev, currentFibNumber); 
}

這，直到生成的數量超過您檢查的值或找到匹配使用遞歸迭代基本上斐波那契數。

至於其他的人士指出，有這種不需要遞歸解決方案。

來源

2012-11-21 06:14:53 kevintodisco

感謝發佈，但這需要在第一次調用時將「兩個previos號碼」傳遞給該函數。對？ – EasyQuestions

@EasyQuestions當你將它們聲明爲可選參數時，就像我一樣。像isFib（144）;'這樣的初始調用就足夠了。 – kevintodisco

是的，你是對的！ – EasyQuestions

斐波納契數有一個數學性質。當且僅當（5 * n^2 + 4）或（5 * n^2 - 4）中的一個或兩個是完美正方形（來源：Wiki）時，數字是斐波那契。

該方法比遞歸函數調用方法簡單得多。檢查此鏈接：

http://www.geeksforgeeks.org/check-number-fibonacci-number/

另一種方法：

static bool IsFib(long n)//n is the number to be checked 
{ 
    double root5 = Math.Sqrt(5); 
    double phi = (1 + root5)/2; 

    long idx = (long)Math.Floor(Math.Log(n*root5)/Math.Log(phi) + 0.5); 
    long u = (long)Math.Floor(Math.Pow(phi, idx)/root5 + 0.5); 

    return (u == n); 
}

此代碼適用於大投入。它是由abelenky在類似的問題stackoverflow公佈。

來源

2015-01-08 06:09:33 LoveToLearn

不完全清楚這是什麼增加了接受的答案，除了略有不同（非現場）鏈接...。 –

如何遞歸檢查數字是否是斐波那契數字？

回答

相關問題