Что проверяет задание

Задание 5 - линейный алгоритм для исполнителя. У исполнителя две команды, например «1. умножь на 5» и «2. вычти 4». Нужно составить программу (последовательность номеров команд), которая из одного числа получает другое не более чем за заданное число команд. Ответ - номера команд подряд, например 21112.

Команды исполнителей

Частые команды и что они делают с числом x:

• прибавь k - x + k;
• вычти k - x - k;
• умножь на k - x * k;
• возведи в квадрат - x * x;
• припиши цифру d справа - x * 10 + d;
• зачеркни справа - последняя цифра пропадает (из 347 получается 34);
• зачеркни слева - убрать первую цифру.

Если сказано «исполнитель работает только с натуральными числами», промежуточные числа не могут быть нулём или отрицательными.

Обратный ход

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

• Если последняя команда «умножь на 5», то предыдущее число равно конечному, делённому на 5. Это возможно, только если конечное число делится на 5.
• Если последняя команда «вычти 4», то предыдущее число на 4 больше.
• Если «возведи в квадрат», конечное число должно быть точным квадратом.

Пример: из 5 получить 65 командами «1. вычти 4», «2. умножь на 5».

• 65 делится на 5: 65 = 13 * 5, перед ним было 13 (команда 2).
• 13 на 5 не делится, значит, 13 = 17 - 4 (команда 1). 17 = 21 - 4, 21 = 25 - 4 (команда 1 трижды).
• 25 = 5 * 5 (команда 2), а 5 - исходное число.

Читаем команды от начала: 2, 1, 1, 1, 2. Ответ: 21112. Проверка прямым ходом: 5 → 25 → 21 → 17 → 13 → 65.

Прямой перебор

Если обратный ход не получается (например, обе команды обратимы при любом числе), можно идти от начала: выпишите, какие числа получаются после одной команды, после двух и так далее, и остановитесь, когда получится нужное число. Ветки, где число ушло слишком далеко от цели, дальше не продолжайте.

Подходит любая программа, которая укладывается в ограничение по числу команд.

Разбор задачи из демоварианта

Задача. У исполнителя Вычислитель две команды:

1. умножь на 3;
2. прибавь 2.

Составьте алгоритм получения из числа 3 числа 37, содержащий не более 5 команд. В ответе запишите только номера команд.

Решение. Идём от конца.

1. 37 на 3 не делится, значит, последней была команда 2: перед ней было 37 - 2 = 35.
2. 35 на 3 не делится - снова команда 2: было 33.
3. 33 делится на 3: 33 = 11 * 3, команда 1, было 11.
4. 11 на 3 не делится - команда 2: было 9.
5. 9 = 3 * 3 - команда 1, было 3. Это исходное число.

Команды получены от конца к началу: 2, 2, 1, 2, 1. Записываем их в обратном порядке: 1, 2, 1, 2, 2.

Проверка: 3 * 3 = 9, 9 + 2 = 11, 11 * 3 = 33, 33 + 2 = 35, 35 + 2 = 37. Команд 5 - укладываемся в ограничение.

Ответ: 12122.

Типичные ошибки

• Записали команды в обратном порядке (как получились при обратном ходе).
• Превысили допустимое число команд.
• Получили отрицательное промежуточное число, хотя исполнитель работает только с натуральными.