Метод трассировки цикла
Метод трассировки цикла — это формальное исполнение алгоритма по шагам: после каждой итерации записывают значения переменных и проверяют, будет ли выполнено продолжение цикла. Такой способ помогает точно решать задания, где нужно определить результат программы, число итераций или значение переменной после завершения цикла.
Что такое трассировка цикла
Трассировка — это последовательное воспроизведение работы программы без догадок. Для каждой команды определяют, какие значения переменных были до её выполнения и какими стали после неё. Особенно важно не пропускать проверку условия: цикл может не выполниться ни разу или завершиться сразу после очередного изменения переменной.
Трассировка цикла — построение последовательности состояний переменных при выполнении цикла. Состояние программы — это значения всех переменных в некоторый момент времени.
Перед решением полезно повторить таблицу состояний переменных и условие цикла. Таблица состояний превращает длинное вычисление в понятную последовательность строк, а анализ условия показывает, когда цикл продолжает работу.
Команды выполняются строго сверху вниз. В цикле сначала проверяется условие, затем при истинном результате выполняется тело цикла, после чего управление возвращается к проверке условия.
Алгоритм трассировки
Для каждого цикла применяйте один и тот же порядок действий. Сначала выпишите начальные значения переменных. Затем определите, какое условие проверяется перед каждой итерацией. После этого выполните команды тела по порядку и занесите новые значения в таблицу.
- Выписать начальные значения всех переменных, которые участвуют в условии, теле или выводе.
- Проверить условие цикла при текущих значениях.
- Если условие ложно, остановить цикл и перейти к командам после него.
- Если условие истинно, выполнить каждую команду тела в указанном порядке.
- Записать новое состояние и снова проверить условие.
- После завершения определить требуемый результат: значение переменной, сумму, количество итераций или выведенную последовательность.
Удобно использовать таблицу, где отдельные столбцы отведены для номера итерации, значений переменных до тела, результата проверки и значений после тела. Если условие проверяется в начале, можно обозначать строку с последней ложной проверкой, чтобы не перепутать число итераций.
| Шаг | Проверка условия | Значения до тела | Значения после тела |
|---|---|---|---|
| 0 | истина или ложь | начальные значения | — |
| 1 | истина | значения перед первой итерацией | результат первой итерации |
| 2 | истина | результат первой итерации | результат второй итерации |
| … | … | … | … |
| последний | ложь | финальные значения | цикл завершён |
Для счётного цикла сначала найдите, как изменяется управляющая переменная. Если она увеличивается на постоянное число, можно проверить результат формулой, но для экзамена надёжнее сделать несколько строк трассировочной таблицы и убедиться, где условие становится ложным.
Пример: цикл с изменением двух переменных
Рассмотрим фрагмент алгоритма. Нужно определить значение \(s\) после завершения цикла. Переменная \(i\) — счётчик, а \(s\) — накапливаемая сумма.
s := 2\ni := 1 while i <= 5 do s := s + 2*i i := i + 2 end while output s
В условии используется значение \(i\), которое было получено после предыдущей итерации. Сначала \(i=1\), затем переменная увеличивается на \(2\): значения счётчика перед телом будут \(1, 3, 5, 7\).
Цикл выполнился три раза, хотя проверка условия проводилась четыре раза: три раза она была истинной и один раз — ложной. Ответ: \(s=20\).
Что произойдёт в цикле while i < 10 do i := i + 3, если перед началом i = 10?
Как не ошибиться в порядке команд
Внутри тела команды могут зависеть друг от друга. Нельзя считать, что все правые части используют старые значения переменных. Каждая следующая команда видит изменения, сделанные предыдущими командами этой же итерации.
Например, в последовательности \(a:=a+1\) и \(b:=a\cdot2\) вторая команда использует уже увеличенное значение \(a\). Если поменять команды местами, результат может измениться. Поэтому в таблице полезно записывать промежуточные значения после каждой существенной команды, а не только итог итерации.
1. Проверять условие после тела вместо проверки до тела. Это неверно для цикла с предусловием. 2. Считать последнюю ложную проверку итерацией. Она завершает цикл, но тело не выполняется. 3. Использовать старое значение переменной. Команды тела исполняются последовательно. 4. Путать \(<\) и \(\le\). При равенстве условие с \(\le\) истинно, а с \(<\) — ложно. 5. Забывать начальное значение. Накопитель часто начинается не с нуля.
Особые случаи и быстрые проверки
Если условие изначально ложно, цикл с предусловием не выполняется. Если управляющая переменная изменяется в сторону, противоположную требуемой, цикл может стать бесконечным. Например, при условии \(i<10\) команда \(i:=i-1\) не приближает \(i\) к границе, если начальное значение меньше 10.
Для проверки результата применяйте трассировку алгоритма целиком: иногда ошибка находится не в цикле, а в начальном присваивании или в команде после цикла. Арифметические действия удобно сверять отдельно, используя правила арифметических выражений. Если циклы вложены, внешний и внутренний счётчики следует анализировать раздельно; для этого пригодится анализ вложенных циклов.
Формула выше подходит для переменной, которая на каждой итерации изменяется на постоянную величину \(d\). Но найденное значение нужно проверить условием цикла: не всякое значение \(k\) соответствует реально выполненной итерации.
Сначала проверка условия, затем тело, затем возврат к условию. Последняя проверка может быть ложной, но последней итерации без выполнения тела не бывает.
Связь с другими способами анализа
Трассировка отвечает на вопрос «что произошло на каждом шаге». Инвариант цикла отвечает на более общий вопрос «какое свойство сохраняется после каждой итерации». Для коротких программ достаточно таблицы, а для длинных циклов инвариант помогает проверить общий результат без записи всех строк.
При проверке алгоритма можно использовать разработку тестов: отдельно проверять нулевое число итераций, одну итерацию и обычный случай. Это особенно полезно, если условие содержит границу или несколько логических операций.
Quick-test
Проверьте себя
Главное
- Трассировка — это последовательная запись состояний переменных при выполнении алгоритма.
- В цикле с предусловием сначала проверяют условие, затем при его истинности выполняют тело.
- Число итераций равно числу истинных проверок условия; последняя ложная проверка итерацией не является.
- Команды тела выполняются сверху вниз, поэтому изменения одной команды влияют на следующие.
- Для надёжного решения составляйте таблицу, отмечайте начальное состояние и отдельно фиксируйте момент завершения цикла.