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

 

1.2. Послідовне виконання дій

 Досі ми передавали виконавцеві інструкції, кожна з яких вимагала виконання однієї команди. Такі інструкції називають елементарними. Поки що нам відомі три з них: інструкція на виконання команди введення, або, коротше кажучи, інструкція введення; інструкція виведення і інструкція простого присвоєння, окремі випадки якої названі пересилкою, ініціалізацією і тотожною інструкцією.

 Розглянемо тепер правила, за допомогою яких елементарні команди об'єднуються у складені. Таких правил досить багато. У цілому їх прийнято називати структурами керування.

 Спочатку оговоримо деякий загальний принцип виконання складених інструкцій. Будемо вважати, що нарівні з вже розглянутими вузлами, а саме: пам'яттю, яка зберігає значення змінних; пристроєм введення, який готує числа для передачі ззовні в пам'ять; пристроєм виведення, який демонструє значення шуканих величин назовні, і операційним пристроєм, який виконує присвоєння, існує ще один, головний вузол, званий пристроєм керування.

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

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

 

1.2.1. Ланцюг команд

 Перша серед складених інструкцій - це інструкція послідовного виконання команд інакше ланцюг команд.

 Правило ланцюга:

 Нехай Р і R - інструкції (елементарні або складені), їх ланцюгом (послідовністю), складеним з Р і R, назвемо складену інструкцію

 

                               Р; R                         (C)

 

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

 Якщо яка-небудь з команд, що виконуються, закінчується відмовою, то сам ланцюг також дає відмову.

 

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

 

 Приклад 1.1. Записати інструкцію для обчислення квадратного тричлена

 у = ax2 + bx + c.

 Розв’язок. Розіб'ємо вираз квадратного тричлена на прості вирази. Для цього розставимо дужки

 у = ((ax) + b)х + c.

Визначимо u = ax; v = u+b; w = vx; у = w+c. Будемо поступово будувати ланцюг простих присвоєнь.

 а) Застосуємо правило (С) до присвоєнь u <- а*х і v <- u+b. Отримаємо перший ланцюг

 

 u <- а*х; v <- u+b.

 

 б) Знов застосуємо це ж правило до першого ланцюга і присвоєння w <- v*x. Маємо другий ланцюг

 

 u <- а*х; v <- u+b; w <- v*х.

 

 с) Ще раз застосувавши правило (С) до другого ланцюг і присвоєння

у <- w+c, остаточно отримаємо

 

 u <- а*х; v <- u+b; w <- v*х; у <- w+c. (1.1)

 

 Домовимося тепер про спосіб зображення стану виконавця A0. Він визначається множиною змінних Var, значеннями, які отримали змінні, і числами, встановленими в пристрої введення і виведення даних. Нехай Var = {x1, x2,. .., xn}. Стан виконавця A0 можна зобразити у вигляді такої таблиці

 

       ------------------------------------¬

       ¦        Mem         ¦      ¦       ¦

       +----+----+-----+----+      ¦       ¦

       ¦ х  ¦ х  ¦. .. ¦ х  ¦  In  ¦  Out  ¦

       ¦  1 ¦  2 ¦     ¦  n ¦      ¦       ¦

       +----+----+-----+----+------+-------+

       ¦ d  ¦ d  ¦. .. ¦ d  ¦  а   ¦   b   ¦

       ¦  1 ¦  2 ¦     ¦  n ¦      ¦       ¦

       L----+----+-----+----+------+--------

 

У прикладі 1.1 Var = {a, b, c, х, u, v, w, у}.

Визначимо значення змінних a, b, c і х відповідно через  А, B, C і X. Тоді виконання ланцюжка (1.1) можна зобразити такою таблицею

 

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

             ¦ а ¦ b ¦ c ¦ х ¦ u  ¦  v   ¦   w    ¦    у     ¦

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

             ¦ А ¦ В ¦ C ¦ X ¦ -  ¦  -   ¦    -   ¦    -     ¦

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

    u <- а*х ¦   ¦   ¦   ¦   ¦ AX ¦      ¦        ¦          ¦

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

    v <- u+b ¦   ¦   ¦   ¦   ¦    ¦ AX+В ¦        ¦          ¦

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

    w <- v*х ¦   ¦   ¦   ¦   ¦    ¦      ¦ AX2+BX ¦          ¦

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

    у <- w+c ¦   ¦   ¦   ¦   ¦    ¦      ¦        ¦ AX2+BX+C ¦

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

 Розглянемо інший ланцюг простих присвоєнь

 

 u <- х*х; v <- а*u; w <- b*х; t <- v+w; у <- t+c.

Він присвоює змінній у те ж значення, що і ланцюг (1.1) (доведіть). Складаючи інструкцію, корисно звертати увагу на її раціональність, маючи на увазі кількість дій і допоміжних змінних. Зрозуміло, що останній ланцюжок менш раціональний, ніж (1.1).

 Більш раціональною, ніж (1.1), буде послідовність

 

 у <- а*х; у <- у+b; у <- у*х; у <- у+c,

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

 

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

             ¦ а ¦ b ¦ c ¦ х ¦    у     ¦

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

             ¦ А ¦ В ¦ C ¦ X ¦    -     ¦

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

    у <- а*х ¦   ¦   ¦   ¦   ¦ AX       ¦

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

    у <- у+b ¦   ¦   ¦   ¦   ¦ AX+В     ¦

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

    у <- у*х ¦   ¦   ¦   ¦   ¦ AX2+BX   ¦

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

    у <- у+c ¦   ¦   ¦   ¦   ¦ AX2+BX+C ¦

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

 

Залишаючи більш детальне вивчення ланцюгів присвоєння для наступних розділів, розглянемо одну просту, але важливу для майбутнього властивість. Для розгляду властивостей алгоритмів важливе значення має їх порівняння. Дійсно, будь-яка інструкція змінює стан виконавця. В цьому сенсі інструкцію можна розглядати як функцію на станах виконавця. Дамо визначення рівносильності інструкцій.

Якщо інструкція P переводить стан виконавця S1 у стан S2, будемо це позначати так:

         P

      S1 ® S2

 

Дві інструкції Р і Q назвемо рівносильними (Р º Q), якщо " S1

         P           Q

      S1 ® S2     S1 ® S2,

тобто інструкції P та Q будь-який вихідний стан виконавця переводять в один і той же стан.

 

 Властивість 1.1. Для будь-якої інструкції Р справедлива тотожність

 Р º Р; Нічого º Нічого; Р.

 Доведення є очевидним наслідком визначення тотожньої інструкції, яка не міняє значення жодної з змінних. Тому виконання її після Р не змінить результатів, а перед Р - не порушить аргументів інструкції Р.¦

 

1.2.2. Лінійні алгоритми

 Домовимося тепер про загальний спосіб запису алгоритмів.

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

 

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

       ¦ Алгоритм А це                      ¦

       ¦    конст c1 = d1; ...; cn = dn;    ¦

       ¦    змін x1: t1; ...; xm: tm;       ¦

       ¦ початок                            ¦                (Alg)

       ¦    Р                               ¦

       ¦ кінець_алгоритму.                  ¦

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

 

 Тут А - ім'я алгоритму; c1,..., cn - імена констант; d1,..., dn - відповідно їх значення; x1,..., xm - імена змінних; t1, ..., tm - їх типи; Р - інструкція.

 Арифметичні алгоритми допускають три числових типи, які позначаються скорочено: рац, ціл, нат.

 Якщо алгоритм не використовує символьні позначення для констант, їх визначення може не бути.

 Допускаються скорочення: алг, поч, кін_алг, навіть, ка, а також

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

замість

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

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

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

 

      Алг Trinomial це

            змін a, b, c, х, у: рац;

            поч

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

                  у <- а*х; у <- у+b;

                  у <- у*х; у <- у+c;

                  { у = ax2 +bx +c }

                  показати (у)

            ка.

 

 Зауваження 1.1. У тексті алгоритму (1.2) присутній рядок, що не є інструкцією. Він взятий у фігурні дужки і його наявність ніяк не впливає на процес виконання алгоритму. Його призначення подвійне. По-перше, це пояснення (коментар), що роз'яснює призначення алгоритму, по-друге, цей запис можна трактувати як твердження: "Якими б не були значення змінних a, b, c і х, після виконання вказаних присвоєнь має місце виписане співвідношення у = ax2 +bx +c".¦

 Як приклад розглянемо обчислення значення тричлена у = x2 +3x - 2 при х = -1.

 

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

                   ¦ а ¦ b ¦ c ¦ х ¦ у ¦   In   ¦ Out ¦

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

    взяти (a, b, c)¦ 1 ¦ 3 ¦-2 ¦ - ¦ - ¦ 1 3 -2 ¦     ¦

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

    взяти (х)      ¦   ¦   ¦   ¦-1 ¦ - ¦  -1    ¦     ¦

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

     у <- а*х      ¦   ¦   ¦   ¦   ¦-1 ¦        ¦     ¦

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

     у <- у+b      ¦   ¦   ¦   ¦   ¦ 2 ¦        ¦     ¦

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

     у <- у*х      ¦   ¦   ¦   ¦   ¦-2 ¦        ¦     ¦

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

     у <- у+c      ¦   ¦   ¦   ¦   ¦-4 ¦        ¦     ¦

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

     показати (у)  ¦   ¦   ¦   ¦   ¦   ¦        ¦ -4  ¦

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

 

1.2.3. Узагальнене присвоєння

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

 Арифметичним назвемо вираз е, який визначається індуктивно:

 - якщо е - числова константа, то е - арифметичнитй вираз;

 - якщо е - змінна, то е – арифметичний вираз;

- якщо e1, e2 - арифметичні вирази, w - арифметична операція, то е = e1 w e2 - арифметичний вираз;

- якщо e1 - арифметичнийй вираз, то е = (e1) - арифметичний вираз.

 Арифметичний вираз, який приймає тільки цілі значення, будемо називати цілим, тільки натуральні - натуральним.

 Користуючись приведеним визначенням, побудуємо декілька прикладів арифметичних виразів: 1, (1+2), х, (х+1), ((х+1)+z), (1+(2*х)), ((2*х)+1), (2*(х+у)).

 Нашу увагу у приведених прикладах залучає невиправдана кількість дужок. Дужки насправді вказують порядок виконання дій у виразі. Якщо є упевненість в тому, що порядок дій буде зрозумілим, можна використовувати скорочений запис, замість повного. При цьому вважається, що повний запис негайно відновлюється за скороченому. Як завжди, будемо вважати, що множення і ділення - це дії більш старші, ніж додавання і віднімання. Дії одного старшинства при відсутності дужок будуть виконуватися зліва направо.

 У скороченому записі приведені вище приклади будуть мати більш привабливий вигляд: 1+2, х+1, х+1+z, 1+2*х, 2*х+1, 2*(х+у).

 Запис х/у*z при цьому буде читатися як (х/у)*z; у виразі типу х/(у*z) дужки відкинути не можна.

 Визначимо узагальнений арифметичний виконавець А, замінивши команду простого присвоєння командою присвоєння загального вигляду

 

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

                   ¦  х <- е,    ¦                           (As)

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

де х - змінна, е - арифметичний вираз.

 Команда простого присвоєння є окремим випадком узагальненого. Вираз, який допускається простим присвоєнням, будемо називати також простим, інакше складеним. Вираз, задаий константою або змінною, назвемо тривіальним.

 Для виконавця А, обчислення квадратного тричлена запишеться одним присвоєнням

 

 у <- а*х*х + b*х + c,

яке внаслідок прийнятих скорочень повністю читається так:

 

 у <- ((((а*х)*х) + (b*х)) + c)

- п'ять множень і додавань.

 Інший спосіб розуміється під записом

 

 у <- (а*х + b)*х + c.

Запишіть його повний вигляд і підрахуйте кількість дій.

 Визначимо правило присвоєння (As). Воно виконується шляхом попереднього перетворення у ланцюг простих присвоєнь. Перетворення залежить від множини змінних Var, що використовуються виконавцем. Нехай V=Var. Визначимо шуканий ланцюг як Seq[V, х, е].

 Можливі такі випадки.

1)    Присвоєння х <- е просте. Тоді перетворення тотожнє

2)     

 Seq[V, х, е] = х <- е,

додаткових змінних в цьому випадку не потрібно.

 У інших трьох випадках вираз е - складений.

 2) Вираз е має вигляд e' w u, де u - тривіальний вираз,

а e' - ні. Тоді

 

 Seq[V, х, е] = Seq[V', z, e'];

 х <- z w u,

де V' = V È {z}, z - змінна, яка не належить V.

 3) Вираз е має вигляд u w e', де u – тривіальний вираз,

e' - ні. Знову

 

 Seq[V, х, е] = Seq[V', z, e'];

 х <- u w z,

де V' = V È {z}, z - змінна, яка не належить V.

 4) Вираз е складений з двох нетривіальних виразів е=e1 w e2. Тоді

 

 Seq[V, х, е] = Seq[V', z1, e1];

 Seq[V', z2, e2];

 х <- z1 w z2,

де V' отримане з V приєднанням двох додаткових змінних z1 і z2, які не належать V: V' = V È {z1, z2}.

 5) Вираз е є виразом у дужках е=(e1). Тоді

 

 Seq[V, х, е] = Seq[V, x, e1]

 

 Приклад 1.2. Застосуємо перетворення Seq до присвоєння

 у <- (а*х+b)*х+c.

 

Нехай V0 = {a, b, c, х, у}.

 

Seq[V0, у, (а*х+b)*х+c] = Seq[V1, r, (а*х+b)*х];

 у <- r+c;

де V1 = V0 È {r}.

 

 Seq[V1, r, (а*х+b)*х] = Seq[V2, s, а*х+b];

 r <- s*х;

де V2 = V1 È {s}.

 

 Seq[V2, s, а*х+b] = Seq[V3, t, а*х];

 s <- t+b;

де V3 = V2 È {t}.

 Нарешті Seq[V3, t, а*х] = t <- а*х.

 Остаточно маємо

 

 Seq[V0, у, (а*х+b)*х+c] = t <- а*х; s <- t+b;

 r <- s*х, у <- r+c.

 Зазначимо, що приведене правило перетворення не економить змінних.

 Дамо тепер правило присвоєння для узагальненого арифметичного виконавця.

 

 Правило узагальненого присвоєння:

 Нехай V множина змінних, використаних виконавцем до цього. Тоді присвоєння х <- е виконується як ланцюг Seq[V, х, е].

 

 Узагальнений арифметичний виконавець А допускає ще одну інструкцію

 

 показати (е),

де е - нетривіальний вираз, як скорочення для ланцюга

 

 t <- е; показати (t),

де t - допоміжна змінна.

 Приклад 1.3. Будемо вважати, що виконавець А наділений умінням знаходження квадратного кореня з числа x. Цю дію запишемо як sqrt(х). Тоді алгоритм обчислення періоду коливань маятника довжини l:

                ____

       t = 2 p Ö l/g,

 

де g = 981 см/с2 - прискорення вільного падіння, можна представити

у вигляді:

 

 Алгоритм Period це

 конст g = 981; Pi = 3.14159265;

 змін l, t: рац;

 поч

 взяти (l);

 t <- 2*Pi*sqrt(l/g);

 показати (t)

 ка.

 

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