Цикли в алгоритмах і в програмах

Пригадайте!

1. Які процеси називаються циклічними? Наведіть приклади.

2. Опишіть характерні властивості лінійних алгоритмів (фрагментів алгоритмів), алгоритмів з розгалуженням.

3. Як виглядає і як виконується команда повного розгалуження в Delphi?

4. Як виглядає і як виконується команда неповного розгалуження в Delphi?

5. Як і для чого використовуються перемикачі та прапорці?

Цикли в алгоритмах

У лінійних алгоритмах і в алгоритмах з розгалуженням кожна команда алгоритму могла бути виконана не більше одного разу.

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

 

Задача 1. Є діжка і відро. Використовуючи відро, наповнити діжку водою. (Вважаємо, що існує джерело води, з якого можна наповнювати відро, і води у джерелі достатньо для наповнення діжки.)

Розглянемо виконавця з такою системою команд:

1. Наповнити відро водою.

2. Вилити воду з відра в діжку.

3. Перевірити умову «Діжка неповна?».

Оскільки з умови задачі невідомо, чи є в діжці вода, виконавець повинен спочатку перевірити умову «Діжка неповна?». Якщо результат цієї перевірки true, то він повинен наповнити відро водою, вилити її з відра в діжку і знову перевірити умову «Діжка неповна?». І так до тих пір, поки результат перевірки цієї умови стане false. Після цього можна припинити виконання алгоритму.

Подамо алгоритм розв’язування цієї задачі для розглянутого виконавця у словесній формі і у формі блок-схеми (рис. 2.53).

1. Перевірити умову «Діжка неповна?»

2. Якщо результат виконання попередньої команди true, то виконати команду 3, якщо false, то закінчити виконання алгоритму.

3. Наповнити відро водою.

4. Вилити воду з відра в діжку.

5. Перейти до виконання команди 1.

У цьому алгоритмі команди 3-5 можуть бути виконані більше одного разу. Чергове виконання цих команд залежить від результату перевірки умови в команді 1. Якщо цей результат true, то команди 3-5 виконуються ще раз, якщо ж false, то ці команди більше не виконуватимуться.

Звертаємо вашу увагу: команди 3-5 саме «можуть бути виконані більше одного разу», а не «обов’язково виконуються більше одного разу». Адже можливо, що після першого ж виливання води з відра в діжку вона наповниться і виконання алгоритму закінчиться. Крім того, якщо діжка з самого початку є повною, то ці команди не виконаються жодного разу.

Запам’ятайте!

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

У наведеному алгоритмі цикл складається з трьох команд: команди перевірки умови і двох команд, які утворюють тіло циклу.

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

Загальний вигляд циклу з передумовою наведено на рис. 2.54. Виконання такого циклу відбувається так: виконавець виконує команду перевірки умови (обчислення значення логічного виразу); якщо результат виконання цієї команди true, то виконавець виконує команди тіла циклу, після чого знову виконує команду перевірки умови (обчислення значення логічного виразу); якщо ж результат виконання команди перевірки умови (обчислення значення логічного виразу) false, то виконавець переходить до виконання першої команди наступного фрагмента алгоритму.

Верстальнику: на рис. 2.54 в ромбі написати «Перевірка умови (обчислення значення логічного виразу)

 

Якщо б в умові задачі 1 було відомо, що діжка порожня, то виконавцю не потрібно було б одразу перевіряти умову «Діжка неповна?». Він мав би хоча б один раз наповнити відро водою, перелити воду з відра в діжку і лише після цього перевірити умову «Діжка неповна?» (або умову «Діжка повна?», якщо вона входить до системи його команд).

Блок-схема алгоритму розв’язування такої задачі з використанням умови «Діжка повна?» виглядає так (рис. 2.55):

Верстальнику: на рис. 2.55 Стрілку Так пустити справа від ромба і вниз, а Ні – зліва від ромба і вгору!

 

Рис. 2.55. Блок-схема алгоритму розв’язування модифікованої задачі 1

 

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

Загальний вигляд блок-схеми циклу з післяумовою наведено на рис. 2.56. Верстальнику: на рис. 2.56 Стрілку Так пустити справа від ромба і вниз, а Ні – зліва від ромба і вгору! І в ромбі написати «Перевірка умови (обчислення значення логічного виразу)

Виконання такого циклу відбувається так: виконавець виконує команди тіла циклу, після чого виконує команду перевірки умови (обчислення значення логічного виразу); якщо результат виконання цієї команди false, то виконавець знову виконує команди тіла циклу; якщо ж true, то виконавець переходить до виконання першої команди наступного фрагмента алгоритму.

Звертаємо вашу увагу: якщо в алгоритмі, блок-схема якого наведена на рис. 2.55 використати умову «Діжка неповна?», то виконання циклу продовжувалося б при результаті true виконання команди перевірки умови і припинялося б при результаті false виконання цієї команди.

 

 

Таким чином, ми розглянули три базові структури алгоритмів: лінійні фрагменти (слідування), розгалуження та цикли (повторення). Доведено, що використовуючи тільки ці три структури, можна скласти алгоритм розв’язування будь-якої задачі, якщо він існує.

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

 

Команда циклу з лічильником в Delphi

У мові програмуванні Delphi є кілька команд, які можуть реалізувати цикл. Одна з них – команда циклу з лічильником. Її доцільно використовувати в тих випадках, коли кількість повторень команд тіла циклу відома до початку виконання команди циклу. Загальний вигляд цієї команди такий:

for <ім′я змінної>:= <вираз1> to <вираз2> do

Begin

<команди тіла циклу>

end;

Рядок for … to … do ( англ. for – для, to – до, do – робити, виконувати ) називається рядком заголовку команди циклу з лічильником. Змінна в рядку заголовка команди циклу з лічильником, що стоїть перед знаком присвоювання, називається лічильником циклу.

Лічильник циклу, вираз1 і вираз2 мають набувати тільки цілих значень. Якщо тіло циклу складається лише з однієї команди, операторні дужки begin і end можна не ставити.

Виконується команда циклу з лічильником так:

1. Надати лічильнику циклу значення виразу1.

2. Обчислити значення логічного виразу i £ вираз 2

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

4. Збільшити значення лічильника циклу на 1.

5. Перейти до виконання команди 2.

Блок-схема виконання команди циклу з лічильником наведена на рис. 2.57 (і – лічильник циклу).

 

Для ілюстрації виконання команди циклу з лічильником розглянемо фрагмент програми, в якому обчислюється сума 1! + 2! + 3! +4! (нагадаємо, що n! = 1×2×3×...×n):

var a, s, i: Integer;

Begin

s:= 0; a:= 1;

For i:= 1 to 4 do

Begin

a:= a*i;

s:= s + a;

end;

Label1.Caption:= IntToStr (s);

end;

Функція IntToStr (англ. int eger to str ing– ціле в рядок) використовується для переведення цілого числа в його текстове представлення для виведення в напис.

Виконаємо цей фрагмент програми.

Команда	Результат виконання
s:= 0	s = 0
a:= 1	a = 1
i:= 1	i = 1
і <= 4	(1 <= 4) = true
a:= a*i	a = 1*1= 1
s:= s + a	s = 0 + 1 = 1
i:= i + 1	i = 2
і <= 4	(2 <= 4) = true
a:= a*i	a = 1*2= 2
s:= s + a	s = 1 + 2 = 3
i:= i + 1	i = 3
і <= 4	(3 <= 4)= true
a:= a*i	a = 2*3= 6
s:= s + a	s = 3 + 6 = 9
i:= i + 1	i = 4
і <= 4	(4 <= 4) =true
a:= a*i	a = 6*4= 24
s:= s + a	s = 9 + 24 = 33
i:= i + 1	i = 5
і <= 4	(5 <= 4) = false
Label1.Caption:= IntToStr (s)	Label1.Caption = 33

Звертаємо вашу увагу:

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

2. Існує різновид команди циклу з лічильником, який змінюється в зворотному порядку:

For <ім′я змінної>:= <вираз1> downto <вираз2> do

Begin

<команди тіла циклу>

end;

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

 

Команди циклу з передумовою і циклу з післяумовою в Delphi

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

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

while <логічний вираз> do

Begin

<команди тіла циклу>

end;

( англ. while – поки). Якщо тіло циклу складається лише з однієї команди, операторні дужки begin і end можна не ставити.

 

Виконується команда циклу з передумовою так:

6. Обчислити значення логічного виразу.

7. Якщо це значення true, то виконати команди тіла циклу і перейти до команди 1, а якщо false, то виконати команду, наступну за командою циклу.

Для ілюстрації виконання команди циклу з передумовою розглянемо фрагмент програми для розв’язування наступної задачі.

Задача 2. Обчислити суму додатних членів арифметичної прогресії з додатним першим членом і від’ємною різницею.

 

Домовимося вводити перший член прогресії в поле Edit1, а її різницю – в поле Edit2.

var a, d, s: Real;

Begin

a:= StrToFloat (Edit1.Text);

d:= StrToFloat (Edit2.Text);

s:= 0;

While a > 0 do

Begin

s:= s + a;

a:= a + d;

end;

Label1.Caption:= FloatToStr (s);

end;

Виконаємо цей фрагмент програми для деякого набору значень a і d.

Команда	Результат виконання
a:= StrToFloat (Edit1.Text)	a = 7
d:= StrToFloat (Edit2.Text)	d = -3
s:= 0	s = 0
a > 0	(7 > 0) = true
s:= s + a	s = 0 + 7 = 7
a:= a + d	a = 7 +(-3) = 4
a > 0	(4 > 0) = true
s:= s + a	s = 7 + 4 = 11
a:= a + d	a = 4 +(-3) = 1
a > 0	(1 > 0) = true
s:= s + a;	s = 11 + 1 = 12
a:= a + d	a = 1 +(-3) = -2
a > 0	(-2 > 0) = false
Label1.Caption:= FloatToStr (s)	Label1.Caption = 12

 

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

Repeat

<команди тіла циклу>

until <логічний вираз>;

( англ. repeat – повторити, until – доки, не раніше як).

Виконується команда циклу з передумовою так:

1. Виконати команди тіла циклу.

2. Обчислити значення логічного виразу.

3. Якщо це значення false, то виконати п.1, а якщо true, то виконати команду, наступну за командою циклу.

 

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

Проілюструємо, як виглядатиме фрагмент програми для розв’язування попередньої задачі з використанням циклу з післяумовою:

var a, d, s: Real;

Begin

a:= StrToFloat (Edit1.Text);

d:= StrToFloat (Edit2.Text);

s:= 0;

Repeat

s:= s + a;

a:= a + d;

until a <= 0;

Label1.Caption:= FloatToStr (s);

end;

Виконаємо цей фрагмент програми для деякого набору значень a і d.

Команда	Результат виконання
a:= StrToFloat (Edit1.Text)	a = 7
d:= StrToFloat (Edit2.Text)	d = -3
s:= 0	s = 0
s:= s + a	s = 0 + 7 = 7
a:= a + d	a = 7 +(-3) = 4
а <= 0	(4 <= 0) = false
s:= s + a	s = 7 + 4 = 11
a:= a + d	a = 4 +(-3) = 1
а <= 0	(1 <= 0) = false
s:= s + a	s = 11 + 1 = 12
a:= a + d	a = 1 +(-3) = -2
а <= 0	(-2 <= 0) = true
Label1.Caption:= FloatToStr (s)	Label1.Caption = 12

Звертаємо вашу увагу:

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

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