Анализ алгоритма программы
Анализ алгоритма программы — это последовательное восстановление её работы: какие команды выполняются, как изменяются значения переменных, какие ветви выбираются и чем заканчивается выполнение. Такой разбор особенно важен для заданий выполнения программы и управления выполнением программы, где ответ нужно получить без запуска кода.
1. Что нужно установить при анализе
Программа состоит из команд, выполняемых в определённом порядке. При анализе нужно проследить этот порядок и после каждой существенной команды определить текущее состояние программы. Состояние включает значения переменных, положение в алгоритме и, если используются функции, данные о стеке вызовов.
Анализ программы — это пошаговое определение результатов выполнения её команд для заданных исходных данных. Итогом могут быть значения переменных, напечатанный текст, количество повторений или логическое значение.
- Выписать исходные значения переменных и входные данные.
- Разделить программу на команды или блоки команд.
- Определить порядок выполнения команд.
- После присваиваний обновлять значения переменных.
- Для условий установить, истинны они или ложны.
- Для циклов определить число итераций и состояние переменных после каждой итерации.
- Найти итоговый вывод или значение, которое требуется в условии.
Удобнее всего пользоваться таблицей трассировки. В её строках записывают моменты, когда изменяются переменные или проверяется условие. Необязательно заносить каждую строку исходного кода: важно фиксировать все изменения, влияющие на ответ.
| Шаг | Команда или событие | a | b | Условие | Вывод |
|---|---|---|---|---|---|
| 0 | Исходные данные | … | … | — | — |
| 1 | Присваивание | … | … | — | — |
| 2 | Проверка условия | … | … | истина/ложь | — |
| 3 | Итерация цикла | … | … | — | — |
| 4 | Печать | … | … | — | … |
2. Переменные и присваивание
Переменная хранит одно текущее значение. Команда присваивания вычисляет выражение справа и записывает результат в переменную слева. Старое значение этой переменной после присваивания теряется, если оно не сохранено в другой переменной.
Здесь \(E\) — выражение, вычисляемое с использованием прежних значений переменных. Например, после команд \(a=5\) и \(a=a+2\) переменная \(a\) равна \(7\), а не сохраняет оба значения.
В выражении справа используются значения переменных, существовавшие до выполнения данной команды. Сначала выражение вычисляется, затем результат записывается в переменную слева.
1a = 3 2b = a + 4 3a = b - 1
После первой строки \(a=3\). Во второй строке вычисляется \(3+4\), поэтому \(b=7\). В третьей строке используется уже новое значение \(b\), и \(a\) становится равной \(6\). При анализе нельзя читать весь блок как математическую систему уравнений: команды выполняются по очереди.
3. Ветвления и логические условия
В операторе ветвления сначала вычисляется логическое условие. Если оно истинно, выполняется первая ветвь; если ложно — вторая, если она предусмотрена. Команды пропущенной ветви не влияют на значения переменных.
Логическое условие — выражение, результатом которого является истина или ложь. Примеры: \(x>0\), \(a=b\), \(n\le 10\). Составные условия объединяются операциями И, ИЛИ и НЕ.
- Для \(A\) И \(B\) результат истинен только тогда, когда истинны оба условия.
- Для \(A\) ИЛИ \(B\) достаточно истинности хотя бы одного условия.
- НЕ \(A\) меняет истину на ложь, а ложь — на истину.
Что будет выведено после выполнения: \(x=4\); если \(x>5\), то \(x=x+10\), иначе \(x=x-1\)?
При нескольких условиях проверяйте их именно в том порядке, в котором они записаны. В конструкции «если — иначе если — иначе» выполняется только первая подходящая ветвь, а последующие уже не рассматриваются.
4. Циклы: итерации и условие остановки
Цикл повторяет набор команд. Один проход тела цикла называется итерацией. Для каждого прохода нужно определить значения переменных в начале, проверить условие и вычислить новые значения после тела цикла.
Для цикла с предусловием условие проверяется перед каждой итерацией. Если оно ложно сразу, тело не выполняется ни разу. Для цикла с постусловием тело выполняется хотя бы один раз, а проверка производится после него.
В цикле со счётчиком полезно выписать первое, второе и последнее значение счётчика. Если шаг постоянен, значения образуют арифметическую последовательность. Не забывайте проверить, входит ли конечная граница в диапазон.
Не путайте проверку условия до и после тела цикла; не считайте начальное состояние итерацией; не используйте старое значение переменной после присваивания; не выполняйте обе ветви условного оператора; не забывайте, что печать внутри цикла происходит несколько раз.
5. Разобранный пример
Рассмотрим программу. Нужно определить напечатанное значение переменной \(s\).
1s = 0 2x = 2 3while x <= 8: 4 if x % 4 == 0: 5 s = s + x 6 else: 7 s = s + 1 8 x = x + 2 9print(s)
Сначала выпишем начальные значения \(s=0\) и \(x=2\). Затем для каждой итерации проверим \(x\le 8\), выберем ветвь по условию \(x\bmod 4=0\), изменим \(s\) и увеличим \(x\) на 2.
| Итерация | x до тела | Выбранная ветвь | s после тела | x после тела |
|---|---|---|---|---|
| 1 | 2 | иначе: +1 | 1 | 4 |
| 2 | 4 | если: +x | 5 | 6 |
| 3 | 6 | иначе: +1 | 6 | 8 |
| 4 | 8 | если: +x | 14 | 10 |
Ответ — \(14\). Обратите внимание: значение \(x=10\) не является новой итерацией, потому что при нём условие цикла уже ложно. Оно лишь фиксирует состояние после последнего увеличения.
6. Универсальный алгоритм решения заданий
Если код содержит функции или процедуры, отдельно отслеживайте параметры при вызове функции и возвращаемое значение. Для вызова процедуры проверяйте, какие переменные изменяются внутри неё. Сначала разберите внутренний вызов, затем продолжите выполнение с команды после вызова.
- Прочитайте вопрос и определите, что именно требуется найти.
- Отметьте исходные данные и типы переменных.
- Нарисуйте или заполните таблицу трассировки.
- Двигайтесь строго сверху вниз, переходя по ветвям и циклам.
- После каждой итерации сверяйте условие остановки.
- Проверьте арифметику независимо вторым способом.
- Сформулируйте ответ в требуемом формате: число, строка, последовательность или логическое значение.
Помечайте стрелками переходы к началу цикла и к каждой ветви. Если переменных много, записывайте только те, которые участвуют в условии, изменяются или выводятся. Это уменьшает объём таблицы и помогает не потерять порядок команд.
Быстрая проверка
Главное
- Анализируйте программу последовательно: команда за командой, с фиксацией новых значений переменных.
- В ветвлении сначала вычисляется условие, затем выполняется только выбранная ветвь.
- Для цикла отдельно проверяйте условие и фиксируйте состояние после каждой итерации.
- Таблица трассировки помогает не перепутать старые и новые значения.
- При окончательном ответе проверьте арифметику, число итераций и момент завершения программы.