Условие:
Числа Фибоначчи - 2
(Время: 1 сек. Память: 16 Мб Сложность: 20%)
Числа Фибоначчи строятся следующим образом: 1, 1, 2, 3, 5, …. В этой последовательности, начиная с третьего числа, каждый следующий член равен сумме двух предыдущих. Получаем, что, например, шестое число равно 8, а десятое - 55.
Требуется написать программу, которая определяет, является ли заданное число числом Фибоначчи.
Входные данные
Входной текстовый файл INPUT.TXT содержит одно натуральное число в диапазоне от 2 до 1200000000.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать в первой строке 1, если заданное число является числом Фибоначчи, и 0, иначе. В первом случае во вторую строку требуется вывести его порядковый номер.
Примеры
№ INPUT.TXT OUTPUT.TXT
1 8 1
6
2 10 0
Решение:
Для решения задачи о проверке, является ли заданное число числом Фибоначчи, мы можем использовать несколько подходов. Один из наиболее эффективных способов заключается в предварительном вычислении чисел Фибоначчи до заданного предела, а затем проверке, содержится ли заданное число в этом списке. Шаги решения: 1. Генерация чисел Фибоначчи: Мы будем генерировать числа Фибоначчи до тех пор, пока не превысим заданное число (в данном случае 1,2 миллиарда). 2. Хранение чисел Фибоначчи: Мы будем хранить числа Фибоначчи в списке, чтобы затем легко проверить, есть ли заданное число в этом списке, и ...
Теперь давайте разберем, как работает этот код: 1. Мы читаем число из файла . 2. Мы создаем список и добавляем в него первые два числа Фибоначчи. 3. В цикле мы продолжаем вычислять следующее число Фибоначчи, пока оно не превысит 1,2 миллиарда. 4. После завершения генерации мы проверяем, содержится ли заданное число в списке. 5. Если число найдено, мы находим его индекс и записываем результат в файл . Если число не найдено, записываем 0. Таким образом, мы решаем задачу проверки, является ли заданное число числом Фибоначчи, и выводим соответствующий результат.