16. Шаг за шагом

Определения и обозначения

Алгоритм — это точная последовательность команд, которая приводит к нужному результату. Порядок команд важен: следующая команда может использовать данные, изменённые предыдущей. Если поменять команды местами, результат иногда изменится или одна из команд станет невыполнимой.

Шаг алгоритма — одно выполнение одной команды. Прослеживая решение по шагам, мы видим, что происходит после каждого действия, а не только конечный ответ. Это помогает не пропустить команду и найти место, где возникла ошибка.

Трассировка — запись изменений значений переменных и действий исполнителя во время выполнения алгоритма. Переменная — это именованное место для хранения данных, например x или сумма. Трассировка превращает выполнение алгоритма в последовательность наблюдаемых действий.

Трассировочная таблица — таблица, в которой по шагам фиксируют состояние переменных и промежуточные результаты. В ней удобно сравнивать исходные данные, новые значения и ожидаемый ход решения. Такая запись особенно полезна для ветвлений и циклов.

Как это устроено

Чтобы проверить алгоритм, начинают с первой команды и выполняют команды строго по порядку. Нельзя перескакивать к знакомому итоговому действию, потому что его данные могут зависеть от нескольких предыдущих шагов. После каждой команды полезно записать новое состояние переменных и только потом переходить дальше.

Команда присваивания заменяет значение переменной новым значением, полученным из числа, другой переменной или выражения. Поэтому в трассировке указывают актуальное состояние: если было x = 3, а затем выполнили x = x + 2, стало x = 5. Старое значение остаётся только в записи предыдущего шага, а не в текущем состоянии переменной.

Ветвление нельзя выполнять, не проверив условие. Сначала подставляют известные значения в условие и выясняют, истинно оно или ложно. Затем выполняют только соответствующую ветвь, потому что две альтернативы описывают разные варианты развития алгоритма.

В цикле один и тот же набор команд повторяется, пока выполняется условие продолжения. Каждый проход меняет значения или состояние исполнителя, поэтому его записывают отдельным шагом или строкой таблицы. Если не фиксировать проходы отдельно, легко пропустить повторение или выполнить его лишний раз.

После завершения выполнения полученный результат сравнивают с ожидаемым. Если ответы различаются, просматривают таблицу сверху вниз и находят первый шаг, где значение или действие стало неправильным. Проверка именно с этого места помогает отличить ошибку в алгоритме от ошибки в более поздних вычислениях.

Что фиксируют при пошаговом выполнении алгоритма

Таблица должна показывать не только финальный ответ, но и путь к нему. Перед выполнением команды можно записать текущие значения, а после неё — изменения, которые произошли. Для условий и циклов отдельно отмечают результат проверки или номер прохода.

При заполнении таблицы сначала записывают исходные значения, затем переходят к первой команде. Каждая следующая строка должна опираться на состояние из предыдущей строки. Если результат неверен, по таблице можно быстро найти первый шаг с ошибкой.

Разбор задач

Задача 1. Последовательность присваиваний

Пусть начальные значения таковы: a = 4 и b = 7. Алгоритм состоит из команд: c = a + b; a = c − 2; b = a + c. Нужно найти конечные значения переменных, не используя только устный подсчёт итогового результата.

1. На первом шаге вычисляем c = 4 + 7, поэтому c = 11, а a и b пока равны 4 и 7.
2. На втором шаге выполняем a = c − 2. Новое значение a равно 9; прежнее значение a = 4 больше не считается текущим.
3. На третьем шаге используем уже обновлённое a: b = 9 + 11, поэтому b = 20.

Ответ: a = 9, b = 20, c = 11. Трассировка показывает, почему в последней команде нужно брать a = 9, а не его начальное значение.

Задача 2. Ветвление

Рассмотрим алгоритм: если x > 0, то y = x + 5, иначе y = x − 5. Выполним его для двух наборов данных: x = 3 и x = −2. Главное — каждый раз отдельно проверить условие до выполнения команды присваивания.

1. При x = 3 проверяем 3 > 0: условие истинно. Выполняем только первую ветвь и получаем y = 3 + 5 = 8.
2. При x = −2 проверяем −2 > 0: условие ложно. Переходим только ко второй ветви и получаем y = −2 − 5 = −7.

Ответ: при x = 3 значение y равно 8, а при x = −2 значение y равно −7. Выполнение обеих ветвей дало бы неверный результат, потому что алгоритм выбирает одну из них.

Задача 3. Цикл и поиск ошибки

Пусть s = 0, а алгоритм три раза повторяет команду s = s + 2. Ожидаемый результат — s = 6, но в записи проверки после второго прохода почему-то указано s = 6. Нужно восстановить значения и найти ошибочный шаг.

1. До цикла s = 0. После первого прохода s = 0 + 2 = 2.
2. После второго прохода используется новое значение: s = 2 + 2 = 4, поэтому запись s = 6 на этом шаге неверна.
3. После третьего прохода s = 4 + 2 = 6. Условие о трёх проходах выполнено, цикл заканчивается.

Ответ: правильная последовательность значений — 0, 2, 4, 6; ошибка появилась при записи результата второго прохода. Проверка каждого повторения отдельно позволяет отличить ошибку таблицы от ошибки самого алгоритма.

Типичные ошибки

Ученик пропускает команду или выполняет команды не по порядку, потому что мысленно сразу видит итог. Так теряется зависимость между промежуточными значениями. Проверить себя можно, пронумеровав все команды и поставив отметку после каждой выполненной.

Иногда считают, что присваивание добавляет новое значение к прежнему или сохраняет оба значения. На самом деле после команды присваивания текущим становится только новый результат. Для проверки сравните значение переменной до команды и сразу после неё в таблице.

При ветвлении выполняют обе ветви, хотя условие выбирает только одну. Такая ошибка появляется, если воспринимать ветви как последовательные команды. Сначала запишите результат проверки условия, а затем зачеркните ветвь, которая не должна выполняться.

В цикле неверно считают проходы или проверяют условие только один раз. Из-за этого появляется пропущенное либо лишнее повторение. Помогает отдельная строка для каждого прохода и повторная запись условия после изменения переменных.

Связь с другими темами

До пошагового выполнения нужно знать, что такое алгоритм, команда, переменная и присваивание. Эти понятия объясняют, какие действия выполняет исполнитель и где хранятся данные. Без них невозможно правильно прочитать строку трассировочной таблицы.

Трассировка пригодится при проверке программ и поиске ошибок. Она особенно полезна в алгоритмах с ветвлениями и циклами, где итог зависит от условия и количества повторений. Такой анализ помогает исправлять программу не наугад, а по конкретному шагу.

Что запомнить

• Алгоритм выполняют строго в заданном порядке.
• Один шаг соответствует выполнению одной команды.
• После присваивания у переменной становится новое значение.
• Условие проверяют до выбора ветви.
• Каждый проход цикла нужно учитывать отдельно.
• Трассировка помогает найти шаг, на котором возникла ошибка.