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

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

 ,


 

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

30720. Общее и особенное в политике британских консерваторов и лейбористов в 1920-е гг 23 KB
  Консервативная партия Великобритании одна из двух ведущих политических партий страны образовавшаяся в 1867 году на базе партии тори. К 1930му году в Великобритании стала ясной гибель радикального социализма тогда на первый план выдвинулся либерализм который настаивал на прямом вмешательстве государства в экономику и передаче государству целого ряда социальных функций. Внутреннюю политику консерваторов Великобритании 1920 1930х годов можно охарактеризовать как стремление сохранить существующую ранее универсальность и...
30721. Основные этапы первой мировой войны. Факторы поражения германо-австрийского блока 27.5 KB
  В июле 1914 г Германия и Австровенгрия начинают первую мировую войну. Германия хотела сначала вывести из строя Францию чтобы прекратить борьбу на два фронта: Западном и Восточном. 1 этап вторжение в Бельгию где Германия потерпела поражение: в Восточной Пруссии Германия воевала с русскими армиями; в Галиции и Польше где победы достались русским. Германия и АвстроВенгрия были экономически истощены под влиянием революций в России среди военных германии и Австрии усилилась антивоенная агитация народ устал от...
30722. «Новый курс» Результата и его историческое значение 24.5 KB
  Его основная цель состояла в оздоровлении экономики и восстановления доверия граждан к государству. Политика Рузвельта получила название Новый курс который он восстановил государственное регулирование экономики и социальных отношений. Законом об оздоровлении национальной экономики вся промышленность была разделена на 17 групп по отраслям и регулировалась нормативными актами кодексами чести определявшими объем выпуска товаров уровня заработной платы распределение рынков сбыта продолжительность рабочего времени и др....
30723. Эволюция и крах бюрократических режимов в стране ЦЮВЕ 26.5 KB
  было сформировано коалиционное правительство в ГДР. Чехословакия и ГДР несколько условно могут быть отнесены к государствам с довольно высоким уровнем развития Польша Венгрия Хорватия и Словения страны среднего развития а Болгария Румыния четыре другие республики бывшей Югославии Сербия Черногория Македония Босния и Герцеговина Албания низкого. По решению парламентов ГДР и ФРГ с 1 июля 1990 г. ГДР прекратила свое существование вместо нее появились пять новых федеральных земель ФРГ.
30724. Изоляционизм США термин использовавшийся с середины 19 в. 25 KB
  Изоляционизм США термин использовавшийся с середины 19 в. для обозначения направления во внешней политике США в основе которого лежит идея невмешательства в европейские дела и вообще в вооруженные конфликты вне американского континента. складывались под влиянием ряда факторов: географическая обособленность Американского континента создание в США ёмкого внутреннего рынка способствовавшего тому что значительная часть буржуазии мало интересовалась заокеанской экспансией расширение за счет др.
30725. Великобритания выбор новой модели развития в условиях кризиса и распада колониальной империи 28.5 KB
  Черчилль предложил емкую формулировку такого мировидения концепцию трех великих кругов центром пересечения которых считалась Британия. Чем глубже пускала корни биполярная система мира тем активнее Британия искала себе место в условиях противостояния двух сверхдержав. в 19401950е годы Британия все еще ощущала себя империей однородным государством и державой глобального масштаба.
30726. Ялтинская и Потсдамская конференции глав правительств СССР, США и Великобритании. (1945) 22.5 KB
  Участвовали: Сталин СССР Черчилль Великобритания Рузвельт США. Основные решения: 1 Германия делилась на 4 оккупационные зоны СССР Франция Англия США. 3 Согласия СССР вступить в войну с Японией через 3 месяца после капитуляции Германии.
30727. Кризис неолиберализма в США. Переход к неконсервативной модели развития ГМК 26 KB
  Главный замысел неолиберализма снижение регулирующей роли государства в экономике При общем экономическом подъеме неолиберальный курс обусловил неустойчивость и нестабильность развития США Причиной экономического роста в США стали специфические внутренние и внешние факторы конца ХХ в. Экономическое развитие США последнего десятилетия окончательно подтверждает: неолиберальная перестройка это путь к строительству эффективной капиталистической экономики. Неолиберальный режим вызвал крайне нестабильный экономический рост в США в 90е...
30728. Политика «невмешательства» (1935 – 1937 гг.). Мюнхенское соглашение 1938 г. и его значение для судеб мира 24.5 KB
  СССР готово было прийти на помощь Чехословакии в 1935 г у СССР и Чехословакии был договор о взаимопомощи при поддержке Франции у которой с СССР был такой же договор. Но французское правительство не поддержало СССР т. Попытки англофранцузской дипломатии умиротворить нацистов без участи СССР оказались тщетными и тогда Англия и Франция вынуждены были предоставить гарантии безопасности возможным жертвам агрессии Польше Румынии Греции и начали секретные переговоры с Советским союзом. провалились изза недоверия...