День 5 — быстрый.
Предыдущие части:
День 1
День 2
День 3
День 4
Проблема первая:
От процессора поступает срочное прерывание: он застрял в лабиринте инструкций перехода, и ему нужна помощь любых программ с запасными циклами, чтобы помочь найти выход.
Сообщение включает в себя список смещений для каждого перехода. Переходы относительные:
-1
переходит к предыдущей инструкции, а2
пропускает следующую. Начните с первой инструкции в списке. Цель состоит в том, чтобы следовать за прыжками, пока один из них не окажется за пределами списка.
Кроме того, эти инструкции немного странные; после каждого перехода смещение этой инструкции увеличивается на
1
. Итак, если вы встретите смещение3
, вы переместитесь на три инструкции вперед, но измените его на4
в следующий раз, когда оно встретится.
Например, рассмотрим следующий список смещений перехода:
0
3
0
1
-3
Положительные скачки («вперед») движутся вниз; отрицательные скачки движутся вверх. Для удобочитаемости в этом примере все эти значения смещения будут записаны в одной строке, а текущая инструкция будет отмечена в круглых скобках. Прежде чем будет найден выход, необходимо предпринять следующие шаги:
(0) 3 0 1 -3
– до каких-либо действий.
(1) 3 0 1 -3
- прыгать со смещением0
(то есть вообще не прыгать). К счастью, инструкция затем увеличивается до1
.
2 (3) 0 1 -3
- шаг вперед из-за инструкции, которую мы только что изменили. Первая инструкция снова увеличивается, теперь до2
.
2 4 0 1 (-3)
- прыгнуть до конца; оставить4
позади.
2 (4) 0 1 -2
- вернуться туда, где мы только что были; увеличить-3
до-2
.
2 5 0 1 -2
- прыгнуть на4
шагов вперед, выйдя из лабиринта.
В этом примере выход достигается за
5
шагов.
Сколько шагов нужно, чтобы добраться до выхода?
Проблема вторая:
Теперь прыжки стали еще более странными: после каждого прыжка, если смещение было три или больше, вместо этого уменьшайте его на
1
. В противном случае увеличьте его на1
, как и раньше.
Используя это правило в приведенном выше примере, процесс теперь занимает
10
шагов, а значения смещения после нахождения выхода остаются равными2 3 2 3 -1
.
Сколько шагов нужно пройти, чтобы добраться до выхода?
Решение:
Увидимся завтра!
SR.