Реализация разветвляющихся алгоритмов

Для описания даже простых вычислительных процессов оказывается недостаточно лишь одних линейных алгоритмов. Например, алгоритм вы­числения функции, заданной формулой

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

В разветвляющихся алгоритмах принцип линейного автоматического перехода от предписания к предписанию (от оператора к оператору) в порядке их естественной записи не является всеобщим, так как возникает потребность выполнения «произвольного» предписания, определяемого не­которыми условиями.

Итак, разветвляющимися называются алгоритмы, в которых по­следовательность выполнения некоторых предписаний определяется выполнением (или невыполнением) определенных условий.

Для реализации разветвлений в Турбо Паскале используются условные опера­торы и оператор выбора. Кроме них может оказаться необходимым оператор перехода.

Условный оператор

Одна из форм условного оператора имеет вид:

IF <условие> THEN <оператор1> ELSE <оператор 2>

Здесь IF (ecлu), THEN (то, тогда), ELSE (иначе) — ключевые слова языка; <условие> — логическое выражение; <оператор1 и оператор2> — один исполняемый оператор.

Смысл условного оператора: если условие при текущих значениях вхо­дящих в него переменных истинно, то выполняется < оператор1 > (< опе­ратор2> не выполняется), если же условие ложно, то выполняется < оператор2 > (<оператор1> не выполняется). После выполнения < оператора1 > или < оператора2 > управление передается очередной строке программы, если в < операторах1 и 2 > не предусмотрено программ­ное изменение последовательности выполнения строк.

Примеры записи условного оператора:

- для нахождения большего из двух значений:

IF A > В THEN X:=A ELSE Х:=В;

- для нахождения большегоиз двух значений с фиксацией его имени:

IF A > В THEN

BEGIN

X:=A;

F:=’A’

END

ELSE

BEGIN

X:=B;

F:=’B’

END;

Здесь F переменная символьного типа.

В конструкции условного оператора ветвь «иначе» не обязательна, она может отсутствовать. В этом случае имеет место сокращенная форма услов­ного оператора:

IF <условие> THEN <оператор>

Смысл оператора: если <условие> истинно, то выполняется указанный оператор. Если условие ложно, то оператор не выполняется, управление просто переходит к очередной строке программы.

Очевидно, что один условный оператор в полной форме можно заменить двумя в сокращенной форме; например для нахождения большего из двух значений с фиксацией его имени

IF A > В THEN

BEGIN

X:=A;

F:=’A’

END;

IF A <=В THEN

BEGIN

X:=B;

F:=’B’

END;

В условном операторе после ключевых слов THEN и ELSE можно ис­пользовать другой условный оператор. Получающиеся конструкции называ­ются вложенными условными операторами.

Примеры вложенных услов­ных операторов:

IF Х > 0 THEN

IF Х<=1 THEN Y:=1 +X

ELSE Y:=X*X;

Здесь возможна неоднозначность исполнения программы с ветвью, сле­дующейза ELSE. Чтобы ее исключить принимается, что ELSE «закрывает» последний «незакрытый» THEN.

 

Примеры использования условного оператора

Пример 1.3. Вычислить функцию:

1 –e^-x при x < 0,

y = 1 + р при х = 0,

1/(x + p) при 0 < x < 1,

1+ p sin x при x 1.

Решение.

Фрагмент программы

IF X<0 THEN Y:= l + EXP(-X);

IF X=0 THEN Y:=1+P;

IF (X > 0) AND (X < 1) THEN Y:=1/(X+P);

IF X>=1 THEN Y:=1+P*SIN(X);

Пример 1.4. Вычислить значения Y иZ:

Y = a e^{- b} при ab <1,

b sin² a ³ при ab 1,

 

 

Z = a + cos b при ab < 1,

1/(| b | + e^{- a} ) при ab 1.

Решение.

Фрагмент программы

IF А*В < 1 THEN

BEGIN

Y:=A*EXP(-B);

Z=A+COS(B)

END

ELSE

BEGIN

Y=B*SQR(SIN(A*A*A));

Z=1/(ABS(B)+EXP(-A))

END;

Пример 1.5. Найти наибольшее из трех вещественных чисел (А, В, С) с фиксацией его имени.

Решение.

Фрагмент программы

IF A > В THEN

BEGIN

X:=A;

F:=’A’

END

ELSE

BEGIN

X:=B;

F:=’B’

END;

IF C > X THEN

BEGIN

X:=C;

F:=’C’

END;

 

Оператор перехода

Оператор перехода (безусловного перехода) используется для изме­нения естественной последовательности выполнения строк программы. Об­щая форма оператора:

GOTO <метка>

Смысл оператора: управление программой передается оператору с указан­ной меткой. Например:

GOTO Metka;

GOTO 200;

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

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

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

Учитывая эти два противоречивых высказывания, можно сделать вывод: следует рационально использовать оператор перехода, исключив его ис­пользование, там, где можно использовать другие средства.

Оператор выбора

Оператор выбора (CASE) обеспечивает выполнение одного оператора (простого или сложного) из нескольких возможных. Выбор оператора определяется значением выражения (селектора), которое располагается между ключевыми словами CASE и OF. Значение выражения должно совпадать с константами, стоящими перед операторами. Выражение может принадлежать любому простому типу, кроме вещественного.

Выбор оператора определяется совпадением значения селектора и константы, стоящей перед оператором.

 

Пример 1.6. Написать программу для вывода дней недели.

PROGRAM Prim16;

VAR

NUMBER: BYTE;

BEGIN

READ (NUMBER);

CASE NUMBER OF

1: WRITELN(‘ПОНЕДЕЛЬНИК’);

2: WRITELN(‘ВТОРНИК’);

3: WRITELN(‘СРЕДА’);

4: WRITELN(‘ЧЕТВЕРГ’);

5: WRITELN(‘ПЯТНИЦА’);

6: WRITELN(‘СУББОТА’);

7: WRITELN(‘ВОСКРЕСЕНЬЕ’);

END

END.

 

 

Примеры реализации разветвляющегося алгоритма

Пример 1.7. Разработать программу для вычисления функции

для произвольных значений аргументов.

Решение.

Анализ постановки задачи

На первый взгляд кажется, что решение задачи сводится к линейному алгоритму, т.е. вычислению функции, заданной формулой. Однако это мне­ние ошибочное, так как возможны значения аргументов а и b, обращающие знаменатель дроби в нуль. Следовательно, в таких случаях задача не имеет решения. Поэтому в алгоритме (и программе) необходимо предусмотреть две ветви:

- первая, когда знаменатель обращается в нуль и об этом необходимо вывести сообщение;

- вторая, если знаменатель отличен от нуля, то вычисляется функция и выводятся результаты вычисления.

Если ограничиться выводом простейших сообщений, то решение практически очевидно:

— ввести аргументы функции (А и В);

— вычислить знаменатель;

— если знаменатель равен 0, то выводится “сообщение”;

— если знаменатель не равен 0, то выводится результат.

Все инструкции алгоритма максимально детализированы, поэтому со­ставим текст программы.

Нельзя считать хорошей программу для ЭВМ, если в результате ее исполнения на экран ПК выводится одна малозначащая фраза. Поэтому дополним вывод результатов заголовком, значениями аргументов и расширенным сообщением для первой ветви.

Вариант программы будет иметь вид:

PROGRAM Prim17;

{Программа вычисления функции }

VAR

A,B,Y: REAL;

{А, В — Аргументы }

{Y—Функция}

BEGIN

{Этап ввода исходных данных}

WRITE(‘Введите А=’);

READLN(A);

WRITE(‘Введите B=’);

READLN(B);

{Вычисления и вывод}

Y:=1-A*A+B*B;

IF Y=0 THEN WRITELN(‘Нет решения!’);

IFY < >0 THEN WRITELN(‘Функция =’, l/Y:7:4);

END.

 

Пример 1. 8. Определить, попадает ли точка с координатами x, y в круг радиуса r с центром в начале координат (уравнение окружности r ² = x ² + + y ²).

Решение.

Вариант программы будет иметь вид:

PROGRAM Prim18;

VAR

x, y, r: REAL;

BEGIN

WRITE(‘Введите радиус окружности R=’);

READLN(R);

WRITE(‘Введите координаты точки X и Y’);

READLN(X, Y);

IF X*X+Y*Y<=R*R

THEN WRITELN(‘Точка лежит внутри круга’)

ELSE WRITELN(‘Точка лежит вне круга’);

END.

 

Пример 1.9. Составить программу для упорядочивания трех чисел a, b, c по возрастанию таким образом, чтобы имени a соответствовало наименьшее число, имени b – среднее, а имени c – наибольшее.

Решение.

Вариант программы будет иметь вид:

PROGRAM Prim19;

LABEL 10, 20, 30;

VAR A, B, C, H: REAL;

BEGIN

WRITE(‘Введите три числа a, b, c:’);

READ(a,b,c);

IF A<=B THEN GOTO 10

ELSE BEGIN

H:=A;

A:=B;

B:=H

END;

10: IF A<=C THEN GOTO 20

ELSE BEGIN

H:=A;

A:=C;

C:=H

END;

20: IF B<=C THEN GOTO 30

ELSE BEGIN

H:=B;

B:=C;

C:=H

END;

30: WRITELN(‘A=’,A:5:2,’ B=’,B:5:2,’ C=’,C:5:2);

END.

 

 

Контрольные вопросы

1. Что такое вычислительный процесс разветвляющейся структуры?

2. Какие управляющие конструкции в Турбо Паскале используются для организации разветвления?

3. Какова последовательность действий при выполнении условного оператора?

4. Какие действия выполняются оператором перехода goto?

5. Почему не рекомендуется использование в программах оператора goto?

6. Какие особенности существуют при написании вложенных операторов If?

7. Какой оператор позволяет выполнить одно из нескольких действий в зависимости от результата вычисления выражения?

 

 

Задачи

Эти задания предназначены для при­обретения навыков организации разветвлений.

1. На плоскости расположена окружностьрадиуса R с цен­тром в начале координат. Ввести заданныекоординаты точки, определить, лежит ли она наокружности. Решить задачу при R =2 для точек с координатами (0, 2), (-1.5, 0.7), (1, 1), (3, 0).

Указание. Считать, что точкас координатами х, у лежит наокружности радиуса R, если х ² + у ² — R ² < 10^-3.

2. Вычислить площадь треугольника со сторонами a, b, c по формуле Герона, проверив условие корректности исходных данных (длины всех сторон положительны, сумма длин любых двух сторон больше длины третьей).

3. Для заданных а и b получить

mах(а,b), если a > 0,

C =

min(а,b), если a 0.

4. Для заданных а, b, с вычислить z =max(min(a,b), c).

5. Заданы площади круга R и квадрата S. Определить,поместится ли квадрат в круге. Задачу решить при: 1) R = 70, S =36.74; 2) R =0.86, S = 0.74.

Указание. Для решения задачи выразить диагональ квадрата и диаметр круга через заданные площади фигур. Квадрат поме­стится в круге,если диагональ квадратане превышаетдиаметрокружности.

6. Длязадачи 5 определить, поместится ли круг в квадрате. Задачу решить при: 1) R = 3.2, S= 3.5; 2) R = 3.2, S =4; 3) R = 6, S = 9.

В задачах 7 —10 определитьзначение функции у при заданном аргументе х.

7.

 

8.

 

9.

 

10.

В задачах 11 — 15 определить принадлежность точки (х,y) заданной области. Координаты трех точек задать самостоятельно.

11. у 0 и х ² + у ² 1.

12. у | x |и у 1- x ².

13. у 0, у ² 4 - x ²и у ² 9 - x ².

14. х 0, у 0 и x ² + у ² 4.

15. x 0, y 0 и y ² 9 - x ².