Что такое числа Фибоначчи и зачем они нужны ЕГЭ
Числа Фибоначчи встречаются почти в каждом тренировочном варианте профильного ЕГЭ по информатике. Именно поэтому первые задачи на программирование чаще всего просят вывести n-е число этой последовательности. Проверяются базовые навыки работы с циклом, рекурсией и типами данных. Последовательность начинается с нуля и единицы, а каждое следующее число равно сумме двух предыдущих. Такой простой закон создаёт идеальную площадку для отработки роста сложности алгоритма и анализа памяти.
Формальное определение и классическая рекурсия
Формально F(0)=0, F(1)=1, дальше F(k)=F(k-1)+F(k-2). Прямолинейный код, записывающий правило рекурсивно, выглядит почти как математическая формула, поэтому его любят начинающие. Однако под капотом происходит экспоненциальное разрастание вызовов: каждый вызов порождает два новых, затем четыре и так далее. Начиная примерно с сорокового индекса программа тормозит ощутимо даже на современном компьютере. На экзамене время на одну программу ограничено двумя-тремя секундами, поэтому такой подход сдаст позицию уже при n≈50.
Проблемы рекурсии на больших n
Главная беда классической реализации — повторное вычисление одних и тех же промежуточных значений. F(10) вызывается внутри F(12) и одновременно внутри F(11), что создаёт огромную избыточность. Кроме того, глубина стека растёт линейно от n, и при крупных входных данных можно получить переполнение. Такие ошибки сложно ловить под давлением экзамена, ведь программа компилируется, запускается, а потом неожиданно падает по «Segment fault». Затратить баллы на лишнюю отладку равносильно сдаче сопернику.
Итеративный подход: быстрее и проще
Итеративная реализация решает обе проблемы. Создаём две переменные a=0, b=1. Далее в цикле for от 2 до n обновляем их значения: a, b = b, a + b. Алгоритм выполняет ровно n-2 шагов, использует константную память и не рискует переполнить стек. Такой код легко проверять, он дружелюбен к ограничению по времени и памяти в тестирующих системах ФИПИ. Кроме того, его просто расширить: достаточно хранить массив, если требуется вывести всю последовательность до n, а не только последний член.
Матрицы и быстрое возведение в степень
Когда n может достигать миллиарда, даже линейный цикл становится медленным. Тогда применяют матричное возведение в степень. Известно, что вектор (F(k), F(k+1)) равен произведению базовой матрицы [[0,1],[1,1]] в степени k и вектора (F(0), F(1)). Экспоненту матрицы находят алгоритмом быстрого возведения в степень за O(log n) умножений. Каждое умножение двух 2×2 матриц — константная операция, поэтому асимптотика получается логарифмической. Для экзамена такие крайности встречаются редко, однако понимание метода выделяет выпускника на олимпиадном уровне.
Сравнение алгоритмов: оценка времени и памяти
- Рекурсия без мемоизации: время O(φⁿ), память O(n) из-за стека.
- Рекурсия с кешем (динамическое программирование): время O(n), память O(n).
- Итеративный цикл: время O(n), память O(1).
- Матрица+log: время O(log n), память O(1).
На реальном экзамене типичный порог n не превышает 90, поэтому итеративного решения достаточно. Однако таблица демонстрирует, как одна и та же задача может требовать разных подходов в зависимости от ограничений. Умение составлять такую сравнительную таблицу помогает быстро аргументировать выбор метода в ответах на задачах с развернутым пояснением.
Числа Фибоначчи в типовых заданиях КИМ
Варианты последних лет показывают три главных формата. Первый: нужно вывести n-е число, зная, что n<45, — достаточно рекурсии. Второй: требуется вывести все члены до заданного n, что тренирует работу с массивами. Третий: предлагается изменить базовые значения, например F(0)=1, F(1)=2, и проверить внимательность. Иногда добавляют проверку на остаток по модулю m, чтобы заставить работать с длинными целыми. Разобрав каждую модификацию дома, выпускник резко сокращает риск неожиданности на экзамене.
Как тренироваться и не потерять баллы
Работайте в той же среде, что и на экзамене: PascalABC.NET, C++ или Python, зависимо от вашего выбора. Засеките время: рекурсивный и итеративный варианты должны компилироваться и сдавать тесты за минуту. Далее добавьте построчный вывод последовательности, включая проверку крайних значений: n=0 и n=1 часто забывают. Третий шаг — внедрите проверку на переполнение типа; в C++ используйте unsigned long long, в Python достаточно встроенного int. Главное — не заучивать код, а понимать логику. Тогда на реальном КИМ руки напишут правильный ответ быстрее, чем нервы успеют дрогнуть.