Тест, если число является fibonacci

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

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

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

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

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

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

Если и только если одно из {{1} } 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);
}

ОМГ! Их всего ЧЕТЫРЕ !!!

Другим методом

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)]

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

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

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

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

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

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

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

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

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

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

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

Основываясь на предыдущих ответах меня и 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 чисел можно легко найти в Интернете.

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

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

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

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

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

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

Существует менее 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);
}

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

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

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

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

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