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

1. Цикл з передумовою в алгоритмах.

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

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

Задача. Є діжка і відро. Використовуючи відро, наповнити діжку водою з колодязя.

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

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

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

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

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

І так до тих пір, поки результат перевірки цієї умови стане false. Після цього можна припинити виконання алгоритму.

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

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

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

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

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

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

У цьому алгоритмі команди 3–5 можуть бути виконані більше одного разу.

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

Зверніть увагу: команди 3–5 саме можуть бути виконані більше одного разу, а не обов’язково виконуються більше одного разу.

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

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

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

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

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

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

2. Цикл з післяумовою в алгоритмах.

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

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

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

Загальний вигляд блок-схеми циклу з післяумовою наведено на рисунку.

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

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

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

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

Практичні завдання:

Виконайте алгоритми: