[ЗМІСТ]     [Далі]       [Назад]      [Початок розділу]

 

2.2. Бульові інструкції

2.2.1. Бульове присвоєння

 

Доповнимо виконавець арифметичних алгоритмів засобами обчислення умов. Для цього розширимо можливі типи даних бульовим типом, вважаючи, що бульова змінна q, визначена як

 

       змін q: бул;

приймає значення з області істинності B2.

Пам'ять Mem доповнимо клітинками, здатними зберігати бульові значення Іст і Хиб, пристрої введення і виведення - здатністю вводити і виводити ці величини.

    Наприклад, показати (х>0 & у>0).

    Операційний пристрій Op, будемо називати його тепер арифметико-бульовим пристроєм, додатково уміє:

    1) обчислювати відношення Rel={ =, <>, <, >, <=, >= };

    2) обчислювати бульові операції V, & і Ø.

Арифметичне присвоєння, вивчене раніше, тепер можна доповнити бульовим

 

       q <- F,

де q - бульова змінна; F - умова.

 

Правило виконання бульового присвоєння дослівно повторює правило виконання складеного арифметичного присвоєння.

    Приклади: q <- Ø q;

              r <- х>0 & у>0.

 

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

 

Приклад 2.1. Скласти алгоритм перевірки належності точки координатної площини, заданої своїми координатами (х, у), другому квадранту.

Результатом виконання такого алгоритму виконавцем AB потрібно вважати деякий булів вираз. Причому значення Іст, інтерпретується як відповідь  "так, точка (х, у) належить другому квадранту", а значення Хиб - як відповідь  "ні, точка (х, у) не належить квадранту, що розглядається". Отримуємо алгоритм:

 

    Алгоритм Two1 це

       змін х, у: дійсн;

    поч

       взяти (х, у);

       показати (х<=0 & у>=0)

    ка.

 

2.2.2. Розгалуження

 

Наступний крок полягає у побудові структури керування подібної умовному виразу. Нехай F - булів вираз, Р, Q - інструкції. Нову інструкцію визначимо за схемою

 

                       ¦ Р, якщо F = Іст;

       IF (F, Р, Q) = <

                       ¦ Q, якщо F = Хиб.

 

    Назвемо її розгалуженням і визначимо

       ----------------------------------------------

       ¦ якщо F то Р інакше Q кінець_розгалуження,  ¦                 (IF)

       L---------------------------------------------

Розширимо пристрій керування виконавця AB, визначимо його тепер як (C+IF), правилом розгалуження.

 

Правило розгалуження:

    ¦     Виконання розгалуження здійснюється у два кроки.

    ¦     На першому виконавець обчислює значення F0 умови F. На

    ¦ другому пристрій керування виконує інструкцію Р, якщо

    ¦ F0 = Іст, або інструкцію Q, якщо F0 = Хиб.

    L---------------------------------------------------------------

Помітимо, що у разі невизначеності умови F розгалуження також невизначене, оскільки вже на першому кроці виконавець дасть відмову.

    Службові слова кінець_розгалуження будемо скорочено писати кр.

    Наприклад, інструкція

 

       якщо х>0 то у <- х інакше у <- -x кр

надає змінній у значення у=¦х¦, а інструкція

 

       якщо х<0 то у <- -1 інакше

          якщо х=0 то у <- 0 інакше у <- 1 кр

       кр

- значення у=sign(х).

    Останнє розгалуження є прикладом каскадного розгалуження

вигляду

 

       якщо F1 то P1 інакше

       якщо F2 то P2 інакше

       ...................

       якщо Fn то Pn інакше

          Q

       кр кр ... кр,

яке скорочено будемо записувати так

 

       якщо F1 то P1

       інякщо F2 то P2

       ...................

       інякщо Fn  то Pn

       інакше Q

       кр.

Розгалуження

 

       якщо F то Р інакше Нічого кр

будемо записувати у скороченій формі

 

       якщо F то Р кр                                      (2.2)

і називати захищеною інструкцією, а умову F - її охороною.

 

    Відмітимо основні властивості розгалужень.

 

    Властивість 2.8.

       a) якщо Іст то Р кр º Р;

       b) якщо Хиб то Р кр º   Нічого.

 

    Властивість 2.9. Якщо інструкція Р не змінює значень  аргументів

що входять в умову F, яка визначена, то

       якщо F то Р інакше Q кр º

     º якщо F то Р кр; якщо Ø F то Q кр.

    Доведення. Нехай F = Іст. Тоді за правилом розгалуження

       якщо Іст то Р інакше Q кр = Р.

З іншого боку за властивістю 2.8

       якщо Іст то Р кр; якщо Хиб то Q кр = Р; Нічого,

тобто також Р.

    Другий випадок розглядається аналогічно.¦

    Наслідок 2.2.

       a) якщо Іст то Р інакше Q кр º Р;

       b) якщо Хиб то Р інакше Q кр º Q.

 

    Властивість 2.10. Справедлива тотожність

       якщо F то Р інакше Q кр º

º      якщо ØF то Q інакше Р кр.

 

    Властивість 2.11. Якщо інструкція Р не змінює значень аргументів, що входять в умову F, яка визначена, то

       якщо F то Р; R інакше P; Q кр º

     º P; якщо F то R інакше P; Q кр.

 

    Властивість 2.12. Справедлива тотожність

       якщо F то Р; R інакше Q; R кр º

º      якщо F то P інакше Q кр; R.

 

      Розгалуженим алгоритмом назвемо алгоритм, тілом якого є інструкція P, вигляд якої визначається індуктивно:

1)    P – ланцюг команд присвоєння, введення та виведення;

2)    P – розгалуження;

3)    P = P1; P2, де P1, P2 – ланцюг або розгалуження.

 

      Розгалужений алгоритм

 

       взяти (a, b);

       якщо а>b то у <- а

       інакше у <- b кр;

       { у = max(a, b) }

       показати (у)

може слугувати прикладом тіла алгоритму обчислення найбільшого з двох чисел а і b.

      Розглянемо декілька прикладів.

 

      Приклад 2.2. Знайти у = max(a, b, c).

      Користуючись умовним виразом, запишемо, що

 

       max(a, b) = IF (а>b, a, b).

Тоді max(a, b, c) = max(max(a, b), c). Отже для знаходження y необхідно послідовно обчислити дві величини

 

       y1 = max(a, b);

       y2 = max(y1, c),

для чого досить однієї змінної y. Отримуємо алгоритм

 

       взяти (a, b, c);

       якщо а>b то у <- а

       інакше у <- b кр;

       якщо y>c то y <- y

       інакше y <- c кр;

       показати (y).

 

      Помітимо, що алгоритм, що обчислює одну і ту ж величину, можна записати декількома рівносильними способами. Так, наприклад, останнє з розгалужень алгоритму 2.2 можна переписати так:

 

       якщо y>=c то y <- y

       інакше y <- c кр.

      За властивістю 2.10 це розгалуження записується у вигляді

 

       якщо y<c то y <- c

       інакше y <- y кр.

      Помітимо також, що інструкція у <- у є тотожною інструкцією, що не змінює стан виконавця.Тоді використовуючи захищену інструкцію (2.2) алгоритм 2.2 можна переписати у вигляді

 

       взяти (a, b, c);

       якщо а>b то y <- а

       інакше y <- b кр;

       якщо y<c то y <- c кр;

       показати (y).

 

      У алгоритмах зручно застосовувати розгалуження в комплексі з бульовими змінними. Повернемося до прикладу 2.1. Для отримання словесної відповіді на поставлене питання служить алгоритм

 

    Алгоритм Two2 це

       змін х, у: дійсн; l: бул;

    поч

       взяти (х, у);

       l <- х<=0 & у>=0;

       якщо Øl то показати (' не ') кр;

       показати (' належить')

    ка.

 

    Приклад 2.3. З'ясувати, який випадок має місце:

    а) значення а і b мають один і той же знак;

    б) знаки протилежні або одне із значень дорівнює нулю.

      Очевидно, випадок а) відповідає істинності виразу а*b>0. Дійсно, а*b>0 = (а>0 & b>0) V (а<0 & b<0). Розглянемо його заперечення Ø(а*b>0) = а*b<=0 = (а*b<0) V (а*b=0) = (а<0 & b>0) V (а>0 & b<0) V (а=0) V (b=0), що відповідає випадку б). Отримуємо алгоритм:

 

    Алгоритм Znak це

       змін a, b: дійсн; l: бул;

    поч

       взяти (a, b);

       l <- а*b>0;

       показати (' Знаки ');

       якщо l то

          показати (' однакові')

       інакше

          показати (' протилежні або а=0, або b=0')

       кр

    ка.

 

Приклад 2.4. Скласти алгоритм дослідження системи двох алгебраїчних рівнянь

 

       а *х + b *у = c ,

        1      1      1

       а *х + b *у = c.

        2      2      2

 

Користуючись відомими фактами з алгебри запишемо

 

    Алгоритм Sys2 це

       змін a1, a2, b1, b2, c1, c2, D, Dx, Dy: дійсн;

             Comp, Def: бул;

    поч

       взяти (a1, a2, b1, b2, c1, c2);

 

       D <- a1*b2-a2*b1;

       Dx <- c1*b2-c2*b1; Dy <- a1*c2-a2*c1;

       якщо D=0 то

          якщо Dx=0 & Dy=0 то

             Comp <- Іст; Def <- Хиб

          інакше

             Comp <- Хиб

          кр

       інакше

          Comp <- Іст; Def <- Іст

       кр;

       якщо Comp то

          показати (' Система сумісна ');

          якщо Def то

             показати (' і визначена')

          інакше

             показати (', але не визначена')

          кр

       інакше

          показати (' Система не сумісна')

       кр

    ка.

 

    Приклад 2.5. Обчислити значення функції

 

               |g (х), х < 0,

       f(х) = <  1

               |g (х), х >= 0,

                 2

де

             |2x+1,  х > -0,5,               |- х+1, х < 1,

    g (х) = <                       g (х) = <

     1       |-2x-1, х >= -0,5,      2       |х-1,  х >= 1.

 

Тіло алгоритму обчислення значення функції f(х) можна записати таким чином:

 

       взяти (х);

       якщо х>-0.5 то g1 <- 2*х+1

       інакше g1 <- -2*х-1 кр;

       якщо х<1 то g2 <- -x+1

       інакше g2 <- х-1 кр;

       якщо х<0 то f <- g1

       інакше f <- g2 кр;

       показати (f)

 

або враховуючи вигляд функцій g1 (х) і g2 (х) так

 

       взяти (х);

       g1 <- 2*х+1;

       якщо х<=-0.5 то

          g1 <- -g1

       кр;

       g2 <- х-1;

       якщо х<1 то

          g2 <- -g2

       кр;

       якщо х<0 то f <- g1

       інакше f <- g2 кр;

       показати (f).

 

      Запишемо функцію f(х) іншим способом, а саме

 

              ¦ -2x-1, х <= -0,5,

              ¦  2x+1, -0,5 < х < 0,

       f(х) = <

              ¦  -х+1, 0 <= х < 1,

              ¦   х-1, х >= 1.

 

Для складання алгоритму в подібній ситуації, доцільно користуватись наступним твердженням про каскадні розгалуження.

 

    Теорема 2.1. Справедливе твердження

 

       { х = а }

 

       якщо F (х) то у <- g (х)

             1             1

       інякщо F (х) то у <- g (х)

               2             2

       ........................

       інякщо F (х) то у <- g (х)

               n             n

       інакше           у <- h(х)

       кр

 

       { у = f(a) },

де

              ¦ g (х), якщо F (х) = Іст;

              ¦  1           1

              ¦ g (х), якщо ØF  (х)&F (х) = Іст;

              ¦  2            1     2

       f(х) = <.  .............................

              ¦ g (х), якщо Ø(F (х) V. .. V F   (х))&F (х) = Іст;

              ¦  n             1             n-1      n

              ¦ h(х),  якщо F (х) V. .. V F (х) = Хиб.

              ¦              1             n

 

    Доведення. Визначимо Q (х) =Ø(F (х)V.. V F   (.х))&F (х),

                          k        1          k-1       k

k=2,..., n, Q (х) = F (х). Очевидно, що

             1       1

 

       Q (х) & Q (х) = Хиб при i<>k.

        i       k

Неважко довести також, що

 

       Q (х) V Q (х) V.. V. Q (х) = F (х) V F (х) V.. V. F (х).

        1       2            n       1       2            n

Отже при довільному х істинним може бути не більш, ніж одна з умов Qi (х). Нехай Qk (a) = Іст при деякому k. Тоді

 

        Ø(F (a) V.. V. F   (a))&F (a) = Іст

           1            k-1      k

і f(a) = g (a).

          k

    З іншого боку за властивостю кон’юнкції

 

        Ø(F (a) V.. V. F   (a)) = Іст, F (a) = Іст.

           1            k-1             k

За властивістю заперечення

 

       F (a) V.. V. F   (a) = Хиб

        1            k-1

і за властивістю диз’юнкції

 

       F (a) = Хиб,.  .. F   (a) = Хиб.

        1                 k-1

Тоді за правилом розгалуження буде виконано присвоєння

у <- g (х), отже у = g (a), що і було потрібно.

      k               k

      Тепер допустимо, що Q (a) = Q (a) = ... = Q (a) = Хиб, тоді

                           1       2             n

Q (a) V ... V Q (a) = Хиб, а отже і F (a) V.. V F (a) = Хиб.

 1             n                     1          n

Маємо f(a) = h(a).

    Далі за властивістю диз’юнкції F (a) = Хиб, ..., F (a) = Хиб,  а тоді

                                    1                 n

за правилом розгалуження буде виконано присвоєння у <- h(х), отже у = h(a).¦

 

      Використовуючи цю теорему складемо наступний алгоритм

 

    Алгоритм Fx це

       змін х, у: дійсн;

    поч

       взяти (х);

       якщо х<=-0.5 то

          у <- -2*х-1

       інякщо х>=1 то

          у <- х-1

       інякщо х<0 то

          у <- 2*х+1

       інакше { 0<=х<1 }

          у <- -x+1

       кр;

       { у = f(х) }

       показати (у)

    ка.

цілком вільний від додаткових змінних.

 

    Приклад 2.6. Обчислити значення виразу

 

             ¦ max(х, у+5),     х > у,

         z = <

             ¦ min(х+1, у2, 3), х <= у.

 

Запишемо алгоритм розв’язку задачі у вигляді:

 

    Алгоритм Zxy це

       змін х, у, z, u: дійсн;

    поч

       взяти (х, у);

       якщо х>у то

          z <- у+5;

          якщо х>z то z <- х кр

       інакше { х<=у }

          z <- х+1;

          якщо z>3 то z <- 3 кр; { писати інакше не можна }

          u <- у*у;

          якщо z>u то z <- u кр

       кр;

       показати (z)

    ка.

    Приклад 2.7. Скласти алгоритм обчислення розв’язку і кількості розв’язків квадратного рівняння ax2 + bx + c = 0.

      Відомо, що квадратне рівняння має нескінченну кількість розв’язків, якщо а=b=c=0. Не має розв’язків, якщо а=b=0 і c<>0. Має один розв’язок, якщо b<>0, а=0 і два розв’язки, якщо а<>0. В останньому випадку, корні рівняння можуть бути як дійсними, так і уявними.

      Тому, алгоритм може мати вигляд:

 

    Алгоритм Kv_Ur це

       змін a, b, c, d, z, Xr, Yr, Xi, Yi: дійсн;

    поч

       взяти (a, b, c);

       якщо а=0 то

          якщо b=0 то

             якщо c=0 то

                показати ('Рішень нескінченна кількість')

             інакше { а=b=0, c<>0 }

                показати ('Рішень немає')

             кр

          інакше { а=0, b<>0 }

             Xr <- -c/b;

             показати ('Рішення одне = ', Xr)

          кр

       інакше { а<>0 }

          показати ('Два рішення: ');

          z <- 2*a; Xr <- -b/z;

          d <- b*b-2*z*c;

          якщо d>=0 то

             d <- sqrt(d);

             Yr <- Xr-d/z; Xr <- Xr+d/z;

             показати (' 1: ', Yr);

             показати (' 2: ', Xr)

          інакше { d<0 }

             d <- sqrt(- d);

             Xi <- d/z; Yi <- -Xi; Yr <- Xr;

             показати (' 1: ', Yr,' ', Yi,' *i');

             показати (' 2: ', Xr,' ', Xi,' *i')

          кр

       кр

    ка.

2.2.3. Порівняння розгалужених алгоритмів

 

      Аналогія між розгалуженням і умовним виразом узагальнюється далі, якщо поняття рівносильности інструкцій доповнити поняттям розширення (звуження) інструкцій

 

       P Ì Q (Q É P).

 

      Якщо кожний раз, коли інструкція Р виконується успішно (без відмови) успішно виконується також Q, причому дає той же результат, то Q називається розширенням інструкції Р (Р називається звуженням інструкції Q).

 

    Властивість 2.13.

 

       якщо F то Р інакше P кр Ì P

 

    Властивість 2.14. Інструкція

 

       якщо F  & F  то Р інакше Q кр                        (2.3)

             1    2

 

служить звуженням для інструкції

 

       якщо F  то

             1

          якщо F  то Р інакше Q кр                          (2.4)

                2

       інакше

          Q

       кр.

    Доведення. Спочатку розглянемо випадки  визначеності обох умов F1 і F2.

    Нехай F  = Хиб, тоді F  & F  = Хиб. Інструкція (2.3) переходить в

           1              1    2

 

       якщо Хиб то Р інакше Q кр = Q.

Інструкція (2.4) - аналогічно

 

       якщо Хиб то

          якщо F  то Р інакше Q кр                          (2.5)

                2

       інакше

          Q

       кр = Q.

 

    Нехай F  = Іст. Можливі два випадки. Умова F  = Іст,  тоді  (2.3)

           1                                    2

переходить в

 

       якщо Іст & Іст то Р інакше Q кр =

     = якщо Іст то Р інакше Q кр = Р;

а з інструкції (2.4) отримаємо

 

       якщо Іст то

          якщо Іст то Р інакше Q кр

       інакше

          Q

       кр =

     = якщо Іст то Р інакше Q кр = Р.

Нехай тепер F  = Хиб. Структура (2.3) переходить в

             2

 

       якщо Іст & Хиб то Р інакше Q кр =

     = якщо Хиб то Р інакше Q кр = Q;

а інструкція (2.4) - в

 

       якщо Іст то

          якщо Хиб то Р інакше Q кр

       інакше

          Q

       кр =

     = якщо Хиб то Р інакше Q кр = Q.

Тепер розглянемо випадки невизначеності умов. Якщо не визначена умова F1, то не визначені обидві інструкції.

      Залишається випадок невизначеності умови F2 при визначеності умови F1. Перша інструкція в цьому випадку не визначена. Визначеність другої залежить від F1. Якщо F1 = Іст, то (2.4) знову не визначена. Якщо ж F1 = Хиб, то (2.4), як показує (2.5), перетворюється в Q.

      Отже (2.3) Ì (2.4), що і потрібно було довести.¦

 

      Аналогічно доводиться справедливість

      Властивість 2.15. Інструкція

 

       якщо F  V F  то Р інакше Q кр                        (2.6)

             1    2

 

служить звуженням для інструкції

 

       якщо F  то

             1

          Р

       інакше

          якщо F  то Р інакше Q кр

                2

       кр.

 

      Зауваження 2.2. Вводячи додаткові змінні q1 і q2 можна відмінити розширення, тобто довизначення, інструкцій (2.3) і (2.6). Наприклад, ланцюг

 

       q1 <- F1; q2 <- F2;

       якщо q1 то

          якщо q2 то Р інакше Q кр

       інакше

          Q

       кр

равносильний наступному

 

       q1 <- F1; q2 <- F2;

       якщо q1 & q2 то Р інакше Q кр.¦

 

      Будова виконавця AB приведена на мал. 2.1. Подвійними лініями зображена передача даних між компонентами.

 

                 ----------                               ----------

                 ¦   In   ¦==============================>¦        ¦

                 L---------                               ¦        ¦

                     ^              -----------           ¦        ¦

                     ¦  взяти(х)    ¦__ Op __ ¦           ¦        ¦

                     ¦              ¦ А:      ¦           ¦        ¦

 1) Р; Q         ----------         ¦ + - * / ¦           ¦        ¦

                 ¦        ¦ х <- е  ¦ div mod ¦==========>¦        ¦

 --------------->¦ C + IF ¦-------->¦---------¦           ¦__Mem__ ¦

                 ¦        ¦         ¦ B:      ¦           ¦        ¦

 2) якщо F то P  L---------         ¦  V & ¬  ¦<==========¦        ¦

                     ¦              ¦---------¦           ¦ N Z Q  ¦

    інакше Q кр      ¦              ¦ AB:     ¦           ¦        ¦

                     ¦              ¦ =  <  > ¦           ¦ В      ¦

                     ¦  показати(х) L----------           ¦  2     ¦

                     v                                    ¦        ¦

                 ----------                               ¦        ¦

                 ¦  Out   ¦<==============================¦        ¦

                 L---------                               L---------

 

                        Мал. 2.1.

[ЗМІСТ]     [Далі]       [Назад]      [Початок розділу]