Алгоритми з повторенням і розгалуженням

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

Всі мови програмування мають такі спеціальні вказівки (оператори) для галуження залежно від справдження певної умови.

Є такі умовні оператори:

• повний — з двома гілками;
• неповний — з однією гілкою;
• множинний вибір.

Повний оператор (розгалуження) має такий вигляд:
якщо умова вказівка₁ інакше вказівка₂

При справдженні умови буде виконано вказівку₁, інакше — вказівку₂.

Тут під вказівками розуміємо як окрему вказівку, так і серію (послідовність) вказівок10. Тому у блок-схемі повної вказівки розгалуження замість слова «вказівка» вжито слово «серія».

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

Неповна вказівка розгалуження має такий вигляд:
якщо умова вказівка

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

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

Цикл — різновид керівної конструкції мови програмування, призначеної для організації багаторазового виконання послідовності вказівок.

Tіло циклу — послідовність вказівок, призначена для багаторазового виконання.

Ітерація — одноразове виконання тіла циклу.

Умова виходу (завершення) циклу або умова продовження циклу залежно від того, як тлумачити її істинність — як ознаку необхідності завершення чи продовження циклу — висловлювання, що визначає, чи буде виконано наступну ітерацію, чи буде завершено цикл.

Лічильник ітерацій циклу (або просто лічильник циклу) — змінна, величина якої є номером поточної ітерації.

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

Більшість мов програмування надають засоби для дострокового керування циклом. Наприклад:

• оператор завершення циклу, тобто виходу з циклу незалежно від істинності умови виходу (у мові С — break);
• оператори пропущення ітерації (у мові С — continue).

Цикли, як і умовні оператори, можуть бути вкладеними. У цьому випадку розрізняють зовнішній і внутрішній цикли.

Зазвичай мови програмування мають такі види циклів:
— безумовний;
— з лічильником;
— з передумовою;
— з післяумовою.

Блок-схема оператора безумовного цикла має такий вигляд:

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

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

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

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

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

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

Завдання 1. Вказати, які структури мови програмування — умовний оператор (повний, неповний, пауза) чи цикл (безумовний, з лічильником, з передумовою чи з післяумовою) — найдоречніше (найзручніше) використати при розв'язанні таких завдань.

1. Дано два числа. Знайти більше число.
2. За допомогою мірної посудини об'ємом 1 літр наповнити водою іншу порожню посудину, якщо об'єм останньої: a) відомий; б) невідомий.
3. Знайти суму чисел від 1 до 100.
4. Визначити агрегатний стан води (крига, рідина, пара) за її температурою.
5. На числовій прямій задано дві точки своїми координатами. Знайти, яка з точок знаходиться далі від початку числової осі.
6. Є порожні діжка і відро, причому відро легко входить у діжку повністю. Використовуючи відро, наповнити діжку водою з криниці натуральною кількістю відер води, не проливши з неї жодної краплини.
7. Капосний папуга навчився висмикувати у пірата Сільвера волосини, які ще залишилися у того на голові. Почавши з однієї волосини, папуга щодня збільшував кількість волосин удвічі. Через скільки днів пірату не знадобиться гребінець, якщо спочатку в нього на голові було N волосин?
8. На дверях ліфта висіло загрозливе попередження про те, що двері самі зачиняються в той самий момент, коли зайвий за вагою пасажир переступить поріг ліфта. Котрий пасажир постраждає, якщо ліфт витримує вагу не більше S кг, а вага пасажирів, що стоять у черзі до ліфта, дорівнює відповідно a₁, a₂, a₃, …, a_n кг.
9. Є 9 монет, одна з них — фальшива (легша). За допомогою двох зважувань на терезах знайти її.

Завдання 2. Для кожної з 7 структур мови програмування: умовний оператор (повний, неповний, пауза) чи цикл (безумовний, з лічильником, з передумовою чи з післяумовою) сформулювати умови якомога простіших завдань, для виконання яких найдоречніше (найзручніше) використати саме цю структуру. Ці умови мають якомога більше відрізнятися від перелічених у попередньому завданні.