Проверка на число Фибоначчи
Онлайн калькулятор для проверки введенного числа 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$$ — не число Фиббоначчи.
Заметили неточность в работе калькулятора? Убедительная просьба сообщить об этом в комментариях или через форму обратной связи. Заранее Вас благодарим.
Является ли число числом Фибоначчи
Задача 2.23
Дано натуральное число Х. Если оно является числом Фибоначчи, то присвоить переменной Т значение 1, иначе — значение 0. Вывести на экран значение Т.
На мой взгляд, задачка любопытная. Начинающим придётся подумать и включить воображение, что и требуется при изучении программирования.
О том, как получить последовательность чисел Фибоначчи с помощью рекурсии, я рассказывал здесь (если вы не знаете, что такое числа Фибоначчи, то узнаете там же).
Напомню, как выглядит исходный код рекуррентной функции для получения нужной нам последовательности чисел:
//********************************************************** // Вычисляет число Фибоначчи //********************************************************** function Fibonachi(Num : integer) : integer; begin //Если это 1-й или 2-й элемент if (Num = 1) or (Num = 2) then Result := 1 //Иначе функция вызывает сама себя (рекурсия) else Result := Fibonachi(Num-1) + Fibonachi(Num-2); end;
Один из способов решения данной задачи — это просто вызывать эту функцию и сравнивать результат с числом Х. Однако с рекурсией надо быть осторожным — при большом количестве чисел она может занять очень много времени на выполнение. Поэтому лучше обойтись без неё.
Для решения задачи сначала присвоим переменной Т значение 0. Затем в цикле будем создавать числа Фибоначчи, и сравнивать с числом Х. Если текущее число Фибоначчи будет равно числу Х, то мы прервём цикл и присвоим значение 1 переменной Т.
Ну а дальше останется только вывести на экран значение Т.
Для лучшей наглядности предоставим пользователю возможность ввести число Х, а также будем выводить ряд чисел Фибоначчи на экран в ходе выполнения программы.
Также ограничим аппетиты пользователя при вводе значения Х, например, числом 1 000 000 000. Иначе время работы программы может сильно затянуться (особенно если использовать рекурсию). Кроме того, введённое число не должно быть равно нулю — это тоже будем проверять. Также число не должно быть отрицательным.
А ещё пользователь может ввести вместо числа букву (или строку). В С++ это будет обработано как число и выдано сообщение. В Паскале же придётся делать дополнительную обработку. Но, чтобы не загромождать код, мы этого делать не будем.
Также обратите внимание на проверку условия в if (X == F2) — в С++ здесь многие новички совершают ошибку, которую долго не могут найти и не понимают, почему программа работает неправильно.
Решение задачи 2.23 на Паскале
program mytask; //**************************************************************** // КОНСТАНТЫ //**************************************************************** const MAX_VAL = 1000000000; //**************************************************************** // ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ //**************************************************************** var X : Integer; Y : Integer; F1 : Integer = 1; F2 : Integer = 1; T : WORD = 0; //**************************************************************** // ОСНОВНАЯ ПРОГРАММА //**************************************************************** begin Write(‘X = ‘); ReadLn(X); if X > MAX_VAL then begin WriteLn(‘The number is too big!’); WriteLn(‘The number X should be no more than ‘, MAX_VAL); WriteLn(‘Press ENTER. ‘); ReadLn; Exit; end; if X < 1 then begin WriteLn('The number is too small!'); WriteLn('Number X should not be less than ', 1); WriteLn('Press ENTER. '); ReadLn; Exit; end; Write(F1, ' '); while F2 Break; end; Y := F2; F2 := F2 + F1; F1 := Y; end; WriteLn(#10#13'T = ', T); WriteLn('The end. Press ENTER. '); ReadLn; end.