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

 

3.4.2. Зв'язок циклу з умовою повторення з розгалуженням

 

      З'ясуємо співвідношення між циклом з умовою повторення (Lw) і розгалуженням. Ці дві структури керування тісно пов'язані, причому провідна роль належить циклу. Застосування додаткових бульових змінних дозволяє звести розгалуження до циклу. Це зведення проведемо виходячи з таких початкових міркувань. По-перше, цикл, як і розгалуження, виконується чи ні в залежності від умови. По-друге, виконуючи цикл перший раз, можна впливати на умову так, щоб більше він не повторювався. А тепер формально.

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

 

      якщо b то Р кр.

Перепишемо її по іншому, змінивши тільки значення b

 

      якщо b то Р; b <- Хиб кр.

Остання захищена команда рівносильна наступному циклу

 

      поки b повт Р; b <- Хиб кц.

      Дійсно, за властивістю 3.4

 

       поки b повт Р; b <- Хиб кц =

     = якщо b то

          Р; b <- Хиб;

          поки b повт Р; b <- Хиб кц

       кр =

     = якщо b то

          Р; b <- Хиб;

          поки Хиб повт Р; b <- Хиб кц

       кр =

     = якщо b то Р; b <- Хиб кр.

 

      Ми довели

      Властивість 3.6. Нехай F - довільна умова. Якщо не враховувати значення змінної b, то захищена команда

 

       якщо F то Р кр

зводиться до циклу таким чином

 

       b <- F; поки b повт Р; b <- Хиб кц.¦

 

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

 

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

в ланцюг

 

       b <- F; c <- ¬F;

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

який за властивістю 2.4 перепишемо, використовуючи захищені команди

 

       b <- F; с <- ¬F;

       якщо b то Р кр;

       якщо с то Q кр.

      Як чинили раніше, замінимо захищені команди циклами

 

       b <- F; с <- ¬F;

       поки b повт Р; b <- Хиб кц;

       поки с повт Q; с <- Хиб кц.

      Ми довели

      Властивість 3.7. Якщо не враховувати значення змінних b і с, то розгалуження

 

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

можна перетворити в ланцюг що містить цикли

 

       b <- F; с <- ¬F;

       поки b повт Р; b <- Хиб кц;

       поки с повт Q; с <- Хиб кц.¦

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

      Висновок  3.1. Довільний алгоритм, відносно керування (С+IF+Lw), можна, використовуючи додаткові бульові змінні, виконати за допомогою керування (С+Lw).¦

 

3.4.3. Цикл з умовою закінчення

 

      Познайомимося з ще однією універсальною структурою керування.

      Нехай F - умова, Р - інструкція. Циклом з умовою закінчення

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

                    ¦ повторити Р до F ¦                   (Lu)

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

 

називається інструкція, яка визначається тотожністю

 

       повторити Р до F = Р; поки ¬F повт Р кц.

 

      Скорочене позначення: повт Р до F.

 

              Правило циклу з умовою закінчення:

    ¦     Виконується інструкція Р.

    ¦     Потім обчислюється значення F0 умови F.

    ¦     Якщо F0=Іст, то інструкція (Lu) припиняє свою роботу.

    ¦     Якщо F0=Хиб,  то цикл (Lu) продовжує виконуватися  по цьому

    ¦ же правилу.

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

 

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

       повт Р до F =

    =  Р;

       якщо ¬F то

          повт Р до F

       кр.

      Доведення. Перепишемо праву частину тотожності, використовуючи визначення (Lu)

 

       Р;

       якщо ¬F то

          Р;

          поки ¬F повт Р кц

       кр.

Тепер, скориставшись властивістю 3.4, виключимо розгалуження

 

       Р;

       поки ¬F повт Р кц.

Ще раз застосувавши визначення (Lu), отримаємо шукане

       повт Р до F.¦

 

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

      Властивість 3.9. Коли цикл (Lu) закінчиться, умова F буде виконуватись

       повт Р до F { F }.¦

 

      Наведемо приклад одного з найпростіших застосувань цієї властивості.

      Доповнення до прикладу 3.15. Умовою задачі було передбачено обмеження на можливі значення параметра х: 0<х<2. В той же час, алгоритм, складений в попередньому розділі, не містив перевірки вхідних значень х на допустимість. Тут можливі два принципово різних підходи. Перший гарантує правильний результат у всіх випадках, коли вхідні дані правильні. Порушення цих умов не контролюється і може призводити до будь-якого результату. Другий передбачає відповідну перевірку на відповідність вхідних даних. Оскільки обмеження на них відомі, обчислення не будуть проводитися, поки не будуть введені відповідні значення. Нижче наводиться цикл, який забезпечує саме такий підхід.

 

       повт

          взяти (х, eps)

       до (0<х) & (х<2) & (eps>0).

      Тепер правильність введених даних гарантована. Цей прийом будемо називати захищеним введенням.

      Повернемося ще раз до прикладу 3.17.

      Приклад 3.17 (продовження). Показати всі десяткові цифри заданого натурального числа n і обчислити їх суму.

      Трохи перетворюємо сам алгоритм DigitSum, що допоможе прийти  до більш компактного його запису. Розіб'ємо ініціалізацію S <- а на два присвоєння. Отримаємо ніщо інше, як цикл з умовою закінчення

 

       Р <- N; S <- 0;

       А <- Р mod 10; показати (А);

       S <- S+А; Р <- Р div 10;

       поки Р<>0 повт

          А <- Р mod 10; показати (А);

          S <- S+А; Р <- Р div 10;

       кц.

Остаточно маємо алгоритм

 

    Алгоритм DigitSum1 це

       змін N, Р, А, S: нат;

    поч

       повт

          взяти (N)

       до N>0;

       Р <- N; S <- 0;

       повт

          А <- Р mod 10; показати (А);

          S <- S+А; Р <- Р div 10;

       до Р=0;

       показати (S)

    ка.

 

      Доповнення до прикладу 3.14. Допустимо, що за умовою задачі n>0.

Розвернемо цикл

 

       { n>0 }

       Q <- Іст; k <- 0;

       поки k<n & Q повт

          k <- k+1; взяти (a);

          Q <- а>0

       кц

     =

       { n>0 }

       Q <- Іст; k <- 0;

       якщо k<n & Q то

          k <- k+1; взяти (a);

          Q <- а>0;

          поки k<n & Q повт

             k <- k+1; взяти (a);

             Q <- а>0

          кц

       кр.

Перевірку умови k<n & Q в розгалуженні можна опустити, як явно істинну, а тоді негайно застосовуємо визначення циклу (Lu)

 

       { n>0 }

       Q <- Іст; k <- 0;

       повт

          k <- k+1; взяти (a);

          Q <- а>0

       до k>=n V ¬Q.

Тепер присвоєння Q <- Іст стало просто зайвим. Остаточно маємо

 

    Алгоритм Positive2 це

       змін А: дійсн;

            K, N: нат; Q: бул;

    поч

       повт

          взяти (N)

       до N>0;

       K <- 0;

       повт

          K <- K+1; взяти (А);

          Q <- А>0

       до K=N V  ¦Q;

       показати (' Те, що всі числа >0, є', Q)

    ка.

 

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

 

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

       поки F повт Р кц =

    =  якщо F то

          повт Р до ¬F

       кр.

      Доведення. Застосуємо до правої  частини тотожності визначення циклу (Lu)

 

       якщо F то

          Р;

          поки F повт Р кц

       кр.

Даний вираз відразу згортається за властивістю 3.4 до циклу

 

       поки F повт Р кц,

що і потрібно було довести.¦

 

      Властивість 3.10 спільно з визначенням (Lu) дають можливість вибирати той або інший тип циклу за власним бажанням. Наступна теорема дає одне з можливих застосувань циклу з умовою закінчення.

 

      Теорема 3.4. Нехай а0, а1,. .., аk,. .. числова послідовність, задана співвідношенням (R1), G(k, х, у) - умова. Тоді

 

       { k=0 & у=с }

       повт

          х <- у;

          k <- k+1;

          у <- f(k, х, р)

       до G(k, х, у)

       { k=n & х=а   & у=а  & G(k, х, у) }.

                  k-1     k

 

      Доведення. Спочатку розглянемо ланцюг

       х <- с; k <- 1; у <- f(k, х, р);

       поки ¬G(k, х, у) повт

          х <- у;

          k <- k+1;

          у <- f(k, х, р)

       кц.

      За теоремою 3.3 можна затверджувати, що після виконання циклу буде справедлива умова

 

       { k=n & х=а   & у=а & G(k, х, у) }.

                  k-1     k

 

      Присвоєння х <- c замінимо ланцюгом у <- с; х <- у, а k <- 1 -

також парою k <- 0; k <- k+1. Отримаємо

 

       у <- с; k <- 0;

       х <- у; k <- k+1; у <- f(k, х, р);

       поки ¬G(k, х, у) повт

          х <- у;

          k <- k+1;

          у <- f(k, х, р)

       кц

       { k=n & х=а   & у=а & G(k, х, у) }.

                  k-1     k

Даний ланцюг інструкцій згортається  до необхідного вигляду безпосереднім застосуванням визначення циклу (Lu).¦

 

      Приклад 3.18. Знайти корінь рівняння

             3     2

            х  + 4x  + х - 6 = 0,

що міститься в інтервалі [0, 2] із заданою точністю e>0.

 

                              3     2

    Покладемо а=0, b=2, у(х)=х  + 4x  + х - 6.

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

       u  = a;

        0

                        у(u   )

                           n-1

       u  = u    - ----------------- * (b-u   )

        n    n-1    у(b)  - у(u   )        n-1

                               n-1

 

до виконання умови ¦u  - u   ¦ < e.

                     n    n-1

      Безпосереднє застосування теореми 3.4 приводить до ланцюга

 

       а <- 0; b <- 2;

       yb <- ((b+4)*b+1)*b-6;

       u <- a; k <- 0;

       повт

          uu <- u; k <- k+1;

          y <- ((u+4)*u+1)*u-6;

          u <- u-y*(b-u)/(yb-y)

       до abs(u-uu)<е.

      Змінна k при цьому дасть номер члена послідовності, при якому виконується умова закінчення циклу. Якщо цей номер неістотний, змінну k можна забрати.

 

3.4.4. Цикл з виходом за умовою

 

      Розглянемо ще один тип інструкції циклу.

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

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

                 ¦   цикл                   ¦

                 ¦      Р;                  ¦

                 ¦      якщо F то вихід;    ¦              (Le)

                 ¦      Q                   ¦

                 ¦   кц,                    ¦

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

 

рівносильна такій

 

       Р;

       поки ¬F повт

          Q; Р

       кц.

              Правило циклу з виходом:

    ¦     Виконується інструкція Р.

    ¦     Потім обчислюється значення F0 умови F.

    ¦     Якщо F0=Іст, то цикл (Le) припиняє свою роботу і пристрій

    ¦ керування приступає до виконання команди, наступної за циклом.

    ¦     Якщо F0=Хиб, то виконується інструкція Q і цикл (Le) продовжує

    ¦ виконуватися за цим же правилом.

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

 

      Як і в попередніх випадках, можна дати характерну властивість циклу з виходом.

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

       цикл                    Р; якщо ¬F то

          Р;                         Q;

          якщо F то вихід;  =        цикл

          Q                             P;

       кц                               якщо F то вихід;

                                        Q

                                     кц

                                  кр.

      Доведення. Застосувавши до правої частини тотожності визначення (Le), будемо мати

 

       Р; якщо ¬F то

             Q; Р;

             поки ¬F повт

                Q; Р

             кц

          кр.

Застосовуючи властивість 3.4, отримаємо

 

       Р; поки ¬F повт Q; Р кц,

звідки безпосереднім застосуванням визначення (Le) завершуємо доведення.¦

 

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

       поки F повт     цикл

          Р        =     Нічого;

       кц                якщо ¬F то вихід;

                         Р

                      кц.

      Доведення виходить з визначення циклу (Le) і властивості тотожної інструкції.¦

 

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

       повт      цикл

          Р  =     Р;

       до F        якщо F то вихід;

                   Нічого

                кц.¦

 

      Таким чином ми встановили, що всі три способи організації циклів за умовою взаємно рівносильні. Відповідні властивості дозволяють провести перетворення алгоритму з метою заміни одного циклу будь-яким іншим.

 

      Наступний приклад показує можливі застосування циклу з виходом.

      Приклад 3.19. На вхід поступають послідовно числа а0, а1, ..., аn. Кількість чисел зазделегідь невідома, але відомо, що всі вони, крім останнього, відмінні від нуля. Знайти їх суму і добуток.

      Аналогічно з теоремою 3.3 будуємо цикл (Lw)

 

       S <- 0; Р <- 1;

       взяти (a);

       поки а<>0 повт

          S <- S+a; Р <- Р*a;

          взяти (a)

       кц,

який відразу переписуємо в цикл з виходом (Le)

 

       S <- 0; Р <- 1;

       цикл

          взяти (a);

          якщо а=0 то вихід;

          S <- S+a; Р <- Р*a;

       кц.

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