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

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

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

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

Answer 2

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

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

Update: прослушивались @ неоднократные претензии 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 больше, чем в два раза быстрее! Так много для веры на основе оптимизации производительности ;-)

Для записи, модифицирующих приведенный выше код, чтобы использовать long переменные вместо int, алгоритм генератора (теперь, как и следовало ожидать, так как он должен сложить long значения) становится медленнее , и точка пересечения, где формула начинает быть быстрее, составляет около 1000000000000L, то есть 10 .

Update2: Как IVlad и Морон отметило, я не совсем эксперта в области вычислений с плавающей точкой :-) на основе их предложения, которые я улучшил формулу следующим образом:

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

Моей точкой (и IVlad's) было просто, что всегда будет точка пересечения, ниже которой алгоритм генератора будет быстрее. Поэтому утверждения о том, что один из них лучше работает, не имеют никакого значения вообще, только в контексте.

Answer 3

Прочитать раздел под названием «распознавание чисел фибоначчи» по телефону wikipedia.

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

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

Answer 4

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

Answer 5

Я не знаю, если существует реальная формула, что вы могут применяться к пользовательскому вводу, однако вы можете сгенерировать последовательность фибоначчи и проверить его на вход пользователя, пока он не станет меньше последнего сгенерированного числа.

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 6

Если мой 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 7

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

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 8

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

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

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

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

Answer 9

Вы можете сделать это двумя способами: рекурсивным и математическим. рекурсивный способ начинает генерировать последовательность Фибоначчей, пока вы нажмете номер или передать его математический способу хорошо описанный здесь ... http://www.physicsforums.com/showthread.php?t=252798

удачи.

Answer 10

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

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

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

Answer 11

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

Рассмотрим последовательность чисел Фибоначчи 1,1,2,3,5,8,13,21 и т.д. Желательно, чтобы построить 3 стеки каждый из емкости 10, содержащий номера из вышеуказанных последовательностей следующим :

Стек 1: первые 10 чисел из последовательности. Стек 2: первые 10 простых чисел из последовательности. Стек 3: первые 10 не простых чисел из последовательности.

(i) Дайте алгоритм блок-схемы (ii) Запишите программу (в BASIC, C++ или Java) для ее реализации.

Выход: Когда выполняются операции стека, вы должны отображать в любой удобной форме 3 стека вместе со значениями, содержащимися в них.

Answer 13

Выяснить, является ли число Фибоначчи на основе формулы:

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 14

Думал, что это было просто, пока я не должен был ломать голову над этим несколько минут. Его отличие от генерации последовательности фибоначчи. Эта функция возвращает 1, если Fibonnaci или 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)); 
}