В общем случае, трассировка - один из отладки программ врукопашную: состояние программы контролируется на определённом отрезке времени её выполнения путём анализа значений переменных. трассировка в том или ином виде при отладке программ сложнее школьного дз практически неизбежна. в простейшем случае, трассировка - вывод значений переменных на экран (например, в окно консоли) , либо расчёт их на бумажке для каждого шага. в более продвинутом варианте используются точки останова, окно наблюдения, выполнение по шагам и, если есть, контекстный интерпретатор выражений. есть также специальная "трассирующая консоль" - интерфейс вывода информации из программы в отладчик, если таковой присутствует. почти любой современный отладчик показывает состояние програмm при её останове, что делает трассировку процессом легко доступным
1. → 2 [сдвинуться вправо, перейти на строку 2] 2. → 3 [сдвинуться вправо, перейти на строку 3] — в вопросе опечатка? 3. → 4 [сдвинуться вправо, перейти на строку 4] 4. ? 5;2 [если в текущей ячейке нет метки, перейти на строку 5, иначе вернуться на 2] 5. ← 6 [сдвинуться влево, перейти на строку 6] 6. V 7 [поставить метку, перейти на строку 7] 7. ! [закончить работу]
Программа делает следующее: переходит на метку вправо, шагами по две ячейки идёт вправо, пока не дойдёт до пустой ячейки, возвращается на ячейку влево, ставит там метку и заканчивает работу.
Пусть метки расположены в ячейках 0 - (n-1), каретка под ячейкой 0. Тогда сначала каретка окажется подячейкой 1, сделает [n/2] шагов по 2 вправо ([x] — целая часть x), оказавшись под ячейкой 1 + 2 * [n/2], вернётся на ячейку влево (ячейка 2 * [n/2]) и поставит там метку.
Если n было четным, будут заполнены ячейки от 0 до n, каретка под ячейкой n Если n было нечетным, будут заполнены ячейки от 0 до n - 1, каретка под ячейкой n - 1
