Трассировка алгоритма
Трассировка алгоритма — это пошаговая запись его выполнения: какие команды выполняются, как изменяются значения переменных и какой результат получается. Такой способ помогает проверить формальное исполнение алгоритма, обнаружить ошибку и решить задания, где нужно определить значение переменной после выполнения программы.
Что такое трассировка алгоритма
Алгоритм состоит из команд, которые выполняются в определённом порядке. При трассировке мы не перескакиваем сразу к ответу, а последовательно просматриваем каждую команду. После каждой команды фиксируем состояние переменных — их текущие значения. Если команда ничего не меняет, это также важно учитывать: переход происходит к следующей строке.
Трассировка алгоритма — это последовательное выполнение команд алгоритма с записью промежуточных результатов и значений переменных. Обычно результат представляют в виде таблицы трассировки.
Перед началом работы нужно понять, где находятся исходные данные, какие переменные используются, в каком порядке записаны команды и какое значение требуется найти. Полезно отделять номер команды от её результата: номер показывает, что выполняется, а результат — как изменилось состояние алгоритма.
| Шаг | Команда | a | b | Результат или действие |
|---|---|---|---|---|
| 0 | Начальные значения | 2 | 5 | Исходное состояние |
| 1 | a := a + b | 7 | 5 | Изменилось значение a |
| 2 | b := a − b | 7 | −2 | Изменилось значение b |
В таблице каждая строка описывает состояние после выполнения указанной команды. Начальная строка часто имеет номер 0 и содержит значения, данные до запуска алгоритма.
Как читать команды и присваивания
Главная команда при трассировке — присваивание. Запись \(x := выражение\) означает: сначала вычислить выражение по старым значениям переменных, затем записать полученный результат в \(x\). Знак \(:=\) не означает равенство в обычном смысле и не является математическим уравнением.
Например, если \(x=4\), команда \(x := x+1\) делает \(x=5\). Нельзя считать, что такая запись утверждает невозможное равенство \(x=x+1\): это инструкция изменения значения.
В правой части команды используются значения переменных, которые были до выполнения команды. Все вычисления правой части выполняются сначала, а запись нового значения в левую переменную — после этого.
Если команда имеет вид \(c := a+b\), значения \(a\) и \(b\) не меняются, а новое значение получает только \(c\). Если одна переменная встречается и слева, и справа, старое значение справа нужно сохранить до записи нового.
- Запишите текущие значения всех переменных.
- Возьмите значения из состояния до команды.
- Вычислите правую часть.
- Измените только переменную слева от \(:=\).
- Перейдите к следующей команде.
После выполнения команд \(x:=3\) и \(x:=x+2\) чему равно \(x\)?
Таблица трассировки
Таблица особенно удобна в алгоритмах, содержащих несколько переменных, повторение команд или логические условия. Для каждой переменной создают отдельный столбец. В столбце «шаг» можно указывать номер команды или номер итерации цикла.
Если выполняется линейный алгоритм, строки таблицы идут по порядку сверху вниз. При ветвлении алгоритма сначала проверяют условие, затем выполняют только ту ветвь, которая соответствует результату проверки. При цикле повторяют действия до тех пор, пока условие цикла остаётся истинным или пока не выполнено заданное число повторений.
Выписывайте значения всех переменных после каждой команды, даже если меняется только одна. Так легче заметить, на каком шаге появилась ошибка, и не перепутать старое значение с новым.
Разобранный пример: алгоритм с условием
Рассмотрим алгоритм. Нужно определить значение переменной \(s\) после выполнения команд.
- \(a := 7\)
- \(b := 3\)
- \(s := a+b\)
- Если \(s>8\), то \(s := s−4\), иначе \(s := s+4\).
Нужно выполнить команды по порядку. На четвёртом шаге сначала проверить условие \(s>8\), затем выбрать только одну из двух команд.
| Шаг | Команда или проверка | a | b | s |
|---|---|---|---|---|
| 0 | Начальные значения | — | — | — |
| 1 | a := 7 | 7 | — | — |
| 2 | b := 3 | 7 | 3 | — |
| 3 | s := a + b | 7 | 3 | 10 |
| 4 | Проверка s > 8 | 7 | 3 | 10 |
| 5 | s := s − 4 | 7 | 3 | 6 |
После выполнения всего алгоритма \(s=6\). Важно: ветвь «иначе» не выполнялась, потому что условие \(s>8\) оказалось истинным.
Трассировка повторений и циклов
В циклическом алгоритме одну и ту же команду выполняют несколько раз. Для каждой итерации удобно записывать номер повторения, значение счётчика и изменяемые данные. Сначала нужно определить начальное значение счётчика, затем проследить изменение после каждой итерации.
Например, для команд «\(i:=1\); повторить 3 раза: \(i:=i+2\)» таблица будет такой:
| Итерация | i до команды | Изменение | i после команды |
|---|---|---|---|
| 0 | 1 | — | 1 |
| 1 | 1 | +2 | 3 |
| 2 | 3 | +2 | 5 |
| 3 | 5 | +2 | 7 |
Если число повторений задаётся условием, после каждой итерации нужно заново проверить это условие. Такой порядок связан с циклическим алгоритмом: нельзя заранее прекращать цикл только потому, что значение переменной стало «похожим» на ответ.
Для каждого повторения фиксируйте состояние до выполнения тела цикла, результат выполнения тела и состояние после него. Затем проверьте условие продолжения или переходите к следующему повторению.
Как проверять полученный результат
После трассировки полезно выполнить обратную проверку. Сравните число строк с числом реально выполненных команд, убедитесь, что при условии выполнена только одна ветвь, а в каждом присваивании изменена именно переменная слева. Если алгоритм решает задачу, проверьте ответ на здравый смысл: например, счётчик не должен уменьшиться после команды прибавления.
Трассировка помогает и при составлении алгоритма решения задачи. Сначала записывают общий порядок действий, затем на конкретных данных проверяют его работу. Для сложных условий важно отдельно определить, истинно ли каждое сравнение; этому посвящена тема истинности условия.
1. Выполнение команд не по порядку. 2. Использование уже изменённого значения внутри той же команды. 3. Изменение переменной, которой нет слева от \(:=\). 4. Выполнение обеих ветвей условия вместо одной. 5. Пропуск последней итерации или лишнее повторение цикла. 6. Потеря знака минус при вычислении выражения.
- Я выписал исходные значения.
- Я выполнял команды сверху вниз.
- После каждой команды записал новые значения.
- Условие проверил до выбора ветви.
- Количество итераций цикла посчитал внимательно.
- В конце ответил именно на вопрос задания.
Стратегия выполнения задания
В заданиях уровня ОГЭ сначала перепишите алгоритм в сокращённую таблицу. Если программа короткая, достаточно столбцов для всех переменных. Если есть цикл, добавьте столбец с номером итерации. Условия лучше записывать отдельной строкой: рядом укажите «истина» или «ложь». Это предотвращает случайный переход не в ту ветвь.
Не пытайтесь считать всё в уме, если переменных больше двух или есть несколько повторений. Небольшая таблица обычно быстрее, чем исправление ошибки в конце. Если значение переменной уже не нужно, всё равно оставьте его в строке: оно может понадобиться в следующем выражении.
Проверь себя
Главное
- Трассировка — это пошаговое выполнение алгоритма с записью состояний переменных.
- В присваивании сначала вычисляют правую часть по старым значениям, затем изменяют переменную слева.
- При условии выполняется только одна выбранная ветвь.
- В цикле нужно фиксировать каждую итерацию и проверять условие продолжения.
- Таблица трассировки помогает найти ошибку и точно получить ответ экзаменационного задания.