3

我需要编写一个程序来递归检查一个数字是否是斐波那契数；迭代地执行相同的任务很容易；递归地找到第 n 个斐波那契数也很容易，但我被困在如何使用递归检查数字是否是斐波那契数。这是查找第 n 个 fib 的代码。数字：

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

我不知道该怎么做是如何修改上面的代码来检查给定的数字是否是斐波那契？

4

4 回答 4

5

传统的方法是使用 Gessel 的测试。N是斐波那契数当且仅当5N 2 + 4或5N 2 – 4是平方数。这在这个 SO question和这个 SO question中进行了讨论。您也可以在此处找到示例，但此页面包含 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)，如本 SO question中所述。

于 2012-11-21T06:10:29.513 回答
1

这对我来说有点笨拙，但你可以尝试：

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-21T06:14:53.540 回答
0

确定一个数字是否是斐波那契数字看起来是一回事，但在 Java 中 - 你可能会在那里找到你想要的东西。

于 2012-11-21T06:05:42.600 回答
0

斐波那契数具有数学属性。一个数字是斐波那契当且仅当 (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-08T06:09:33.563 回答