→ Данный материал продолжает тему изучения рекурсивных функций и является прямым продолжением предыдущих частей (ЧАСТЬ 1, ЧАСТЬ 2, ЧАСТЬ 3, ЧАСТЬ 4) 🔽
✅ В этой статье представлен подробный разбор решения задачи формата ЕГЭ по информатике, но другим способом. Данная задача отличается повышенной сложностью: для её решения требуются дополнительные знания по работе с библиотеками языка Python.
УСЛОВИЕ ЗАДАЧИ
Необходимо 2 - 3 раза внимательно прочитать условие задачи ⤵
→ Из предыдущего материала (ЧАСТЬ 4) известно:
- Для решения данной задачи необходимо записать рекурсивную функцию.
- Использовать дополнительный модуль (import sys) для увеличение лимита рекурсивной функции.
РЕШЕНИЕ С ИСПОЛЬЗОВАНИЕМ РЕКУРСИВНОЙ ФУНКЦИИ + ИМПОРТ sys.setrecursionlimit ↓
❗НО
— Часто лучшим решением является не увеличение лимита, а переписывание рекурсивного алгоритма на итеративный (с использованием циклов или мемоизации), что более безопасно и эффективно.
☑ В ЭТОЙ СТАТЬЕ БУДЕТ ПОДРОБНО РАССМОТРЕНО РЕШЕНИЕ ЗАДАЧИ ИТЕРАИЦОННЫМ МЕТОДОМ ↓
- Что такое итерация?
Итера́ция (от лат. iteratio — повторение) — это процесс последовательного выполнения набора операций или команд, который повторяется многократно до достижения определённого условия завершения.
🚥HERE WE GO →
ИТЕРАТИВНЫЙ МЕТОД
— Подход к решению задач через повторяющиеся циклы вместо повторяющихся рекурсивных вызовов.
→ Данный метод использует конструкции циклов for или while для многократного выполнения блока кода до достижения нужного условия.
КЛЮЧЕВЫЕ ОСОБЕННОСТИ ИТЕРАТИВНОГО МЕТОДА
Основные преимущества использования данного метода →
☑ ОТСУТСТВИЕ РЕКУРСИВНЫХ ВЫЗОВОВ:
— функция не вызывает сама себя, программа выполняет алгоритм шаг за шагом (последовательно).
☑ ЦИКЛИЧЕСКОЕ ВЫПОЛНЕНИЕ:
— повторение определенного алгоритма (рекуррентная формула) с помощью циклов for / while.
☑ ЭКОНОМИЯ ПАМЯТИ:
— для сохранения результатов используется список или словарь, при этом не создаётся длинная цепочка вызовов в стеке (которая может занимать много место в памяти ОС).
☑ ПРОИЗВОДИТЕЛЬНОСТЬ:
— как правило, итеративный алгоритм работает быстрее рекурсии (в зависимости от поставленной задачи).
⚠ ВАЖНЫЙ МОМЕНТ
Рекурсивный код, как правило, проще и удобнее для решения заданий.
Поэтому, рекурсия чаще применяется в учебных целях (ОГЭ, ЕГЭ), научных расчетах или для построения деревьев и графов.
РЕШЕНИЕ ЗАДАНИЯ ИТЕРАТИВНЫМ МЕТОДОМ НА PYTHON
Решение будет включать в себя 5 основных этапов 🔽
- СОЗДАНИЕ СПИСКА
- ЗАПУСК ЦИКЛА for
- БАЗОВЫЙ СЛУЧАЙ РЕКУРСИИ
- РЕКУРСИВНЫЙ ВЫЗОВ
- ВЫВОД РЕЗУЛЬТАТА НА ЭКРАН
Переходим к первому этапу →
🔻СОЗДАНИЕ СПИСКА
Для хранения результатов работы функции ⤵
🚀 ПЕРВЫЙ ЭТАП РЕШЕНИЯ ЗАДАЧИ ИТЕРАТИВНЫМ МЕТОДОМ:
💢 Зачем создавать список?
— В списке будут хранится все вычисленные значения рекуррентной формулы:
F(n) = n * F(n - 1)
💢Почему для значений рекурсивной функции выбран список, а не стандартный стек?
— Для экономии памяти и сокращения времени работы программы.
📦 В данном варианте решения вместо стека будет использоваться список. Список будет выступать местом хранения (контейнером) для всех вычисленных значений функции F.
❕ВАЖНЫЕ МОМЕНТЫ:
- Использование списка позволяет сократить время работы программы по сравнению с рекурсивным методом.
- Итеративные решения, как правило, быстрее — так как не тратят ресурсы на вызовы функций.
→ При итеративном методе используется принцип сохранения текущих результатов: как только функция вычисляет очередное значение, оно тут же записывается в список.
→ За счёт этого на каждом новом этапе процесса все предшествующие значения остаются доступными для использования.
⚠ Тогда как в рекурсивных алгоритмах происходит многократный вызов функции до тех пор, пока не будет достигнут базовый случай. При этом, каждый новый вызов будет сохранён в стеке.
- СХЕМАТИЧЕСКОЕ ИЗОБРАЖЕНИЕ РАБОТЫ АЛГОРИТМА:
На первом этапе решения необходимо просто создать список (list), содержащий всего один элемент — 0 ↓
❕ВАЖНЫЙ ВОПРОС:
💢 Почему создаётся не пустой список?
— В представленном коде первый элемент списка a = [0] используется как техническая «заглушка», чтобы упростить индексацию и сделать её интуитивно понятной.
☑ Это стандартный приём в программировании, который позволяет «синхронизировать» индекс элемента в списке со значением, которое этот элемент хранит ⤵
- Благодаря использованию «заглушки» удобно работать со списком.
- Без «заглушки» пришлось бы во всей программе использовать индекс n - 1.
⭐ Несколько примеров по работе по списками для лучшего понимания алгоритмов на Python ⤵
📍 СОЗДАНИЕ СПИСКА
→ Для создания списка необходимо присвоить (придумать) имя списку и указать в квадратных кавычках элементы списка.
a — имя списка.
[0] — элементы списка (а).
📍СОЗДАНИЕ СПИСКА + ИНДЕКСЫ
a[0] — первый (нулевой) элемент списка (а).
b[0] + b[1] — сложение первого и второго элементов в списке (b).
👉 СЛЕДУЮЩИЙ ЭТАП →
🔻ЗАПУСК ЦИКЛА for
Для вычисления всех значений функции ⤵
🚀 ВТОРОЙ ЭТАП РЕШЕНИЯ ЗАДАЧИ ИТЕРАТИВНЫМ МЕТОДОМ:
💢 Какую роль выполняет цикл for?
— Цикл for служит для перебора значений переменной n.
Переменная n — натуральное число из условия задачи. Каждое новое значение функции F(n) вычисляется в зависимости от текущего значения переменной n →
→ Алгоритм вычисления значений функции F(n) в зависимости от n:
F(1) = 1, при n = 1
F(2) = 2, при n = 2
F(3) = 6, при n = 3 и так далее.
F — рекурсивная функция, а переменная n её аргумент.
💢 Почему выбран именно такой диапазон для цикла for?
— Для вычисления значений F(2023) и F(2020).
В задаче необходимо найти значение выражения F(2023) / F(2020) ↓
→ Это значит, что значения функций F(2023) и F(2020) должны быть обязательно вычислены (найдены).
Чтобы вычислить значения функции F итерационным методом, необходимо узнать чему будет равно значение соответствующих элементов в списке — a[2023] и a[2020] →
→ Следовательно, алгоритм должен последовательно добраться до элементов с индексами [2023] и [2020].
☑ Именно для этого и используется цикл for с данным диапазоном range(0, 2023 + 1).
- СХЕМАТИЧЕСКОЕ ИЗОБРАЖЕНИЕ РАБОТЫ АЛГОРИТМА:
После создания списка необходимо запустить цикл for, для вычисления значений рекурсивной функции F ↓
💢 Почему в range диапазон до 2023 + 1?
— Для вычисления значения элемента в списке a[2023].
→ Функция range() хранит в себе список чисел, который начинается с первого указанного в скобках числа и заканчивается числом, на единицу меньшим второго. Поэтому range(1, 4) — это 1, 2, 3.
🏁 Поэтому, чтобы получить значение a[2023], цикл for должен дойти до этого значения в списке .
Также можно было записать:
- for n in range(0, 2024) — диапазон значений от 0 до 2024 (не включительно)
или
- for n in range(2024) — диапазон значений от 0 до 2024 (не включительно)
👉 СЛЕДУЮЩИЙ ЭТАП →
🔻БАЗОВЫЙ СЛУЧАЙ РЕКУРСИИ
Добавление первого элемента в список ⤵
📦 На этом этапе начинается добавление элементов в список (а).
Первым элементом будет базовый случай рекурсии:
- F(n) = 1, при n = 1
💢 Как записать выражение F(1) = 1, при n = 1 в Python?
— Использовать исходный список (а) и команду (append).
- a[n] = 1, при n = 1
или
- a[1] = 1
→ Это значит, что необходимо в первую (не нулевую) ячейку списка добавить цифру 1:
🚀 ТРЕТИЙ ЭТАП РЕШЕНИЯ ЗАДАЧИ ИТЕРАТИВНЫМ МЕТОДОМ:
💢 ДЛЯ ЧЕГО НУЖЕН append()?
— Команда для добавления элементов в конец списка.
append() — встроенный метод, который добавляет один элемент в конец списка (list).
Метод append() изменяет исходный список (на месте), не создавая при этом новый объект.
Синтаксис:
- имя списка.append(элемент)
☑ Поддержка любых типов данных — можно добавлять числа, строки, списки, словари, объекты и так далее.
ПРИМЕРЫ:
1️⃣ ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ В СПИСОК
a[ ] — создание пустого списка (а).
a.append(1) — добавление числа (1) в список (a).
a.append(2) — добавление числа (2) в конец списка (a).
2️⃣ ДОБАВЛЕНИЕ ЭЛМЕНТОВ В СПИСОК + ЦИКЛ for
a.append(i) — добавление каждого значения переменной (i) в список (a).
☑ В качестве проверки, попробуем вывести на экран список а после добавления нового элемента →
⭐ Отлично! После выполнения условия if n == 1, в списке находится два элемента: [0, 1].
Оператор break используется для немедленного выхода из цикла.
- СХЕМАТИЧЕСКОЕ ИЗОБРАЖЕНИЕ РАБОТЫ АЛГОРИТМА:
После создания списка и запуска цикла for, начинается добавление элементов в список ↓
→ Цикл for стартует с n = 0, но это значение не добавляется в исходный список (а) — так как условие n == 1 не будет выполнено ↓
⚡Дополнительный пример для лучшего понимания работы алгоритма ↓
a[ ] — создание пустого списка (а).
a.append(i) — добавление каждого значения переменной (i) в список (a).
for i in a — запуск цикла (for) по элементам списка (a).
if i % 2 == 0 — проверка каждого элемента из списка (а) на кратность двум.
Данный код ⏏ создёт список (а). Поочерёдно добавляет в список числа от 10 до 15. И выводит на экран только элементы, кратные 2.
👉 СЛЕДУЮЩИЙ ЭТАП →
🔻РЕКУРСИВНЫЙ ВЫЗОВ
Добавление всех элементов в список по рекурсивному алгоритму ⤵
В условии задачи записан алгоритм, по которому должен добавляться каждый новый элемент в список (не включая базовый случай):
Рекурсивный алгоритм: F(n) = n * F(n - 1)
или как алгоритм будет выглядеть в нашем решении:
a[n] = n * a[n - 1]
→ Каждый новый элемент в списке это:
Умножение предыдущего элемента на текущее значение переменной n.
🔥Теперь нужно записать условие для переменной (n) с последующим добавлением элементов в список (а) ↓
🚀 ЧЕТВЁРТЫЙ ЭТАП РЕШЕНИЯ ЗАДАЧИ ИТЕРАТИВНЫМ МЕТОДОМ:
- СХЕМАТИЧЕСКОЕ ИЗОБРАЖЕНИЕ РАБОТЫ АЛГОРИТМА:
Каждый новый элемент добавляется после выполнения условия (if n > 1) ↓
→ Рекуррентная формула:
a[n] = a[n - 1] * n
- Как меняется список (а) после добавления новых элементов:
☑ В качестве проверки, попробуем вывести на экран список а после добавления нескольких элементов. Для этого необходимо изменить функцию range():
- range(0, 2023 + 1) → range(0, 8)
И записать в конце программы print():
⭐ Первые восемь элементов списка совпадают с результатами рекурсивной функции — алгоритм работает верно ↓
[a] — список значений функции (F), полученный итерационным методом.
F(n) — значения функции, полученные рекурсивным методом.
🔥 ПЕРЕХОДИМ К ЗАКЛЮЧИТЕЛЬНОМУ ЭТАПУ ↓
🔻ВЫВОД РЕЗУЛЬТАТА НА ЭКРАН
С помощью встроенной функции print() ⤵
По условию задачи необходимо найти отношение F(2023) к F(2020):
→ В решении на Python это соответствует выражению:
- a[2023] // a[2020]
(то есть значение 2023-го элемента функции (алгоритма) к значению 2020-го элемента) →
🚀 ПЯТЫЙ ЭТАП РЕШЕНИЯ ЗАДАЧИ (ИТОГОВОЕ РЕШЕНИЕ):
☑ Полученный ответ совпадает с верным ответом, полученным с помощью рекурсивного решения:
Ответ: 8266912626
⭐ Good Job! Everything is OK!
Задача решена с помощью итеративного метода!
Небольшие итоги по решению и затем интересные моменты ↓
♻ КРАТКИЕ ИТОГИ
Для решения исходной задачи использовался итеративный метод →
❕ПЛЮСЫ И МИНУСЫ, КОТОРЫЕ НЕОБХОДИМО УЧИТЫВАТЬ ПРИ РЕШЕНИИ РЕКУРСИВНЫХ ЗАДАЧ ИТЕРАТИВНЫМ МЕТОДОМ:
→ Для наглядности, сравнение двух способ решения исходной задачи:
📍 СОЗДАНИЕ РЕКУРСИВНОЙ ФУНКЦИИ + sys.setrecursionlimit()
📍 ИТЕРАТИВНЫЙ МЕТОД:
🚨ИНТЕРЕСНЫЕ МОМЕНТЫ ПО РЕШЕНИЮ
Для лучшего понимания работы алгоритма →
❶ ЗНАЧЕНИЕ РЕКУРСИВНОЙ ФУНКЦИИ
— Как посмотреть чему равно конкретное значение функции?
→ В списке а будут поочередно записаны все значения заданного алгоритма:
F(n) = F(n - 1) * n
→ Поэтому, для просмотра определённого значения функции нужно указать аналогичный индекс в списке:
a[25] — элемент из списка (а), в котором хранится значение функции F(25).
a[100] — элемент из списка (а), в котором хранится значение функции F(100).
❷ КОМПАКТНОЕ РЕШЕНИЕ
— Можно ли записать итоговое решение в более компактном виде?
→ ПОЯСНЕНИЕ:
- По условию задачи, базовый случай рекурсии выглядит так:
F(n) = 1, при n = 1
- В решении итеративным методом базовый случай записывается так:
a[1] = 1
❕Следовательно, первый элемент списка (а) должен равняться 1.
И это значение можно не записывать с помощью if + append, а сразу же записать в исходный список а ↓
☑ Получается более компактный код, который занимает меньше строк.
❸ РЕШЕНИЕ С ПОМОЩЬЮ СЛОВАРЯ
— Можно ли использовать другой тип хранения данных, вместо списка (list)?
- ЧТО ТАКОЕ СЛОВАРЬ?
Словарь (dict) в Python — это изменяемая коллекция пар «ключ‑значение», где каждый ключ уникален.
Словарь по структуре похож на телефонную книгу 📕:
- Имя (ключ) → Номер телефона (значение)
Каждый раз в словаре f создаётся новая пара ключ - значение, в которой:
- КЛЮЧ — текущее значение переменной (n)
n = 1, 2, 3 ... 2023.
- ЗНАЧЕНИЕ — рекурсивная функция F(n)
F(1) = 1, F(2) = 2, F(3) = 6 и так далее.
→ Для отображения нескольких элементов в словаре f необходимо изменить range:
- range(1, 2024) → range(0, 8)
{3 : 6} — значение переменной n = 3 и значение рекурсивной функции F(3) = 6.
{5 : 120} — значение переменной n = 5 и значение рекурсивной функции F(5) = 120.