7

我需要编写一个 Java 代码来检查用户输入的数字是否在斐波那契数列中。

我将斐波那契数列写入输出没有问题，但是（可能是因为它在深夜）我正在努力思考“是否”它是斐波那契数的序列。我不断地从头开始。它真的让我很头疼。

我目前拥有的是第n个。 

public static void main(String[] args)
{
    ConsoleReader console = new ConsoleReader();

    System.out.println("Enter the value for your n: ");
    int num = (console.readInt());
    System.out.println("\nThe largest nth fibonacci: "+fib(num));
    System.out.println();
}

static int fib(int n){
    int f = 0;
    int g = 1;
    int largeNum = -1;
    for(int i = 0; i < n; i++)
    {
      if(i == (n-1))
          largeNum = f;
      System.out.print(f + " ");
      f = f + g;
      g = f - g;
    }
    return largeNum;
}
4

14 回答 14

28

阅读维基百科上标题为“识别斐波那契数”的部分。

或者，正整数 z 是斐波那契数当且仅当 5z^2 + 4 或 5z^2 - 4 之一是完美正方形。 [17]

或者，您可以继续生成斐波那契数，直到一个等于您的数字：如果是，那么您的数字是斐波那契数，如果不是，数字最终将变得大于您的数字，您可以停止。然而，这是非常低效的。

于 2010-06-29T10:11:51.523 回答
10

如果我理解正确，您需要做的（而不是写出前n 个斐波那契数）是确定n是否是一个斐波那契数。

所以你应该修改你的方法以继续生成斐波那契数列，直到你得到一个 >= n 的数字。如果它等于，n是一个斐波那契数，否则不是。

更新：被@Moron 反复声称基于公式的算法在性能上优于上述简单算法的说法所困扰，我实际上做了一个基准比较——具体是在 Jacopo 的解决方案作为生成器算法和 StevenH 的最后一个版本作为基于公式的算法之间。作为参考，这里是确切的代码：

public static void main(String[] args) {
    measureExecutionTimeForGeneratorAlgorithm(1);
    measureExecutionTimeForFormulaAlgorithm(1);

    measureExecutionTimeForGeneratorAlgorithm(10);
    measureExecutionTimeForFormulaAlgorithm(10);

    measureExecutionTimeForGeneratorAlgorithm(100);
    measureExecutionTimeForFormulaAlgorithm(100);

    measureExecutionTimeForGeneratorAlgorithm(1000);
    measureExecutionTimeForFormulaAlgorithm(1000);

    measureExecutionTimeForGeneratorAlgorithm(10000);
    measureExecutionTimeForFormulaAlgorithm(10000);

    measureExecutionTimeForGeneratorAlgorithm(100000);
    measureExecutionTimeForFormulaAlgorithm(100000);

    measureExecutionTimeForGeneratorAlgorithm(1000000);
    measureExecutionTimeForFormulaAlgorithm(1000000);

    measureExecutionTimeForGeneratorAlgorithm(10000000);
    measureExecutionTimeForFormulaAlgorithm(10000000);

    measureExecutionTimeForGeneratorAlgorithm(100000000);
    measureExecutionTimeForFormulaAlgorithm(100000000);

    measureExecutionTimeForGeneratorAlgorithm(1000000000);
    measureExecutionTimeForFormulaAlgorithm(1000000000);

    measureExecutionTimeForGeneratorAlgorithm(2000000000);
    measureExecutionTimeForFormulaAlgorithm(2000000000);
}

static void measureExecutionTimeForGeneratorAlgorithm(int x) {
    final int count = 1000000;
    final long start = System.nanoTime();
    for (int i = 0; i < count; i++) {
        isFibByGeneration(x);
    }
    final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9;
    System.out.println("Running generator algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds");
}

static void measureExecutionTimeForFormulaAlgorithm(int x) {
    final int count = 1000000;
    final long start = System.nanoTime();
    for (int i = 0; i < count; i++) {
        isFibByFormula(x);
    }
    final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9;
    System.out.println("Running formula algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds");
}

static boolean isFibByGeneration(int x) {
    int a=0;
    int b=1;
    int f=1;
    while (b < x){
        f = a + b;
        a = b;
        b = f;
    }
    return x == f;
}

private static boolean isFibByFormula(int num) {
    double first = 5 * Math.pow((num), 2) + 4;
    double second = 5 * Math.pow((num), 2) - 4;

    return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}

private static boolean isWholeNumber(double num) {
    return num - Math.round(num) == 0;
}

结果甚至让我感到惊讶：

Running generator algorithm 1000000 times for 1 took 0.007173537000000001 seconds
Running formula algorithm 1000000 times for 1 took 0.223365539 seconds
Running generator algorithm 1000000 times for 10 took 0.017330694 seconds
Running formula algorithm 1000000 times for 10 took 0.279445852 seconds
Running generator algorithm 1000000 times for 100 took 0.030283179 seconds
Running formula algorithm 1000000 times for 100 took 0.27773557800000004 seconds
Running generator algorithm 1000000 times for 1000 took 0.041044322 seconds
Running formula algorithm 1000000 times for 1000 took 0.277931134 seconds
Running generator algorithm 1000000 times for 10000 took 0.051103143000000004 seconds
Running formula algorithm 1000000 times for 10000 took 0.276980175 seconds
Running generator algorithm 1000000 times for 100000 took 0.062019335 seconds
Running formula algorithm 1000000 times for 100000 took 0.276227007 seconds
Running generator algorithm 1000000 times for 1000000 took 0.07422898800000001 seconds
Running formula algorithm 1000000 times for 1000000 took 0.275485013 seconds
Running generator algorithm 1000000 times for 10000000 took 0.085803922 seconds
Running formula algorithm 1000000 times for 10000000 took 0.27701090500000003 seconds
Running generator algorithm 1000000 times for 100000000 took 0.09543419600000001 seconds
Running formula algorithm 1000000 times for 100000000 took 0.274908403 seconds
Running generator algorithm 1000000 times for 1000000000 took 0.10683704200000001 seconds
Running formula algorithm 1000000 times for 1000000000 took 0.27524084800000004 seconds
Running generator algorithm 1000000 times for 2000000000 took 0.13019867100000002 seconds
Running formula algorithm 1000000 times for 2000000000 took 0.274846384 seconds

简而言之，生成器算法方式在所有正 int 值上都优于基于公式的解决方案 - 即使接近最大 int 值，它的速度也快两倍以上！基于信念的性能优化就这么多；-)

作为记录，修改上面的代码以使用long变量而不是int，生成器算法变得更慢（正如预期的那样，因为它现在必须将long值相加），并且公式开始更快的截止点大约是 1000000000000L，即 10 12 .

Update2：正如 IVlad 和 Moron 所指出的，我并不是浮点计算方面的专家 :-) 根据他们的建议，我将公式改进为：

private static boolean isFibByFormula(long num)
{
    double power = (double)num * (double)num;
    double first = 5 * power + 4;
    double second = 5 * power - 4;

    return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}

这将切换点降低到大约。10 8（对于long版本 -int对于所有 int 值，生成器仍然更快）。毫无疑问，用sqrt@Moron 建议的方式替换呼叫会进一步降低切换点。

我（和 IVlad 的）的观点很简单，就是总会有一个切换点，低于该点生成器算法会更快。因此，关于哪个表现更好的说法通常没有意义，只有在上下文中。

于 2010-06-29T10:11:05.600 回答
6

与其传递索引，n不如编写一个接受限制的函数，并让它生成斐波那契数，直到并包括这个限制。让它返回一个布尔值，具体取决于它是否达到或跳过限制，您可以使用它来检查该值是否在序列中。

既然是家庭作业，我们应该给你的就是这样的轻推……

于 2010-06-29T10:08:28.240 回答
3

好的。由于人们声称我只是空谈（“事实”与“猜测”），没有任何数据支持，因此我编写了自己的基准。

不是java，而是下面的C#代码。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SO
{
    class Program
    {
        static void Main(string[] args)
        {
            AssertIsFibSqrt(100000000);

            MeasureSequential(1);
            MeasureSqrt(1);

            MeasureSequential(10);
            MeasureSqrt(10);

            MeasureSequential(50);
            MeasureSqrt(50);

            MeasureSequential(100);
            MeasureSqrt(100);


            MeasureSequential(100000);
            MeasureSqrt(100000);

            MeasureSequential(100000000);
            MeasureSqrt(100000000);

        }

        static void MeasureSequential(long n)
        {
            int count = 1000000;
            DateTime start = DateTime.Now;
            for (int i = 0; i < count; i++)
            {
                IsFibSequential(n);
            }
            DateTime end = DateTime.Now;

            TimeSpan duration = end - start;

            Console.WriteLine("Sequential for input = " + n + 
                              " : " + duration.Ticks);
        }

        static void MeasureSqrt(long n)
        {
            int count = 1000000;

            DateTime start = DateTime.Now;
            for (int i = 0; i < count; i++)
            {
                IsFibSqrt(n);
            }
            DateTime end = DateTime.Now;

            TimeSpan duration = end - start;

            Console.WriteLine("Sqrt for input =  " + n + 
                              " : " + duration.Ticks);
        }

        static void AssertIsFibSqrt(long x)
        {

            Dictionary<long, bool> fibs = new Dictionary<long, bool>();
            long a = 0;
            long b = 1;
            long f = 1;

            while (b < x)
            {
                f = a + b;
                a = b;
                b = f;

                fibs[a] = true;
                fibs[b] = true;
            }

            for (long i = 1; i <= x; i++)
            {
                bool isFib = fibs.ContainsKey(i);

                if (isFib && IsFibSqrt(i))
                {
                    continue;
                }

                if (!isFib && !IsFibSqrt(i))
                {
                    continue;
                }

                Console.WriteLine("Sqrt Fib test failed for: " + i);
            }
        }
        static bool IsFibSequential(long x)
        {
            long a = 0;
            long b = 1;
            long f = 1;

            while (b < x)
            {
                f = a + b;
                a = b;
                b = f;
            }
            return x == f;
        }

        static bool IsFibSqrt(long x)
        {
            long y = 5 * x * x + 4;

            double doubleS = Math.Sqrt(y);

            long s = (long)doubleS;

            long sqr = s*s;

            return (sqr == y || sqr == (y-8));
        }
    }
}

这是输出

Sequential for input = 1 : 110011
Sqrt for input =  1 : 670067

Sequential for input = 10 : 560056
Sqrt for input =  10 : 540054

Sequential for input = 50 : 610061
Sqrt for input =  50 : 540054

Sequential for input = 100 : 730073
Sqrt for input =  100 : 540054

Sequential for input = 100000 : 1490149
Sqrt for input =  100000 : 540054

Sequential for input = 100000000 : 2180218
Sqrt for input =  100000000 : 540054

当 n=50 本身时，sqrt 方法胜过天真的方法，这可能是由于我的机器上存在硬件支持。即使它是 10^8（如在彼得的测试中），在该截止值下最多有 40 个斐波那契数，可以很容易地将其放入查找表中，并且对于较小的值仍然可以击败幼稚版本。

此外，Peter 对 SqrtVersion 的实现也很糟糕。他实际上并不需要使用 Math.Pow 计算两个平方根或计算幂。在发布他的基准测试结果之前，他至少可以尝试让它变得更好。

无论如何，我会让这些事实自己说话，而不是所谓的“猜测”。

于 2010-07-01T21:40:58.740 回答
2 
//Program begins


public class isANumberFibonacci {

    public static int fibonacci(int seriesLength) {
        if (seriesLength == 1 || seriesLength == 2) {
            return 1;
        } else {
            return fibonacci(seriesLength - 1) + fibonacci(seriesLength - 2);
        }
    }

    public static void main(String args[]) {
        int number = 4101;
        int i = 1;
        while (i > 0) {
            int fibnumber = fibonacci(i);
            if (fibnumber != number) {
                if (fibnumber > number) {
                    System.out.println("Not fib");
                    break;
                } else {
                    i++;
                }
            } else {
                System.out.println("The number is fibonacci");
                break;
            }
        }
    }
}

//Program ends
于 2013-06-07T16:37:19.877 回答
2

正整数 x 是斐波那契数当且仅当 5x^2 + 4 和 5x^2 - 4 之一是完美平方

于 2010-06-29T10:12:45.513 回答
2

有许多方法可以用来确定给定的数字是否在斐波那契数列中，可以在wikipedia上看到其中的一部分。

但是，鉴于您已经完成的工作，我可能会使用更暴力的方法，例如：

  1. 生成斐波那契数
  2. 如果小于目标数，则生成下一个斐波那契并重复
  3. 如果是目标数，则成功
  4. 如果它大于目标数，则失败。

我可能会使用递归方法，传入当前的 n 值（即它计算第 n 个斐波那契数）和目标数。

于 2010-06-29T10:24:57.423 回答
1

如果我的 Java 不是太生锈...

static bool isFib(int x) {
    int a=0;
    int b=1;
    int f=1;
    while (b < x){
        f = a + b;
        a = b;
        b = f;
    }
    return x == f;
}
于 2010-06-29T10:16:28.533 回答
1

尝试利用您已经编写的代码，我将首先提出以下建议，因为它是最简单的解决方案（但不是最有效的）：

private static void main(string[] args)
{
    //This will determnine which numbers between 1 & 100 are in the fibonacci series
    //you can swop in code to read from console rather than 'i' being used from the for loop
    for (int i = 0; i < 100; i++)
    {
        bool result = isFib(1);

        if (result)
            System.out.println(i + " is in the Fib series.");

        System.out.println(result);
    }

}

private static bool isFib(int num)
{
    int counter = 0;

    while (true)
    {
        if (fib(counter) < num)
        {
            counter++;
            continue;
        }

        if (fib(counter) == num)
        {
            return true;
        }

        if (fib(counter) > num)
        {
            return false;
        }
    }
}

我会在生成斐波那契数时提出一个更优雅的解决方案，它利用递归，如下所示：

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

对于额外的信用阅读： http ://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers

你会看到有一些更有效的方法来测试一个数字是否在斐波那契数列中，即：(5z^2 + 4 或 5z^2 − 4) = 一个完美的正方形。

//(5z^2 + 4 or 5z^2 − 4) = a perfect square 
//perfect square = an integer that is the square of an integer
private static bool isFib(int num)
{
    double first = 5 * Math.pow((num), 2) + 4;
    double second = 5 * Math.pow((num), 2) - 4;

    return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}

private static bool isWholeNumber(double num)
{
    return num - Math.round(num) == 0;    
}
于 2010-06-29T10:24:53.977 回答
0

您可以通过两种方式做到这一点，递归和数学。递归方式开始生成斐波那契数列，直到您点击数字或通过这里很好描述的数学方式... http://www.physicsforums.com/showthread.php?t=252798

祝你好运。

于 2010-06-29T11:44:51.407 回答
0

考虑斐波那契数列 1、1、2、3、5、8、13、21 等。希望构建 3 个堆栈，每个容量为 10，包含来自上述序列的数字，如下所示：

堆栈 1：序列中的前 10 个数字。堆栈 2：序列中的前 10 个素数。堆栈 3：序列中的前 10 个非质数。

(i) 给出流程图的算法 (ii) 编写一个程序（在 BASIC、C++ 或 Java 中）来实现它。

输出：当堆栈操作发生时，您应该以任何方便的形式显示 3 个堆栈以及其中保存的值。

于 2013-09-20T12:01:58.367 回答
0

我不知道是否有可以应用于用户输入的实际公式，但是，您可以生成斐波那契序列并根据用户输入检查它，直到它变得小于最后生成的数字。

int userInput = n;
int a = 1, b = 1;

while (a < n) {
  if (a == n)
    return true;

  int next = a + b;
  b = a;
  a = next;
}

return false;
于 2010-06-29T10:13:30.707 回答
0

根据公式找出一个数字是否是斐波那契：

public static boolean isNumberFromFibonacciSequence(int num){

    if (num == 0 || num == 1){
        return true;
    }

    else {
        //5n^2 - 4 OR 5n^2 + 4 should be perfect squares
        return isPerfectSquare( 5*num*num - 4) || isPerfectSquare(5*num*num - 4);
    }
}

private static boolean isPerfectSquare(int num){
        double sqrt = Math.sqrt(num);
        return sqrt * sqrt == num;
}
于 2016-07-28T22:15:39.953 回答
0

认为这很简单，直到我不得不在它上面绞尽脑汁几分钟。它与生成斐波那契数列完全不同。如果是斐波那契，则此函数返回 1，否则返回 0

public static int isFibonacci (int n){
  int isFib = 0;
  int a = 0, b = 0, c = a + b; // set up the initial values
  do 
   {
    a = b;
    b = c;
    c = a + b;
    if (c == n)
    isFib = 1;
    } while (c<=n && isFin == 0)
  return isFib;
}

public static void main(String [] args){
  System.out.println(isFibonacci(89));
}
于 2017-11-03T00:39:40.117 回答