4789

Ветвящиеся программы. Тип данных Boolean

Лекция

Информатика, кибернетика и программирование

Ветвящиеся программы 1.Понятие условия. Тип данных Boolean (логический). 2.Составной оператор. 3.Выбирающие операторы: условный оператор. 4.Ветвящиеся программы. Пример. 5.Оптимизация ветвящихся программ по времени. 6.Скалярный тип. 7.Выбирающие опе...

Русский

2012-11-27

96 KB

7 чел.

Ветвящиеся программы

1.Понятие условия. Тип данных Boolean (логический).

2.Составной оператор.

3.Выбирающие операторы: условный оператор.

4.Ветвящиеся программы. Пример.

5.Оптимизация ветвящихся программ по времени.

6.Скалярный тип.

7.Выбирающие операторы: оператор варианта

8.Упражнения.

1.Понятие условия. Тип данных Boolean (логический).

Условия используются в программах для организации ветвлений и повторяющихся действий. Условием в языке является логическое выражение - выражение типа Boolean. Булевские значения - это логические истинностные значения: True (истина) и False (ложь).

Этот тип данных, как и другие простые типы данных, упорядочен. На нем определены функции Ord, Succ, Pred.

Таким образом , имеют место следующие соотношения :

False < True ,

Ord (False)=0,  Ord (True)=1,

Succ (False)=True,  Pred (True)=False.

На множестве < True, False > определены логические операции

Операции:

 And - логическая коньюнкция ( и )

  Or - логическая дизньюнкция ( или )

Not - логическое отрицание ( не )

Эти операции определяются следующими таблицами истинности:

                                     

And

False

True

 Or

False

True

  x

Not x

False

False

False

False

False

True

False

True

True

False

True

True

True

True

True

False

Отношения, определенные ранее для простых стандартных типов являются операциями, результат которых имеет логический тип. Иными словами, булевское значение дает любая из операций отношений :  =, < > , <= , < , > , >= , in.

Для типа Boolean определены стандартные функции, принимающие значения этого типа (логические значения):

Odd(Х) { Odd(Х) = True, если Х - целое нечетное число

 Odd(Х) = False, если Х - целое четное число}

Eoln(F) { конец строки в текстовом файле}

Eof(F) { конец файла}

Функции Eoln(F) и Eof(F) будут определены при описании файлов.

Условия можно классифицировать как простые и сложные.

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

Простое

условие

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

Приведем примеры простых и сложных выражений типа Boolean (условий).

Простые выражения типа Boolean (условия) :

Sin(2*x) > Ѕ, (X + Y) mod Prime = 0,

b*b > 4*a*c ,

Number div Modulo = 2, Odd(A*P + B),

Flag ;

Сложные выражения типа Boolean (условия) :

а) (а + i > в) or ( х [Index] = с )

{ Здесь а, в, с - переменные типа Real, х - массив вещественных чисел , Index - переменная типа Integer }

б) Odd (n) And (n < 10е4)

в) Eof(f) Or (f^.data = 0)            {f - файл действительных чисел}

г) Not(beta) And (gamma)   {beta и gamma - переменные типа Boolean}

д) (A > B) = (C > D)

Логические выражения преобразуются по законам логики высказываний. Например,

Not((A > 0) And (B <> 0))  <==>  Not(A > 0) Or Not(B <> 0)  <==>   (A <= 0) Or (B = 0)

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

2.Составной оператор.

Несколько операторов, выполняемых последовательно, можно объединять в один составной оператор.

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

Составной оператор определяется диаграммой :

составной

оператор

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

Примеры составных операторов :

а)

Begin

Write(‘Введите координаты вектора: ‘);

Readln(a, b, c);

Length := sqrt(a*a + b*b+ c*c);

Write(‘длина (a,b,c) равна ‘, Length)

end

б)

Begin

u := u*х/n;

s := s+u

End

в) Begin writeln (‘уравнение корней не имеет’) End

3.Выбирающие операторы: Условный оператор.

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

Существует две формы условного оператора :

If <условие> then < оператор >

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

Они соответствуют базовым управляющим структурам короткого и полного ветвления. Условие - это выражение типа Boolean .

Синтаксическая диаграмма условного оператора имеет вид:

                                                                     

Условный 

оператор

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

а) If a >= b then Max := a else Max := b

б) If IntFun(i) mod 3 = 0 then write(i)

в) If  (a11*a22 = a12*a21) And

 ((a11*b2 <> a12*b1) Or

 (b1*a22 <> b2*a21))

 then Write(‘система решений не имеет’)

 else Write(‘система имеет решения’)

г) If х <= 0

     then begin

       u :=х*х - 2*х + 3;

       v :=1/2*х + 1

    end

    else begin

     u :=1/3*х+2;

     v :=х*х+3*х-2

    end

Обратите внимание на то, что в теле условного оператора может использоваться и другой условный оператор. Это создает возможность реализовывать многозначные ветвления. Например:

If Discriminant < 0

 then If LeadCoef < 0

  then Write(‘Решений нет’)

  else Write(‘Решения - вся числовая ось’)

  else If LeadCoef < 0

    then Write(‘Решения - между корнями уравнения’)

    else Write(‘Решения - вне корней уравнения’)

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

If<усл 1> then If <усл 2> then <оператор 1> else <оператор 2>

 1 вариант:   If <усл 1>

then begin

    I f <усл 2> then <оператор 1> else <оператор 2>

   end

2 вариант:   If<усл 1>

then begin

 If <усл 2> then <оператор 1>

end

else <оператор 2>

Для устранения двусмысленности в языке избран 1-ый вариант интерпретации в соответствии с правилом: разделителю else соответствует ближайший предыдущий разделитель then.

4.Ветвящиеся программы. Пример.

Ветвящимися называют программы, в которых используются операторы ветвления.

Пример 1.

Program SquareEquation;

Const Line = ‘----------------------------‘;

Var a, b, c, Root1, Root2: real;

Solution: Integer;

Discriminant: Real;

Begin

 {Ввод данных}

 Write(‘Введите коэффициенты уравнения (через пробел):’);

 Readln(a, b, c) ; Writeln(Line);

{Вычисления}

Discriminant := Sqr(b) - 4*a*c;

If Discriminant < 0

 then Solution := 0 { Нет корней }

 else If Discriminant = 0 { Один корень }

   then begin

     Solution := 1;

     Root1 := -b/a;

     Writeln (‘х1= ‘ ,Root1)

   end

  else { Два корня } begin

    Solution := 2;

    Root1 := (-b + Sqrt(Discriminant))/(2*a);

    Root2 := -b/a - Root1;

    Writeln(‘х1= ‘, Root1, ‘ х2= ‘, Root2)

  end ;

    Writeln(Line);

    Writeln(‘Количество решений равно: ‘, Solution)

End.

5.Оптимизация ветвящихся программ по времени.

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

Пусть Tп - временная сложность программы в худшем случае, Tу - временная сложность условия и Tв1, Tв2 - временные сложности ветвей программы. Тогда имеет место соотношение:

Tп = Tу + Max( Tв1, Tв2 )        (1)

Временная сложность в среднем определяется формулой

Tп = Tу + PуTв1 + (1 - Pу)Tв2        (2)

где Pу - вероятность выполнения условия.

Поскольку условием является логическое выражение, общие приемы оптимизации выражений применимы и для логических выражений. Время выполнения логических операций And, Or, Not, =, <> Tл существенно меньше времени выполнения аддитивных операций, а время выполнения операций <, >, <=, >= равно времени выполнения аддитивных операций.

   Tf >> Tm > Ta > Tл      (3)

Рассмотрим пример: требуется выяснить, является ли одно из двух чисел A, B равным нулю.

1 вариант условия: A*B = 0

2 вариант условия: (A = 0)Or(B = 0)

Во первом варианте использовано умножение и сравнение, во втором - 3 логических операции. Сложность 2-го варианта меньше.

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

If x < 0 then    <==>  If (x < 0) And (Y < 0)

If y < 0 then z := 1      then z := 1

If x < 0

then Flag := False   <==>  Flag := (x >= 0)

else Flag := True

В следующем примере условия ветвлений упрощены за счет использования соотношений, выполняющихся после  вычисления предыдущего условия:

Пример 2. Программа вычисления значения функции, определенной кусочно:

      2x - 1   при x < -1                                               

   y  =  x2 + 1   при -1 <= x < 1

     2x + 1  при x >= 1

1 вариант ( часто встречающийся у начинающих )

If x < -1 then y := 2*x - 1;

If (-1 <= x)And(x < 1) then y := Sqr(x) + 1;

If x >= 1 then y := 2*x + 1;

2 вариант ( оптимальный )

If x < -1 then y := 2*x - 1

 else If x < 1 then y := Sqr(x) + 1

 else y := 2*x + 1;

Для получения  2-го  варианта  заметим,  что  условия x < -1, (-1 <= x)And(x < 1), x >= 1 взаимно исключающие и в совокупности тождественно истинные. Поэтому (-1 <= x) и x >= 1 можно заменить на else.

6.Перечисляемый тип. Раздел типов.

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

Tипы данных, определяемые программистом, описываются в специальном разделе - разделе типов. Раздел типов опреден синтаксической диаграммой:

Раздел

типов

            

Перечисляемый тип данных определяется следующей диаграммой :

 

Перечисляемый 

тип

Примеры определений перечисляемых типов :

а) Type Weekday = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

Colour = (Red, Orange, Yellow, Green, Blue, Black);

Operation = (Plus, Minus, Times, Divide)

Заметим, что стандартный тип Boolean, если бы его нужно было описать, выглядел бы как : type Boolean = (False, True);

Для аргументов перечисляемого типа определены такие стандартные функции :

Succ(x) - значение, следующее за x.

Pred(x) - значение, предыдущее x.

Ord(x)  - порядковый номер x.

К значениям перечисляемого типа применимы отношения:

=, <>, <, <=, >=, > .

Упорядоченность значений определяется порядком перечисления констант в описании типа. Например :

Red < Orange < Yellow < Green < Blue < Black ;

Описание типа переменной может быть дано и в разделе переменных. Например, описание :Type Figure = (Triangle, Circle, Rhombus, Square);

Var f: Figure; эквивалентно описанию Var f: (Triangle, Circle, Rhombus, Square); однако во втором случае описание типа становится анонимным: тип описан, но не имеет имени. Использование этого типа ограничено.  Поэтому 1-ый вариант более соответствует стилю языка.

7.Выбирающие операторы: оператор варианта

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

Оператор варианта вычисляет значение селектора и выбирает для исполнения оператор, одна из меток которого равна этому значению. По окончании выполнения выбранного оператора управление передается в начало следующего за оператором варианта оператора.

Если значение селектора не совпадает ни с одной из меток, то выбирается оператор, помеченный ключевым словом else.  Этот оператор должен быть последним в списке вариантов.  Если значение селектора не совпадает ни с одной из меток и else отсутствует, то оператор варианта игнорируется.

Оператор варианта имеет вид :

Case < выражение {селектор}>  of  <список меток варианта> : < оператор >;

. . . . . . . . . .

< список меток варианта > : < оператор >

[else < оператор > ]

end

На языке синтаксических диаграмм это выглядит так:

Оператор

варианта 

Список меток

варианта

                          

Примеры операторов варианта :

а) Select : = Index mod 4;

 case Select of

   0 : x := y*y + 1;

   1 : x := y*y - 2*y;

   2,3 : x := 0

 end;

В этом примере Select принимает значение 0, 1, 2, 3. Это достигнуто вычислением Select := Index mod 4.

Таким образом, вместо имени Select можно использовать выражение Index mod 4:

case Index mod 4 of

 0 : x := y*y + 1;

 1 : x := y*y - 2*y;

 2,3 : x := 0

end;

б) case ch of

 ‘a’,’b’,’c’ : ch := succ(ch);

 ‘y’,’z’ : ch := pred(ch);

 ‘f’,’g’ : {пустой вариант};

else ch := pred(pred(ch)

end;

Программа в следующем примере вычисляет знак одной из тригонометрических функций в зависимости от квадранта декартовой плоскости.

Пример 3.

program Sign_of_Function;

Type Fun = (Unknown, FSin, FCos, Ftg, Fctg);

var FunNumber, Quoter: Integer;

TrigFun : Fun;

Begin

 Write(‘Введите номер тригонометрической функции ‘);

 Readln(FunNumber);

{ Вычисление имени функции }

Case FunNumber of

 1: TrigFun := FSin;

 2: TrigFun := FCos;

 3: TrigFun := FTg ;

 4: TrigFun := FCtg

else begin

 TrigFun := Unknown;

 Writeln(‘Неизвестная функция’)

end

end;

Write(‘Введите номер квадранта ‘); Readln(Quoter);

{ Вычисление знака функции }

case TrigFun of

FSin: case Quoter of

 1, 2: Writeln (‘знак синуса +’);

 3, 4: Writeln (‘знак синуса -‘)

 end;

 FCos: case Quoter of

1, 3: Writeln (‘знак косинуса +’);

2, 4: Writeln (‘знак косинуса -‘)

end;

FTg, FCtg: case Quoter of

 1, 4: Writeln (‘знак тангенса и котангенса +’);

 2, 3: Writeln (‘знак тангенса и котангенса -‘) end;

Unknown: Writeln(‘Функция не определена’)

end

end.

8. Упражнения.

I Сформулируйте условия для оператора ветвления:

1.Белый конь расположен на поле (х, n). Черная пешка расположена на поле (y, m). Находится ли пешка под боем коня?

2.Белый слон расположен на поле (х, n). Черная пешка расположена на поле (y, m). Других фигур на поле нет. Находится ли пешка под боем слона?

3.Белая шашка расположена на поле (х, n). Черная шашка расположена на поле (y, m). Находится ли черная шашка под боем белой?

4.Белая дамка расположена на поле (х, n). Черная шашка расположена на поле (y, m). Находится ли черная шашка под боем белой дамки? (Других фигур на доске нет)

5.Вектор a = (x, y), вектор b = (u, v). Являются ли векторы параллельными или перпендикулярными?

6.Вектор a = (x, y), вектор b = (u, v). Можно ли повернуть вектор a против часовой стрелки на некоторый угол, меньший 1800. так, чтобы векторы стали сонаправленными?

7.Пересекаются ли окружность O1 с центром (x, y) и радиусом R1 c окружностью O2 с центром (u, v) и радиусом R2?  

8.Является ли треугольник с вершинами A(x1, y1), B(x2, y2), C(x3, y3) равнобедренным?

9.Можно ли из отрезков a, b, c составить треугольник и можно ли этот треугольник поместить в круг радиуса R?

10.Прямая задана уравнением Y = kX + b. Лежит ли точка A(u, v) над этой прямой?

II Напишите программу решения задачи:

1.Решить квадратное неравенство ax2 + bx + c < 0.

2.Решить систему линейных уравнений:

 a11x + a12y = b1

 a21x + a22y = b2

3.Вычислить внутренние углы треугольника, с вершинами A(x1, y1), B(x2, y2), C(x3, y3)

4.Найти самую короткую сторону треугольника с вершинами A(x1,y1), B(x2, y2), C(x3, y3).

5.Найти максимум и минимум из трех целых чисел.

6.Вычислить значение функции:

1, если x > 0

 Sign(x)  =      0, если x = 0

                        -1, если x < 0 .

7.Вычислить наибольшее и наименьшее значения функции Y=ax2 +bx+c на отрезке [p ; q].

8.Найти область определения функции: y=1/(x2 + px + q).

9.Решить биквадратное уравнение ax4 + bx2 + c = 0

10.Найти квадрат наименьшей площади со сторонами, параллельными осям координат, содержащий три точки плоскости A(x1,y1), B(x2,y2), C(x3,y3).

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


Выражение

  Отношение

Выражение

Логическая функция

Логическое значение 

      Begin

 Оператор

End

,

If

Условие

Then

Оператор

Else

Оператор

Type

Имя типа

=

Описание типа

(

)

Имя данного

,

 Case

Селектор

Of

 Список меток варианта

Оператор

 :

 ;

 Else

Оператор

End

 метка варианта

 ,


 

А также другие работы, которые могут Вас заинтересовать

50960. Каналы передачи данных 104 KB
  Рассматривают три основных параметра сигнала существенных для передачи информации по каналу. Первый важный параметр это время передачи сигнала Tс. Следовательно общее условие согласования сигнала с каналом передачи информации определяется соотношением Однако соотношение выражает необходимое но недостаточное условие согласования сигнала с каналом.
50961. Сигналы и их характеристики 367.5 KB
  Например при выборе прибора для контроля технологического процесса может потребоваться знание дисперсии сигнала; если сигнал используется для управления существенным является его мощность и так далее. Рассматривают три основных параметра сигнала существенных для передачи информации по каналу. Первый важный параметр это время передачи сигнала Tx . Второй характеристикой которую приходится учитывать является мощность Px сигнала передаваемого по каналу с определенным уровнем помех Pz .
50962. Информация, сообщения, сигналы 70 KB
  Структурная схема системы передачи информации Классификация сигналов по дискретнонепрерывному признаку Квантование и кодирование сигналов Квантование по уровню Квантование по времени Лекция №5 Тема: Информация сообщения сигналы Структурная схема системы передачи информации Теория информации – это наука о получении преобразовании накоплении отображении и передаче информации. В настоящее время существуют различные определения информации. Структурная схема одной из характерных информационных систем в общем случае может быть...
50963. Монтаж центрифуги прачечной 556.54 KB
  Важнейшим звеном в решении задач является дальнейшее развитие инициативы и творческой активности работников коммунальных предприятий, совершенствование производственных отношений, внедрение научной организации труд, повышение квалификации, овладение смежными профессиями.
50964. Критика А. Шопенгауэром концепции соотношения рассудка и разума в теории познания И. Канта 247.5 KB
  Идеи Шопенгауэра невозможно адекватно постичь без знания философии Канта. Структура и проблематика кантовской системы – вот та основа, на которой в первую очередь формируются взгляды Шопенгауэра. Это относится как к прямым заимствованиям у Канта
50965. Организация данных. Типы и структуры данных 96.5 KB
  Понятие тип данных делает манипулирование данными с использованием средств вычислительной техники абстрактным процессом и скрывает лежащее в основе обращения с ними представление их в виде двоичного кода. Виды типов данных: Аналоговые данные...
50966. Можливості використання здобутків теорії поля для моделювання та прогнозування реальної поведінки споживача 25.1 KB
  Передбачення майбутнього неможливе за багатьох обставин. Жоден екстрасенс не зможе сказати, наскільки успішним буде той чи інший товар, який підприємство планує вивести на ринок. Навіть з урахуванням безлічі математичних моделей, значної кількості змінних, залишається так звана «чорна скринька» свідомості споживача.
50967. Средства вычислительной техники. Принципы построения функциональных узлов и устройств ЭВМ 5.49 MB
  Для отечественных системотехников и специалистов в области ВТ отсутствие отечественных микросхем современного уровня компилируется допустимостью зарубежной элементной базы, поэтому Вам, как специалистам в области информационных технологий, изучение аппаратных средств ВТ, то есть цифровых узлов и устройств во всем ее разнообразии имеет большое практическое значение.
50968. Информация, сообщения, сигналы. Структурная схема системы передачи информации 66 KB
  В узком смысле кодирование – это отображение дискретных сообщений сигналами в виде определенных сочетаний символов. Под помехами подразумеваются любые мешающие внешние возмущения или воздействия атмосферные помехи влияние посторонних источников сигналов а также искажения сигналов в самой аппаратуре аппаратурные помехи вызывающие случайное отклонение принятого сообщения сигнала от передаваемого. Решающее устройство помещенное после приемника осуществляет обработку принятого сигнала с целью наиболее полного извлечения из него...