Как проверить является ли число числом фибоначчи

Как проверить является ли число числом фибоначчи

Последовательность чисел Фибоначчи определяется формулой F_n = F_n-1 + F_n-2 . То есть, следующее число получается как сумма двух предыдущих.

Первые два числа равны 1 , затем 2(1+1) , затем 3(1+2) , 5(2+3) и так далее: 1, 1, 2, 3, 5, 8, 13, 21. .

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

Напишите функцию fib(n) которая возвращает n-е число Фибоначчи.

function fib(n) < /* ваш код */ >alert(fib(3)); // 2 alert(fib(7)); // 13 alert(fib(77)); // 5527939700884757

P.S. Все запуски функций из примера выше должны работать быстро. Вызов fib(77) должен занимать не более доли секунды.

Сначала решим через рекурсию.

Числа Фибоначчи рекурсивны по определению:

function fib(n) < return n alert( fib(3) ); // 2 alert( fib(7) ); // 13 // fib(77); // вычисляется очень долго

При больших значениях n такое решение будет работать очень долго. Например, fib(77) может повесить браузер на некоторое время, съев все ресурсы процессора.

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

Например, посмотрим на отрывок вычислений для fib(5) :

. fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) . 

Здесь видно, что значение fib(3) нужно одновременно и для fib(5) и для fib(4) . В коде оно будет вычислено два раза, совершенно независимо.

Полное дерево рекурсии:

Можно заметить, что fib(3) вычисляется дважды, а fib(2) – трижды. Общее количество вычислений растёт намного быстрее, чем n , что делает его огромным даже для n=77 .

Можно это оптимизировать, запоминая уже вычисленные значения: если значение, скажем, fib(3) вычислено однажды, затем мы просто переиспользуем это значение для последующих вычислений.

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

Вместо того, чтобы начинать с n и вычислять необходимые предыдущие значения, можно написать цикл, который начнёт с 1 и 2 , затем из них получит fib(3) как их сумму, затем fib(4) как сумму предыдущих значений, затем fib(5) и так далее, до финального результата. На каждом шаге нам нужно помнить только значения двух предыдущих чисел последовательности.

Вот детальные шаги нового алгоритма.

// a = fib(1), b = fib(2), эти значения по определению равны 1 let a = 1, b = 1; // получим c = fib(3) как их сумму let c = a + b; /* теперь у нас есть fib(1), fib(2), fib(3) a b c 1, 1, 2 */

Теперь мы хотим получить fib(4) = fib(2) + fib(3) .

Переставим переменные: a,b , присвоим значения fib(2),fib(3) , тогда c можно получить как их сумму:

a = b; // теперь a = fib(2) b = c; // теперь b = fib(3) c = a + b; // c = fib(4) /* имеем последовательность: a b c 1, 1, 2, 3 */

Следующий шаг даёт новое число последовательности:

a = b; // now a = fib(3) b = c; // now b = fib(4) c = a + b; // c = fib(5) /* последовательность теперь (на одно число больше): a b c 1, 1, 2, 3, 5 */

…И так далее, пока не получим искомое значение. Это намного быстрее рекурсии и не требует повторных вычислений.

function fib(n) < let a = 1; let b = 1; for (let i = 3; i return b; > alert( fib(3) ); // 2 alert( fib(7) ); // 13 alert( fib(77) ); // 5527939700884757

Цикл начинается с i=3 , потому что первое и второе значения последовательности заданы a=1 , b=1 .

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

В смысле не является ли введенное число одним из чисел этой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. ?

Один из вариантов решения.

#include using namespace std; int main() < double x; int i,y,z,b; bool q; cout > x; y = z = b = 1; q = 0; for (i = 1; i < x; i++) < z = y; y = b; b = z + y; if (b == x) < q = 1; >> if (q) else ; system ("pause"); return 0; > 

pivovarnik 24 октября 2013

n-ое число Фибоначи можно найти за формулой
F(n) = (a^n-b^n)/sqrt(5)
a^n — a в степени n
a = (1+sqrt(5))/2
b = (1-sqrt(5))/2
http://en.wikipedia.org/wiki/Fibonacci_number
Просто перебираешь числа, пока i-ое число Фибоначи не будет равно данному числу или не будет больше него
Чтобы избежать неточностей в связи с исчислением корня квадратного от пяти, можно использовать функцию округления

/*While24. Дано целое число N (> 1). Последовательность чисел Фибоначчи FK определяется следующим образом: F1 = 1, F2 = 1, FK = FK−2 + FK−1, K = 3, 4, . . Проверить, является ли число N числом Фибоначчи. Если является, то вывести TRUE, если нет — вывести FALSE.*/ #include using namespace std; int main() < setlocale(LC_ALL, "Rus"); unsigned n,f=0,f1=1,f2=1; cout 1)\n"; cin >> n; while(f cout.setf(ios_base::boolalpha); cout

Внимание! Это довольно старый топик, посты в него не попадут в новые, и их никто не увидит. Пишите пост, если хотите просто дополнить топик, а чтобы задать новый вопрос — начните новый.

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

Один из способов проверки является проверка, является ли заданное число N числом Фибоначчи, основываясь на том, что каждое четвертое число является числом Фибоначчи.
Вот пример кода на языке Python:

def is_fibonacci(num):
a = 0
b = 1
while b Переписать другими словами

Написать сочинение по запросу
Или попробуйте другие режимы нейросети.

Хотите знать, является ли введенное число числом Фибоначчи? Оставьте все нашей нейросети онлайн. Наша нейросеть пишет текст, которым можно проверить, является ли это число членом последовательности Фибоначчи. Просто введите число и получите ответ в считанные секунды. Наша нейросеть быстро и точно решает эту задачу и поможет Вам справиться с любой математической задачей. Попробуйте ее прямо сейчас и убедитесь в высокой точности и скорости нашей работы. С нейросетью онлайн Вы не только экономите время, но и получаете надежный результат!

Проверка на число Фибоначчи

Онлайн калькулятор для проверки введенного числа N на число Фибоначчи. Другими словами, проверить является ли введенное число — числом Фибоначчи.

Как пользоваться:

В единственное поле необходимо ввести N — число, которое необходимо проверить.
Нажать кнопку «Проверить», получить ответ является ли число — числом Фибоначчи или нет. Подробнее в разделе «теория».

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

Ограничения:

Число N — натуральное. То есть N = 1, 2, ….
Число N меньше 65 000 000.

Способ проверки:

Натуральное число N является числом Фибоначчи тогда и только тогда, когда $$5N^2 + 4$$ или $$5N^2 − 4$$ является квадратом, то есть $$\sqrt[2] = a$$ или $$\sqrt[2] = b$$,

где $$a,b$$ — целые числа.

Пусть $$N = 3$$

Считаем $$5N^2 + 4$$ и $$5N^2 − 4$$

$$5N^2 + 4 = 5 * 3^2 + 4 = 5 * 9 + 4 = 49$$ — является квадратом целого числа, так как $$49 = 7^2$$. Далее можно не проверять с минусом, так как одно условие выполнилось, значит, $$N = 3$$ — число Фиббоначчи.

Пусть $$N = 9$$

Считаем $$5N^2 + 4$$ и $$5N^2 − 4$$

$$5N^2 + 4 = 5 * 9^2 + 4 = 5 * 81 + 4 = 409$$ — не является квадратом целого числа. Проверяем с минусом.
$$5N^2 — 4 = 5 * 9^2 — 4 = 5 * 81 — 4 = 401$$ — не является квадратом целого числа, а значит, $$N = 9$$ — не число Фиббоначчи.

Заметили неточность в работе калькулятора? Убедительная просьба сообщить об этом в комментариях или через форму обратной связи. Заранее Вас благодарим.