Кузнечик/исполнитель с командами +N и −M: как подобрать программу, чтобы попасть в нужную точку?
Дан исполнитель, который умеет прибавлять и отнимать (например, +3 и −2). Надо из числа A получить число B, и часто ещё «минимальным числом команд». Я просто наугад подбираю и путаюсь. Есть какой-то системный способ решать такие задачи?
1 ответ
Тут не надо угадывать — есть систематический подход.
1. Считаем нужную разницу. Пусть надо из A получить B. Разница d = B − A. Например, A=1, B=10, команды +3 и −2 → нужно набрать +9.
2. Ищем, сколькими «плюсами» и «минусами» набрать эту разницу. Если команды +3 и −2, то ищем целые неотрицательные x (число +3) и y (число −2), такие что 3x − 2y = 9. Перебираем x: при x=3 → 9 − 2y = 9 → y=0. Готово: три раза +3.
3. «Минимум команд» — выбираем вариант с наименьшим x+y. Обычно стараемся побольше использовать команду с большим шагом в нужную сторону.
Если вариантов разрешают перебрать программой — на Python это решается перебором:
for x in range(0, 20):
for y in range(0, 20):
if 3 * x - 2 * y == 9:
print(x, y, x + y)
И выбираешь строку с минимальной суммой x + y. Главное — перевести задачу в уравнение «шаги вперёд минус шаги назад = разница», а не перебирать руками вслепую.