Трассировка программы
Трассировка программы — это последовательная запись состояния программы после выполнения каждой команды. Такой способ помогает вручную проверить значения переменных, понять ход выполнения программы и найти результат без запуска кода.
Что такое трассировка
При трассировке программа выполняется мысленно или на бумаге по правилам языка программирования. Для каждой команды нужно определить, какие переменные изменились, и записать их новые значения. Если команда ничего не меняет, это также важно учитывать: переход к следующей строке не означает, что значения можно пересчитать заново произвольно.
Трассировка программы — пошаговая запись выполнения алгоритма, в которой для каждой существенной команды фиксируются значения переменных, условия переходов и промежуточные результаты.
Состояние программы — это набор текущих значений всех переменных, которые влияют на дальнейшее выполнение. Например, при наличии переменных \(a\), \(b\) и \(s\) состояние можно записать как \((a,b,s)\). При трассировке не обязательно записывать постоянные переменные, но на экзамене безопаснее сначала включить в таблицу все используемые величины.
| Шаг | Команда или действие | a | b | Результат проверки |
|---|---|---|---|---|
| 0 | Начальные значения | — | — | — |
| 1 | Присваивание | ... | ... | — |
| 2 | Условие | ... | ... | истина/ложь |
| 3 | Следующая команда | ... | ... | — |
Как составить таблицу трассировки
Перед началом выделите начальные значения, команды присваивания, условия, циклы и вызовы функций. Затем пронумеруйте шаги. Номер шага не обязан совпадать с номером строки: одна строка может содержать несколько действий, а условие иногда нужно рассматривать отдельно.
- Прочитайте программу целиком и определите, с какой команды начинается выполнение.
- Выпишите начальные значения переменных, если они заданы.
- Выполните текущую команду, используя значения, которые были получены на предыдущем шаге.
- Запишите новые значения переменных в таблицу.
- Для условия отдельно определите значение логического выражения: истина или ложь.
- Если условие ложно, пропустите тело условной команды; если истинно — выполните его.
- В цикле после каждой итерации снова проверьте условие и занесите результат в таблицу.
- После завершения программы прочитайте именно тот результат, который требуется вывести.
В команде \(x := E\) сначала вычисляется выражение \(E\) по старым значениям переменных, затем полученный результат записывается в \(x\). Поэтому в команде \(x := x+1\) правая часть использует прежнее значение \(x\), а не уже увеличенное.
Например, последовательность a := b; b := a не меняет местами значения. После первой команды \(a\) получает старое значение \(b\), а во второй команде это новое значение \(a\) записывается в \(b\). Для обмена обычно используют дополнительную переменную.
Условия, ветвления и циклы
При проверке условия вычисляйте сначала арифметические выражения, затем сравнение, а после этого логические операции. Не подменяйте условие своим ожиданием: даже небольшое изменение переменной перед проверкой может изменить ветвь программы.
Записывайте условие в отдельном столбце. Например, для if x > 3 занесите не только \(x\), но и результат проверки: «истина» или «ложь». Это снижает риск выполнить не ту ветвь.
В цикле while условие проверяется до выполнения тела. Если оно сразу ложно, тело не выполняется ни разу. В цикле for удобно составить отдельные строки для начального значения счётчика, каждой итерации и изменения счётчика.
Какое значение будет у \(x\) после выполнения команд x := 4; y := x + 3; x := y - 1?
Разобранный пример с циклом
Рассмотрим программу. Она накапливает сумму квадратов чисел от 1 до 4. Важно после каждой итерации записывать и значение счётчика, и накопленную сумму.
1s = 0\ni = 1 2while i <= 4: 3 s = s + i * i 4 i = i + 1 5print(s)
Нужно определить значение, которое будет выведено командой print(s). Начальное состояние: \(s=0\), \(i=1\).
| Перед проверкой | Условие | s после тела | i после тела |
|---|---|---|---|
| s=0, i=1 | 1 ≤ 4 — истина | 1 | 2 |
| s=1, i=2 | 2 ≤ 4 — истина | 5 | 3 |
| s=5, i=3 | 3 ≤ 4 — истина | 14 | 4 |
| s=14, i=4 | 4 ≤ 4 — истина | 30 | 5 |
| s=30, i=5 | 5 ≤ 4 — ложь | 30 | 5 |
В задачах с несколькими ветвями сначала проследите путь выполнения, а не все возможные пути сразу. Для анализа сложных фрагментов полезно отдельно выписывать значения логических выражений и возвращаемые значения функций. Если программа содержит вызов функции, временно рассматривайте его как отдельный блок: определите аргументы, выполните тело функции и подставьте результат обратно.
Трассировка строковых и логических алгоритмов
В задачах со строками переменная обычно не изменяется «частично»: после операции ей присваивается новая строка. При замене фрагмента строки записывайте результат полностью, чтобы не перепутать старую и новую длину. Если используется разбиение строки, фиксируйте получившийся список или количество элементов.
В логических выражениях соблюдайте приоритет операций: сначала выполняются действия в скобках, затем отрицание not, затем and, затем or — если язык не задаёт иной порядок. При сомнении расставьте скобки явно. В задачах на несколько условий удобно использовать отдельные столбцы для промежуточных сравнений.
1. Использовать новое значение переменной при вычислении той же команды присваивания. 2. Выполнить тело цикла, не проверив условие. 3. Забыть последнюю проверку, которая заканчивает цикл. 4. Перепутать = как присваивание и сравнение в конкретном языке. 5. Изменить значение счётчика не там, где это делает программа. 6. Вывести промежуточную переменную вместо той, которая указана в команде вывода.
Каждая команда читается слева направо только в том смысле, который установлен языком. Главное правило трассировки: сначала вычислить правую часть по текущему состоянию, затем изменить левую часть.
Связь с другими способами анализа
Трассировка — практический инструмент анализа алгоритма программы. Она показывает один конкретный путь выполнения для выбранных входных данных, но не доказывает правильность алгоритма для всех входов. Для проверки разных случаев применяют тестирование программы, а для особых ситуаций полезно выбирать граничные значения.
Если алгоритм содержит вызов процедуры, процедура может изменить переданные переменные или выполнить вывод. В рекурсивных и вложенных вызовах важно учитывать стек вызовов: сначала завершается самый последний начатый вызов, затем управление возвращается к предыдущему.
Проверь себя
while x < 3, если вначале \(x=3\)?Главное
- Трассировка — пошаговая жазба значений переменных и результатов проверок.
- В присваивании сначала вычисляют правую часть по старым значениям, затем меняют левую.
- В цикле нужно фиксировать каждую итерацию и отдельную последнюю проверку, завершившую цикл.
- Для условий записывайте результат «истина» или «ложь», чтобы не перепутать ветвь.
- Трассировка показывает выполнение для конкретных входных данных; для других входов нужны дополнительные тесты.