Испытание, если число является фибоначчи

Question

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

Любые идеи?

Answer 1

Очень хороший тест, что N является числом Фибоначчи, если и только если 5 N^2 + 4 или 5N^2 – 4 квадратное число. Для идей о том, как эффективно проверить, что число является квадратным, относятся к SO discussion.

Надеется, что это помогает

Answer 2

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

См. The Faboulous Fibonacci Numbers для получения дополнительной информации.

Answer 3

Положительного целого числа ω является Фибоначчи числом

Если и только если один из 5ω +-и 5ω - 4 является идеальным площадь

с В (Потрясающе) Числа Фибоначчи Альфреда Posamentier и Ингмар Lehmann

bool isFibonacci(int w) 
{ 
     double X1 = 5 * Math.Pow(w, 2) + 4; 
     double X2 = 5 * Math.Pow(w, 2) - 4; 

     long X1_sqrt = (long)Math.Sqrt(X1); 
     long X2_sqrt = (long)Math.Sqrt(X2); 

     return (X1_sqrt*X1_sqrt == X1) || (X2_sqrt*X2_sqrt == X2) ; 
} 

I copied it from this source

---

Snippet, который печатает чисел Фибоначчи между 1k и 10k.

for (int i = 1000; i < 10000; i++) 
{ 
     if (isFibonacci(i)) 
       Console.Write(" "+i); 
} 

OMG Есть только ЧЕТЫРЕ !!!

С другой метод

from math import * 

phi = 1.61803399 
sqrt5 = sqrt(5) 

def F(n): 
    return int((phi**n - (1-phi)**n) /sqrt5) 

def isFibonacci(z): 
    return F(int(floor(log(sqrt5*z,phi)+0.5))) == z 

print [i for i in range(1000,10000) if isFibonacci(i)] 

Answer 4

Поскольку числа Фибоначчи растут в геометрической прогрессии, метод вы предлагаете довольно быстро. Другой номер this.

Answer 5

Если ваши номера имеют ограниченный размер, чем просто положить все числа фибоначчи ниже верхней границы в хеш-таблицу, а тестовое сдерживание сделает трюк. Число фибоначчи очень мало (например, только 38 ниже 5 млн.), Так как они растут экспоненциально.

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

Answer 6

Насколько велики цифры, с которыми вы имеете дело?

Может ли таблица поиска работать на вас? (предварительно вычисленный список номеров, которые вы можете найти в нем)

Существует также closed-form expression, который, я думаю, вы можете инвертировать, чтобы аналитически получить ответ (хотя я не математик, поэтому я не могу обещать, что это предложение имеет смысл)

Answer 7

Чтобы получить решение, взгляните на Формулу Бине.
(Посмотрите на «Замкнутый формы выражения» под Fibonacci Number в Википедии)

Это говорит о том, что последовательность Фибоначчи номера модели создается простой замкнутой формулой:

Я считаю, что если вы решите для n и проверьте, является ли n целым числом, вы получите ответ.

Редактировать Как отмечает @psmears, в той же статье в Википедии есть раздел о обнаружении чисел Фибоначчи. Википедия - отличный источник.

Answer 8

См. Раздел «Распознавание чисел Фибоначчи» на wikipedia article about the Fibonacci numbers.

Answer 9

Материал из Википедии: http://en.wikipedia.org/wiki/Fibonacci_number

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

Answer 10

#!/bin/bash 
victim="144" 
curl http://aux.planetmath.org/files/objects/7680/fib.txt | sed 's/^[0-9]*//;s/[ \t]//g' | grep "^$victim$" >/dev/null 2>/dev/null 
if [[ $? -eq 0 ]] ; then 
    echo "$victim is a fibonacci number" 
else 
    echo "$victim aint" 
fi 

Answer 11

Основываясь на предыдущих ответах по мне и psmears, я написал это C# код.

Он проходит через шаги медленно и четко можно уменьшить и оптимизировано:

// Input: T: number to test. 
// Output: idx: index of the number in the Fibonacci sequence. 
// eg: idx for 8 is 6. (0, 1, 1, 2, 3, 5, 8) 
// Return value: True if Fibonacci, False otherwise. 
static bool IsFib(long T, out int idx) 
{ 
    double root5 = Math.Sqrt(5); 
    double PSI = (1 + root5)/2; 

    // For reference, IsFib(72723460248141) should show it is the 68th Fibonacci number 

    double a; 

    a = T*root5; 
    a = Math.Log(a)/Math.Log(PSI); 
    a += 0.5; 
    a = Math.Floor(a); 
    idx = (Int32)a; 

    long u = (long)Math.Floor(Math.Pow(PSI, a)/root5 + 0.5); 

    if (u == T) 
    { 
     return true; 
    } 
    else 
    { 
     idx = 0; 
     return false; 
    } 
} 

Тестирование показывает, что это работает в течение первых 69 чисел Фибоначчи, но срывается на 70-й.

F(69) = 117,669,030,460,994 - Works 
F(70) = 190,392,490,709,135 - Fails 

В целом, если вы используете библиотеку BigInt какой-то, это, вероятно, лучше, чтобы иметь простую поисковую таблицу чисел Фибоначчи и проверить, что вместо запуска алгоритма.

Список первых 300 номеров можно легко найти в Интернете.

Но в этом коде описывается работоспособный алгоритм, если у вас есть достаточная точность и не переполняйте систему представления чисел.

Answer 12

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

Существует менее 80 чисел Фибоначчи, которые могут быть даже сохранены в стандартном 64-битном целочисленном значении.

Это мое решение, которое полностью использует , чем число, подлежащее проверке.
(написанный на C#, используя основные типы, как double и long. Но алгоритм должен работать нормально для больших типов.)

static bool IsFib(long T, out long idx) 
{ 
    double root5 = Math.Sqrt(5); 
    double phi = (1 + root5)/2; 

    idx = (long)Math.Floor(Math.Log(T*root5)/Math.Log(phi) + 0.5); 
    long u = (long)Math.Floor(Math.Pow(phi, idx)/root5 + 0.5); 

    return (u == T); 
} 

---

Более 4 лет после того, как я написал этот ответ, комментатор спросил о второй параметр, принятый out.

Параметр №2 - это «Индекс» в последовательность Фибоначчи.
Если значение, подлежащее проверке, T является числом Фибоначчи, то idx будет индексом 1 этого числа в последовательности Фибоначчи. (С одним исключением)

Последовательность Фибоначчи 1 1 2 3 5 8 13 и т.д.
3 является 4-м номером в последовательности: IsFib(3, out idx); будет возвращать true и значение 4.
- это 6-е число в следующей последовательности: IsFib(8, out idx); вернет true и значение 6.
13 - 7-й номер; IsFib(13, out idx); вернет true и значение 7.

Единственным исключением является IsFib(1, out idx);, который будет возвращать 2, даже если появляется значение 1 как при индексе 1 и 2.

Если IsFib передается номер, не Фибоначчи, то он вернет false, и значение idx будет индексом самого большого числа Фибоначчи менее T.

16 не является значением Фибоначчи.
IsFib(16, out idx); вернет false и значение 7.
Вы можете использовать Binet's Formula для преобразования индекса 7 в значение Фибоначчи 13, который является самым большим числом, меньшим, чем 16.

Answer 13

Я провел несколько тестов по методам, представленным здесь, наряду с простым сложением, предварительно вычислительном массив, и memoizing результаты в хеше. Для Perl, по крайней мере, метод квадратизации немного быстрее, чем логарифмический метод, возможно, на 20% быстрее. Как указывает Абеленкий, это компромисс между тем, есть ли у вас место для квадратов чисел бит.

Конечно, самым быстрым способом является хэш всех чисел Фибоначчи в вашем доменном пространстве. Вдоль линий другого пункта, который делает абеленки, есть только 94 из этих присосок, которые меньше 2^64.

Вы должны просто предварительно вычислить их и поместить в Perl-хэш, словарь Python или что-то еще.

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

Answer 14

Общее выражение для числа Фибоначчи - это F (n) = [[(1 + sqrt (5))/2] sup n + 1 - [(1-sqrt (5))/2] sup n +1]/sqrt (5) ..... (*) Вторая экспонента стремится к нулю при больших n и выполняет численные операции , мы получаем F (n) = [(1.618) sup n + 1]/2.236

Если K - это число, подлежащее проверке, log (k * 2.2336)/log (1.618) должно быть целым числом!

Пример для K, равный 13, мой калькулятор дает ответ 7.00246 Для K равным 14 ответ 7.1564.

Вы можете повысить уверенность в результате, взяв ближайшее целое число к ответа и подставим в (*), чтобы подтвердить, что результат K

Answer 15

int isfib(int n /* number */, int &pos /* position */) 
{ 
    if (n == 1) 
    { 
     pos=2; // 1 1 
     return 1; 
    } 
    else if (n == 2) 
    { 
     pos=3; // 1 1 2 
     return 1; 
    } 
    else 
    { 
     int m = n /2; 
     int p, q, x, y; 
     int t1=0, t2 =0; 
     for (int i = m; i < n; i++) 
     { 
     p = i; 
     q = n -p; // p + q = n 
     t1 = isfib(p, x); 
     if (t1) t2 = isfib(q, y); 
     if (t1 && t2 && x == y +1) 
     { 
      pos = x+1; 
      return 1; //true 
     } 
     } 
     pos = -1; 
     return 0; //false 
    } 
} 

Как насчет этого?

Answer 16

Re: Код Ахмада - более простой подход, без рекурсии или указателей, довольно наивный, но для чего-то не хватает вычислительной мощности, для чего-либо, кроме действительно титанических чисел (примерно 2N дополнений для проверки номера N-го фибра, который на современном машина займет миллисекунды в худшем случае)

// возвращает поз, если он находит что-либо, 0, если он не (C/C++ рассматривает любое значение! = 0, как верно, так же конечный результат)

int isFib (long n) 
{ 
    int pos = 2; 
    long last = 1; 
    long current = 1; 
    long temp; 

    while (current < n) 
    { 
     temp = last; 
     last = current; 
     current = current + temp; 
     pos++; 
    } 

    if (current == n) 
     return pos; 
    else 
     return 0; 

} 

Answer 17

#include <stdio.h> 
#include <math.h> 

int main() 
{ 
int number_entered, x, y; 

printf("Please enter a number.\n"); 
scanf("%d", &number_entered); 
x = y = 5 * number_entered^2 + 4;  /*Test if 5N^2 + 4 is a square number.*/ 
x = sqrt(x); 
x = x^2; 
if (x == y) 
{ 
     printf("That number is in the Fibonacci sequence.\n"); 
    } 
x = y = 5 * number_entered^2 - 4;  /*Test if 5N^2 - 4 is a square number.*/ 
x = sqrt(x); 
x = x^2; 
if (x == y) 
{ 
    printf("That number is in the Fibonacci sequence.\n"); 
} 
else 
{ 
    printf("That number isn't in the Fibonacci sequence.\n"); 
} 
return 0; 
} 

Будет ли это работать?

Answer 18

Это мое решение Я не уверен, что это тесты. Надеюсь, это поможет!

def is_fibonacci?(i) 
    a,b=0,1 
    until b >= i 
     a,b=b,a+b 
     return true if b == i 
    end 
end 

, что а, Ь = Ь, а + б делает

0, 1 = 1, 0 +1 
1, 1 = 1, 1 + 1 
1, 2 = 2, 1 + 2 
2, 3 = 3, 2 + 3 

fib1 = fib2 
fib2 = fib1 + fib2 

Answer 19

A Scala версию-

def isFib(n: Int): Boolean = { 

def checkFib(f1: Int = 1, f2: Int = 1): Boolean = { 

if(n == f1 || n == f2) true 
else if(n < f2) false 
else checkFib(f2, f1+f2) 

} 

checkFib() 

} 

Answer 20

решение Java может быть сделано, как показано ниже. Но все это может быть оптимизировано

следующее решение работает для

1. 1≤T≤10^5
2. 1≤N≤10^10

Т No.of тест случаи, N является диапазон числа

import java.util.Scanner; 
    import java.math.BigDecimal; 
    import java.math.RoundingMode; 

    public class FibonacciTester { 
     private static BigDecimal zero = BigDecimal.valueOf(0); 
     private static BigDecimal one = BigDecimal.valueOf(1); 
     private static BigDecimal two = BigDecimal.valueOf(2); 
     private static BigDecimal four = BigDecimal.valueOf(4); 
     private static BigDecimal five = BigDecimal.valueOf(5); 

     public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in); 
      int n = sc.nextInt(); 
      BigDecimal[] inputs = new BigDecimal[n]; 
      for (int i = 0; i < n; i++) { 
       inputs[i] = sc.nextBigDecimal(); 
      } 

      for (int i = 0; i < inputs.length; i++) { 
       if (isFibonacci(inputs[i])) 
        System.out.println("IsFibo"); 
       else 
        System.out.println("IsNotFibo"); 
      } 


     } 

     public static boolean isFibonacci(BigDecimal num) { 
      if (num.compareTo(zero) <= 0) { 
       return false; 
      } 

      BigDecimal base = num.multiply(num).multiply(five); 
      BigDecimal possibility1 = base.add(four); 
      BigDecimal possibility2 = base.subtract(four); 


      return (isPerfectSquare(possibility1) || isPerfectSquare(possibility2)); 
     } 

     public static boolean isPerfectSquare(BigDecimal num) { 
      BigDecimal squareRoot = one; 
      BigDecimal square = one; 
      BigDecimal i = one; 
      BigDecimal newSquareRoot; 
      int comparison = -1; 

      while (comparison != 0) { 
       if (comparison < 0) { 
        i = i.multiply(two); 
        newSquareRoot = squareRoot.add(i).setScale(0, RoundingMode.HALF_UP); 
       } else { 
        i = i.divide(two); 
        newSquareRoot = squareRoot.subtract(i).setScale(0, RoundingMode.HALF_UP); 
       } 

       if (newSquareRoot.compareTo(squareRoot) == 0) { 
        return false; 
       } 

       squareRoot = newSquareRoot; 
       square = squareRoot.multiply(squareRoot); 
       comparison = square.compareTo(num); 
      } 

      return true; 
     } 
    }