Привет! Сегодня научу тебя решать 23 задание КЕГЭ на Python. Алгоритм несложный, но требуется понимать, что такое рекурсия и как она работает.
Для тех, кто не знаком с рекурсией, рекомендую прочитать о ней, например, на сайте Питонтьютор ( https://pythontutor.ru/lessons/functions/ ).
Поиск количества программ по заданному числу
Условие задачи
У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 5.
Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 5 раз.
Программа для Калькулятора — это последовательность команд.
Сколько есть программ, которые число 2 преобразуют в число 50?
Решение
Строка 1. Функция принимает на вход один аргумент: число, с которого начинается отсчет.
Строки 2-5. Точки выхода рекурсии. Если мы достигли цели (число 50), то путь есть (возвращаем 1), а если число стало больше, чем 50, то этот путь не учитываем (возвращаем 0).
Строки 6-7. Продолжение рекурсии. Функция вызывает саму себя с новыми значениями и складывает результат выполнения.
Строка 9. Вызов функции с начальным числом 2.
Количество программ с избегаемым этапом
Условие задачи
Исполнитель РазДваТри преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Прибавить 3
Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает на 3.
Программа для исполнителя РазДваТри — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 3 в число 16 и при этом траектория вычислений не содержит чисел 6 и 12?
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 9, 10, 20.
Решение
Строка 1. Функция принимает на вход один аргумент: число, с которого начинается отсчет.
Строки 2-5. Точки выхода рекурсии. Если мы достигли цели (число 16), то путь есть (возвращаем 1), а если число стало равно 6, 12 или больше, чем 16, то этот путь не учитываем (возвращаем 0).
Строки 6-7. Продолжение рекурсии. Функция вызывает саму себя с новыми значениями и складывает результат выполнения.
Количество программ с обязательным этапом
Условие задачи
Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Сколько существует программ, для которых при исходном числе 4 результатом является число 13, и при этом траектория вычислений содержит число 11?
Решение
В задаче с обязательной вершиной необходимо разбить путь 4 -> 13 на два пути: 4 -> 11 и 11 -> 13. Программа выведет два числа: 25 и 2, а ответом к задаче будет являться произведение этих чисел, т.е. число 50.
Поиск количества чисел по заданному числу команд
Условие задачи
У исполнителя Калькулятор две команды:
1. прибавь 2
2. прибавь 3.
Первая из них увеличивает число на экране на 2, вторая — на 3. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 10 команд?
Решение
Строка 1. Заведем список, чтобы складывать в него полученные числа.
Строка 2. Функция принимает на вход два аргумента: n - число, которое будет увеличиваться, k - количество команд.
Строки 3-5. Точка выхода рекурсии. Если команд ровно 10, текущее число добавляем в список, функцию прерываем.
Строки 6-7. Точка выхода рекурсии. Если команд больше 10, функцию прерываем.
Строки 8-9. Продолжаем рекурсию, но на этот раз результаты функций не складываем, а объединяем оператором "или" (OR)
Строка 11. Вызываем функцию с начальным значением 2 и числом команд 0.
Строка 12. Печатаем длину множества чисел списка sp.