Л4. Цикли й повторення: стан, межі та вибір форми

Коротко про лекцію

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

У Л2 умова обирала одну гілку виконання. Цикл використовує умову багато разів. Після кожного повторення стан програми змінюється, а умова вирішує, чи потрібне наступне повторення.

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

1. Повторювані інструкції утворюють шаблон

Потрібно знайти суму чисел від 1 до 5.

int total{0};
total = total + 1;
total = total + 2;
total = total + 3;
total = total + 4;
total = total + 5;

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

Отже стан має дві частини: поточне число та накопичена сума.

2. Повторюємо, доки умова істинна

C++ має цикл while. Слово while можна читати як «поки». У круглих дужках записують умову продовження, а у фігурних — дії одного повторення.

Загальна форма:

while (condition) {
    // Ця дія повторюється лише доки condition має значення true.
}

Перед кожним повторенням C++ перевіряє умову. Тіло виконується лише для true.

2.1. Перший цикл

#include <iostream>

int main() {
    int number{1};
    int total{0};

    while (number <= 5) {
        total = total + number;
        number = number + 1;
    }

    std::cout << total << "\n";
}

Перед першим повторенням маємо number = 1 і total = 0.

Умова number <= 5 перевіряється перед кожним входом у тіло циклу. Для істинної умови виконуються дві інструкції.

Перша додає поточне число до суми. Друга готує наступне число.

2.2. Один прохід називається ітерацією

Ітерація	`number` на початку	`total` після додавання	`number` після зміни
1	1	1	2
2	2	3	3
3	3	6	4
4	4	10	5
5	5	15	6

Одне виконання тіла циклу називають ітерацією. Після п’ятої ітерації number стає 6. Умова 6 <= 5 хибна, тому цикл завершується.

Термін: ітерація

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

flowchart TD
    A["number = 1; total = 0"] --> B{{"number <= 5?"}}
    B -- "так" --> C["total = total + number"]
    C --> D["number = number + 1"]
    D --> B
    B -- "ні" --> E["вивести total"]

2.3. Стан циклу

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

Як читати цикл

Для кожної ітерації фіксуйте стан до перевірки, результат умови, виконану дію та новий стан. Так видно причину завершення циклу.

Для цього циклу стан утворюють number і total.

(number, total)
→ додати number до total
→ збільшити number
→ новий (number, total)

Таке представлення показує цикл як послідовність змін стану.

2.4. `while` може не виконатися жодного разу

Умова while перевіряється до входу в тіло. Якщо вона хибна одразу, тіло не виконається жодного разу.

int number{6};

while (number <= 5) {
    std::cout << number << "\n";
    number = number + 1;
}

Для number = 6 умова 6 <= 5 одразу хибна. Виведення всередині циклу не відбудеться.

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

3. `do-while`: коли тіло має виконатися щонайменше один раз

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

Для такого випадку C++ має цикл do-while:

do {
    // Ця дія виконається щонайменше один раз.
} while (condition);

Термін: цикл з післяумовою

do-while перевіряє умову після виконання тіла. Тому перша ітерація відбувається завжди.

Зверніть увагу на крапку з комою після while (condition);. Вона належить до синтаксису do-while.

#include <iostream>

int main() {
    int attempt{1};

    do {
        std::cout << "Спроба " << attempt << "\n";
        attempt = attempt + 1;
    } while (attempt <= 3);
}

Тіло виконується для значень 1, 2, 3. Після кожної ітерації змінюється attempt, а потім перевіряється умова.

do-while доречний, коли одна дія справді потрібна до першої перевірки. Якщо такої вимоги немає, while зазвичай читається простіше.

4. Лічильник і накопичувач

4.1. Лічильник

number визначає, який крок виконується зараз. У багатьох циклах така змінна є лічильником.

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

4.2. Накопичувач

total зберігає результат, який поступово оновлюється. Це накопичувач.

Для суми природне початкове значення дорівнює нулю.

int total{0};

Для добутку природне початкове значення дорівнює одиниці.

4.3. Скорочені форми

Повний запис додавання до накопичувача виглядає так:

total = total + number;

Скорочений запис для тієї самої дії має такий вигляд:

total += number;

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

number = number + 1;

Скорочений запис:

++number;

Короткі форми з’являються після повного запису, тому їхній зміст уже відомий.

5. `for`: компактна форма циклу з лічильником

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

Загальна форма має три частини в круглих дужках:

for (початок; умова; зміна) {
    // Код тут працює з поточним значенням лічильника.
}

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

Тепер застосуємо цю форму до суми чисел від 1 до 5.

#include <iostream>

int main() {
    int total{0};

    for (int number{1}; number <= 5; ++number) {
        total += number;
    }

    std::cout << total << "\n";
}

Заголовок має три частини:

for (int number{1}; number <= 5; ++number)

Частина	Коли виконується	Роль
`int number{1}`	один раз на початку	створює лічильник
`number <= 5`	перед кожною ітерацією	вирішує, чи продовжувати
`++number`	після кожної ітерації	готує наступний стан

Цей for і попередній while дають результат 15.

5.1. Порядок дій усередині `for`

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

flowchart TD
    A["int number = 1"] --> B{"number <= 5?"}
    B -- "ні" --> F["вихід із циклу"]
    B -- "так" --> C["тіло циклу"]
    C --> D["++number"]
    D --> B

Через цей порядок ++number не виконується перед першою ітерацією. Так само він не виконується після того, як умова стала хибною.

6. Коли кількість повторів визначається під час виконання

Нехай на рахунку є 100, щомісяця додається 250, а мета становить 1000.

#include <iostream>

int main() {
    int balance{100};
    const int monthly_deposit{250};
    const int target{1000};
    int months{0};

    while (balance < target) {
        balance += monthly_deposit;
        ++months;
    }

    std::cout << "Місяців: " << months << "\n";
    std::cout << "Баланс: " << balance << "\n";
}

Умова balance < target прямо описує причину продовження. Коли баланс стає 1100, умова стає хибною.

months рахує виконані кроки. balance є станом, який наближається до цілі.

Для задач, де повторення триває до події або стану, while часто читається природніше.

6.1. Трасуємо цикл до умови завершення

Для початкового балансу 100 зміни виглядають так:

Ітерація	Баланс до внеску	Баланс після внеску	`months`
1	100	350	1
2	350	600	2
3	600	850	3
4	850	1100	4

Після четвертої ітерації умова balance < target стає хибною. Значення 1100 перевищує ціль, але це не помилка: правило говорить лише досягти щонайменше 1000.

Таблиця також показує, чому months треба збільшувати всередині тіла. Кожне збільшення відповідає одному фактично виконаному внеску.

6.2. Сигнальне значення може завершувати інтерактивний цикл

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

Термін: сигнальне значення

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

У прикладі нуль завершує введення. Введіть одним рядком 4 7 -2 0. Потім повторіть запуск із власною послідовністю.

#include <iostream>

int main() {
    int number{0};
    int sum{0};

    std::cout << "Вводьте цілі числа. Нуль завершує введення: ";
    std::cin >> number;

    // Нуль є сигнальним значенням: він завершує ввід і не входить до суми.
    while (number != 0) {
        sum += number;
        std::cin >> number;
    }

    std::cout << "\nСума: " << sum << "\n";
}

Перший std::cin створює початковий стан до перевірки while. Усередині циклу сума змінюється, а наступне читання готує нову перевірку. Значення 0 робить умову хибною і не додається до суми.

7. Межі циклу й помилка на одну ітерацію

7.1. Діапазон від `0` до `4`

#include <iostream>

int main() {
    for (int index{0}; index < 5; ++index) {
        std::cout << index << ' ';
    }
    std::cout << "\n";
}

Умова index < 5 зупиняє цикл перед значенням 5. Для проходу від 1 до 5 включно потрібна умова number <= 5. Отже < і <= вибираємо за точним набором значень, який повинен пройти цикл.

7.2. Чотири питання до межі

Яке значення лічильника буде першим?
Яке значення повинно бути останнім?
Яким стане лічильник після останньої ітерації?
На якому значенні умова вперше стане хибною?

Ці відповіді швидко викривають помилку на одну ітерацію.

7.3. Кількість ітерацій перевіряємо через конкретні значення

Для index = 0; index < 5; ++index тіло отримує значення 0, 1, 2, 3, 4. Це рівно п’ять ітерацій.

Для number = 1; number <= 5; ++number тіло отримує 1, 2, 3, 4, 5. Тут теж п’ять ітерацій, хоча початкове значення інше.

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

8. Нескінченний цикл виникає через незмінний стан

int number{1};

while (number <= 5) {
    std::cout << number << "\n";
}

number лишається 1. Умова number <= 5 весь час істинна.

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

Для лічильника прогресом може бути ++number. Для накопичення до цілі прогресом є збільшення balance. Якщо жодна інструкція не наближає стан до завершення, цикл треба перевірити ще до запуску.

flowchart TD
    A["Початковий стан"] --> B{"Умова істинна?"}
    B -- "ні" --> F["Цикл завершено"]
    B -- "так" --> C["Виконати тіло"]
    C --> D{"Стан наблизився до завершення?"}
    D -- "так" --> B
    D -- "ні" --> E["Ризик нескінченного циклу"]

9. Чотири шаблони стану циклу

9.1. Лічильник

Відповідає на питання «скільки разів сталася подія?».

count = 0
для кожного підхожого випадку:
    count збільшується на 1

9.2. Накопичувач

Відповідає на питання «яка накопичена сума?».

total = 0
для кожного значення:
    total оновлюється

9.3. Поточний найкращий результат

Нехай послідовно надходять значення 8, 3, 12, 7.

Нове значення	Поточний максимум після перевірки
`8`	`8`
`3`	`8`
`12`	`12`
`7`	`12`

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

У наступній лекції цей шаблон перенесемо на послідовність значень.

9.4. Пошук

Стан пошуку може містити логічне значення found.

Для значень 4, 9, 13, 6 і правила «знайти перше число від 10» стан зміниться на found = true при значенні 13.

flowchart TD
    A["наступне значення"] --> B{{"умова пошуку істинна?"}}
    B -- "ні" --> A
    B -- "так" --> C["found = true"]
    C --> D["завершити пошук"]

10. `continue` і `break`

10.1. `continue` пропускає решту поточної ітерації

Інструкція continue одразу припиняє поточну ітерацію та переходить до наступної перевірки циклу. Код, що стоїть нижче continue у цій ітерації, не виконується.

#include <iostream>

int main() {
    for (int number{1}; number <= 5; ++number) {
        if (number == 3) {
            continue;
        }
        std::cout << number << ' ';
    }
    std::cout << "\n";
}

Для number = 3 інструкція continue переходить до наступної ітерації. Число 3 не виводиться.

10.2. `break` завершує весь цикл

Інструкція break припиняє весь поточний цикл. Виконання продовжується з першої інструкції після нього.

#include <iostream>

int main() {
    for (int number{1}; number <= 8; ++number) {
        if (number == 5) {
            break;
        }
        std::cout << number << ' ';
    }
    std::cout << "\n";
}

Для number = 5 виконується break. Цикл завершується, тому 5 та наступні числа вже не виводяться.

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

10.3. `continue` потребує особливої уваги у `while`

У циклі for зміна лічильника з заголовка виконається після continue. У while зміна стану часто записана вручну в тілі.

int number{1};

while (number <= 5) {
    if (number == 3) {
        continue;
    }
    ++number;
}

Для number = 3 виконується continue, тому ++number пропускається. number назавжди лишається 3, і цикл не завершується.

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

11. Як перевіряти цикл

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

Для циклу корисно мати щонайменше три масштаби перевірки:

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

До них додаються точні межі, специфічні для задачі. Для циклу 0..4 це, наприклад, останнє дозволене значення 4 та перше заборонене 5.

Окремо шукайте контрприклад: вхід, на якому правдоподібне правило дає неправильний результат.

Термін: контрприклад

Контрприклад — конкретний вхід, який спростовує припущення про правильність правила або алгоритму. Одного такого входу достатньо, щоб відкинути загальне твердження.

Тест, який одного разу знайшов дефект, варто зберігати після виправлення. Такий тест стає регресійним.

Термін: регресійний тест

Регресійний тест уже виявляв конкретний дефект. Після виправлення він допомагає помітити повернення тієї самої помилки.

12. Інтерактивна самоперевірка лекції

Самоперевірка перевіряє трасування циклів, межі, кількість ітерацій, накопичення та завершення.