Від вимог до алгоритму

Як побудувати алгоритм із вимог задачі

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

Розгляньмо навчальне паркування: перша почата година коштує 20 умовних одиниць, кожна наступна – 15, а введення задається цілими хвилинами від 1 до 1440. Слово «почата» означає округлення кількості годин угору. Звичайне ціле ділення minutes / 60 неправильне для 61 хвилини: воно дає 1, хоча оплачуються дві години. Для додатних хвилин формула (minutes + 59) / 60 дає потрібний результат. Додавання 59 безпечне лише тому, що відома невелика верхня межа входу.

Нехай hours – обчислена кількість годин. Оплата 20 + (hours - 1) * 15 відокремлює першу годину від решти. Не слід множити всі години на 15, а потім додавати 20: так перша година буде врахована двічі. Перед кодом корисно заповнити таблицю вручну.

Таблиця 2.1. Тести на межах навчального тарифу

Хвилини	Години	Оплата й причина
1	1	20: почалася перша година.
59	1	20: друга година ще не почалася.
60	1	20: рівно одна година.
61	2	35: почалася друга година.
120	2	35: рівно дві години.
121	3	50: почалася третя година.

Ця таблиця перевіряє не синтаксис, а тлумачення умови. Випадки 59,60,61 важливіші за три випадкові значення всередині одного тарифного інтервалу. Для будь-якої порогової умови використовуйте правило «безпосередньо до межі, точно на межі, безпосередньо після межі». Для дробових величин крок біля межі обирають відповідно до точності вхідних даних, наприклад 0.01 грн або 0.1 км.

Накопичувач, лічильник і поточний результат

У задачі із серією вимірювань потрібно розрізняти три ролі змінних. Поточне value зберігає одне введене значення. count рахує прийняті вимірювання. sum накопичує їхню суму. Якщо введене значення відхилено, не слід збільшувати count або додавати його до sum. Інакше середнє врахує дані, яких у звіті немає.

Початковий стан для суми – 0, для добутку – 1. Для мінімуму зручніше окремо прийняти перше коректне значення, а потім порівнювати наступні. Початковий мінімум 0 дасть неправильну відповідь, якщо всі температури додатні. Початковий максимум 0 аналогічно помилковий для повністю від’ємної серії. Можна скористатися межами типу, але порожню серію все одно доведеться розпізнавати окремо.

Інваріант циклу – твердження, яке справджується перед кожною ітерацією і зберігається після неї. Для накопичення це «sum дорівнює сумі count уже прийнятих значень». Спочатку твердження правильне для порожнього набору. Додавання одного перевіреного значення та збільшення лічильника зберігають його. Коли введення закінчилося, воно пояснює, чому підсумок є правильним. Такий короткий доказ допомагає знайти зайве обнулення суми всередині циклу.

Послідовність дій при помилці

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

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

Для числових таблиць з дробовим кроком повторне додавання кроку накопичує похибку. Якщо кількість рядків відома, можна обчислювати точку як start + index * step, де index цілий. Окремо встановіть максимальну кількість рядків. Умова x <= end сама по собі не гарантує, що через похибку останній очікуваний рядок буде надруковано рівно один раз.

Таблиця станів замість здогадок

Для меню корисно записати не лише команди, а й переходи стану. Стан навчального банкомата – поточний баланс. Команда перегляду нічого не змінює, поповнення збільшує баланс лише після перевірки межі, зняття зменшує лише за достатніх коштів. Невідома команда також залишає стан незмінним. Такий опис дозволяє перевіряти програму навіть без читання її реалізації.

Наприклад, початковий баланс 1000. Команда зняття 1500 має видати відмову, після чого перегляд знову повинен показати 1000. Якщо він показує−500, перевірка запізнилася. Якщо показує 2500, розробник помилково додав суму під час «відкату», хоча віднімання не відбулося. Послідовності команд перевіряють зв’язок операцій, якого не видно при окремому тесті кожної гілки switch.

Для випадкової гри також є стан: таємне число, кількість прийнятих спроб і поточна відповідь. Неприпустиме число 11 не повинно збільшити число спроб, якщо так записано в умові. Введення 0 завершує гру й не повинно вивести «Higher». Порядок перевірок у коді має повторювати цей зміст: синтаксис, команда виходу, діапазон, рахунок спроб, порівняння з ціллю.

Звіт про перевірку

Корисна таблиця тестів має колонки «вхід», «очікуваний результат», «фактичний результат» і «пояснення». Очікуваний результат записують до запуску. Інакше легко назвати будь-яку відповідь програми правильною. Для помилкового введення зазначайте також, чи програма повторила запит, чи завершилася, та який код завершення повернула. Саме повідомлення «error» не доводить правильного подальшого стану.

Не обмежуйте звіт скриншотом успішного запуску. Запишіть ключі компіляції та дані, щоб інша людина могла повторити перевірку. Для випадкових алгоритмів збережіть зерно і версію бібліотеки; для дробових результатів визначте допуск порівняння, а для таблиць – очікувану кількість рядків. Відсутність аварії не дорівнює правильності відповіді.

Перевірка алгоритму і типові помилки

Для кожної програми складіть три групи тестів: звичайні дані, граничні значення та некоректне введення. Для суми перших N чисел це можуть бути N=5, N=0 і від’ємне N. Нульові обсяги не завжди є помилкою: порожня сума дорівнює нулю, але середнє порожньої сукупності потребує окремого рішення. Пояснення цієї різниці має передувати написанню ділення в коді.

Таблиця 2.2. Джерела помилок у простих алгоритмах

Помилка	Наслідок і виправлення
sum / count для цілих	Дробова частина втрачається; перетворити операнд перед діленням і перевірити count != 0.
= замість ==	Стан змінюється замість перевірки; читати /W4 і використовувати змістовні умови.
Лише cin.clear()	Некоректний текст залишається; відкинути залишок рядка, а EOF обробити завершенням.
Неперевірений крок циклу	Нульовий або неправильний знак кроку може спричинити нескінченність; перевірити до запуску.
Перевірка після переповнення	Невизначена поведінка вже настала; перевіряти можливість операції до її виконання.
Ширина формату як обмеження	Завелике число не обрізається; перевіряти дані незалежно від оформлення.