Мета та підготовка
Побудувати алгоритм відбору навчальних задач за доступним часом, представити його псевдокодом і перевірити виконуваною програмою. Потрібно знати змінні, умови, цикли та функції. Встановіть Python 3.11 або новішу підтримувану версію. Перевірте команду python --version; у системах, де виконуваний файл має назву python3, використовуйте її в усіх командах.
Створіть порожню папку selection-lab та файл demo.py. Робота використовує стандартну бібліотеку, тому додаткові пакети не потрібні. Зберігайте вхідні набори й пояснення очікуваних результатів поруч із кодом. Визначте одиницю тривалості: у всіх прикладах це цілі хвилини.
Теоретичний мінімум
Контракт функції задає допустимі входи й результат. Лінійний пошук переглядає елементи послідовно. Граничний випадок виникає на межі умови: тривалість дорівнює бюджету, бюджет нульовий, список порожній. Інваріант нашого демонстраційного циклу: результат містить саме придатні елементи з уже переглянутої частини списку, у початковому порядку.
Демонстраційний алгоритм відбирає кожну задачу, яка окремо вкладається в бюджет. Він не складає загальний план кількох задач. Це важлива частина контракту: сума тривалостей повернутих елементів може перевищувати бюджет. Змінити постановку на пошук комбінації означає розробити інший алгоритм і перевірки.
Демонстраційний приклад: повний код
from dataclasses import dataclass
@dataclass(frozen=True)
class Task:
title: str
minutes: int
def eligible(tasks: list[Task], budget: int) -> list[Task]:
if budget < 0:
raise ValueError("Бюджет не може бути від’ємним")
if any(task.minutes <= 0 for task in tasks):
raise ValueError("Тривалість задачі має бути додатною")
result = []
for task in tasks:
if task.minutes <= budget:
result.append(task) # Зберігаємо початковий порядок.
return result
if __name__ == "__main__":
tasks = [Task("Читання", 15), Task("Конспект", 20), Task("Тести", 35)]
selected = eligible(tasks, 20)
assert [task.title for task in selected] == ["Читання", "Конспект"]
assert eligible([], 20) == []
assert eligible(tasks, 0) == []
print([(task.title, task.minutes) for task in selected])
Запустіть python demo.py. Очікуваний результат: [('Читання', 15), ('Конспект', 20)]. dataclass зберігає назву й тривалість у зрозумілій структурі. any повертає істину, якщо хоча б одна задача порушує контракт. Новий список result відокремлений від входу; append додає посилання на незмінювану задачу. Розуміння цієї дії допоможе пояснити, чому вхідний список залишається тим самим.
Покрокове виконання
Спочатку запишіть контракт словами: додатні тривалості, невід’ємний бюджет, незмінність входу, збереження порядку. Потім складіть псевдокод із перевіркою та циклом. Побудуйте таблицю трасування для бюджету 20: назва, тривалість, результат умови, поточний список. Для першої задачі додається один елемент; друга приймається на границі; третя пропускається.
Додайте набір із повторюваними назвами й різними тривалостями. Перевірте, що програма не об’єднує такі задачі автоматично. Окремо передайте задачу нульової тривалості й зафіксуйте ValueError. Після кожної зміни порівняйте результат із попередньо записаним очікуванням, щоб випадково не пристосувати пояснення до фактичного виводу.
Самостійне завдання
Реалізуйте функцію вибору найдовшої задачі, яка окремо вкладається в бюджет. Якщо кілька мають однакову тривалість, поверніть першу у вхідному списку. Якщо придатних немає, поверніть None. Напишіть контракт, псевдокод і власну реалізацію. Демонстрація навчає перебору й перевірки, а вибір максимуму ви маєте спроєктувати самостійно.
Підготуйте щонайменше шість перевірок: звичайний вибір, точна границя, нічиї, порожній список, відсутність придатних і некоректні дані. Додатковий варіант: повернути всі задачі з максимальною придатною тривалістю; поясніть зміну типу результату та пам’яті. Не додавайте сортування без обґрунтування його впливу на правило першого елемента.
Типові помилки та налагодження
Знак < замість <= відкидає задачу на границі. Початкове значення «кращої тривалості» може приховати відсутність результату. Зміна вхідного списку під час перебору створює пропуски. Друк і повернення — різні дії: тест повинен отримати значення з функції. Відтворюйте збій мінімальним набором із двох або трьох елементів і записуйте стан після кожного кроку.
Результат і контрольні запитання
Збережіть demo.py, файл власної реалізації, таблицю трасування та результати перевірок. Поясніть інваріант, завершення й складність. Чому відбір усіх придатних задач не є планом у межах загального бюджету? Як перевірити незмінність входу? Який приклад відрізняє > від >=? Відповіді повинні посилатися на конкретні дані вашої роботи.
Таблиця ручного трасування та аргументація
Перед запуском створіть таблицю зі стовпцями номер завдання, його тривалість, доступний бюджет, результат перевірки та поточний кандидат. Для демонстраційного алгоритму кожне завдання оцінюється окремо: придатність одного не зменшує бюджет для наступного. Після проходу поясніть, чому кожен включений елемент задовольняє умову, а кожен пропущений — її порушує.
Для основного завдання «найдовше придатне» інваріант інший: поточний кандидат має найбільшу тривалість серед уже переглянутих придатних елементів. Якщо тривалості рівні, зберігайте перший у вхідному порядку згідно з контрактом. Самостійно запишіть, за якої умови кандидат змінюється; це допоможе уникнути випадкового вибору останнього при нічиїй.
Підготуйте три контрольні набори: жодного придатного завдання; кілька придатних із різними тривалостями; два з однаковою максимальною тривалістю. Для кожного перед запуском запишіть очікуване значення. Якщо програма повертає None, поясніть цей стан в інтерфейсі або звіті без вигаданого завдання з нульовою тривалістю.
У висновку оцініть число перевірок як функцію довжини списку. Однопрохідний вибір потребує перегляду кожного елемента; додатковий кандидат займає сталий обсяг пам’яті. Порівняйте це з повним сортуванням та поясніть, які додаткові можливості сортування потрібні або зайві для вашого контракту. Числовий час маленького запуску не замінює аналізу складності.
Схема процесу
Уточнюємо правило й одиниці вимірювання.
Самоперевірка
Як обґрунтувати відповідь своїми словами?
Підсумок
Відбір потребує точного контракту. Трасування пояснює зміну стану, а граничні перевірки виявляють помилки умов. Самостійний вибір максимуму розвиває демонстраційний перебір без підміни постановки задачі.