Задача 74.74. Знайти найбільший спільний дільник (НСД) двох чисел.

Розв’язання: Використаємо для розв’язання цієї задачі класичний спосіб великого математика минуло – так званий алгоритм Евкліда. Запропонований ним спосіб знаходження НСД двох чисел можна словесно сформулювати так: доки дві змінні різні, то від більшої змінної віднімай меншу і результат занось у меншу. Якщо ж змінні стали однаковими, то це і є НСД початкових двох чисел. Погодьтесь, що все геніальне – просте! Що ж реалізуємо програмно алгоритм Евкліда:

program nsd;

var a, b, a1, b1: integer;

begin

write(’Введіть перше число: ’); readln(a);

write(’Введіть друге число: ’); readln(b);

a1:= a; b1:= b; {Зберегли початкові значення змінних }

while a1 <> b1 do { поки а1 № b1 то }

if a1 > b1 then a1:= a1 - b1 { якщо більше а1 то а1=а1–b1 }

else b1:= b1 - a1; { інакше b1 = b1 – a1 }

writeln(’НСД чисел ’,a,’ та ’,b,’ = ’,a1);

readln

end.

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

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

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

Цикл з передумовою може виконуватись яку завгодно кількість разів.

Параметром циклу може бути змінна довільного типу.

Зміну параметру циклу повністю покладено на програміста і змінювати його можна як завгодно.

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

5. Цикл з передумовою може бути вічним, якщо змінна-параметр не набуде значення закінчення циклу!

Цикл з післяумовою

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

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

Program summa3; { варіант з використанням циклу з післяумовою }

var i, sum: integer;

Begin

sum:= 0;

i:= 1;

Repeat { цикл з післяумовою! }

sum:= sum + i;

inc (i);

until i > 100; { кінець циклу }

Write ('S = ',sum);

Readln;

End.

Зверніть увагу, що при організації початку і кінця циклу з післяумовою не використовується наша нерозлучна пара Begin... End, а замість неї нами використано нову пару слів: Repeat... Until.... Власне вона і є способом організації циклу з післяумовою і розшифровується як виконувати (повторювати)... поки не виконаються умова...

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

Даний цикл з точки зору машинної логіки розуміється так: спочатку виконуються команди, що стоять в тілі циклу, а лише потім перевіряється умова закінчення циклу. Якщо умова виконалась, то цикл закінчується, а якщо ні, то цикл починається спочатку. В умовах поставленої нами задачі в приведеній вище програмі розуміється наступне: спочатку до змінної Sum додати значення змінної і, збільшувати параметр і на 1, якщо і стало більше 100, то цикл на цьому закінчити.

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

Отже, по кількості виконань, цикл з післяумовою:

n завжди виконується хоча б один раз;

n може виконуватись скінчену кількість разів;

n може бути “вічним”.

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

Пояснимо логіку «машинного мислення» при виконанні циклу з передумовою на прикладі нашої задачі. До початку організації циклу ми присвоюємо значення 0 шуканій сумі і крім того задаємо значення параметра циклу – змінній і(що в загальному випадку не є обов’язковим). Цикл починається з значення параметру рівного 1, ПЕОМ виконує операцію циклу Sum:= Sum +1, в результаті якої значення Sum = 1, збільшує значення параметра і на 1, і стає рівним 2 і лише тепер виконується перевірка умови завершення циклу, чи 1>100, отримується результат “ні” і оскільки умова закінчення циклу не виконалась, то цикл виконується ще раз. Виконується операція циклу Sum:= Sum + 2, в результаті якої значення Sum = 3, збільшується значення параметра і на 1, і стає рівним 3 і т.д. На 99 кроці значення Sum було 4950 і параметр і став 100, перевіряється чи 100>100, отримується результат “ні”, то цикл виконується ще раз – Sum:= Sum +100, в результаті якої значення Sum =5050, збільшується значення параметра і на 1, і стає рівним 101. Перевіряється чи 101>100, отримується результат “так” і цикл на цьому закінчується. Наступною виконується операція, що йде за циклом: надрукувати результат. Весь хід приведених “машинних роздумів” зручно привести в такій таблиці.

Дія S і i > 100

+1 ні

+2 ні

+3 ні

... ... ...

+99 ні

+100 так

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

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

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