69132

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

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2014-09-30

83.5 KB

7 чел.

Лекція 9. Тема:Алгоритмічна конструкція повторення.

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

План:

1. Алгоритмічна конструкція повторення

2. Цикл із передумовою

3. Цикл із постумовою

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

5. Переривання циклу

1. Алгоритмічна конструкція повторення

У розглянутих вище прикладах усі оператори виконувалися не більше одного разу. Проте часто постає потреба виконати один і той самий оператор декілька разів. Для цього застосовують оператори циклів, що реалізують алгоритмічну конструкцію повторення. Цикл складається із заголовка та тіла. У заголовку циклу зазначається умова завершення циклу, а тіло циклу являє собою блок операторів, що повторюються. Кожне виконання операторів тіла циклу супроводжується перевіркою умови завершення циклу і називається його ітерацією. Якщо умова завершення хибна, то тіло циклу виконується ще раз, якщо істинна, то виконання циклу припиняється і здійснюється перехід до виконання наступного за циклом оператора. Замість умови завершення циклу може перевірятися її заперечення — умова продовження, хибність якої призводить до припинення виконання циклу, а істинність — до продовження. Змінні, значення яких модифікуються в тілі циклу і впливають на істинність умови завершення, називаються параметрами циклу. Виконанню будь-якого циклу має передувати ініціалізація його параметрів.

У мові Pascal є три різновиди операторів циклу: оператор циклу з передумовою, оператор циклу з постумовою та оператор циклу з лічильником. Вибір того чи іншого оператора циклу для розв'язання певної алгоритмічної задачі здійснюється залежно від типу умови завершення циклу. Цикли з передумовою розглянуто в розділі 3.2.1, цикли із постумовою - в розділі 3.2.2, а цикли з лічильником — у розділі 3.2.3. Нарешті, у розділі 3.2.4 обговорюються допоміжні засоби керування циклами — процедури break і continue.

2. Цикл із передумовою

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

while <умова продовження циклу> do <оператор>;

Тут whi 1 є <умова продовження циклу> do є заголовком циклу, <оператор> - його тілом. Тіло циклу може бути операторним блоком і містити в собі будь-які оператори: циклу, вибору,присвоєння тощо. Умова продовження циклу повинна бути виразом булевого типу. Оператору циклу з передумовою відповідає блок-схема, що зображена на рис.

Блок-схема циклу з передумовою

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

Приклад

Розглянемо задачу перевірки натурального числа на простоту. Як відомо, число я є простим, якщо воно ділиться лише на одиницю та на себе, тобто його додатними дільниками є лише числа 1 і я, інакше я вважається складеним числом. Отже, в алгоритмі перевірки числа на простоту повторюються такі дії: перевірка подільності числа п на дільник k та вибір наступного дільника шляхом збільшення k на одиницю. Таким чином, алгоритм є циклічним. Очевидною умовою продовження циклу є умова k < п. Оскільки на одиницю ділиться будь-яке число, то найменше значення параметра циклу k дорівнюватиме 2. Неважко побачити, що перебір всіх п - 2 чисел, від 2 до п - і, є недоцільним, оскільки значення найбільшого дільника складеного я не може перевищувати величини -Jn. У такому разі достатньо перебрати лише цілі числа від 2 до |_Vn J (символами \_х J позначатимемо цілу частину числа х).

Розглянемо будову циклу детальніше. Як сигналізувати про те, що знайшовся деякий дільник числа п? Це можна зробити за допомогою змінної логічного типу, дамо їй ім'я f 1 ag (прапорець). До початку виконання циклу присвоїмо цій змінній значення true, а в разі знаходження дільника я - значення f al se. Отже, після виконання циклу flag дорівнюватиме false, якщо дільник п знайдено (п - складене), і значенням flag залишиться true, якщо п є простим. Зауважимо, що в разі знаходження хоча б одного дільника я подальша перевірка чисел не потрібна, оскільки я тоді напевне буде складеним. Таким чином, цикл можна зупиняти не тільки по досягненні дільником k значення, а й внаслідок хибності значення змінної flag. Умова продовження циклу буде складеною: (k<=trunc(sqrt(n))) and flag (вираз trunc(sqrt(n)) дорівнює цілій частині кореня з я; функції trunc(x), sqrt(x) та інші стандартні функції розглядатимуться в розділі 4.1.3). Залишилося навести код програми та екранну копію результатів її виконання.

program ехЗ_4;

var n.k:integer:

flag:boolean;

begin

writeln ( number simplicity')

writeln (enter integer:  ');

readln(n):

k:-2:

flag:-true

while (k<=trunc(sqrt(n))) and flag do

begin

1f n mod k - 0 then flag:-false:

K:=k+1;

end:

1f flag then writeln (n. ‘is simple’) else writeln (n, ‘is not simple’):

end.

Оскільки цикл може почати роботу лише в разі істинності умови його продовження, а завершити роботу — лише в разі хибності цієї умови, то її істинність, а отже, і значення параметрів циклу, повинні змінюватися під час його роботи. В іншому разі відбудеться «зациклення», тобто виникне ситуація, коли цикл ніколи не завершує своєї роботи. У середовищі Borland Pascal 7.0 виконання нескінченного циклу, а разом із ним і виконання всієї програми переривається комбінацією клавіші Ctrl+Break.

3. Цикл із постумовою

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

repeat

<оператор1>: ... <onepaтopN>;

until <умова завершення циклу>;

Тут repeat, until — зарезервовані слова, <оператор1>;...<оператор№>; - тіло циклу; <умова завершення циклу> — деякий булів вираз. Дослівно ця мовна конструкція перекладається так:

Повторювати послідовність операторів доти, доки не виконається умова.

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

Синтаксичною особливістю оператора циклу з постумовою є те, що тіло циклу не обов'язково оточувати операторними дужками begin та end, оскільки воно розташоване між зарезервованими словами repeat та until. Символ ■*;* після останнього оператора тіла циклу також є необов'язковим, що уможливлює запис циклу із порожнім тілом. Наведемо приклад застосування даної циклічної конструкції.

Приклад

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

Очевидно, що процес відгадування є циклічним, оскільки повторюються такі дії, як введення числа, його порівняння із генерованим і зменшення призового фонду. Для моделювання цієї гри найзручнішою конструкцією буде саме цикл із постумовою, оскільки, по-перше, кількість спроб наперед невідома, і, по-друге, принаймні одна спроба повинна бути здійснена. Використаємо змінні для збереження «призового фонду» (prize), числа, що буде згенероване комп'ютером (у), числа, що його вводитиме користувач (х), та штрафу (penalty).

Для генерування випадкового числа використовуються дві бібліотечні підпрограми. Процедура randomi ze ініціалізує датчик випадкових чисел значенням, отриманим від системного таймера, а функція random(n) повертає згенероване цим датчиком випадкове ціле число з діапазону 0 .. я- 1. Процедуру randomize слід викликати до першого виклику функції random. Насправді згенеровані в такий спосіб числа не є випадковими з математичної точки зору, вони лише схожі на випадкові і називаються псевдовипадковими числами.

program ехЗ_5:

const penalty»10:

var x.

       у.

prize-.integer;

begin

writeln('define number.'which computer generate');
randomize; {ініціалізувати генератор випадкових чисел}

y:=random(1000):     {генерувати випадкове число з діапазону від 0 до 999}

prize:-100; repeat          {початкова "призова сума"}

repeat

writeln ('enter number');

readln(x);

if x>y then begin

        writeln ('Wrong, enter smaller');

        prize:=prize-penalty;

end:

if x<y then begin

writeln('Wrong, enter bigger');

prize:=prize-penalty;

end;

until x=y: {поки число не відгадане користувачем}

writeln (You have guessed right!'):

writeln (You have won the prize '.prize);

end.

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

Розглянемо задачу обчислення факторіала невід'ємного цілого числа п. Нагадаємо формулу факторіала: n! = 1 • 2 •... • (п -1) • n, де n > 0,0! = 1. Легко побачити, що n! = (n - і)! • n, тому обчислення можна звести до багаторазового виконання операції factorial :=factorial*i, де і = 2,3,..., п, а початкове значення змінної factorial дорівнює 1. Отже, задачу можна розв'язати за допомогою циклічної структури. Тіло циклу складатиметься із однієї вищезгаданої операції присвоєння, а кількість її повторень становитиме я. Таким чином, умовою завершення циклу буде виконання певної кількості ітерацій. Відстежити істинність такої умови дозволяє спеціальний різновид параметра циклу, тильних ітеращй. Лічильник - це змінна, що під час кожного повторення збільшується на одиницю. В операторі циклу з лічильником облік числа виконаних ітерацій ведеться автоматично, і тому цей оператор є зручною формою запису циклів із наперед визначеною кількістю повторень. Наведемо синтаксис оператора циклу з лічильником.

for <лічильник>:=<початкове значення> to <кінцеве значення> do <оператор>:

Тут for, to, do — зарезервовані слова («для», «до», «виконати»); <початкове значення та <кінцеве значення — вирази того самого перелічуваного типу; <лічильник — змінна перелічуваного типу, що є узгодженим за присвоюванням з типом початкового та кінцевого значення; <оператор - простий або складений оператор, що є тілом циклу. Фраза від слова for до слова do є заголовком циклу, а зазначений після слова do оператор — тілом циклу.

Виконання оператора for здійснюється за таким алгоритмом. Спочатку обчислюються та порівнюються значення виразів <початкове значення> та <кінцеве значенням Якщо початкове значення більше за кінцеве, то виконання циклу завершується, інакше лічильнику циклу присвоюється початкове значення і виконується тіло циклу. Після виконання тіла циклу порівнюється поточне значення лічильника з його кінцевим значенням, і, якщо ці значення не рівні, то поточне значення лічильника збільшується на одиницю і виконання циклу триває далі. Цикл завершує свою роботу тоді, коли поточне значення лічильника циклу стає рівним його кінцевому значенню.

Приклад  

Складемо програму обчислення факторіала цілого невід'ємного числа. Тіло циклу в цій програмі міститиме один оператор — присвоєння змінній factorial добутку її попереднього значення та поточного значення лічильника циклу. Результати роботи програми наведено на рис.

{обчислення факторіала числа}

{значення факторіала}

{вхідне число та лічильник циклу}

Program ехЗ_6:

var factorial:longint:

n.i:integer;

begin

writelnCfactorial calculation - n! '):
repeat {введення даних}

writeCenter integer number:1):

readln(n):

until n<=16;       {обмеження діапазону вхідних даних}

factorial:-1;        {початкове значення факторіала}

for i:-2 to n do  {заголовок циклу обчислення факторіала}

factorial: = factorial* i {тіло циклу}

writeln (n.'!='.factorial):      {виведення результату}

                                           end.

Допустимий діапазон вхідних значень було обмежено числом 16, оскільки функція факторіала числа дуже швидко зростає, і вже для значення п =17 величина л! перевищує найбільше допустиме значення типу longint.

Рис. Результати роботи програми ехЗ_6. Обчислення факторіала числа

5. Переривання циклу

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

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

Приклад

Як і у прикладі 3.4, розв'яжемо задачу перевірки на простоту натурального числа п, застосувавши той самий алгоритм. Але у програмній реалізації алгоритму відмовимося від логічної змінної flag, перериваючи виконання циклу в разі знаходження дільника п оператором виклику процедури break. Після завершення циклу саме значення потенційного дільника k визначатиме, чи є число складеним: якщо k-trunc(sqrt(n))+l, то оператор виклику процедури break не було застосовано жодного разу і число я є простим, інакше вихід із циклу було здійснено оператором виклику процедури break внаслідок того, що знайшовся дільник я, а отже, число п є складеним.

program ехЗ_7: var n.k:integer: begin

writeln (‘number simplicity');

writeln('enter integer:  '):

readln(n);

k:=2:  

while (k<=trunc(sqrt(n))) do

begin

if n mod k =0 then {якщо k ділить n.}

break; {сигналізуємо про це}

k:=k+l: {наступний дільник}

end:

if k=trunc(sqrt(n))+l then writeln (n.' is simple')

else writeln (n.' is not simple'):

end.

Контрольні питання

1. Алгоритмічна конструкція повторення

2. Цикл із передумовою

3. Цикл із постумовою

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

5. Переривання циклу