Статья Автор: Лебедев Дмитрий

Решаем задание 16 из демоверсии 2025

Начальные сведения о решении заданий на рекурсию методом динамического программирования
можно посмотреть здесь

Задача 0 (Демоверсия экзамена 2025).

Алгоритм вычисления значения функции F(n),
где n – натуральное число, задан следующими соотношениями:
F(n)=1 при n=1;
F(n)=(n−1)×F(n−1), если n>1.
Чему равно значение выражения (F(2024)+2×F(2023))/F(2022)?

Для решения этой задачи использование компьютера нужно только для того, чтобы выполнить
элементарные арифметические операции.
1. Выразим F(2024) через  F(2023) 
\(F(2024)=2023\cdot F(2023) \\ Тогда\ F(2024)+2\cdot F(2023)=2025\cdot F(2023)\)
2. Выразим F(2023) через АF(2022)
\(F(2023)=2022\cdot F(2022) \\ Тогда\ (F(2024)+2\cdot F(2023))=2025\cdot 2022\cdot F(2022)\)
Таким образом получаем ответ \(2025\cdot 2022=4094550\)

На этом можно было бы закончить разбор, однако в классе нашелся ученик Фома, который 
"потребовал" решить задачу через рекурсию или динамическое программирование.
В качестве аргумента он "немного" изменил условие

Задача 1 (Редакция от Фомы).

Алгоритм вычисления значения функции F(n),
где n – натуральное число, задан следующими соотношениями:
F(n)=1 при n=1;
F(n)=(n−1)×F(n−1), если n>1.
Чему равна целая часть выражения (F(2024)+F(1112)×F(1113))/F(2022)?

Пришлось искать другое решение sad
 


Ученики класса начали предлогать различные варианты решений.
Наиболее реальными были:
  • написать рекурсию, увеличив её глубину 
  • решить методом ДП (динамического программирования) снизу-вверх
Наш Фома заявил, что он не знает/помнит как увеличивать глубину рекурсии и её увиличение тоже имеет ограничения.
На второе предложение он возразил тем, что переписать задачу на вариант снизу-вверх не всегда получиться (надо думать, можно ошибиться)

Для начала решили написать рекурсию через ДП.
Получилась небольшая программа:


Программа будет работать при а<1000.
Но как заставить её работать при больших значениях?

Небольшой мозговой штурм и ...  оказалось, что это несложно, поскольку :
  • значения F(n) можно заменить на cash[n] - надо было понять, что мы пишем в cash
  • значения словаря cash сохраняются и используются при следуюших вызовах 
Значит, например, можно
  • вначале запустить F(500) и программа заполнит cash[i] для i от 2 до 500,
  • затем запустить F(1000) и программа заполнит cash[i] для i от 2 до 500 (глубина рекурсии будет небольшой)
  • и т.д.
В результате получим следующее решение Задачи 0


Программа легко модифицируется для Задачи 1 и наш Фома успокоился.
Подведем итоги:
  • задание можно решать программно методом динамического программирования
  • для решения задания разумно использовать структуру словарь
  • можно не использовать увеличение глубины рекурсии, а вызывать функцию с шагом,
    меньшим глубины рекурсии (не обязательно 500, можно и 50) 
  • для вычисления итогового значения использовать значения из словаря


Предложенный подход не претендует на оптимальность или универсальность. Он лишь иллюстрирует, как можно
простыми методами решать некоторый класс простых "одномерных" задач (которые встречаются в ЕГЭ)
Вы можете предложить свой метод или задание, которое сложно/невозможно решить предложенным подходом.

Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать