Определение, является ли число числом Фибоначчи - PullRequest
Новая
       9

Определение, является ли число числом Фибоначчи

7 голосов
/ 29 июня 2010

Мне нужно написать код Java, который проверяет, входит ли введенный пользователем номер в последовательность Фибоначчи.

У меня нет проблем с записью последовательности Фибоначчи для вывода, но (вероятно, потому что поздно ночью) я изо всех сил пытаюсь подумать о последовательности "является ли" это число Фибоначчи. Я продолжаю начинать снова и снова. Это действительно делает мою голову.

В настоящее время у меня есть nth. 

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

Ответы [ 14 ]

28 голосов
/ 29 июня 2010

Прочтите раздел «Распознавание чисел Фибоначчи» в Википедии .

В качестве альтернативы, положительное целое число z является числом Фибоначчи тогда и только тогда, когда одно из 5z ^ 2 + 4 или 5z ^ 2 - 4 является идеальным квадратом. [17]

В качестве альтернативы, вы можете продолжать генерировать числа Фибоначчи до тех пор, пока одно из них не станет равным вашему числу: если это так, то ваше число будет числом Фибоначчи, если нет, числа в конечном итоге станут больше вашего числа, и вы сможете остановиться. Это довольно неэффективно, однако.

10 голосов
/ 29 июня 2010

Если я правильно понимаю, что вам нужно сделать (вместо того, чтобы выписывать первые n числа Фибоначчи), чтобы определить, является ли n числом Фибоначчи.

Таким образом, вы должны изменить свой метод, чтобы он продолжал генерировать последовательность Фибоначчи, пока не получите число> = n. Если оно равно, n - это число Фибоначчи, иначе нет.

Обновление: из-за неоднократных утверждений @ Moron о превосходстве алгоритма на основе формул по сравнению с простым, приведенным выше, я фактически провел сравнение производительности - конкретно между решением Якопо как алгоритм генератора и последняя версия 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) точка зрения заключалась в том, что всегда будет точка переключения, ниже которой алгоритм генератора работает быстрее. Так что утверждения о том, какой из них работает лучше, не имеют смысла вообще, только в контексте.

6 голосов
/ 29 июня 2010

Вместо того, чтобы передавать индекс, n, напишите функцию, которая принимает предел, и заставьте его генерировать числа Фибоначчи вплоть до этого предела включительно. Получите его, чтобы он возвращал логическое значение в зависимости от того, достигнет ли он или пропустит лимит, и вы можете использовать его, чтобы проверить, присутствует ли это значение в последовательности.

Поскольку это домашнее задание, такое толчок, вероятно, это все, что мы должны вам дать ...

3 голосов
/ 02 июля 2010

Хорошо. Так как люди утверждали, что я просто говорю на пустом месте («факты» против «догадок») без каких-либо данных, подтверждающих это, я написал собственный тест.

Не 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, возможно, из-за наличия аппаратной поддержки на моем компьютере. Даже если бы это было 10 ^ 8 (как в тесте Питера), под этим отсечением есть не более 40 чисел Фибоначчи, которые можно легко поместить в справочную таблицу и все же превзойти наивную версию для меньших значений.

Кроме того, у Питера плохая реализация SqrtVersion. На самом деле ему не нужно вычислять два квадратных корня или вычислять силу, используя Math.Pow. Он мог бы хотя бы попытаться сделать это лучше, прежде чем публиковать результаты своих тестов.

В любом случае, я позволю этим фактам говорить за себя, вместо так называемых «догадок».

2 голосов
/ 07 июня 2013 
//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
2 голосов
/ 29 июня 2010

Существует ряд методов, которые можно использовать для определения того, входит ли данное число в последовательность Фибоначчи, выбор из которых можно увидеть в wikipedia .

Учитывая то, что выуже сделали, однако, я бы, вероятно, использовал более грубый подход, такой как следующий:

  1. Генерация числа Фибоначчи
  2. Если оно меньше целевого числа, сгенерируйте следующее число Фибоначчи и повторите
  3. Если это целевое число, тогда успех
  4. Если он больше целевого числа, то сбой.

I 'Возможно, я буду использовать рекурсивный метод, передавая текущее n-значение (т. е. таким образом, оно вычисляет n-е число Фибоначчи) и целевое число.

2 голосов
/ 29 июня 2010

Положительное целое число x является числом Фибоначчи тогда и только тогда, когда одно из 5x ^ 2 + 4 и 5x ^ 2 - 4 является идеальным квадратом

1 голос
/ 29 июня 2010

Пытаясь использовать код, который вы уже написали, я сначала предложил бы следующее, так как это самое простое (но не самое эффективное) решение: 

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;    
}
1 голос
/ 29 июня 2010

Если моя 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;
}
0 голосов
/ 03 ноября 2017

Думал, что все просто, пока мне не пришлось несколько минут ломать голову.Это сильно отличается от генерации последовательности Фибоначчи.Эта функция возвращает 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));
}
Страница:
...