Информатика: как вручную проследить два вложенных цикла

Вручную проследить два вложенных цикла помогает таблица: для каждого шага записываете значение переменной внешнего цикла, переменной внутреннего, счётчик повторов и итоговую переменную. Разберём пример: s := 0; для i от 1 до 3, внутри — для j от 1 до i выполняем s := s + 1. Внутренний цикл выполнится 1 + 2 + 3 = 6 раз, потому что при i = 1 он крутится один раз, при i = 2 — дважды, при i = 3 — трижды; в итоге s станет равно 6.
Зачем нужна трассировка
Код с вложенными циклами неудобно считать «в уме», потому что внутренний цикл выполняется заново для каждого значения внешнего — легко потерять счёт или пропустить итерацию. Трассировка снимает эту проблему: вы фиксируете каждый шаг в таблице и видите всю картину, а не держите её в голове. Навык нужен и для понимания чужого кода, и для проверки собственного: прежде чем запускать программу, полезно предсказать результат вручную. На маленьком примере трассировка занимает пару минут, зато выявляет ошибки в логике ещё до компилятора.
Пример и план трассировки
Возьмём псевдокод: s := 0; для i := 1 до 3; для j := 1 до i; s := s + 1; конец; конец. Внешний цикл задаёт значения i: 1, 2, 3. Внутренний цикл при каждом i крутится от 1 до i, то есть длина его меняется от прохода к проходу — именно поэтому нельзя просто перемножить границы. Заведите таблицу из четырёх столбцов: i, j, номер выполненного присваивания, текущее s. Заполнять будем построчно: одно выполнение тела внутреннего цикла — одна строка.
Трассировка по шагам
Шаг 1: i = 1, внутренний цикл запускается с j = 1 по 1 — одна строка: j = 1, s = 0 + 1 = 1. Шаг 2: i = 2, внутренний цикл работает дважды: строка «j = 1, s = 2», затем «j = 2, s = 3». Шаг 3: i = 3, три строки: «j = 1, s = 4», «j = 2, s = 5», «j = 3, s = 6». Всего строк в таблице 1 + 2 + 3 = 6 — столько же, сколько раз выполнилось тело внутреннего цикла. Внешний цикл сделал 3 прохода, а тело внутреннего выполнилось 6 раз. Финальное значение s = 6. Каждое число в таблице получено из предыдущего, поэтому ошибку в одной строке сразу видно по несостыковке со следующей.
Как считать число повторов быстрее
Когда граница внутреннего цикла зависит от переменной внешнего, число повторов считают суммой по проходам: при i от 1 до 3 и j от 1 до i получаем 1 + 2 + 3 = 6. Если границы независимы — например, i от 1 до 3 и j от 1 до 2 — общее число повторов равно произведению: 3 · 2 = 6. Убывающий цикл, например j от i до 1, не меняет общего принципа: просто перечислите длины проходов. Всегда сверяйте быстрый расчёт с первыми строками таблицы: если сумма сходится с трассировкой, остальное можно не писать вручную — достаточно досчитать по формуле.
Типичные ошибки при трассировке
Первая — забыть, что внутренний цикл начинается сначала при каждом новом i: переменная j каждый раз возвращается к начальному значению, а не продолжает с прошлого прохода. Вторая — потерять последнюю итерацию: в нашем псевдокоде цикл «от 1 до n» включает и n-й шаг. Третья — перепутать, что наращивается в теле: в нашем примере растёт s на 1 при каждом выполнении, а не i и не j — переменные цикла меняются автоматически по своим правилам. Четвёртая — начать считать s не с нуля: начальное значение задаётся до циклов, и пропустить его нельзя.
Как тренироваться
Меняйте в примере по одному параметру и заново предсказывайте результат: пусть j идёт от 1 до 2 независимо от i; пусть i идёт от 1 до 4; пусть вместо s := s + 1 записано s := s + i. После каждого изменения сначала ответьте на два вопроса без таблицы — сколько раз выполнится внутренний цикл и чему равно s, — и только потом проверьте трассировкой. Расхождение предсказания и таблицы — самый ценный момент: именно там рождается понимание того, как вложенные циклы «считают». Такой навык переносится на любые задачи с итерациями, а не только на один конкретный шаблон.
Посмотрите программу и условия обучения по этой теме.
Посмотреть программуПосмотрите программу и условия обучения по этой теме.
Посмотреть программу