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

 

3.6. Цикли з лічильником

 

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

      Візьмемо арифметичну прогресію з цілим початковим членом b і позитивною різницею d > 0

 

       а  = b,                                             (AP)

        0

       а  = а   + d, k=1,2,...

        k    k-1

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

      Канонічним зростаючим циклом з лічильником або коротше канонічно зростаючим циклом назвемо інструкцію

 

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

                  ¦  для k<-b до с через d повт  ¦

                  ¦     Р                        ¦            (Lc+)

                  ¦  кц,                         ¦

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

 

яка служить скороченням для розгалуження

 

       якщо b<=с то

          k <- b;

          цикл

             Р;

             якщо k>c-d то вихід;

             k <- k+d

          кц

       кр.

 

              Правило зростаючого циклу з лічильником:

    ¦     Якщо початкове значення b лічильника циклу k більше кінцевого

    ¦ значення с, то цикл (Lc+) рівносильний інструкції Нічого.

    ¦     У іншому випадку виконується ланцюг:

    ¦ 1. Лічильнику циклу k присвоюється початкове значення b.

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

    ¦ 3. Обчислюється значення F умови k>c-d.

    ¦ 4. Якщо F=Іст, то цикл (Lc+) завершує свою роботу.

    ¦    Якщо F=Хиб, то значення лічильника k збільшується на величину

    ¦ приросту d і пристрій керування знову переходить до виконання

    ¦ пункту 2 даного правила.

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

 

      Таким чином, лічильник циклу пробігає послідовно всі члени аi арифметичної прогресії, якщо вони існують, які задовольняють нерівності аi<=c. Причому останнє значення k рівне найбільшому серед них. Якщо ж таких членів послідовності не існує, то маємо

      Властивість 3.14. Якщо с<b, то цикл (Lc+) вироджується в інструкцію Нічого.

      Доведення безпосередньо витікає з властивості 2.8.¦

      Канонічний зростаючий цикл називається суцільним, якщо d = 1. Позначення (L1+). У цьому випадку визначення кроку циклу "через 1" можна опустити:

 

       для k<-b до с повт

          Р

       кц.

      Зауваження 3.7. Умову виходу з суцільного циклу можна замінити рівносильною k=с.¦

      Властивість 3.15. Якщо b<=с, то цикл (L1+) рівносильний арифметичному циклу

 

       k <- b-1;

       повт c-b+1 раз

          k <- k+1;

          Р

       кц.

      Доведення. Присвоєння k <- b замінимо ланцюгом k <- b-1; k <- k+1. Перепишемо визначення (Lc+), враховуючи зауваження 3.7 і очевидну тотожність b<=с = Іст:

 

       k <- b-1; k <- k+1;

       цикл

          Р;

          якщо k=с то вихід;

          k <- k+1

       кц,

звідки отримуємо

 

       k <- b-1;

       поки k<>с повт

          k <- k+1;

          Р

       кц.

Неважко підрахувати, що кількість повторень останнього циклу складає c-b+1.¦

 

      Приклад 3.20. Обчислити факторіал у=n! (див. приклад 3.3).

       у <- 1;

       для k<-1 до n повт

          у <- у*k

       кц.

 

      Приклад 3.21. Обчислити добуток всіх непарних чисел від  1 до n.

       у <- 1;

       для k<-1 до n через 2 повт

          у <- у*k

       кц.

 

      Повернемося до арифметичної прогресії вигляду (AP) з цілим додатнім членом b і на цей раз від’ємною різницею d<0.

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

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

 

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

                  ¦  для k<-b до с через d повт  ¦

                  ¦     Р                        ¦            (Lc-))

                  ¦  кц,                         ¦

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

 

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

 

       якщо b>=с то

          k <- b;

          цикл

             Р;

             якщо k<c-d то вихід;

             k <- k+d

          кц

       кр.

 

      Правило виконання циклу (Lc-) будується аналогічно правилу виконання зростаючого циклу (Lc+).

      Отже, лічильник циклу пробігає послідовно всі члени аi арифметичної прогресії, якщо вони існують, які задовольняють нерівності аi >=c. Причому останнє значення k рівне найменшому серед них. Якщо ж таких членів послідовності не існує, то знову маємо

      Властивість 3.14'. Якщо с>b, то цикл (Lc-) вироджується в інструкцію Нічого.

      Доведення безпосередньо витікає з властивості 2.8.¦

      Канонічний спадний цикл називається суцільним, якщо d = -1. Позначення (L1-). Але в цьому випадку визначення кроку циклу "через -1") не опускається.

      Властивість 3.15'. Якщо b>=с, то цикл (L1-) рівносильний арифметичному циклу

 

       k <- b+1;

       повт b-c+1 раз

          k <- k-1;

          Р

       кц.

      Доведення повторює доведення властивості 3.15.¦

 

      Приклад 3.22. Обчислити факторіал у=n! (див. приклади 3.3 і 3.20).

Інший спосіб обчислення факторіала отримаємо, якщо записати співвідношення

       у  = 1;

        0

       у  = у   * (n-i+1), i=1,2,..., n.

        i    i-1

Суцільний спадний цикл дозволяє записати

 

       у <- 1;

       для k<-n до 1 через -1 повт

          у <- у*k

       кц.

 

      Приклад 3.23. Обчислити подвійний факторіал у=n!!

За означенням

 

              ¦ 1*3*5* ... *n, якщо n - непарне,

       n!! = <

              ¦ 2*4*6* ... *n, якщо n - парне.

 

У обох випадках ми маємо всі члени спадної арифметичної прогресії, що містяться між 1 і n. Отже

 

       у <- 1;

       для k<-n до 1 через -2 повт

          у <- у*k

       кц.

      Помітимо, що при непарному n останнім значенням k буде 1, а при парному - число 2.

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

      Спрощеним циклом з лічильником назвемо цикл вигляду

       k <- b;

       поки k<=с повт

          Р;                                               (Lcw)

          k <- k+d

       кц.

      Він відрізняється від канонічного циклу двома обставинами:

      а) при  b>c залишає значення  k=b,  тоді  як  канонічний не надає k ніякого значення;

      б) результуюче значення k більше останнього використаного в інструкції Р на величину d.

 

      Незахищеним циклом з лічильником назвемо цикл вигляду

       k <- b;

       повт

          Р;                                               (Lcu)

          k <- k+d

       до k>с.

      Цьому циклу властиві обидві попередніх відмінності від канонічного циклу. Крім цього, при b>с незахищений цикл виконується один раз, що може призвести до несподіваних наслідків.

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

 

       якщо b<=с то

          для k<-b до с через d повт Р кц

       кр.

 

3.7. Програмування циклів з лічильником

 

      Що стосується циклу з лічильником, то у мові Паскаль передбачені суцільні канонічні зростаючі і спадні цикли з натуральним або цілим лічильником. Вони записуються відповідно

 

       for k:=b to с do begin

          Pas(Р)

       end

 

і

 

       for k:=b downto с do begin

          Pas(Р)

       end

 

при тих же, що і раніше зауваженнях відносно  "begin-end".

 

      Приклад 9P. Два факторіали (задачі 3.20 і 3.22).

    program Factorials;

       var N, K: word;

           Y1, Y2: real;

    begin

       write('n=? '); readln(N);

       Y1:= 1; Y2:= 1;

       for K:=1 to N do Y1:= Y1*K;

       for K:=N downto 1 do Y2:= Y2*K;

       writeln(N, ' != ', Y1, Y2)

    end.

 

      Інші варіанти циклів з лічильником записуються через цикли за умовою.

      Приклад 10P. Подвійний факторіал (задача 3.23).

    program Double_Factorial;

       var N, K: integer;

           Y: real;

    begin

       write('n=? '); readln(N);

       Y:= 1; K:= N;

       while K>0 do begin

          Y:= Y*K; K:= K-2

       end;

       writeln(N, ' !!= ', Y)

    end.

 

      у мові Сі цикли з лічильником реалізуються за допомогою цикла for Сі. Цикл for має наступний вигляд:

      for (e1; F; e2)

            {

             P

            },

де e1- вираз, який обчислюється один раз перед початком циклу, F – умова продовження циклу, e2- вираз, який обчислюється після кожного кроку циклу, P – ланцюг інструкцій. Цикл for поєднує риси циклів за умовою та циклів з лічильником, оскільки умова продовження циклу F може бути будь-якою. Вирази e1, e2 можуть вміщувати декілька присвоєнь, які в цьому випадку записуються через кому. Наприклад, для обчислення n! можна написати цикл:

      for (k = 1, y = 1; k<=n; k++)

            y *= k;

або навіть

      for (k = 1, y = 1; k<=n; y*=k, k++);

 

      Цикл for є реалізацією спрощеного циклу з лічильником.

      За допомогою циклу for у мові Сі можна програмувати як зростаючі, так і спадні цикли з лічильником. Вони записуються відповідно

 

      for (k = b; k<=с; k +=d)

            {

             С(Р)

            }

 

і

 

      for (k = b; k>=с; k +=d)

            {

             С(Р)

            }

при тих же, що і раніше зауваженнях відносно  "{-}".

Суцільно зростаючий та суцільно спадний цикли реалізуються відповідно

 

      for (k = b; k<=с; k++)

            {

             С(Р)

            }

 

і

 

      for (k = b; k>=с; k--)

            {

             С(Р)

            }

 

      Приклад 9C. Два факторіали (задачі 3.20 і 3.22).

#include <stdio.h>

 

/* Factorials */

main()

{

  unsigned n, k;

  double y1, y2;

 

  printf(“n=? ”); scanf(“%u”, &n);

  y1 = 1; y2 = 1;

  for (k = 1; k<=n; k++) y1 *= k;

  for (k = n; k>=1; k--) y2 *= k;

  printf(“%u != %lf %lf”, n, y1, y2);

}

 

      Приклад 10C. Подвійний факторіал (задача 3.23).

#include <stdio.h>

 

/* Double_Factorial */

main()

{

  int n, k;

  double y;

 

  printf(“n=? ”); scanf(“%d”, &n);

  y = 1; k = n;

  for (k = n; k>=1; k -= 2)

    y *= k;

  printf(“%d !!= %lf”, n, y);

}

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