Задание 5 ОГЭ: как аккуратно выполнить программу для исполнителя с двумя командами?
Дан исполнитель с двумя командами, например «прибавь 1» и «умножь на 2», у каждой свой номер. По цепочке номеров команд надо получить из стартового числа конечное (или наоборот — подобрать кратчайшую цепочку). Я путаюсь и сбиваюсь на середине. Как не терять нить?
2 ответа
Тут спасает аккуратная запись каждого шага в столбик — не держи число в голове.
Пусть команды: 1 — «прибавь 1», 2 — «умножь на 2». Дана цепочка 1 2 2, старт 3:
старт: 3
1 (прибавь 1): 4
2 (умножь на 2): 8
2 (умножь на 2): 16
ответ: 16
Каждую строку пишешь явно — тогда не собьёшься.
Если наоборот, надо подобрать кратчайшую цепочку из старта в цель, удобнее идти с конца к началу, отменяя операции: если число чётное — выгоднее «разделить на 2» (отмена умножения), если нечётное — «вычесть 1». Так получается короткий путь. В конце разверни последовательность.
Жадная идея «с конца» работает почти всегда для команд +1 и ×2: чётное делим, нечётное уменьшаем на 1. Но если команды другие (например ×3 или +2), бездумно жадничать нельзя — там иногда надо перебрать пару вариантов. Сначала пойми набор команд, а потом выбирай стратегию.