какое определение можно использовать для разветвляющегося алгоритма
Какое определение можно использовать для разветвляющегося алгоритма
Во многих случаях требуется, чтобы при одних условиях выполнялась одна последовательность действий, а при других – другая.
Если пошел дождь, то надо открыть зонт.
Если прозвенел будильник, то надо вставать.
Если встречу Сашу, то скажу ему …
Если встречу Сашу, то скажу ему …, иначе зайду к нему сам.
Вычислительный процесс называется ветвящимся, если для его реализации предусмотрено несколько направлений (ветвей). Каждое отдельное направление процесса обработки данных является отдельной ветвью вычислений. Ветвление в программе — это выбор одной из нескольких последовательностей команд при выполнении программы. Выбор направления зависит от заранее определенного признака, который может относиться к исходным данным, к промежуточным или конечным результатам. Признак характеризует свойство данных и имеет два или более значений.
Ветвящийся процесс, включающий в себя две ветви, называется простым, более двух ветвей — сложным. Сложный ветвящийся процесс можно представить с помощью простых ветвящихся процессов.
Направление ветвления выбирается логической проверкой, в результате которой возможны два ответа: «да» — условие выполнено и «нет» — условие не выполнено.
Разветвляющиеся алгоритмы
До сих пор Вы использовали линейные алгоритмы, т.е. алгоритмы, в которых все этапы решения задачи выполняются строго последовательно. Сегодня Вы познакомитесь с разветвляющимися алгоритмами.
Определение. Разветвляющимся называется такой алгоритм, в котором выбирается один из нескольких возможных вариантов вычислительного процесса. Каждый подобный путь называется ветвью алгоритма.
Признаком разветвляющегося алгоритма является наличие операций проверки условия. Различают два вида условий – простые и составные.
Простым условием (отношением) называется выражение, составленное из двух арифметических выражений или двух текстовых величин (иначе их еще называют операндами), связанных одним из знаков:
Например, простыми отношениями являются следующие:
x-y>10; k 11; ‘мама’<>‘папа’.
В приведенных примерах первые два отношения включают в себя переменные, поэтому о верности этих отношений можно судить только при подстановке некоторых значений:
если х=25, у=3, то отношение x-y>10 будет верным, т.к. 25-3>10
если х=5, у=30, то отношение x-y>10 будет неверным, т.к. 5-30 t
Задача. Вычислить значение модуля и квадратного корня из выражения (х-у).
В этом случае программа будет иметь вид:
write (‘Введите значения переменных х и у через пробел ‘);
write (‘Значение квадратного корня из выражения (х-у) равно ‘);
write (‘Значение модуля выражения (х-у) равно ‘);
Казалось бы задача решена. Но мы не учли области допустимых значений для нахождения квадратного корня и модуля. Из курса математики Вы должны знать, что можно найти модуль любого числа, а вот значение подкоренного выражения должно быть неотрицательно (больше или равно нулю).
Поэтому наша программа имеет свою допустимую область исходных данных. Найдем эту область. Для этого запишем неравенство х-у>=0 и решив его получим х>=у. Значит, если пользователем нашей программы будут введены такие числа, что при подстановке значение этого неравенства будет равно True, то квадратный корень из выражения (х-у) извлечь можно. А если значение неравенства будет равно False, то выполнение программы закончится аварийно.
Задание. Наберите текст программы. Протестируйте программу со следующими значениями переменных и сделайте вывод.
а) х=23, у=5; б) х=-5, у=15; в) х=8, у=8.
Каждая программа, насколько это возможно, должна осуществлять контроль за допустимостью величин, участвующих в вычислениях. Здесь мы сталкиваемся с разветвлением нашего алгоритма в зависимости от условия. Для реализации таких условных переходов в языке Паскаль используют операторы If и Else, а также оператор безусловного перехода Goto.
Рассмотрим оператор If.
Для нашей задачи нужно выполить следующий алгоритм:
то вычислить значение квадратного корня,
иначе выдать на экран сообщение об ошибочном введении данных.
Запишем его с помощью оператора If. Это будет выглядеть так.
if x>=y
Then
Else
write (‘Введены недопустимые значения переменных‘);
Теперь в зависимости от введенных значений переменных х и у, условия могут выполняться или не выполняться.
В общем случае полная форма конструкции условного оператора имеет вид:
Then
Else
Условный оператор работает по следующему алгоритму.
Управляющая структура if может показаться негибкой, так как выполняемые действия могут быть описаны только одним оператором. Иногда может потребоваться выполнение последовательности операторов. В этом случае хотелось бы заключить всю последовательность в воображаемые скобки. В Паскале предусмотрен этот случай.
Then
Begin
Else
Begin
Определение. Составной оператор —объединение нескольких операторов в одну группу. Группа операторов внутри составного оператора заключается в операторные скобки (begin-end).
С учетом полученных знаний преобразуем нашу программу.
Program Znachenia;
Uses
Begin
write (‘Введите значения переменных х и у через пробел ‘);
if x>=y
Then
Begin
write (‘Значение квадратного корня из выражения (х-у) равно ‘);
write (‘Значение модуля выражения (х-у) равно ‘);
Else
write (‘Введены недопустимые значения переменных‘);
Составным оператором является и такой оператор
Cимвол “;” в данном случае разделяет оператор присваивания S:=0 и пустой оператор.
Пустой оператор не влечет никаких действий и в записи программы никак не обозначается.
Например, составной оператор
включает лишь один пустой оператор.
Если Вы обратили внимание, программа на языке Паскаль всегда содержит один составной оператор – раздел операторов программы.
Внимание! Перед служебным словом Else разделитель (точка с запятой) не ставится.
Отметим, что большинство операторов в программах на языке Паскаль заканчиваются точкой с запятой, но после некоторых операторов точка с запятой не ставится. Сформулируем общие правила употребления точки с запятой:
1. Каждое описание переменной и определение константы заканчиваются точкой с запятой.
2. Каждый оператор в теле программы завершается точкой с запятой, если сразу за ним не следуют зарезервированные слова End, Else, Until.
3. После определенных зарезервированных слов, таких, как Then, Else, Var, Const, Begin, никогда не ставится точка с запятой.
Рассмотрим еще один пример.
Задача. Вывести на экран большее из двух данных чисел.
Program Example1;
Begin
writeln(‘Введите 2 числа ‘);
if x>y
Then
Else
Можно также использовать и сокращенную (неполную) форму записи условного оператора. Эта форма используется тогда, когда в случае невыполнения условия ничего делать не надо.
Неполная форма условного оператора имеет следующий вид.
Then
Тогда если выражение, расположенное за служебным словом IF. в результате дает истину, выполняются действия после слова THEN, в противном случае эти действия пропускаются.
Задача. Составить программу, которая, если введенное число отрицательное меняет его на противоположное.
Условный оператор
Теоретический материал (Паскаль)
Разветвляющиеся алгоритмы. Оператор If
До сих пор Вы использовали линейные алгоритмы, т.е. алгоритмы, в которых все этапы решения задачи выполняются строго последовательно. Сегодня Вы познакомитесь с разветвляющимися алгоритмами.
Определение. Разветвляющимся называется такой алгоритм, в котором выбирается один из нескольких возможных вариантов вычислительного процесса. Каждый подобный путь называется ветвью алгоритма.
Простым условием (отношением) называется выражение, составленное из двух арифметических выражений или двух текстовых величин (иначе их еще называют операндами), связанных одним из знаков:
Например, простыми отношениями являются следующие:
x-y>10; k 11; ‘мама’<>‘папа’.
В приведенных примерах первые два отношения включают в себя переменные, поэтому об истинности этих отношений можно судить только при подстановке конкретных значений:
Задача. Вычислить значение модуля и квадратного корня из выражения (х-у).
| Koren:=Sqrt(x-y); Modul:=Abs(x-y) |
В этом случае программа будет иметь вид:
| Program Znachenia; Uses Crt; Var x, y : integer; Koren, Modul : real; Begin ClrScr; write (‘Введите значения переменных х и у через пробел ‘); readln (x, y); Koren:=Sqrt(x-y); Modul:=Abs(x-y); write (‘Значение квадратного корня из выражения (х-у) равно ‘, Koren); write (‘Значение модуля выражения (х-у) равно ‘, Modul); readln; End. |
Казалось бы, задача решена. Но мы не учли области допустимых значений для нахождения квадратного корня и модуля. Из курса математики Вы должны знать, что можно найти модуль любого числа, а вот значение подкоренного выражения должно быть неотрицательно (больше или равно нулю).
Поэтому наша программа имеет свою допустимую область исходных данных. Найдем эту область. Для этого запишем неравенство х-у>=0, то есть х>=у. Значит, если пользователем нашей программы будут введены такие числа, что при подстановке значение этого неравенства будет равно True, то квадратный корень из выражения (х-у) извлечь можно. А если значение неравенства будет равно False, то выполнение программы закончится аварийно.
Задание. Наберите текст программы. Протестируйте программу со следующими значениями переменных и сделайте вывод.
Каждая программа, насколько это возможно, должна осуществлять контроль за допустимостью величин, участвующих в вычислениях. Здесь мы сталкиваемся с разветвлением нашего алгоритма в зависимости от условия. Для реализации таких условных переходов в языке Паскаль используют операторы If и Case, а также оператор безусловного перехода Goto.
Рассмотрим оператор If.
Для нашей задачи нужно выполнить следующий алгоритм:
если х>=у,
то вычислить значение квадратного корня,
иначе выдать на экран сообщение об ошибочном введении данных.
Запишем его с помощью оператора If. Это будет выглядеть так.
| if x>=y then Koren:=Sqr(x-y) else write (‘Введены недопустимые значения переменных’); |
Теперь в зависимости от введенных значений переменных х и у, вычисление квадратного корня может выполняться или не выполняться.
В общем случае полная форма конструкции условного оператора имеет вид:
Условный оператор работает по следующему алгоритму.
Управляющая структура if может показаться негибкой, так как выполняемые действия могут быть описаны только одним оператором. Иногда может потребоваться выполнение последовательности операторов. В этом случае хотелось бы заключить всю последовательность в воображаемые скобки. В Паскале предусмотрен этот случай.
| if then begin оператор 1; оператор 2; . end else begin оператор 1; оператор 2; . end; |
| begin оператор 1; оператор 2; end; |
С учетом полученных знаний преобразуем нашу программу.
| Program Znachenia; Uses Crt; Var x, y : integer; Koren, Modul : real; Begin ClrScr; write (‘Введите значения переменных х и у через пробел ‘); read (x, y); if x>=y then begin Koren:=Sqr(x-y); Modul:=Abs(x-y); write (‘Значение квадратного корня из выражения (х-у) равно ‘, Koren); write (‘Значение модуля выражения (х-у) равно ‘, Modul); end else write (‘Введены недопустимые значения переменных’); readln; End. |
Составным оператором является и такой оператор
Cимвол “;” в данном случае разделяет оператор присваивания S:=0 и пустой оператор.
Пустой оператор не влечет никаких действий и в записи программы никак не обозначается.
Например, составной оператор
включает лишь один пустой оператор.
Внимание! Перед служебным словом Else разделитель (точка с запятой) не ставится.
Отметим, что большинство операторов в программах на языке Паскаль заканчиваются точкой с запятой, но после некоторых операторов точка с запятой не ставится. Сформулируем общие правила употребления точки с запятой:
Рассмотрим еще один пример.
Задача. Вывести на экран большее из двух данных чисел.
| Program Example1; Var x, y : integer; <вводимые числа> Begin writeln(‘Введите 2 числа ‘); <вводим два целых числа через пробел> readln(x,y); if x>y then writeln (x) <если х больше y, то выводим х> else writeln (y); <иначе выводим y> readln; End. |
Можно также использовать и сокращенную (неполную) форму записи условного оператора. Эта форма используется тогда, когда в случае невыполнения условия ничего делать не надо.
Неполная форма условного оператора имеет следующий вид.
Тогда если выражение, расположенное за служебным словом IF. в результате дает истину, выполняются действия после слова THEN, в противном случае эти действия пропускаются.
Задача. Составить программу, которая, если введенное число отрицательное, меняет его на противоположное.
Алгоритм ветвления. Отличие от алгоритмов линейной структуры
Статья рассказывает про алгоритмы с разветвлённой структурой. Читатель узнает, чем их решение отличается от решения линейных алгоритмов, как выглядит программный способ записи таких алгоритмов, а также какова будет блок-схема.
В предыдущей статье шла речь об алгоритмах, их особенностях и свойствах. Особое внимание было уделено линейной структуре как самому простому способу реализации. Сегодня поговорим о более сложных алгоритмах, обладающих разветвлённой структурой. Но прежде чем продолжать, следует кое-что вспомнить.
Алгоритм – это ясный перечень действий, который направлен на решение какой-либо задачи. Одно из свойств алгоритма — дискретность. Дискретность связана с наличием в алгоритмической последовательности ряда операций (этапов, действий), выполняемых пошагово, то есть дискретно. Алгоритм обладает свойством дискретности, так как он представляет собой процесс решения задачи в виде последовательного выполнения простых шагов. И каждое действие исполняется лишь после окончания исполнения предыдущего. Также предполагается наличие определённых исходных данных и результата выполнения.
Блок-схема — графический способ описания алгоритмов. Графическое представление обеспечивает наглядность и упрощает запись, делая последовательность более понятной. При использовании схемы каждому действию соответствует определённая геометрическая фигура (эти фигуры называют блоками). Вот наиболее часто употребляемые:
Ещё раз о линейности
Линейная последовательность — самая простая из возможных структур. При наличии линейности команды выполняются в чёткой последовательности и в порядке их записи, то есть друг за другом. Вот линейная алгоритмическая последовательность посадки дерева: 1) выкапывание ямки в земле; 2) размещение в ямке саженца; 3) закапывание ямки; 4) поливание места посадки водой.
Такой линейный алгоритм имеет следующую блок-схему:
А вот и общая схема линейного алгоритма:
Ветвление в алгоритмических последовательностях
На практике очень редко встречается, чтобы последовательность всех требуемых действий была известна заранее. Если на минуту покинуть мир алгоритмизации и программирования, можно спроецировать ветвление на многие жизненные ситуации. Если на улице дождь, человек берёт зонт, если очень жарко, будет выбрана одежда полегче и т. д. Всё зависит от условия выбора. Как тут не вспомнить рыцаря на распутье из русских народных сказок?
Подобная ситуация заставляет принимать решения с учётом определённого условия. Если нужна жена, то витязь идёт направо, если богатство, то налево, если жизнь не мила, то прямо. Условия, которые влияют на решение, располагаются между словами «если» и «то».
От значения условий зависит дальнейшее поведение. Когда условие выполняется, оно принимает значение «истина», когда нет — «ложь». Иногда анализ ситуации и выбор не вызывают особых затруднений, а иногда принять решение очень трудно. А всё потому, что принимающий решение пытается продумать каждый из вариантов и предугадать последствия выбора. Нельзя не вспомнить гроссмейстера, который анализирует позицию на ходы вперёд, прежде чем передвинуть фигуру на шахматной доске.
Компьютерные программы и игры тоже построены на выборе действий. А блок-схема при наличии ветвления приобретает иной вид:
Логика разветвляющих алгоритмов
Логику можно описать следующим образом:
Ветвление — метод и форма организации действий, когда в зависимости от выполнения определённого условия совершается та либо иная последовательность шагов.
В результате совсем несложно составить алгоритм покупки мороженого с учётом наличия необходимой суммы денег. Описать эту алгоритмическую последовательность с помощью схемы и блоков тоже не составит труда:
Для закрепления можно решить задачу.
Есть 3 монеты одинакового достоинства. Одна из монет фальшивая (известно, что она имеет меньший вес). Найдите фальшивую монету на чашечных весах без гирь с помощью только одного взвешивания.
Решение легко описывается посредством схематических блоков:
Следующий пример легко экстраполируется в жизнь. Речь идёт об алгоритме для перехода дороги при наличии светофора. Он имеет следующий вид: 1. Подходим к светофору. 2. Смотрим, какой горит свет. 3. Если зелёный, переходим дорогу. 4. Если красный, ждём, пока загорится зелёный, а потом переходим дорогу.
Программный способ записи
Чтобы алгоритм было понятен компьютеру, машине и любой другой цифровой системе, следует оформить его в таком виде, который эта система способна воспринимать. То есть надо написать программу, используя для этого команды из СКИ. СКИ — это список команд исполнителя — перечень команд, ему понятных. А любой исполнитель способен исполнить лишь те команды, которые включены в его СКИ, а если говорить человеческим языком — входят в набор его компетенций.
Для примера можно реализовать алгоритм на языке программирования Pascal. Исходя из вышесказанного, следует использовать команды, входящие в терминологию Pascal.
Простейший пример описания алгоритма с разветвляющейся структурой — условный оператор IF. Полная конструкция этого условного оператора имеет следующий вид:
Здесь if — это «если», then — это «то», else — «иначе».
Условный оператор работает просто: — вычисляется значение логического выражения, которое расположено после служебного слова IF; — если результат — истина, выполняется оператор 1, который размещён после THEN, причём действие после ELSE пропускается; — если результат — ложь, пропускается уже действие после THEN, а действие после ELSE выполняется с помощью оператора 2.
Теперь можно вспомнить пресловутого витязя на распутье и написать простую программу, реализующую этот алгоритм с помощью соответствующих условных операторов.
Попробовать этот алгоритм в работе можно на любом онлайн-компиляторе, поддерживающим Pascal. Но не стоит на этом останавливаться — лучше всего написать собственную программу, что позволит получить максимальную пользу от урока.
Разветвляющиеся алгоритмические структуры
Вы будете перенаправлены на Автор24
Разветвляющиеся алгоритмические структуры — это алгоритмические структуры, обладающие несколькими вариантами дальнейших действий, которые определяются согласно выполнению определённых условий.
Введение
Алгоритм разветвляющейся структуры — это такой алгоритм, в котором присутствует процедура выбора одного из вариантов возможных действий при наличии некоторой совокупности допустимых вариантов вычислительного процесса. Все эти допустимые варианты присутствуют в алгоритме в виде отдельных его ветвей. Отличительной чертой алгоритма с наличием ветвлений является использование специальных команд условных переходов, в которых осуществляется проверка истинности определённых логических условий, а по итогам их проверки, то есть является условие истинным или ложным, реализуется исполнение одной из ветвей алгоритма.
Разветвляющиеся алгоритмические структуры
Для реализации разветвляющихся алгоритмических структур в языках программирования предусмотрены следующие типы операторов:
Например, в языке программирования Паскаль оператор безусловного перехода определяется следующим образом:
GOTO определяется как зарезервированное слово, осуществляющее переход на метку. В Турбо Паскале метка — это идентификатор, имеющий произвольный вид, позволяющий выполнить присвоение имени определённому программному оператору и далее осуществлять обращение к нему при помощи ссылок. В качестве меток можно использовать также целочисленные величины без знака. Метку следует располагать непосредственно перед оператором, подлежащим отметке, и необходимо её отделять от оператора знаком двоеточие (:).
Перед использованием метки в программе, она должна быть описана. Описание метки может быть выполнено при посредстве зарезервированного слова LABEL, означающего «метка», после которого следует перечислить все метки. К примеру:
Готовые работы на аналогичную тему
Предназначением оператора GOTO является передача управления к необходимому оператору. При использовании меток, необходимо соблюдать следующие правила:
При помощи условных операторов можно выполнить проверку некоторого условия и по её результатам назначить дальнейшие операции. Структура условного оператора имеет следующий вид:
Где IF, THEN, ELSE выступают как зарезервированные слова, которые в переводе означают «если», «то», «иначе».
Совокупность ELSE∠оператор 2>, являющаяся фрагментом условного оператора, применяется не всегда и может быть пропущена.
Структурная организация разветвляющегося алгоритма изображена на рисунке ниже:
Рисунок 1. Структурная организация разветвляющегося алгоритма. Автор24 — интернет-биржа студенческих работ
Приведём конкретный пример. Необходимо разработать программу, которая должна определить, которое из двух чисел x или y больше по величине. Это число следует записать в переменную maх:
Условные операторы позволяют осуществить выбор одного из возможных вариантов при выполнении программы. А когда необходимо выполнить множество проверочных операций, которые исключают друг друга, то удобнее применять оператор выбора или оператор варианта. Структурная организация данного оператора может быть представлена в следующем виде:
В качестве селектора необходимо задать скалярное выражение. Изначально, когда начинается исполнение этого оператора, определяется величина селектора. Затем программа приступает к исполнению оператора, у которого одна из меток равна найденному значению селектора. После окончания работы данного оператора, который может имеет как простую, так и составную структуру, программа начинает исполнять оператор, следующий за вариантным оператором.
Если найденное значение селектора не совпадает ни с одной меткой, то исполняется оператор, стоящий за служебным словом ELSE. Следует отметить, эта ветвь ELSE может просто отсутствовать.
Рассмотрим пример программы, использующей оператор варианта. Необходимо заметить, что оператор варианта удобно использовать в случае ввода и вывода величин, используемых скалярных типов информационных данных. Например, в приводимом далее фрагменте программы, следует с внешнего носителя занести порядковый номер объекта из списка значений COLOR. Оператор CPSE задаёт требуемое значение переменной CLR. Аналогичным образом осуществляется вывод величины CLR при помощи оператора варианта:
Составной оператор может быть представлен как набор выполняемых по очереди операторов, которые должны находиться в операторных скобках. Данные операторы могут быть использованы следующим образом:
Составные операторы используются в тех случаях, когда в соответствии с правилами синтаксиса языка Паскаль разрешена запись только одного оператора, а требуется исполнить целый набор операторов. Различные операторы в теле составного оператора следует разделять между собой точкой с запятой. Знак окончания end может не отделяться знаком точка с запятой, поскольку он не считается отдельным оператором.