ВЕТВЯЩИЙСЯ АЛГОРИТМ ЦЕЛИ: Познакомиться с понятиями: логический тип данных, ветвящийся алгоритм. Освоить средства реализации разветвляющихся алгоритмов. - презентация

1 ВЕТВЯЩИЙСЯ АЛГОРИТМ ЦЕЛИ: Познакомиться с понятиями: логический тип данных, ветвящийся алгоритм. Освоить средства реализации разветвляющихся алгоритмов на языке Паскаль.

2 Операции сравнения Операция отношения Обозначение Равно= Не равно Больше> Больше или равно>= Меньше< Меньше или равно5 Какое значение имеет результат этого сравнения? Это ложь. Результат операции сравнения может иметь одно из двух значений: истина или ложь. В языке программирования Паскаль для хранения в памяти ЭВМ таких значений используется специальный тип данных, который называется логическим.

3 Логический тип данных К логическому типу относятся данные, которые могут принимать одно из двух значений: true (истина) или false (ложь). Различают логические константы и логические переменные. Описание логического типа данных Соnst cl=true; Var L, cl : boolean; Begin L:=3>5; Writeln(значение логической переменной,L); Writeln(значение логической константы,cL); End. В языке Паскаль не предусмотрен ввод с клавиатуры данных логического типа, но существует вывод переменных и констант логического типа, как это показано в примере.

4 Условное выражение Условными выражениями называются такие выражения, которые содержат арифметические выражения, связанные операциями сравнения (отношения). Примеры условных выражений: (а + b) * с >= 1000; c * d > x + (y * c) * b. Результатом условного выражения являются логические величины false или true. Если условие выполняется, то результатом его выполнении является значение true, в противном случае - false. Пример: при а = 4, b = 45 условное выражение а + 16 < b принимает значение true, а условное выражение а * а = b принимает значение false.

5 Логические операции Над данными логического типа определены следующие операции: NOT - логическое НЕ – логическое отрицание; AND - логическое И – логическое умножение; OR - логическое ИЛИ – логическое сложение; XOR - исключающее ИЛИ – исключающее ИЛИ, сложение по модулю 2. Операция NOT имеет один операнд, все остальные - два операнда. Пример: NOT A, A OR В. Операнды А и В являются данными логического типа. Результаты вычисления логических операций приведены в таблице 2.2, которая содержит таблицы истинности для всех описанных выше логических операций.

6 Результаты логических операций Логическая операция Значение операнда 1Значение операнда 2Значение результата NOT TRUEFALSE TRUE AND TRUE FALSE TRUEFALSE TRUEFALSE OR TRUE FALSETRUE FALSETRUE FALSE XOR TRUE FALSE TRUE FALSETRUE FALSE

7 Логические выражения Логическое выражение состоит из логических элементов и логических операций. Логическое выражение, как видно из таблицы 2.2, может принимать одно из двух значений: true или false. Логический элемент, который согласно таблице 2.2. может принимать одно из двух значений true или false, должен быть одним из следующих: - логической константой (true или false); - логической переменной; - условным выражением; - логическим выражением. Здесь впервые мы встречаемся с рекурсивным определением, понятие логического выражения вводится через определение логического выражения. Вычисление значения логического выражения происходит по старшинству операций и его результатом может быть значение true или false. В Паскале определены следующие группы приоритетов логических и арифметических операций: 1) Not; 2) *, /, Div, Mod, And; 3) +, -, Or, Xor; 4) =, ,, =.

8 1) Not; 2) *, /, Div, Mod, And; 3) +, -, Or, Xor; 4) =, ,, =. Приоритет операций убывает в указанном порядке, наивысшим приоритетом обладают операции группы 1, они выполняются первыми при вычислении выражений, а самым низшим - операции группы 4, они выполняются последними. Порядок выполнения операций может быть изменен с помощью скобок, так же, как и при вычислении арифметических выражений. Пример вычисления логического выражения: (а * b + с = х + y) and (k * b > t) Пусть а = 3.0, b = 4.1, с = 4, х = 2.5, у = 5, k = 3, t = 10, тогда логическое выражение вычисляется в следующем порядке: 1) а * b + с равно 16.3; 2) х + у равно 7.5; 3) k * b равно 12.3; 4) (16.3 = 7.5) равно false; 5) (7.5 > 10) равно false; 6) false and false равно false. Таким образом, результатом вычисления всего выражения будет false. Логические выражения можно использовать для записи условий, которые применяются в математике.

9 Примеры записи условных и логических выражений Задача 1. На числовой оси дан отрезок [a,b] и точка с координатой х. Написать условие: точка х принадлежит отрезку [a,b]. Решение. В математике такое условие записывается так: (axb). Вычислительная машина в каждый момент времени выполняет одно действие и записывает результат этого действия в память. Поэтому в программировании это условие записывается следующим образом: (ax)and(xb).

10 Задача 2. На числовой оси дан отрезок [a,b] и точка с координатой х. Написать условие: точка х не принадлежит отрезку [a,b]. Решение. В математике такое условие записывается так: (a>x>b). В программировании это условие записывается следующим образом: (x b).

11 Задача 3. На плоскости в декартовой системе координат задана точка своими координатами (X, Y) и квадрат со стороной 2, центр которого расположен в начале координат. Записать логическое выражение, вычисляющее, принадлежит ли точка заштрихованной области. Решение. Если решать задачу «в лоб», то алгоритм следует записать следующим образом. (1>x>-1), при этом мы выделяем на координатной плоскости вертикальную полосу шириной 2 бесконечной длины, И (1>y>-1), при этом на координатной плоскости выделяется горизонтальная полоса шириной 2 также бесконечной длины. На пересечении этих полос находится заданная область. Получим логическое условие (1>x>-1) И (1>y>-1), которое содержит вычисление 4-х условий и одной логической операции. Можно записать решение этой задачи иначе (x

12 Ветвящийся алгоритм Организовать ветвление в программе можно двумя способами: в зависимости от значения условного или логического выражения или в зависимости от значения переменной порядкового типа. Ветвление в зависимости от значения условного или логического выражения осуществляется с помощью одного из условных операторов. В языке Паскаль существует три вида условных операторов: короткий условный оператор, полный условный оператор и сложный условный оператор. Ветвление в зависимости от значения переменной порядкового типа осуществляется с помощью оператора выбора. В языке Паскаль определены две разновидности оператора выбора.

13 Короткий условный оператор Короткий условный оператор имеет следующий синтаксис. IF THEN ; Здесь IF, THEN – ключевые (или зарезервированные) слова; - любое условное или логическое выражение, отделяется от ключевых слов пробелами; - простой или составной оператор языка Паскаль (кроме условного); ; - разделитель, обозначает конец оператора. TrueFalse Начало ветвления Условн ое или логичес кое выражение Конец Оператор Рисунок 2.1. Блок-схема короткого условного оператора Путь 2Путь 1

14 Полный условный оператор Полный условный оператор имеет следующий синтаксис. IF THEN ELSE ; Здесь IF, THEN, ELSE – ключевые (или зарезервированные) слова; - любое условное или логическое выражение, отделяется от ключевых слов пробелами;, - простой или составной оператор языка Паскаль (кроме условного); ; - разделитель, обозначает конец оператора. TrueFalse Начало ветвления Условно е или логическ ое выражен ие Конец Оператор 1 Рисунок 2.2. Блок-схема полного условного оператора Путь 2 Путь 1 Оператор 2

15 Сложный условный оператор Сложным условным оператором является один из условных операторов – короткий или полный, в котором ИЛИ / И, являются условными операторами. True False True False Начало ветвления Условие 1 Условие 3 Условие 2 Оператор 1Оператор 2Оператор 3 Конец ветвления Рисунок 2.3. Блок-схема сложного условного оператора

16 Оператор выбора В языке Паскаль существуют две разновидности оператора выбора, которые имеют следующий синтаксис: CASE OF : ;... : ; ELSE END; СASE OF : ;... : ; END; Здесь: CASE, OF, ELSE, END – ключевые (зарезервированные) слова; - в операторе CASE может быть только порядкового типа: целого, символьного, логического, перечислимого или ограниченного типов. Нельзя использовать вещественный тип данных; … - конкретные значения, которые входят в диапазон значений типа, к которому принадлежит результат вычисления ; …, - любые простые или составные операторы языка Паскаль; : - разделитель, отделяет значение константы от оператора;

17 Составной оператор Составной оператор - это последовательность операторов программы, заключенная в операторные скобки BEGIN... END. Для наглядности советуем эти операторные скобки размещать друг под другом, а последовательность операторов между ними сдвигать вправо. Среди операторов, входящих в составной оператор, могут быть использованы другие составные операторы: допускается произвольная глубина их вложенности. Тело вложенного составного оператора рекомендуем также сдвигать относительно операторных скобок BEGIN и END. В этом случае запись алгоритма приобретет приблизительно следующий вид: BEGIN ; BEGIN ; BEGIN ; END END; Такая форма записи алгоритма позволяет легко ориентироваться в структуре программы и, следовательно, избегать логических и синтаксических ошибок.

18 Примеры программ Задача 1 Для заданного значения X вычислить значение функции F(X) = Y, которая определяется следующим образом: В этом алгоритме для организации ветвления можно использовать условие X >= 0. Если это условие верно, то надо вычислять Y по формуле Y = 4Х, если не верно, то Y = 0. Var x,y : real; Begin Writeln (' Введите значение X '); Read(x); If x >= 0 then y := 4 * x Else y := 0; Writeln('y=', y:6:3); End.

19 Задача 4. Два прямоугольника, расположенные в первом квадранте, со сторонами, параллельными осям координат, заданы координатами своих левого верхнего и правого нижнего углов. Для первого прямоугольника это точки (xl,yl) и (х 2,0), для второго - (хЗ,уЗ), (х 4,0). Составьте алгоритм или напишите программу, определяющую, пересекаются ли данные прямоугольники, и вычисляющую общую площадь, если они пересекаются. Алгоритм решения этой задачи может быть записан следующим образом: Нарисовать первый квадрант декартовой системы координат и пересекающиеся прямоугольники. Обозначить левую точку пересечения (а, b), правую точку (лежащую на оси X) - (c,d). Алгоритм решения задачи: Переменные xl,yl,x2,x3,y3,x4,a,b,c,d,S : тип - вещественный; Ввести xl,yl,x2,y2,x3,y3,x4; Если у 1 или у 3 равны 0, то прекратить решение; Вычислить минимальное из чисел yl и уЗ : b = min(yl, y3); Вычислить максимальное из чисел xl и xЗ : a = max ( xl, x3); Вычислить минимальное из чисел х 2 и х 4: c = min(x2,x4); Присвоить d = 0 (по условию задачи); Если (а < с) И (b0) то начало Выдать на экран : «Прямоугольники пересекаются»; Вычислить общую площадь S = (c - a) / b; Выдать на экран S Конец иначе выдать на экран «Прямоугольники не пересекаются или касаются».

20 Программа на языке Паскаль. Var X1,y1,x2,y2,x3,y3,x4,a,b,c,d,s:real; Begin Write(x1=); readln(x1);{ввод данных} Write(y1=); readln(y1); Write(x2=); readln(x2); Write(x3=); readln(x3); Write(y3=); readln(y3); Write(x4=); readln(x4); If (y1=0)or(y3=0) then begin Writeln(Не верно введены данные); Halt; Readln; End; If y1x3 then a:=x1 else a:=x3; If x2

21 Задача 5. Дан треугольник ABC с координатами вершин А(Ах,Ау), В(Вх.Ву), С(Сх.Су), где числа Ах, Ay, Bx, By, Cx, Су - целые. Составьте алгоритм, определяющий, является ли этот треугольник равнобедренным. Входные данные задать с помощью датчика случайных чисел из диапазона [0,20]. Алгоритм решения задачи: Ввести координаты вершин Ах, Ay, Bx, By, Cx, Су; Вычислить квадраты длин сторон АВ, ВС и АС по формулам АВ 2 = (Вх-Ах) 2 + (Ву-Ау) 2 ; ВС 2 = (Сх-Вх) 2 + (Су-Ву) 2 ; АС 2 = (Ах-Сх) 2 + (Ay-Су) 2 ; Ecли АВ 2 = ВС 2 или ВС 2 = АС 2 или АВ 2 = АС 2, то Вывести на экран "Треугольник ABC равнобедренный" иначе "Треугольник ABC не равнобедренный".

22 Программа на языке Паскаль: Const Eps= ; Var Ax,Ay,Bx,By,Cx,Cy : Real; AB2,BC2,AC2 : Real; { квадраты сторон } Begin Randomize; Writeln ('Координаты точки А '); Ax:=random(20)+random; Ay:=random(20)+random; Writeln(Ax=,Ax:0:2,Ay,Ay:0:2); Writeln ('Координаты точки В '); Bx:=random(20)+random; By:=random(20)+random; Writeln(Bx=,Bx:0:2,By,By:0:2); Writeln ('Координаты точки С '); Cx:=random(20)+random; Cy:=random(20)+random; Writeln(Cx=,Cx:0:2,Cy,Cy:0:2); AB2 := sqr(Ax - Bx) + sqr(Ay - By); BC2 := sqr(Cx - Bx) + sqr(Cy - By); AC2 := sqr(Ax - Cx) + sqr(Ay - Cy); if (abs(АВ2 - ВС2)