3

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

3.4. Цикли за умовою

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

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

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

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

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

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

3.4.1. Цикл з умовою повторення

Розглянемо пристрій керування (С+IF+Ln) виконавця AB. Ланцюг (С) і розгалуження (IF) залишимо без змін, а замість арифметичного циклу введемо нову структуру керування, яка називається циклом з умовою повторення

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

¦ поки F повторити Р кінець_циклу,¦ (Lw)

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

де F - умова, Р - інструкція.

Скорочення: поки F повт Р кц.

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

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

¦ Якщо F₀=Хиб, то цикл (Lw) вже завершив свою роботу.

¦ Якщо F₀=Іст, то виконується інструкція Р і знову починає

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

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

Отриманий пристрій управління визначимо (С+IF+Lw).

Коротко правило виконання циклу (Lw) можна сформулювати у вигляді такої властивості.

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

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

º якщо F то

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

кр.¦

Отже істинність умови F грає роль критерію продовження циклу. Критерій припинення - її хибність або, що також саме, істинність протилежної умови ¬F. Цикл (Lw) називають ще циклом з умовою продовження.

Наступна властивість дає критерій припинення циклу.

Властивість 3.5. Коли цикл (Lw) завершиться, умова F стане хибною, тобто

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

Дійсно, допустивши протилежне, ми отримали б суперечність правилу циклу, оскільки в такому випадку цикл не припиняють, а виконують інструкцію Р і все починається спочатку. Особливо звертаємо увагу на те, що скінченність циклу властивістю 3.5 не затверджується: цілком може так бути, що виконавець ніколи не зможе закінчити цикл, оскільки на кожному кроці умова його продовження буде залишатися істинною. Властивість 3.5 лише зафіксувало ту частину правила циклу, яка затверджує, що цикл не може закінчитися інакше, як внаслідок помилковості умови його продовження.¦

Наприклад, розглянемо інструкцію

поки n<>0 повт n <- n+1 кц { n=0 }.

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

Зауваження 3.3. При будь-якій умові F і інструкції Р твердження

поки І повт Р кц { F }

вважається істинним, оскільки цикл не припиняється ніколи.¦

Виконуючи цикл, виконавець так чи інакше виконує визначений ланцюг інструкцій. З'ясуємо який саме.

Все залежить від умови F. Вона може бути хибною відразу і тоді весь цикл зводиться до тотожної інструкції, тобто

{ ¬F } Нічого { ¬F }.

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

{ F } Р { ¬F }.

Якщо умова залишилася істинною, то розглянемо її можливі значення після другого разу. Можливості ті ж самі. Знову будемо мати або

{ F } Р; { F } Р { ¬F },

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

1) кінцевий (можливо пустий)

{ F } Р; Р; ...; Р { ¬F }

2) або нескінченний

{ F } Р; Р; ...

ланцюг, отриманий повторенням інструкції Р.

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

повт q раз Р кц

при невідомій, взагалі кажучи, кількості повторень q.

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

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

Знову розглянемо послідовність а₀, а₁,..., а_k,..., задану співвідношенням першого порядку вигляду (R₁)

а = с,

а = f(k, а ,р), k = 1,2,...

k k-1

Розглянемо далі умову G(k, х), яка залежить від одного числового аргументу. Застосуємо цю умову до членів послідовності {а_n}. Визначимо через n>=0 номер першого по порядку члена, який задовольняє цій умові, тобто

G(0, а )=Хиб; G(1, а )=Хиб; ...; G(n-1, а )=Хиб; (3.2)

0 1 n-1

G(n, а )=Іст.

Покладемо х=с, k=0. Тоді цикл

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

k <- k+1; (3.3)

х <- f(k, х, р)

кц

виконується точно так, як і арифметичний цикл

повт n раз

k <- k+1; (3.4)

х <- f(k, х, р)

кц.

Застосувавши до циклу (3.4) першу теорему про рекурентні співвідношення (теорему 3.1), затверджуємо, що після його завершення справедлива рівність х = а_n. Крім цього з доведення теореми 3.1 слідує, що одночасно з рівністю х = а_n виконується рівність k = n, а тому першу з них можна замінити рівністю х = а_k.

Отже, у разі виконання (3.2) після завершення циклу (3.3) справедлива умова х = а_k.

Якщо ніякий член послідовності {а_n} не задовольняє умову G(k, х), тобто G(k, а_k)=Хиб і, відповідно, ¬G(k, а_k)=Іст для всіх k=0,1,2,.., то цикл (3.3) взагалі не завершується, а отже, згідно із зауваженням 3.3, довільне твердження про значення його змінних буде істинним, в тому числі, відносно умови х = а_k.

Таким чином, ми довели таку теорему.

Теорема 3.3. (Рекурентні обчислення за умовою)

При довільній умові G(k, х) в позначеннях (R₁) і початкових значеннях х=с, k=0 цикл (3.3) обчислить перше по порядку значення х=а_k, яке буде задовольняти умові G(k, х), якщо ж такого значення не існує, цикл буде виконуватися нескінченно, тобто

{ k=0 & х=с }

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

k <- k+1;

х <- f(k, х, р)

кц

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

Наслідок 3.4. Справедливе твердження

{ k=0 & х=с }

поки k<n повт

k <- k+1;

х <- f(k, х, р)

кц

{ k=n & х=а }.¦

Доведення безпосередньо виходить з теореми 3.3, якщо в якості умови G(k, а_k) взяти умову k>=n.¦

Зауваження 3.4. Аналогічно можна узагальнити інші твердження, що стосуються рекурентних співвідношень. Крім умов вигляду G(k, а_k), можна розглядати більш складні умови, наприклад, вигляду G(k, а_k_-1, а_k). Таке ускладнення умови впливає на вигляд циклу точно так, як порядок рекурентного співвідношення, що вимагає додаткових змінних. Так умова вигляду G(k, а_k_-1, а_k) для послідовності (R₁) вимагає однієї додаткової змінної для попереднього члена послідовності.¦

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

Приклад 3.13. Для довільного а>1 знайти номер n такий, що

n! > а .

Якщо змінна у пробігає послідовність k!, а змінна х - послідовність а^k , k=0,1,..., то доцільно розглянути умову х<y. Її заперечення - це умова х>=y. Прийнявши до уваги алгоритм прикладу 3.7, отримаємо

Алгоритм FactPower це

змін А, X, Y: дійсн;

N: нат;

поч

взяти (А);

X <- 1; Y <- 1; N <- 0;

поки X>=Y повт

N <- N+1;

Y <- Y*N; X <- X*А

кц;

{ X=а & Y=n! }

показати (X, Y, N)

ка.

Приклад 3.14. Перевірити, чи всі n чисел, що вводяться, позитивні (продовження прикладу 3.5).

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

Q = Іст;

Q = Q & (а >0), k=1,2,..., n.

k k-1 k

Однак очевидно, що негативну відповідь на поставлене питання можна дати, не розглядаючи всю послідовність, а зупинившись на першому ж числі, яке порушує шукану умову. Це слідує, зокрема, з умови стаціонарності значення Хиб відносно кон’юнкції &.

За теоремою 3.3 отримаємо

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

поки K<N & Q повт

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

Q <- Q & (А>0)

кц

{ Q=Q & k>=n V ¬Q }

Нехай виконалася умова k>=n. Как і раніше, в цьому випадку легко довести, що виконується саме рівність k=n. Тоді Q=Q_n і ми маємо той же результат, що в прикладі 3.5.

Нехай тепер k<n. Тоді за властивістю диз’юнкції виконається умова ¬Q, або, що те ж саме, порушиться умова Q. Тоді

Q = Q =. ..= Q = Хиб

k k+1 n

і тому замість Q беремо Q .

n k

Наведений цикл можна ще спростити, враховуючи, що присвоєння Q <- Q & (А>0) рівносильно такому Q <- Іст & (А>0) або такому Q <- А>0 присвоєнню. Остаточно отримаємо

Алг Positive1 це

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

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

поч

взяти (N);

Q <- І; K <- 0;

поки K<N & Q повт

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

Q <- А>0

кц;

показати (Q)

ка.

Наступний приклад показує спосіб застосування циклу (Lw) для наближеного обчислення границь.

Приклад 3.15. Обчислити границю

у = lim а

n->¥ n

послідовності {а_n} із заданою точністю e>0. Послідовність задовольняє системі рекурентних співвідношень (х - числовий параметр)

а = 1, с = 1-x, (0<х<2)

0 0

а = а *(1+с ), с = с ; k=1,2,...

k k-1 k-1 k k-1

За визначенням границі досить знайти номер N такий, що

¦ у - а ¦ < e.

Якщо N найменший номер, який задовольняє цій умові, то

¦ у - а ¦ >= e, k=0,1,..., N-1; ¦ у - а ¦ < e. (3.5)

k N

Схематично це зображено на числовій вісі

y-e у у+e

------+---+--------+--(--+--+-----)------->

а а а а

0 1 N-1 N

Помітимо, що перевірка умови (3.5) утруднена, оскільки границя у зазделегідь невідома. Тому в подібних задачах або задовольняються досить грубими практичними критеріями типу

¦ а - а ¦ < e,

n n-1

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

1 - с

а = ------. (3.6)

n х

Умова 0<х<2 гарантує, що ¦с_n¦<1, тому с_n -> 0. Звідси бачимо, що точне значення межі – це

lim а = 1/х.

n->¥ n

Очевидно, що користуючись виконавцем AB, можна обчислити у як 1/х, взагалі не вдаючись до послідовності {а_n}. Однак постановка, що розглядається, також представляє певний інтерес як спосіб обчислення зворотного числа, що не використовує операцію ділення, наприклад, для перевірки правильності функціонування операційного пристрою.

Співвідношення (3.6) доведемо методом індукції. Початковий член а₀ = 1 = (1-c₀)/х йому задовольняє. Допускаючи справедливість співвідношення (3.6) для довільного k, розглянемо k+1:

1 - c 1 - c 1 - с

k k k+1

а = а *(1+с ) = ------ * (1+с ) = ------ = --------,

k+1 k k х k х х

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

¦с ¦

Тоді ¦у - а ¦ = ¦1/х - а ¦ = ----.

n n х

Умову (3.5) тепер можна замінити на рівносильну

¦с ¦ >= e*х, k=0,1,..., N-1; ¦с ¦ < e*х.

k N

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

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

Алг Limit це

змін А, С, X, Eps: дійсн;

k: нат;

поч

взяти (X, Eps);

k <- 0; А <- 1; С <- 1-x;

поки abs(С)>=Eps*Х повт

k <- K+1;

А <- А*(1+С); С <- С*С

кц;

{ А=а & С=с & abs(С)<Eps*Х }

k k

показати (А, 1/Х)

ка.

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

показати (А, k, 1/Х),

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

Інший варіант алгоритму полягає у виключенні k взагалі.

Алг Limit1 це

змін А, С, X, Eps: дійсн;

поч

взяти (X, Eps);

А <- 1; С <- 1-x;

поки abs(С)>=Eps*Х повт

А <- А*(1+С); С <- С*С

кц;

{ $k (А=а & С=с ) & abs(С)<Eps*Х }

k k

показати (А, 1/Х)

ка.

Зверніть увагу на умову, записану після циклу. Його змінена частина читається так: "Існує такий номер k, що значення змінних А і С рівні відповідним членам послідовностей".

Приклад 3.16. Побудувати алгоритм наближеного обчислення суми

¥ k х

S = å (- 1 ) * ----

k=0 k!

по заданому 0<х<1 із заданою точністю e>0.

Скористаємося тим, що

k n

¥ k х х

¦S ¦ = ¦ å (- 1 ) * ---- ¦ < | ---- |.

n, ¥ k=n k! n!

Отже, помилка наближення не буде перевищувати модуля останнього врахованого доданку. Враховуючи приклад 3.8 побудуємо

Алг Sum це

змін X, Eps, Т, S: дійсн;

K: нат;

поч

взяти (X, Eps);

K <- 0; Т <- 1; S <- 1;

поки abs(Т)>=Eps повт

K <- K+1; Т <- -T*X/K; S <- S+Т

кц;

показати (S)

ка.

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

Розкладемо n по степенях числа 10

k-1

n = а *10 +. .. + а *10 + а , k>0.

k-1 1 0

Досліджуємо поведінку часток від ділення n на 10:

k-1

р = n = а *10 + ... + а *10 + а ,

0 k-1 1 0

k-2

р = р div 10 = а *10 +. .. + а *10 + а ,

1 0 k-1 2 1

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

р = р div 10 = а ,

k-1 k-2 k-1

р = р div 10 = 0.

k k-1

Тепер десяткові цифри а_k числа n виразимо як остачі від ділення

а = р mod 10,

0 0

а = р mod 10,

1 1

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

а = р mod 10.

k-1 k-1

Шукана сума це, очевидно, є S = а₀ +а₁ + ... +а_k_-1, де номер k визначається з умови р_k =0.

Складаємо рекурентні співвідношення

р = n, а = р mod 10, S = а ,

0 0 0 0 0

р = р div 10; а = р mod 10; S = S + а ;

i i-1 i i i i-1 i

i = 1, 2,. .., k-1,

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

Р <- N; А <- Р mod 10;

показати (А); S <- А;

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

Р <- Р div 10; А <- Р mod 10;

показати (А); S <- S+А;

кц.

Помітимо, що тіло циклу (Lw) буде виконуватися і при Р=0. Це не впливає на значення суми цифр S, але приведе до показу цифри нуль, що невірно (А<>0). Для усунення цього недоліку змінимо порядок присвоєнь так, щоб значення величин А і S обчислювалися тільки при Р<>0. Тоді отримаємо

Алг DigitSum це

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

поч

взяти (N); Р <- N;

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

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

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

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

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

кц;

показати (S)

ка.

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