java - 数値がフィボナッチ数かどうかの判定

Question

ユーザーが入力した数値がフィボナッチ数列に含まれているかどうかを確認する 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;
}

Answer 1

ウィキペディアの「フィボナッチ数の認識」というタイトルのセクションを読んでください。

あるいは、5z^2 + 4 または 5z^2 − 4 のいずれかが完全平方である場合にのみ、正の整数 z はフィボナッチ数です。

または、フィボナッチ数があなたの数と等しくなるまで生成し続けることもできます: もしそうであれば、あなたの数はフィボナッチ数です. ただし、これはかなり非効率的です。

Answer 2

私の理解が正しければ、(最初のn 個のフィボナッチ数を書き出す代わりに) すべきことは、 nがフィボナッチ数かどうかを判断することです。

したがって、数値 >= n になるまでフィボナッチ数列を生成し続けるようにメソッドを変更する必要があります。等しい場合、nはフィボナッチ数であり、そうでない場合はそうではありません。

更新:式ベースのアルゴリズムが上記の単純なアルゴリズムよりもパフォーマンスが優れているという@Moronの繰り返しの主張に悩まされ、実際にベンチマーク比較を行いました。参考までに、正確なコードは次のとおりです。

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 値に近づいても、2 倍以上高速です。信念に基づいたパフォーマンスの最適化についてはこれで終わりです;-)

記録のために、上記のコードをlongの代わりに変数を使用するように変更するintと、ジェネレーターのアルゴリズムが遅くなり (予想どおり、long値を加算する必要があるため)、式が高速になり始めるカットオーバー ポイントは約 1000000000000L、つまり 10 ¹²になります。 .

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));
}

これにより、カットオーバー ポイントが約 1 に下がりました。10 ⁸ (longバージョンの場合 - を使用したジェネレーターintは、すべての int 値に対してさらに高速です)。sqrt呼び出しを@Moronが提案するようなものに置き換えると、カットオーバーポイントがさらに押し下げられることは間違いありません。

私 (および IVlad) の要点は、常にカットオーバー ポイントがあり、それ以下ではジェネレーター アルゴリズムが高速であるということでした。したがって、どちらがより優れているかについての主張は、一般的には意味がなく、文脈の中でのみ意味があります.

Answer 3

インデックス を渡す代わりにn、制限を受け取る関数を作成し、それを取得して、この制限までのフィボナッチ数を生成します。制限に達するかスキップするかに応じてブール値を返すように取得します。これを使用して、その値がシーケンス内にあるかどうかを確認できます。

宿題なので、このようなナッジで十分でしょう...

Answer 4

Ok。人々は私がそれをバックアップするためのデータなしでただ薄い空気（「事実」対「推測」）を話していると主張したので、私は自分自身のベンチマークを書きました。

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

sqrtメソッドは、n = 50自体の場合、単純なメソッドよりも優れています。これは、おそらく私のマシンにハードウェアサポートが存在するためです。（Peterのテストのように）10 ^ 8であったとしても、そのカットオフの下には最大40のフィボナッチ数があり、ルックアップテーブルに簡単に入れることができ、小さい値ではナイーブバージョンを上回ります。

また、PeterのSqrtVersionの実装は不適切です。彼は、Math.Powを使用して2つの平方根を計算したり、累乗を計算したりする必要はありません。彼は、ベンチマーク結果を公開する前に、少なくともそれを改善しようとした可能性があります。

とにかく、私はこれらの事実を、いわゆる「推測」の代わりに、それ自体で語らせます。

Answer 5

与えられた数がフィボナッチ数列にあるかどうかを判断するために使用できるいくつかの方法があり、その選択はウィキペディアで見ることができます。

ただし、すでに行ったことを考えると、おそらく次のような、より力ずくのアプローチを使用するでしょう。

1. フィボナッチ数を生成する
2. 目標数より少ない場合は、次のフィボナッチを生成して繰り返します
3. それが目標数であれば、成功
4. 目標数よりも大きい場合は失敗します。

私はおそらく再帰的な方法を使用して、現在のn値（つまり、n番目のフィボナッチ数を計算する）とターゲット数を渡します。

Answer 6

//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

Answer 7

正の整数 x は、5x^2 + 4 と 5x^2 - 4 のいずれかが完全平方である場合に限り、フィボナッチ数です。

Answer 8

すでに作成したコードを活用しようとすると、最初に次のことを提案します。これは最も単純なソリューションです（ただし、最も効率的ではありません）。

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;    
}

Answer 9

私の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;
}

Answer 10

数式に基づいて数値がフィボナッチであるかどうかを調べる:

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;
}

Answer 11

これは、再帰的方法と数学的方法の 2 つの方法で行うことができます。再帰的な方法で、数値に到達するまでフィボナッチ数列の生成を開始するか、ここで適切に説明されている数学的な方法で渡します... http://www.physicsforums.com/showthread.php?t=252798

幸運を。

Answer 12

ユーザー入力に適用できる実際の数式があるかどうかはわかりませんが、フィボナッチ数列を生成し、最後に生成された数値よりも小さくなるまでユーザー入力と照合することができます。

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;

Answer 13

フィボナッチ数列 1、1、2、3、5、8、13、21 などを考えてみましょう。次のように、上記の数列からの数値を含む容量 10 のスタックを 3 つ構築することが望まれます。

スタック 1: シーケンスの最初の 10 個の数字。スタック 2: シーケンスの最初の 10 個の素数。スタック 3: シーケンスの最初の 10 個の非素数。

(i) フローチャートのアルゴリズムを与えてください。 (ii) これを実装するためのプログラムを (BASIC、C++、または Java で) 書きなさい。

出力: スタック操作が行われると、3 つのスタックとそれらに保持されている値を任意の便利な形式で表示する必要があります。