Задание повышенного уровня сложности, на его выполнение отводится примерно 8 минут. Оно проверяет умение анализировать работу алгоритма с ветвлением и циклом. Суть задания заключается в нахождении количества программ, удовлетворяющих заданным условиям.
Условие задачи
Исполнитель преобразует число на экране. У него две команды:
- Прибавить 1
- Умножить на 2
Задача: определить, сколько программ преобразуют исходное число 1 в число 35, при условии, что траектория вычислений содержит число 10, но не содержит число 17.
Решение с помощью рекурсивной функции
Наиболее эффективный способ решения – использование рекурсивной функции. Рекурсивная функция – это функция, которая вызывает саму себя.
Создадим функцию F, которая принимает два параметра:
- X – начальное число.
- Y – целевое число.
Функция работает следующим образом:
- if X > Y: Возвращает 0. Переход из меньшего числа в большее с помощью команд «+1» и «*2» невозможен.
- elif X == Y: Возвращает 1. Целевое число достигнуто.
- else: Возвращает сумму количества программ, получаемых при использовании первой команды (F(X + 1, Y)) и второй команды (F(X * 2, Y)).
Для учета условия о прохождении через число 10 и непрохождении через 17, модифицируем функцию:
- Добавим условие if X == 17: Функция возвращает 0.
- Для учета числа 10, вычислим количество программ до 10 и от 10 до 35, а затем перемножим полученные результаты. Количество путей до 35 через 10 равно произведению количества путей до 10 и количества путей от 10 до 35.
Пример вычисления
Предположим, что из 1 в 10 ведут две программы, а из 10 в 35 – четыре. Тогда общее количество программ, ведущих из 1 в 35 через 10, равно 2 * 4 = 8.
Реализация на Python
В коде необходимо реализовать описанную рекурсивную функцию, учитывающую условия задачи. Результат выполнения кода: 98.
98 – правильный ответ на задание. Хотя задание неизменно в течение нескольких лет, возможны варианты с большими числами, где рекурсия может быть неэффективна. В таких случаях потребуются другие методы решения.