Особенности решения задачи № 23 единого государственного экзамена

Изучение алгоритмов имеет большую практическую значимость. Это связано с тем, что разработка алгоритма предполагает подробное описание каждого шага решения задачи. В едином государственном экзамене по информатике исполнителям отводится три задачи (№ 12, 18, 23).

Рассмотрим задачу № 23 на выполнение алгоритмов для исполнителей, её формулировка:

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1
2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 20 и при этом траектория вычислений содержит число 10?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Можно запрограммировать данное решение или попытаться перечислить все пути в явном виде, но это слишком трудоёмко и скорее всего, в итоге приведёт к ошибке. Данная задача имеет достаточно простое теоретическое решение, то есть решение на бумаге.

Данная задача взята из Дэмо-версии 2021 год [1]. В задаче речь идет об исполнителе, который может исполнять две команды: первая – увеличить число на 1, вторая – умножить это число на 2. Нам необходимо найти количество команд, которые из числа 1 получают результатом число 20, при этом траектория обязательно содержит число 10.

Что это значит: траектория вычисления обязательно содержит какое-то число? Смотрите, если мы стартуем с 1 и выполняем команду № 2 (умножить на 2), то есть 1*2 получаем 2. Исполнитель выполняет опять ту же команду и полученную 2 (двойку) тоже умножает на 2 (2*2=4). Дальше можно выполнить команду № 1 и прибавить 1 (4+1=5). Теперь 5 умножим на 2 (5*2=10). Тем самым мы получаем 10. Согласно условия задачи, это число мы всегда должны иметь ввиду при подсчете траектории вычислений. Далее мы 10 умножаем на 2 и получаем требуемое число 20.

Нам нужно рассмотреть все возможные траектории, которые внутри своих вычислений будут содержать число 10 и подсчитать, сколько их существует.

Как это сделать? Достаточно просто.

Необходимо рассмотреть два случая:

1) мы пойдем с вами от 1 до 10, тогда в результате вычислений мы обязательно получим число 10 и включим её в траекторию;

2) мы начнем от 10 и дойдем до 20.

Таким образом, у нас получится первый набор команд, ведущий нас от 1 до 10 и второй – от 10 до 20.

Если, например, у нас окажется 5 наборов команд для случая от 1 до 10, и 4 набора команд от 10 до 20, то общее количество наборов мы подсчитаем, перемножив 5 и 4. То есть, получится 5*4 = 20 разных вариантов команд.

Итак, давайте вернемся к нашей задаче и посчитаем, сколько у нас таких команд будет, если мы пойдем от 1 до 10. Нарисуем динамическую таблицу. Почему она динамическая вы сейчас поймете.

Мы с вами пишем все числа от 1 до 10. Нижняя строка служит для записи количества команд, при помощи которых можно получить число (которое находится соответственно в верхней строке).

Оригинал публикации (Читать работу полностью): Особенности решения задачи № 23 единого государственного экзамена