[ЗМІСТ] [Далі] [Назад]

 

3. ЦИКЛІЧНІ ПРОГРАМИ

3.1. Арифметичний цикл

3.1.1. Схема виконавця циклу

3.1.2. Основні властивості

3.1.3. Приклади арифметичних циклів

3.2. Рекурентні співвідношення

3.2.1. Співвідношення першого порядку

3.2.2. Співвідношення вищих порядків

3.2.3. Системи рекурентних співвідношень

3.3. Програмування арифметичного циклу

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

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

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

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

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

3.5. Програмування циклів за умовою

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

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

 

3. ЦИКЛІЧНІ ПРОГРАМИ

 

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

 

3.1. Арифметичний цикл

3.1.1. Схема виконавця циклу

 

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

 

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

повторити n раз Р кінець_циклу (Ln)

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

 

де n - натуральний вираз, Р - інструкція.

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

 

Правило арифметичного циклу:

Обчислюється значення n0 виразу n. Можливі два випадки.

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

тотожна інструкція, тобто (Ln) Нічого.

Якщо n0>0, то арифметичний цикл виконується як ланцюг

Р;

повт n-1 раз Р кц.

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

 

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

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

Якщо n більше 0, то повторення n раз зводиться до ланцюжка, який складається з дії Р і того ж повторення, але на один раз коротше.

Отже, правило виконання (Ln) можна переформулювати у вигляді наступного

Твердження 3.1. Нехай вираз n приймає натуральні значення, тоді

 

повт n раз якщо n=0 то

Р Нічого

кц інакше

Р;

повт n-1 раз Р кц

кр.

Доведення проводиться індукцією по значенню n0 виразу n і полягає у розборі двох випадків: n0=0 і n0>0, використовуючи правила виконання циклу і розгалуження.

Схематично правило арифметичного циклу при n > 0 зображене на мал. 3.1.

 

повт n раз Р кц -------------------

------------------------> С + IF + Ln Р

---------->

---------------------->

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

повт n-1 раз Р кц

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

 

МАЛ. 3.1.

 

Зауваження 3.1. Правило буде коректним, якщо дія Р не змінює жодної з змінних, які входять до складу виразу n. Дійсно, спроба застосувати правило, наприклад, для циклу

 

повт m раз m <- m+1 кц

нічого не дала б, оскільки яким би, крім нуля, не було значення змінної m=m0 > 0, після команди m <- m+1 вираз m-1 знову дасть те ж значення m0. Отже нове повторення має таку ж довжину, як і попереднє - цикл не закінчується ніколи.

Інший приклад

 

повт m раз m <- m-1 кц

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

Тому надалі розглядаються тільки цикли, які задовольняють зауваженню 3.1.

 

3.1.2. Основні властивості

 

Приклад 3.1. Розглянемо цикл

повт 3 рази у <- у*х кц.

Застосувавши три рази правило арифметичного циклу і властивість 1.1 перетворимо цикл у ланцюг

 

повт 3 рази у <- у*х кц

у <- у*х; повт 2 рази у <- у*х кц

у <- у*х; у <- у*х; повт 1 раз у <- у*х кц

у <- у*х; у <- у*х; у <- у*х; Нічого

у <- у*х; у <- у*х; у <- у*х.

 

Допустимо, що до початку циклу змінна у має визначене значення а. Тоді після першого присвоєння у=а*х. Запишемо це у вигляді (див. п.2.2)

{у=а} у <- у*х {у=а*х}. (3.1)

Друге присвоєння тоді дасть наступне

{у=а*х} у <- у*х {у=а*х*х}.

Нарешті третє

{у=а*х*х} у <- у*х {у=а*х*х*х}.

Ми встановили, що три присвоєння у <- у*х дають значення у=а*х3, якщо спочатку у=a. Відмітимо також, що початкове значення у=1 дає результат у=х3.

Скорочено властивості розглянутого циклу зобразимо так

 

{у=а}

повт 3 рази у <- у*х кц

{у=а*х3 },

та

 

{у=1}

повт 3 рази у <- у*х кц

{у=х3 }.

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

З властивості 1.1 і правила арифметичного циклу безпосередньо випливає

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

повт 1 раз Р кц Р.

 

Наступна властивість дає правило, рівносильне правилу арифметичного циклу.

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

повт n раз Р кц; Р

Р; повт n раз Р кц.

Доведення. Як правило, властивості індуктивно введених означень зручно доводити методом математичної індукції. У даному випадку проведемо індукцію по числу n повторень циклу.

а) Нехай n = 0. Тогда маємо просто властивість 1.1

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

b) Допустимо, що

повт n-1 раз Р кц; Р

Р; повт n-1 раз Р кц.

с) Розглянемо n>0. За правилом арифметичного циклу

повт n раз Р кц; Р

Р; повт n-1 раз Р кц; Р.

Використовуючи припущення,

Р; повт n-1 раз Р кц; Р

Р; Р; повт n-1 раз Р кц.

Ще раз застосуємо правило арифметичного циклу

Р; Р; повт n-1 раз Р кц

Р; повт n раз Р кц.

Що і треба було довести.

З правила арифметичного циклу і властивості 3.2 випливають

Наслідок 3.1. Для довільної інструкції Р справедливі тотожності

повт n+1 раз Р кц

повт n раз Р кц; Р

Р; повт n раз Р кц.

Наслідок 3.2. Цикл (Ln) рівносильний розгалуженню

якщо n=0 то

Нічого

інакше

повт n-1 раз Р кц;

Р;

кр.

 

Наступна властивість корисна при побудові алгоритмів.

Властивість 3.3. Для довільних інструкцій Р і Q справедлива тотожність

Р; повт n раз Q; Р кц

повт n раз Р; Q кц; Р.

Доведення проведемо знов індукцією.

а) Нехай n = 0. Как і раніше, будемо мати

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

b) Зробимо припущення

Р; повт n-1 раз Q; Р кц

повт n-1 раз Р; Q кц; Р.

с) Розглянемо n>0. Використовуючи правило арифметичного циклу отримаємо

Р; повт n раз Q; Р кц

Р; Q; Р; повт n-1 раз Q; Р кц.

Використовуючи припущення,

 

Р; Q; Р; повт n-1 раз Q; Р кц

Р; Q; повт n-1 раз Р; Q кц; Р.

Ще раз застосувавши правило,

Р; Q; повт n-1 раз Р; Q кц; Р

повт n раз Р; Q кц; Р.

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

 

3.1.3. Приклади арифметичних циклів

 

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

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

Приклад 3.2. Довести, що

{у=1}

повт n раз

у <- у*х

кц

{у=хn}.

Знов використовується індукцію.

а) Нехай n = 0. Поськольку х0 = 1, то

{у=1}

Нічого

{у=х0}.

b) Допустимо, що

{у=1}

повт n-1 раз

у <- у*х

кц

{у=хn-1}.

c) Розглянемо n>0. За властивістю 3.2 цикл можна представити

повт n-1 раз

у <- у*х

кц;

у <- у*х.

Використовуючи припущення індукції і твердження (3.1)

{у=1}

повт n-1 раз

у <- у*х

кц

{у=х n-1}

у <- у*х

{у=х n-1 * х = х }.

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

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

 

Алгоритм Pow це

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

n: нат;

поч

взяти (x, n);

у <- 1;

{у=1}

повт n раз

у <- у*х

кц;

{у=х n}

показати (у)

ка.

 

Приклад 3.3. Аналогічно доводиться справедливість способу обчислення факторіала (доведіть):

 

{у=1}

k <- 1;

повт n раз

у <- у*k; k <- k+1

кц;

{у=n! & k=n+1}.

Розглянемо декілька перетворень останнього прикладу. Спочатку помітимо, що присвоєння k<-1 тотожне ланцюгу k<-0; k<-k+1. Замінивши його таким чином, скористаємося властивістю 3.3,

 

{у=1}

k <- 0; k <- k+1;

повт n раз

у <- у*k; k <- k+1

кц

{у=n! & k=n+1}

 

{у=1}

k <- 0;

повт n раз

k <- k+1; у <- у*k

кц;

k <- k+1

{у=n! & k=n+1}.

Помітивши, що остання дія не впливає на результат у, а значення k збільшує на 1, отримаємо

 

{у=1}

k <- 0;

повт n раз

k <- k+1; у <- у*k

кц;

{у=n! & k=n}.

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

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

 

[ЗМІСТ] [Далі] [Назад]