3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

¦ Р;

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

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

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

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

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

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

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

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

Р Нічого

кц інакше

Р;

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

кр.

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

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

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

¦ ¦

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

¦ ¦---------->

---------------------->¦ ¦

¦ L------------------

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

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

МАЛ. 3.1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{у=а}

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

{у=а*х³ },

та

{у=1}

повт 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 = 0. Поськольку х⁰ = 1, то

{у=1}

Нічого

{у=х⁰}.

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

{у=1}

повт n-1 раз

у <- у*х

кц

{у=хⁿ^-1}.

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

повт n-1 раз

у <- у*х

кц;

у <- у*х.

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

{у=1}

повт n-1 раз

у <- у*х

кц

{у=хⁿ^-1}

у <- у*х

{у=хⁿ^-1 * х = х }.

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

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

Алгоритм Pow це

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

n: нат;

поч

взяти (x, n);

у <- 1;

{у=1}

повт 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 тут грає роль лічильника повторень циклу, до нього ми будемо повертатися ще не раз.

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