Львів, ЛНУ імені Івана Франка, 2022

Вступ

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

Кожному випускникові вищого навчального закладу, що вивчав програмування, необхідно навчитися класифікувати задачі, застосовувати до їхнього розв’язування відомі алгоритми, враховуючи особливості конкретної задачі, необхідно оволодіти основними методами розробки алгоритмів. Саме описові алгоритмів та методів їхньої розробки присвячено цей посібник. У його першій частині (розділи 1–8) наведено розв’язки окремих типових задач, докладно описано процес створення та удосконалення кожного алгоритму. Її можна використовувати і як своєрідний «розв’язник» задач з програмування, і для того, щоб набути початкового досвіду проектування алгоритмів. Друга частина (розділи 9–15) розрахована на читачів, що зважилися іти далі. Її присвячено описові та ілюстрації основних методів розробки алгоритмів. Вони стануть у пригоді тим, кому доведеться створювати програми для зовсім нових, ще не розв’язаних раніше задач.

Усі приклади програм у посібнику написано мовою C++. Сподіваємося, що їх зможуть легко зрозуміти ті читачі, які вивчають будь-яку іншу мову програмування високого рівня. Побудова алгоритму значною мірою залежить від вибору структур даних для відображення у програмі даних задачі. У кожному прикладі це питання буде обговорено зокрема, проте сподіваємось, що читач володіє знаннями щодо таких структур даних як масив, рядок, файл, список, стек, черга, дерево. Ні один з прикладів не претендує на досконалість. Автори розраховують на те, що читачі спробують запропонувати власні варіанти алгоритмів чи модифікації описаних.

Нижче наведено посилання на тексти розділів та програмні проекти до них.

1. Задачі цілочислової арифметики

Середнє арифметичне цифр числа
Чи є число паліндромом?
Гіпотеза Безу
Запис числа у шістнадцятковій системі
Розкладання числа на прості множники

Програми: IntArithm

Вступ

1. Задачі цілочислової арифметики

2. Програми з простим повторенням

3. Поєднання повторення з галуженням

4. Вкладені цикли в матричних задачах

5. Основні алгоритми сортування

6. Сортування структур даних

7. Обчислення з заданою точністю

8. Опрацювання текстової інформації

9. Покрокова розробка програм

10. Рекурсія

11. Програмування з поверненням назад

12. Метод часткових цілей

13. Метод підйому. Евристики

14. Генетичні алгоритми

15. Об’єктно-орієнтоване проектування