Додаткові задачі, що пропонувалися на Всеукраїнських олімпіадах з програмування у 2001 та

2002 Роках (м. Одеса, м. Чернівці)

Задача “Шифр”

Задано символьний рядок S довжини N (0 % N % 100) та словник, що містить M слів (0 % M % 100), довжина кожного з яких не перебільшує N. Cлова словника і рядок S складаються з літер a, b, …, z.

Завдання

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

Задачі на складання ефективних алгоритмів 273

Рядок у прикладі після викреслювання зайвих букв f і t набуде вигляду abachdsya (було зроблено два викреслювання: abafchtdsya) , та може бути поданий як послідовних наступних слів: a, bach, dsy, a. Вхідні дані

В першому рядку вхідного файла CIPHER. DAT знаходяться два цілих числа N та M, відокремлених пропусками. У другому рядку знаходиться символьний рядок S. У кожному з наступних M рядків знаходиться слово словника.

Приклад вхідного файлу

11 5

abafchtdsya

aba

a

bach

dsy

zero

Вихідні дані

В єдиному рядку вихідного файлу CIPHER. SOL має знаходитись натуральне число - мінімальна кількість викреслювань, після яких зашифрований рядок можна подати у вигляді послідовності слів словника.

Приклад вихідного файлу

2

Задача "Абракадабра"

Під час своєї роботи алгоритм стискання даних методом «сортування блоку» застосовує до блоків даних перетворення, яке визначається наступним чином.

Рядок P називається ротацією рядка S, якщо він утворений циклічним зсувом символів S, тобто якщо S=a₁a₂...a_N, де a _i -

i-ий символ рядка S, то P=a_pa_p+1...a_Na₁...a_p-1, де 1<p<N. Розглянемо таблицю M розміру NxN, рядками якої є всі ротації рядка S, відсортовані у лексикографічному (словниковому) порядку за зростанням.

Нехай рядок L є останнім стовпчиком таблиці M. Пряме перетворення отримує на вхід рядок S, видає рядок L та число K -

2 74 Розділ 3. Лабораторні роботи (Сі)

номер рядка таблиці M, що містить рядок S. (Якщо таких рядків декілька, видається номер будь-якого з них).

Для S='abraka' таблицю M зображено на малюнку. Рядок S знаходиться у другому рядку таблиці M, L=‘karaab’.

Завдання

Напишіть програму ABRAKA, що виконує зворотнє перетворення, тобто отримує на вхід рядок L і число K, та видає рядок S.

Вхідні дані

Перший рядок вхідного файлу ABRAKA.DAT містить два цілих числа: K та N, 1% N %30000, 1% K % N. Другий рядок містить N символів рядка L - маленьких латинських літер.

Вихідні дані

Єдиний рядок вихідного файлу ABRAKA.SOL повинен містити рядок S.

Приклад вхідних та вихідних даних

Задача "Циферблат"

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

Кожне число в послідовності не дорівнює 0, та його запис почитається з одиниці. Кількість цифр в двійковому запису числа не перевищує 25. Загальна кількість цифр на циферблаті не більша за 100.

На малюнку зображено звичний нам циферблат з числами від 1 до 12 (в дещо незвичному вигляді). Його розбито на 4 сектори. Суми для секторів будуть 1, 15, 18 та 36.

Завдання

Напишіть програму DIAL, що за заданою послідовністю визначає кількість різних розбиттів циферблату на сектори, такі що сума чисел у всіх секторах однакова.

Задачі на складання ефективних алгоритмів 275

Вхідні дані

В єдиному рядку вхідного файлу DIAL.DAT задана послідовність чисел. Числа послідовності розділені пропуском.

Вихідні дані

В єдиному рядку вихідного файлу DIAL.SOL повинно знаходитися натуральне число — кількість шуканих розбиттів циферблату на сектори.

Приклад вхідних та вихідних даних

DIAL.SOL 9

DIAL.DAT 101 1 1101

Задача "Кубики"

Тривимірна фігура складається з одиничних кубиків. За фігурою можна побудувати її фронтальну та праву проекції. Очевидно, що за цими двома проекціями не завжди можна відтворити фігуру.

Завдання

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

Вхідні дані

В першому рядку вхідного файлу CUBES.DAT знаходиться три числа N, M та Ê, що задають розміри проекцій (1≤N, M, K≤100). Далі задаються дві проекції: спочатку фронтальна, а потім права. Проекція задається N рядками, кожний з яких складається з чисел 0 та 1, що розділені пропуском. Для фронтальної проекції таких чисел буде M, а для правої — K. 0 означає вільну клітину проекції, 1 — заповнену.

Вихідні дані

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

Приклад вхідних та вихідних даних

CUBES.DAT	CUBES.SOL
2 2 3	4 7
1 0
1 1
0 0 1
1 1 1

2 76 Розділ 3. Лабораторні роботи (Сі++)

ІІ семестр (мова програмування Сі++)

Лабораторна робота ¹1 "Вступ у класи та об’єкти. Елементи об'єктного підходу: модульність та обмеження доступу"

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

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

! конструктори без параметрів та з параметрами ;

! додавання;

! знищення;

! виведення інформації на екран;

! пошук потрібної інформації за конкретною ознакою;

! редагування записів;

! сортування за різними полями.

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

Примітка. Завдання необхідно розв’язати двома способами : ! з використанням функціонального підходу; ! з використанням об’єктно-орієнтованого підходу.

	Предметна область БД	Поля бази даних
1.	„бібліотека”	Інвентарний номер, автор, назва, кількість сторінок, рік видання.
2.	„телефонний довідник”	Прізвище, ім’я, по батькові, домашня адреса, телефон.
3.	„розклад руху літаків”	Номер рейсу, тип літака, напрямок руху, періодичність вильоту.
4.	„колекція компакт-дисків”	Інвентарний номер, назва, об’єм диску, тип, дата запису.

277

5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.	„записна книжка”	Прізвище, ім’я, по батькові, домашня адреса, телефон, електронна пошта.
	„предметний покажчик”	Слово; номера сторінок, де це слово зустрічається.
	„користувачі локальної мережі”	Прізвище, ім’я, по батькові, група, обліковий запис, тип облікового запису.
	„склад товарів”	Інвентарний номер, назва товару, вага, ціна, кількість.
	„рахунки банку”	Прізвище, ім’я, дата останньої операції, сума останньої операції, сума вкладу.
	„успішність студентів”	Прізвище, ім’я, номер групи, оцінки з трьох предметів.
	„камера схову ”	Прізвище, ім’я, дата здачі, термін зберігання, інвентарний номер та назва предмета.
	„каса продажу квитків”	Назва пункту, час відправлення, дата відправлення, час прибуття, дата прибуття, ціна квитка.
	„архів програм”	Назва програми, операційна система, розмір програми, дата запису.
	„список файлів”	Ім’я файла, розширення, розмір, дата створення, атрибути.
	“розклад пар”	Номер пари, предмет, прізвище викладача, форма заняття.

Лабораторна робота ¹2 “ Класова ієрархія та механізм успадкування. Віртуальність та поліморфізм."

Мета роботи: навчитися створювати ієрархії класів та використовувати віртуальність і поліморфізм .

Завдання: Створити клас для зберігання бази даних, вказаної у варіанті, із вказаними полями. Утворити похідний клас, залучивши до нього як мінімум два додаткових поля таким чином, щоб клас набув більшої спеціалізованості. Для другого класу використати конструктор, аби він містив усі аргументи, необхідні для ініціалізації

2 78 Розділ 3. Лабораторні роботи (Сі++)

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

Варіант	Предметна область БД	Поля БД
1.	„предметний покажчик”	Слово; номера сторінок, де це слово зустрічається.
2.	„користувачі локальної мережі”	Прізвище, ім’я, по батькові, група, обліковий запис, тип облікового запису.
3.	„колекція компакт-дисків”	Назва, розмір диску, тип, дата запису.
4.	„перелік товарів”	Назва товару, вага, ціна, кількість.
5.	„домашня бібліотека”	Автор, назва, кількість сторінок, рік видання.
6.	„рахунки банку”	Прізвище, ім’я, дата останньої операції, сума вкладу.
7.	„успішність студентів”	Прізвище, ім’я, номер групи, оцінки з трьох предметів.
8.	„телефонний довідник”	Прізвище, ім’я, по батькові, домашня адреса, телефон.
9.	„студентський журнал”	Прізвище, ім’я, домашня адреса, телефон, дата народження.
10.	„список файлів”	Ім’я файла, розширення, розмір, дата створення, атрибути.
11.	“розклад пар на один день”	Номер пари, предмет, прізвище викладача, форма заняття
12.	„записна книжка”	Прізвище, ім’я, по батькові, домашня адреса, телефон, електронна пошта.
13.	„камера схову”	Прізвище, ім’я, дата здачі, термін зберігання, назва предмета.
14.	„каса продажу квитків”	Назва пункту, час відправлення, дата відправлення, час прибуття, дата прибуття, ціна квитка.
15.	„архів програм”	Назва програми, операційна система, розмір програми, примітка

Лабораторна робота ¹3 279

ІІ. Спроектуйте ієрархію класів для представлення графічних об’єктів. Головним базовим класом для усіх об'єктів є клас Point -точка на площині (у просторі) з її координатами. Опис класів слід розмістити у заголовочному файлі, а визначення функцій і головну функцію програми - в двох окремих файлах. Передбачте методи для створення об’єкта, його переміщення на екрані, зміни розмірів та кольору, обертання на заданий кут. Використайте захищення даних для ізоляції елементів-даних класу від підпрограм, в яких цей клас використовується, а також поліморфізм для визначення дії певних функцій у класовій ієрархії. Напишіть головну функцію, що демонструє роботу з цим класом. Програма повинна містити меню, що дозволяє здійснити перевірку всіх методів класу.

1. коло 16. трапеція

2. кільце 17. графічне вікно

3. паралелепіпед у просторі 18. еліпс

4. сфера 19. куб у просторі

5. прямокутник 20. куля

6. вектор на площині 21. курсор на екрані

7. багатокутник 22. ламана лінія

8. рівнобедрений трикутник 23. п’ятикутник

9. відрізок у просторі 24. паралелограм

10. відрізок на площині 25. ромб

11. шестикутник 26. сектор

12. вектор у просторі 27. тетраедр у просторі

13. курсор на екрані 28. трикутна призма у просторі

14. квадрат 29. прямокутний трикутник

15. конус 30. циліндр

Лабораторна робота ¹3 “Перевантаження операторів. Використання об’єктів