Алгоритмы с разветвлением
Пример алгоритма с разветвлением
В предыдущей главе мы подробно рассмотрели программирование линейных алгоритмов, в которых операции выполняются в том порядке, как они записаны в программе. В реальной жизни таких задач до обидного мало, в чем все мы убедились еще в средней школе: первое такое разочарование у многих было связано с решением квадратных уравнений.
Задание 5.1:
1) Постановка задачи:
a, b, c – действительные числа. Требуется найти действительные корни квадратного уравнения[1]
.
В подробном анализе задания и выборе метода решения, надо полагать, особой необходимости нет, задача знакома всем[2]. Тем более, что в главе 1 мы уже ее упоминали.
Выбор метода решения и проектирование
Описание алгоритма:
Шаг 1. Если вы уверены, что начинать надо с вычисления дискриминанта, то вам необходимо вернуться к четвертой лекции – вы не усвоили материал. В самом деле, попробуйте вычислить конкретное значение дискриминанта, не зная конкретных значений коэффициентов a, b и c! Пока вам не скажут, что a=1, b=3, c=–4 вы никогда не сможете вычислить, что d=25. Поэтому:
Шаг 1: определить конкретные значения a, b и c, и только затем:
Шаг 2: вычисление дискриминанта по формуле, набившей оскомину:
.
Пока что все операции алгоритма выполняются линейно – одна за другой.
Шаг 3: На третьем шаге возникают некоторые сложности: выбор дальнейших действий зависит от значения d. Возможны варианты:
1) d<0 – вариант, безусловно, самый приятный и, поэтому, в школе почти не встречавшийся. Считать ничего не надо. Действительных корней нет.
2) d=0 – похуже, чем первый, т.к. считать все-таки придется, хотя и не так уж много: корень всего один
.
3) остается самый неприятный вариант, d>0 и считать придется целых два корня[3]:
Шаг 4: печать результатов. Тоже зависит от того, что мы делали на предыдущих шагах. Возможны варианты:
1) Сообщение «Действительных корней нет» – отсутствие численного результата в программировании тоже результат, о котором, безусловно, надо сообщить.
2) Печать значения x, если корень был единственным.
3) В оставшихся случаях: печать значений x1 и x2.
Из приведенного словесного описания алгоритма видно, что на третьем шаге возникает необходимость в управляющей конструкции, позволяющей выбрать нужный вариант в зависимости от выполнения какого-либо условия. В большинстве современных языков программирования такая конструкция реализована и является базовой схемой управления ходом программы (см. п. 13.4). В Pascal’е с этой целью используются условный оператор и оператор выбора.
Описанный алгоритм представлен на рисунке 5.1 в виде блочной схемы.
Условный оператор
Работает эта управляющая конструкция следующим образом: если 
истинно (
=True), то управление передается на 
, если же 
не выполнилось ( =False), то начинает работать 
. После того, как один из этих двух операторов отработал (или отсутствует), программа продолжает выполняться линейно: начинает работать та ее часть, которая находится непосредственно за условным оператором. Примеры синтаксически допустимого использования условного оператора приводятся ниже.
| № п.п. | Фрагмент программы | Комментарии |
| 1. | X:=0; if X>0 then; | Синтаксически верная конструкция оператора if, тем не менее, не приводящая ни к каким внешне проявляющимся активным действиям. |
| 2. | X:=0; if X>0 then else; | Синтаксически верная конструкция оператора if, тем не менее, не приводящая ни к каким внешне проявляющимся активным действиям. |
| 3. | X:=5; if X>0 then X:=-10; WriteLn(’Результат X=’,X); | Т.к. логическое выражение X>0 истинно[4], управление будет передано оператору X:=-10 и переменная X поменяет свое значение. На экран будет выведено сообщение Результат X=-10 |
| 4. | X:=-15; if X>0 then X:=-10; WriteLn(’Результат X=’,X); | Т.к. логическое выражение X>0 ложно[5], управление будет передано оператору печати, следующему непосредственно за условным оператором и на экран будет выведено сообщение Результат X=-15 |
| 5. | X:=5; if X<=0 then else X:=-10; WriteLn(’Результат X=’,X); | Синтаксически верная конструкция, но, тем не менее, грамотной ее не назовешь. По конечному результату она полностью эквивалентна конструкции, приведенной в примере 3. |
| 6. | X:=5; if X<=0 then X:=1 else X:=-10; WriteLn (’Результат X=’, X); | Т.к. логическое выражение X<=0 ложно, то оператор X:=1 будет пропущен, выполнится оператор присваивания X:=-10, на печать поступит сообщение Результат X=-10 |
| 7. | X:=-15; if X<=0 then X:=1 else X:=-10; WriteLn(’Результат X=’, X); | Т.к. логическое выражение X<=0 истинно, то выполнится оператор X:=1, оператор присваивания X:=-10будет пропущен и на печать поступит сообщение Результат X=1 |
Составной оператор
В примерах, разобранных выше, в случае истинности (ложности) логического выражения управление передавалось оператору, который определял какую-то одну более или менее простую инструкцию: X:=1, или X:=-10, илиX:=Sqr(A)+Sqrt(B), илиWriteLn(A,B)и т.д. Часто возникает необходимость передать управление на целую серию инструкций. Вернемся к задаче нахождения корней квадратного уравнения. На рисунке 5.1 пунктиром отмечены действия, которые необходимо выполнять при выполнении тех или иных условий. Так, если дискриминант отрицательный, то необходимо только напечатать соответствующее сообщение «Действительных корней нет». Если же он положителен, то этих действий уже три:
1) вычислить значение x1;
2) вычислить значение x2;
3) напечатать получившиеся результаты x1, x2.
Несколько элементарных действий можно объединять в блок. Для этого вводится понятие составного оператора:
Составной оператор может включать в себя несколько более простых операторов (в том числе составных). Рассмотрим несколько примеров с использованием составных операторов.
| Фрагмент программы | Комментарии |
| X:=5; if X>0 then begin A:=’круть’; B:=’верть’; end else begin A:=’верть’; B:=’круть’; end; WriteLn(A,’–’,B); | Т.к. логическое выражение X>0 истинно, управление передается составному оператору begin A:=’круть’; B:=’верть’; end. В результате работы приведенного фрагмента программы на экран поступит сообщение круть–верть |
| X:=–5; if X>0 then begin A:=’круть’; B:=’верть’; end else begin A:=’верть’; B:=’круть’; end; WriteLn(A,’–’,B); | Т.к. логическое выражение X>0 ложно, управление передается составному оператору begin A:=’верть’; B:=’круть’; end; В результате работы приведенного фрагмента программы на экран поступит сообщение верть–круть |
Используя понятие составного оператора не трудно программно реализовать алгоритм нахождения действительных корней квадратного уравнения, представленный блочной схемой на рисунке 5.1[6].
Текст программы
program Quadratic;
var
A,B,C,D,X,X1,X2: Real;
Begin
Write(’Введите коэффициенты квадратного уравнения:’);
ReadLn(A,B,C);
D:=Sqr(B)-4*A*C;
if D< 0 then
WriteLn(’Действительных корней нет’)
else
if D=0 then
Begin
X:=-B/(2*A);
WriteLn(’X=’, X:5:1);
End
Else
Begin
X1:=(-B-Sqrt(D))/(2*A);
X2:=(-B+Sqrt(D))/(2*A);
WriteLn(’X1=’,X1:5:1,’ X2=’, X2:5:1);
end;
ReadLn;
end.
В Протоколах 5.1, 5.2, 5.3 продемонстрированы различные варианты работы программы. Проанализировав их, вы легко можете убедиться, что в отличие от линейных алгоритмов, ход выполнения программы с разветвлением может зависеть от исходных данных.
Протокол 5.1
Работа программы Quadratic при решении квадратного уравнения 2x2–8x+6=0
1) Печать сообщения
Введите коэффициенты квадратного уравнения:
2) Программа останавливается и ожидает, когда пользователь наберет строку ввода:
2 –8 6¿
В результате A=2,B=–8,C=6.
3) Вычисление дискриминанта D:=Sqr(B)-4*A*C=(–8)2–4×2×6=16.
4) (D<0)=(16<0)=False
5) (D=0)=(16=0)=False
6) X1:=(-B-Sqrt(D))/(2*A)=1
7) X2:=(-B+Sqrt(D))/(2*A)=3
8) Печать сообщения «X1= 1.0 X2= 3.0».
9) Конец работы программы.
Протокол 5.2
Работа программы Quadratic при решении квадратного уравнения 2x2–8x+16=0
1) Печать сообщения
Введите коэффициенты квадратного уравнения:
2) Программа останавливается и ожидает, когда пользователь наберет строку ввода:
2 –8 16¿
В результате A=2,B=–8,C=16.
3) Вычисление дискриминанта D:=Sqr(B)-4*A*C=(–8)2–4×2×16=–64.
4) (D<0)=(64<0)=True
5) Печать сообщения «Действительных корней нет».
6) Конец работы программы.
Протокол 5.3
Работа программы Quadratic при решении квадратного уравнения 2x2–8x+8=0
1) Печать сообщения
Введите коэффициенты квадратного уравнения:.
2) Программа останавливается и ожидает, когда пользователь наберет строку ввода:
2 –8 8¿
В результате A=2, B=–8, C=8.
3) Вычисление дискриминанта D:=Sqr(B)-4*A*C=(–8)2–4×2×8=0.
4) (D<0)=(0<0)=False
5) (D=0)=(16=0)=True
6) X:=-B/(2*A)=8/(2*2)=2
7) Печать сообщения «X= 2.0».
8) Конец работы программы.
Задание 5.2:
1) Постановка задачи:
Заданы трицелых числаa, b, c. Требуется вывести их на экран дисплея в порядке возрастания.
Выбор метода решения и проектирование
Нетрудно убедиться, что возможны всего шесть вариантов вывода чисел на экран, как это показано в таблице. Программа ничего не должна вычислять, от нее требуется только выбрать подходящий вариант распечатки.
Решать эту задачу мы будем, сравнивая различные пары чисел. В принципе, задача легко программируется с использованием логических операций, но о них речь пойдет несколько позднее.
Алгоритм решения представлен блочной схемой на рисунке 5.2.
Текст программы
program Sorting;
Var
A,B,C: Integer;
Begin
Write(‘Введите три целых числа: ‘);
ReadLn(A,B,C);
if A<=B then
if B<=C 
then
WriteLn(A:3,B:3,C:3) {вариант 1}
Else
if A<=C then
WriteLn(A:3,C:3,B:3) {вариант 2}
Else
WriteLn(C:3,A:3,B:3) {вариант 5}
Else
if C<=B then
WriteLn(C:3,B:3,A:3) {вариант 6}
Else
if C<=A then
WriteLn(B:3,C:3,A:3) {вариант 4}
Else
WriteLn(B:3,A:3,C:3); {вариант 3}
ReadLn;
end.