"Информатика. (в 2 частях)", Поляков К.Ю., Еремин Е.А.
Разветвляющийся алгоритм выбирает дальнейшие действия по результату проверки условия. Он нужен, когда для разных исходных данных требуется выполнить разные команды: например, вывести сообщение о знаке числа или найти большее значение. Условие принимает одно из двух значений — истина или ложь. В полном ветвлении заданы действия для обоих случаев, а в неполном — только для истинного. При выполнении выбирается один путь.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Разветвляющийся алгоритм — алгоритм, в котором дальнейшие действия выбираются в зависимости от результата проверки условия. Он нужен, когда одинаковые команды не подходят для всех возможных исходных данных. Например, алгоритм может по-разному сообщить о положительном и отрицательном числе.
Условие — утверждение или вопрос, имеющий значение «истина» или «ложь». Например, «x больше нуля?» — условие: для конкретного значения x ответ либо да, либо нет. Такая проверка позволяет алгоритму принять решение и перейти к подходящим командам.
Полное ветвление — конструкция, в которой предусмотрены действия и при истинном, и при ложном значении условия. Если условие истинно, выполняется первая ветвь, а если ложно — вторая. Она нужна, когда в обоих случаях алгоритм должен что-то сделать, например вывести одно из двух чисел.
Неполное ветвление — конструкция, в которой действия выполняются только при истинном значении условия, а при ложном алгоритм продолжается дальше. К примеру, сообщение можно вывести только тогда, когда число положительное. Такой вид удобен, если для ложного результата специальное действие не требуется.
Необходимость выбора возникает потому, что исходные данные могут быть разными, а нужный результат зависит от них. Если алгоритм всегда выполняет один и тот же набор команд, он не сможет, например, отдельно обработать положительное и отрицательное число. Проверка условия помогает выбрать подходящую последовательность действий. Поэтому разветвление делает алгоритм применимым к разным ситуациям.
Условие проверяют по текущим значениям данных: например, сравнивают x с нулём и выясняют, верно ли неравенство x > 0. Такая проверка должна давать ясный ответ, потому что алгоритму нужно решить, по какой ветви идти. Ответ обозначают словами «истина» и «ложь», а не неопределёнными оценками вроде «почти верно». Если проверку нельзя однозначно разрешить, по её результату невозможно выбрать путь.
В полном ветвлении сначала проверяют условие, затем выбирают одну из двух ветвей. При истине выполняются команды первой ветви, при лжи — второй; одновременно обе ветви не выполняются. После их завершения пути соединяются, и дальнейшие общие команды выполняются независимо от того, какая ветвь была выбрана. Такое объединение позволяет не повторять один и тот же дальнейший алгоритм.
В неполном ветвлении действия заданы только для истинного условия. Если проверка дала ложь, команды этой ветви пропускаются, и выполнение переходит к продолжению алгоритма. Это отличается от полного ветвления: там для ложного результата предусмотрена отдельная ветвь с командами. Неполную конструкцию выбирают, когда при невыполненном условии ничего специально делать не нужно.
На блок-схеме условие помещают в блок проверки, от которого идут стрелки с исходами «да» и «нет» или «истина» и «ложь». В полном ветвлении каждый исход ведёт к своей последовательности команд, а затем пути объединяются. В неполном одна стрелка ведёт к командам, другая обходит их и сразу продолжает алгоритм. Чтобы определить порядок действий, проследите стрелку, соответствующую результату проверки, и двигайтесь по ней до общего продолжения.
| Свойство | Полное ветвление | Неполное ветвление |
|---|---|---|
| Количество возможных ветвей | Две | Одна явно заданная ветвь |
| Действия при истинном условии | Выполняются | Выполняются |
| Действия при ложном условии | Выполняются команды второй ветви | Ветвь пропускается |
| Когда применяется | Когда нужны разные действия в обоих случаях | Когда действие требуется только при выполнении условия |
| Изображение на блок-схеме | Условие с двумя исходящими стрелками | Условие с одной исполняемой ветвью и продолжением алгоритма |
Чтобы выбрать вид ветвления, спросите себя, нужны ли специальные команды для обоих результатов условия. Если нужны — подходит полное, если действие требуется только при истине — неполное. В блок-схеме учитывайте, что при одном запуске выполняется только один из путей.
Нужно вывести сообщение «Положительное», если заданное число положительно. Для этого достаточно проверить условие x > 0: оно истинно для положительных чисел и ложно для нуля или отрицательного числа. При ложном результате отдельное сообщение по условию задачи не требуется, поэтому выбираем неполное ветвление.
Ответ: проверить x > 0 и при истинном результате вывести «Положительное».
Даны два числа, нужно определить большее и вывести его. Сравним первое число со вторым, обозначив их a и b. Здесь нужен результат и для истинного, и для ложного условия, поэтому используем полное ветвление; случай равенства также нельзя оставить без внимания.
Ответ: сравнить a и b; вывести большее, а при равенстве — любое из равных чисел.
Пусть даны числа a, b и c, и требуется вывести наибольшее. Можно последовательно сравнивать числа, сохраняя найденный на данный момент максимум. Этот способ удобен тем, что не нужно отдельно придумывать ветвь для каждой комбинации значений, но равенство тоже должно обрабатываться корректно.
Ответ: последовательно сравнить b и c с текущим максимумом, затем вывести сохранённое наибольшее число.
Первая ошибка — проверять действие или выражение, которое не даёт однозначного ответа «истина» либо «ложь». Так бывает, если записать вычисление вместо вопроса, который можно разрешить сравнением. Чтобы проверить себя, сформулируйте результат проверки словами «да» или «нет» для любого допустимого набора данных. Если ответ неясен, условие нужно уточнить.
Вторая ошибка — перепутать полное и неполное ветвление: не описать действия при ложном условии там, где они нужны, или добавить лишнюю ветвь. Часто это происходит, когда заранее не продумывают оба возможных результата проверки. Проверьте задачу вопросом: «Что должен сделать алгоритм, если условие ложно?» Если ответ требует команды, предусмотрите её.
Третья ошибка — после выполнения одной ветви продолжить команды другой. Это случается, если воспринимать ветви как команды, которые нужно выполнить по очереди, а не как альтернативные пути. Проследите выполнение от блока условия: при одном запуске истинным или ложным окажется только один исход. Убедитесь, что команды второго пути не выполняются следом за первым.
Четвёртая ошибка — забыть про равные значения при сравнении чисел. Например, проверка только a > b и b > a не срабатывает, когда a = b, и алгоритм может не вывести результат. Подставьте в условие одинаковые числа и проследите все проверки. Если ни одна ветвь не обрабатывает равенство, добавьте его в подходящий случай.
Чтобы строить ветвления, полезно уметь составлять линейные алгоритмы, понимать команды исполнителя и читать блок-схемы. Операции сравнения помогают записывать условия, например x > 0 или a = b. Составные логические выражения позволяют выбирать ветвь сразу по нескольким признакам, например проверять два ограничения одновременно. Позже ветвления пригодятся в программировании, циклах с условиями и алгоритмах обработки числовых и текстовых данных.
Чем разветвляющийся алгоритм отличается от линейного?
В линейном алгоритме команды выполняются одна за другой в заранее заданном порядке. В разветвляющемся сначала проверяется условие, а затем выбираются команды в зависимости от результата.
Почему условие должно иметь только два результата?
Проверка условия должна однозначно показать, выполняется оно или нет. Поэтому её результат трактуют как «истина» или «ложь», и алгоритм может выбрать подходящий путь.
Когда использовать полное, а когда неполное ветвление?
Полное ветвление нужно, когда разные команды требуются и при истинном, и при ложном условии. Неполное используют, если действие необходимо только при истинном результате, а иначе алгоритм может просто продолжиться.
Можно ли записать несколько условий внутри одного ветвления?
Да, условия можно объединять с помощью логических операций, например требовать одновременного выполнения двух проверок. Такое составное условие всё равно должно иметь один итог: истина или ложь.
Как проверить, что в блок-схеме ветви соединены правильно?
От блока условия должны идти пути для истинного и ложного результатов. Проследите каждый путь: выполняется только его набор команд, а затем ветви соединяются перед продолжением общего алгоритма.
§ 38. Разветвляющиеся алгоритмы
