4789

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

Лекция

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

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

Русский

2012-11-27

96 KB

6 чел.

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

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

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

 ,


 

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

65902. ИЗМЕНЕНИЯ КОНСТИТУЦИОННЫХ НОРМ — ФАКТОР РАЗВИТИЯ ТЕОРИИ АДВОКАТСКОЙ ДЕЯТЕЛЬНОСТИ 43.5 KB
  Субъективные права и юридические обязанности активно используются в ходе расследования уголовных дел равно как стороной обвинения так и стороной защиты. Исключать влияние конституционного права эволюции его норм на криминалистику и иные прикладные науки необоснованно.
65903. КРИМИНАЛЬНАЯ КУЛЬТУРОЛОГИЯ. ТЕОРИЯ ГЕНДЕРА 85 KB
  Объединяет же эти преломления их безусловная принадлежность к процессу порождения конкретного акта преступного поведения и к тому что мы называем обыденной средой обитания каждого из нас. Значение категории мотива в изучении характеристик и закономерностей индивидуального преступного поведения трудно переоценить.
65904. ГЕНЕЗИС И ЭВОЛЮЦИЯ ЖАНРА: ВЕРСИЯ ОБОСНОВАНИЯ 73 KB
  Миф как единственно возможная форма восприятия мира на известной стадии развития общества. Эта проблема разрешается формированием жанра который и логически и исторически является модернизированной модификацией мифа его гомоморфным образом. Генезис жанра связан с архаическим ритуалом как языком мифо-поэтической модели мира...
65905. Разработка и реализация управленческих решений 48 KB
  Природа процесса принятия решения Принятие эффективных решений – одно из наиболее важных условий эффективного существования и развития организации. Конечно существует ряд проблем касающихся отношений между людьми здоровья семейного бюджета неудачное решение которых может...
65906. НАРОДОЗНАВЧИЙ АСПЕКТ НАВЧАННЯ І ВИХОВАННЯ МОЛОДШИХ ШКОЛЯРІВ 43 KB
  В контексті розбудови незалежної України створення системи національної освіти і виховання особливого значення набуло науково обґрунтоване розв'зання навчальних і виховних завдань засобами української народної педагогіки.
65907. ПРОЛЕГОМЕНЫ В ФЕНОМЕНОЛОГИЧЕСКУЮ ТЕОРИЮ ЖАНРА 139 KB
  Целью данной работы является попытка прелиминарно обозначить некоторые черты жанра повести о княжеских смертях с помощью сравнительного анализа повести о смерти Игоря Ольговича в Ипатьевской летописи под 1147 г. Повесть о смерти Игоря содержит синтез нескольких точек зрения на события в ней изложенные.
65908. Сущность и специфика рынка недвижимости 28.39 KB
  Рынок недвижимости это сектор национальной рыночной экономики представляющий собой взаимосвязанную систему рыночных механизмов обеспечивающих создание эксплуатацию передачу и финансирование объектов недвижимости передачу и защиту прав и интересов на эти объекты а также механизмов обеспечивающих функционирование рынка недвижимости инфраструктуру.
65909. ЖАНРОВАЯ МОДЕЛЬ НОВЕЛЛЫ В «ПИСЬМАХ РУССКОГО ПУТЕШЕСТВЕННИКА» Н. М. КАРАМЗИНА 58 KB
  Вставные эпизоды в свою очередь либо строятся по образцу новеллы либо близки идиллии хотя две эти жанровые модели взаимосвязаны и взаимопроницаемы. Мы будем ориентироваться на структуру новеллы как на наиболее формально организованную и послужившую автору Писем одной из моделей повествования.