Задание 16 · ЕГЭ, информатика 2027
Рекуррентные выражения
Рекуррентное правило и база: считаем значение функции.
Пять вариантов задания
Данные в вариантах разные, приём решения один. Отмеченные галочкой уже решены — отметка хранится в этом браузере.
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = F(n − 1) + 2·F(n − 2) при n > 2; F(1) = 1, F(2) = 2.
Чему равно значение функции F(30)? В ответе запишите значение F(30).
F(n) = F(n − 1) + 2·F(n − 2) при n > 2; F(1) = 1, F(2) = 2.
Чему равно значение функции F(30)? В ответе запишите значение F(30).
К этому номеру файл не прилагается, но решать его нужно в среде программирования: вручную счёт слишком долгий.
Не раскрывать рекурсию руками
Соотношение определяет F(n) через предыдущие значения. Разворачивать его в формулу не нужно — достаточно посчитать значения по порядку, от базовых к нужному.Посчитать первые значения
n 1 2 3 4 5 6 7 8 9 F(n) 1 2 4 8 16 32 64 128 256 Довести счёт до нужного n
Дальше так же, до n = 30. На бумаге это долго, поэтому задание и решается на компьютере: программа ниже делает ровно те же шаги.Ответ
Получается 536870912.
Эталонная программа (Python)
Программа не исполняется на странице: задание проверяет умение написать её самому. Перенесите текст в свою среду и запустите там.
def F(n):
if n == 1:
return 1
if n == 2:
return 2
return F(n - 1) + 2 * F(n - 2)
print(F(30))Где обычно теряют балл
- Написать рекурсию без запоминания значений: для больших n программа будет считать одно и то же по много раз и не дождётся конца. Лечится строкой
from functools import lru_cacheи декоратором@lru_cache(None)над функцией. - Перепутать базовые значения: у каждого соотношения они свои, и ошибка в F(1) портит всё.
- Забыть, что рекуррентное правило действует только при n больше указанного — для меньших n берутся базовые значения.
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = F(n − 1) + F(n − 2) + n при n > 2; F(1) = 1, F(2) = 1.
Чему равно значение функции F(34)? В ответе запишите значение F(34).
F(n) = F(n − 1) + F(n − 2) + n при n > 2; F(1) = 1, F(2) = 1.
Чему равно значение функции F(34)? В ответе запишите значение F(34).
К этому номеру файл не прилагается, но решать его нужно в среде программирования: вручную счёт слишком долгий.
Не раскрывать рекурсию руками
Соотношение определяет F(n) через предыдущие значения. Разворачивать его в формулу не нужно — достаточно посчитать значения по порядку, от базовых к нужному.Посчитать первые значения
n 1 2 3 4 5 6 7 8 9 F(n) 1 1 5 10 20 36 63 107 179 Довести счёт до нужного n
Дальше так же, до n = 34. На бумаге это долго, поэтому задание и решается на компьютере: программа ниже делает ровно те же шаги.Ответ
Получается 32038976.
Эталонная программа (Python)
Программа не исполняется на странице: задание проверяет умение написать её самому. Перенесите текст в свою среду и запустите там.
def F(n):
if n <= 2:
return 1
return F(n - 1) + F(n - 2) + n
print(F(34))Где обычно теряют балл
- Написать рекурсию без запоминания значений: для больших n программа будет считать одно и то же по много раз и не дождётся конца. Лечится строкой
from functools import lru_cacheи декоратором@lru_cache(None)над функцией. - Перепутать базовые значения: у каждого соотношения они свои, и ошибка в F(1) портит всё.
- Забыть, что рекуррентное правило действует только при n больше указанного — для меньших n берутся базовые значения.
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 3·F(n − 2) + F(n − 1) при n > 2; F(1) = 2, F(2) = 3.
Чему равно значение функции F(26)? В ответе запишите значение F(26).
F(n) = 3·F(n − 2) + F(n − 1) при n > 2; F(1) = 2, F(2) = 3.
Чему равно значение функции F(26)? В ответе запишите значение F(26).
К этому номеру файл не прилагается, но решать его нужно в среде программирования: вручную счёт слишком долгий.
Не раскрывать рекурсию руками
Соотношение определяет F(n) через предыдущие значения. Разворачивать его в формулу не нужно — достаточно посчитать значения по порядку, от базовых к нужному.Посчитать первые значения
n 1 2 3 4 5 6 7 8 9 F(n) 2 3 9 18 45 99 234 531 1233 Довести счёт до нужного n
Дальше так же, до n = 26. На бумаге это долго, поэтому задание и решается на компьютере: программа ниже делает ровно те же шаги.Ответ
Получается 1769853123.
Эталонная программа (Python)
Программа не исполняется на странице: задание проверяет умение написать её самому. Перенесите текст в свою среду и запустите там.
def F(n):
if n == 1:
return 2
if n == 2:
return 3
return 3 * F(n - 2) + F(n - 1)
print(F(26))Где обычно теряют балл
- Написать рекурсию без запоминания значений: для больших n программа будет считать одно и то же по много раз и не дождётся конца. Лечится строкой
from functools import lru_cacheи декоратором@lru_cache(None)над функцией. - Перепутать базовые значения: у каждого соотношения они свои, и ошибка в F(1) портит всё.
- Забыть, что рекуррентное правило действует только при n больше указанного — для меньших n берутся базовые значения.
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = F(n − 1) + F(n − 3) при n > 3; F(1) = F(2) = F(3) = 1.
Чему равно значение функции F(40)? В ответе запишите значение F(40).
F(n) = F(n − 1) + F(n − 3) при n > 3; F(1) = F(2) = F(3) = 1.
Чему равно значение функции F(40)? В ответе запишите значение F(40).
К этому номеру файл не прилагается, но решать его нужно в среде программирования: вручную счёт слишком долгий.
Не раскрывать рекурсию руками
Соотношение определяет F(n) через предыдущие значения. Разворачивать его в формулу не нужно — достаточно посчитать значения по порядку, от базовых к нужному.Посчитать первые значения
n 1 2 3 4 5 6 7 8 9 F(n) 1 1 1 2 3 4 6 9 13 Довести счёт до нужного n
Дальше так же, до n = 40. На бумаге это долго, поэтому задание и решается на компьютере: программа ниже делает ровно те же шаги.Ответ
Получается 1822473.
Эталонная программа (Python)
Программа не исполняется на странице: задание проверяет умение написать её самому. Перенесите текст в свою среду и запустите там.
def F(n):
if n <= 3:
return 1
return F(n - 1) + F(n - 3)
print(F(40))Где обычно теряют балл
- Написать рекурсию без запоминания значений: для больших n программа будет считать одно и то же по много раз и не дождётся конца. Лечится строкой
from functools import lru_cacheи декоратором@lru_cache(None)над функцией. - Перепутать базовые значения: у каждого соотношения они свои, и ошибка в F(1) портит всё.
- Забыть, что рекуррентное правило действует только при n больше указанного — для меньших n берутся базовые значения.
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n·F(n − 1) − F(n − 2) при n > 2; F(1) = 1, F(2) = 2.
Чему равно значение функции F(14)? В ответе запишите значение F(14).
F(n) = n·F(n − 1) − F(n − 2) при n > 2; F(1) = 1, F(2) = 2.
Чему равно значение функции F(14)? В ответе запишите значение F(14).
К этому номеру файл не прилагается, но решать его нужно в среде программирования: вручную счёт слишком долгий.
Не раскрывать рекурсию руками
Соотношение определяет F(n) через предыдущие значения. Разворачивать его в формулу не нужно — достаточно посчитать значения по порядку, от базовых к нужному.Посчитать первые значения
n 1 2 3 4 5 6 7 8 9 F(n) 1 2 5 18 85 492 3359 26380 234061 Довести счёт до нужного n
Дальше так же, до n = 14. На бумаге это долго, поэтому задание и решается на компьютере: программа ниже делает ровно те же шаги.Ответ
Получается 54011212472.
Эталонная программа (Python)
Программа не исполняется на странице: задание проверяет умение написать её самому. Перенесите текст в свою среду и запустите там.
def F(n):
if n == 1:
return 1
if n == 2:
return 2
return n * F(n - 1) - F(n - 2)
print(F(14))Где обычно теряют балл
- Написать рекурсию без запоминания значений: для больших n программа будет считать одно и то же по много раз и не дождётся конца. Лечится строкой
from functools import lru_cacheи декоратором@lru_cache(None)над функцией. - Перепутать базовые значения: у каждого соотношения они свои, и ошибка в F(1) портит всё.
- Забыть, что рекуррентное правило действует только при n больше указанного — для меньших n берутся базовые значения.
Рекуррентные выражения
Функция задана через свои предыдущие значения плюс база. Раскрывать рекурсию в формулу не нужно — значения считаются по порядку от базовых.
На компьютере это несколько строк, но есть подводный камень: «наивная» рекурсия пересчитывает одни и те же значения по много раз и при n около 40 перестаёт укладываться во время. Лечится двумя способами:
- запоминание значений —
from functools import lru_cacheи декоратор@lru_cache(None)над функцией; - обычный цикл снизу вверх с массивом значений.
Где теряют балл. Ошибаются в базовых значениях; применяют рекуррентное правило к n, для которого оно не определено; при вопросе «сумма цифр» отвечают самим значением функции.
Где эта тема разобрана подробно
Структура раздела и темы заданий соответствуют кодификатору и спецификации ФИПИ. Задания и файлы данных составлены редакцией reknow.ru. План варианта приведён по проекту спецификации и демоверсии ФИПИ 2027 года. После публикации утверждённой версии информация будет обновлена.