Проверьте, является ли число Фибоначчи

Question

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

Есть идеи?

Answer 1

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

Надеюсь, это поможет

Answer 2

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

См. Невероятные числа Фибоначчи для более.

Answer 3

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

Существует менее 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.
8 является шестым числом в последовательности: IsFib(8, out idx); вернет true и значение 6.
13 - седьмое число; 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.
Вы можете использовать Формула Бине для преобразования индекса 7 в значение 13 Фибоначчи, которое является наибольшим числом меньше 16.

Answer 4

#!/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 5

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

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

Answer 6

В поисках решения взгляните на формулу Бине.
(Ищите «Выражение в закрытой форме» в Число Фибоначчи в Википедии)

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

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

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

Answer 7

Положительное целое число ω - число Фибоначчи

Если и только если один из 5ω ² + 4 и 5ω ² - 4 - идеальный квадрат

из (Сказочные) числа Фибоначчи Альфреда Посаментье и Ингмара Лемана

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

Я скопировал его из этого источника

---

Фрагмент, который печатает числа Фибоначчи от 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 8

См. Раздел «Распознавание чисел Фибоначчи» в статье Википедии о числах Фибоначчи .

Answer 9

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

Answer 10

Из Википедии: http://en.wikipedia.org/wiki/Fibonacci_number

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