С. П. Мальцев, Э. С. Бадмаева
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Задачник
Улан-Удэ
2025
Стр.1
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«БУРЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМЕНИ ДОРЖИ БАНЗАРОВА»
С. П. Мальцев, Э. С. Бадмаева
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Рекомендовано Экспертным советом университета
в качестве задачника для обучающихся по направлению подготовки
02.03.03 Математическое обеспечение и администрирование
информационных систем
Улан-Удэ
Издательство Бурятского госуниверситета имени Доржи Банзарова
2025
1
Стр.2
УДК 004.421(076.1)
ББК 32.97я7-4
М 21
Утверждено к печати Экспертным советом университета
Протокол № 2 от 10 октября 2025 г.
Рецензенты
В. В. Рабданова
кандидат экономических наук, доцент кафедры «Программная инженерия
и искусственный интеллект», Восточно-Сибирского государственного
университета технологий и управления
А. В. Бадеев
кандидат физико-математических наук, доцент кафедры информационной
безопасности, Бурятский госуниверситет им. Д. Банзарова
Мальцев С. П.
М 21
Алгоритмы и структуры данных: задачник / С. П. Мальцев,
Э. С. Бадмаева. — Улан-Удэ: Издательство Бурятского госуниверситета
им. Д. Банзарова 2025. — 114 с.
ISBN 978-5-9793-1057-2
Задачник содержит подбор задач для проведения лабораторных работ
по дисциплине «Алгоритмы и структуры данных», но будет полезен
для всех, кто интересуется программированием и хочет углубить свои знания
в этой области.
Предназначено для обучающихся по направлению подготовки
02.03.03 Математическое обеспечение и администрирование информационных
систем.
УДК 004.421(076.1)
ББК 32.97я7-4
ISBN 978-5-9793-1057-2
2
© С. П. Мальцев, Э. С. Бадмаева, 2025
© Бурятский госуниверситет
им. Д. Банзарова, 2025
Стр.3
Оглавление
Предисловие ............................................................................... 8
Введение ................................................................................... 11
Задача 0.1. Дольки .................................................................................... 11
Задача 0.2. Попадание в круг ................................................................... 11
Задача 0.3. Сумма отрезка ....................................................................... 12
Задача 0.4. Треугольник Паскаля ............................................................ 12
Задача 0.5. Фигура .................................................................................... 13
Задача 0.6. Покраска забора .................................................................... 15
Часть I ....................................................................................... 16
Глава 1 Теория Чисел .......................................................... 16
Задача 1.1 Делители числа ....................................................................... 16
Задача 1.2 Проверка на простоту ............................................................ 16
Задача 1.3 Простые в отрезке .................................................................. 17
Задача 1.4 Бинарное возведение в степень ............................................ 17
Задача 1.5 Основная теорема арифметики ............................................. 18
Задача 1.6 НОД и НОК ............................................................................. 19
Задача 1.7 Расширенный алгоритм Евклида .......................................... 19
Задача 1.8 Обратный в кольце по модулю ............................................. 20
Глава 2 Линейные контейнеры .......................................... 21
Задача 2.1 Скобочки I ............................................................................... 21
Задача 2.2 Скобочки II ............................................................................. 22
Задача 2.3 Очередь в кабинет .................................................................. 23
Задача 2.4 Не лезь вперед очереди! ........................................................ 23
Задача 2.5 Красивые массивы I ............................................................... 25
Задача 2.6 Орки и шаман ......................................................................... 26
Задача 2.7 Стек на основе очереди ......................................................... 27
Задача 2.8 Красивые массивы II .............................................................. 28
Глава 3 Нелинейные контейнеры ...................................... 30
Задача 3.1 Различные числа ..................................................................... 30
Задача 3.2 Замены ..................................................................................... 30
3
Стр.4
Задача 3.3 Отрезок со всеми числами ..................................................... 31
Задача 3.4 Словарь ................................................................................... 32
Задача 3.5 Работа по приоритету ............................................................ 33
Задача 3.6 Поиск пар с равной суммой .................................................. 34
Глава 4 Сортировки ............................................................. 36
Задача 4.1 Сортировка пузырьком .......................................................... 36
Задача 4.2 Сортировка вставками ........................................................... 36
Задача 4.3 Сортировка выбором ............................................................. 37
Задача 4.4 Шейкерная сортировка .......................................................... 37
Задача 4.5 Быстрая сортировка ............................................................... 38
Задача 4.6 Сортировка слиянием ............................................................ 39
Задача 4.7 Пирамидальная сортировка ................................................... 39
Задача 4.8 Сортировка подсчетом ........................................................... 40
Задача 4.9 Блочная сортировка ............................................................... 41
Глава 5 Поиск ....................................................................... 42
Задача 5.1 Игра в угадай число ............................................................... 42
Задача 5.2 Корень числа ........................................................................... 42
Задача 5.3 Поиск минимума в отрезке на параболе .............................. 43
Задача 5.4 Подземелье ............................................................................. 43
Задача 5.5 Точка в многоугольнике ........................................................ 44
Задача 5.6 Передача сообщений .............................................................. 45
Задача 5.7 Интерполяционный поиск ..................................................... 46
Глава 6 Рекурсия. Перебор ................................................. 48
Задача 6.1 Рекурсивный факториал ........................................................ 48
Задача 6.2 Рекурсивные числа Фибоначчи ............................................ 48
Задача 6.3 Ферзи на шахматной доске ................................................... 49
Задача 6.4 Ханойские башни ................................................................... 49
Задача 6.5 Ходы коня ............................................................................... 50
Задача 6.6 Генерация всех перестановок ............................................... 51
Задача 6.7 Поиск номера перестановки .................................................. 52
Задача 6.8 Поиск перестановки по номеру ............................................ 52
Глава 7 Линейные алгоритмы ............................................ 53
Задача 7.1 Префиксная сумма ................................................................. 53
Задача 7.2 Произведение на отрезке ....................................................... 53
4
Стр.5
Задача 7.3 Подотрезок с максимальной суммой.................................... 54
Задача 7.4 Поиск в окне фиксированной длины .................................... 55
Задача 7.5 Ближайший меньший слева .................................................. 56
Задача 7.6 Ближайший больший справа ................................................. 56
Задача 7.7 Поиск в плавающем окне ...................................................... 57
Задача 7.8 Гистограммы........................................................................... 57
Задача 7.9 Большой белый прямоугольник ............................................ 58
Задача 7.10 Охранник ............................................................................... 59
Часть II ...................................................................................... 61
Глава 8 Геометрия ............................................................... 61
Задача 8.1 Знаковая площадь треугольника ........................................... 61
Задача 8.2 Длина объединения отрезков на прямой ............................. 61
Задача 8.3 Нахождение площади простого многоугольника ............... 62
Задача 8.4 Выпуклая оболочка ................................................................ 63
Задача 8.5 Поиск пары ближайших точек .............................................. 64
Задача 8.6 Пара пересекающихся отрезков ............................................ 64
Задача 8.7 Минимальный периметр ........................................................ 65
Глава 9 Жадные алгоритмы ................................................ 67
Задача 9.1 Калькулятор с процентами .................................................... 67
Задача 9.2 Размен монет .......................................................................... 67
Задача 9.3 Рюкзак ..................................................................................... 68
Задача 9.4 Непересекающиеся заявки .................................................... 69
Глава 10 Динамическое программирование ..................... 70
Задача 10.1 Зайчик .................................................................................... 70
Задача 10.2 Фибоначчи ............................................................................ 70
Задача 10.3 Без двух нулей подряд ......................................................... 70
Задача 10.4 Количество N-значных чисел.............................................. 71
Задача 10.5 Количество путей в таблице ............................................... 71
Задача 10.6 Таблица с препятствиями .................................................... 72
Задача 10.7 Зайчик с выносливостью и временем ................................. 72
Задача 10.8 Рюкзак ................................................................................... 73
Задача 10.9 Багаж ..................................................................................... 74
Задача 10.10 Сумма чисел ....................................................................... 75
Задача 10.11 Регулярное выражение ...................................................... 76
5
Стр.6
Задача 10.12 Задача о паркете ................................................................. 76
Задача 10.13 Игральные кости ................................................................ 77
Глава 11 Основы теории графов ........................................ 78
Задача 11.1 Преобразование графов ....................................................... 78
Задача 11.2 Компоненты .......................................................................... 79
Задача 11.3 Время входа и выхода .......................................................... 80
Задача 11.4 Топологическая сортировка ................................................ 81
Задача 11.5 Поиск цикла .......................................................................... 82
Задача 11.6 Кратчайшие пути .................................................................. 82
Задача 11.7 Самый длинный путь ........................................................... 83
Задача 11.8 01 БФС.................................................................................. 84
Задача 11.9 1-k БФС ................................................................................ 85
Задача 11.10 Лабиринт ............................................................................. 86
Задача 11.11 Лабиринт с сокровищами .................................................. 87
Глава 12 Структуры данных ............................................... 89
Задача 12.1 Пирамида из треугольников ................................................ 89
Задача 12.2 Перекрестки .......................................................................... 90
Задача 12.3 Эксперимент с отрезками .................................................... 91
Задача 12.4 Парады в городе N ............................................................... 92
Задача 12.5 Трехмерные запросы на подсчёт ........................................ 94
Задача 12.6 Декартово дерево ................................................................. 96
Глава 13 Теория графов ...................................................... 97
Задача 13.1 Алгоритм Дейкстры ............................................................. 97
Задача 13.2 Алгоритм Флойда-Уоршелла .............................................. 98
Задача 13.3 Алгоритм Прима .................................................................. 98
Задача 13.4 Алгоритм Форда-Беллмана ................................................. 99
Задача 13.5 Алгоритм A* ....................................................................... 100
Задача 13.6 Алгоритм Краскала ............................................................ 101
Задача 13.7 Наименьший общий предок .............................................. 102
Задача 13.8 Двудольный граф ............................................................... 103
Задача 13.9 Танцы .................................................................................. 105
Задача 13.10 Водопровод ....................................................................... 106
Глава 14 Строковые алгоритмы и структуры ................. 108
Задача 14.1 Хеши .................................................................................... 108
6
Стр.7
Задача 14.2 Поиск подстроки ................................................................ 109
Задача 14.3 Префиксная функция ......................................................... 109
Задача 14.4 Бор ....................................................................................... 110
Задача 14.5 Суффиксный автомат ......................................................... 111
Заключение ............................................................................. 112
Библиографический список………………………………..113
7
Стр.8
Предисловие
Настоящее учебное издание представляет собой задачник для дисциплины
«Алгоритмы и структуры данных» в рамках реализации образовательной
программы высшего образования по направлению подготовки
02.03.03 Математическое обеспечение и администрирование информационных
систем очной формы обучения и подготовлено в соответствии с требованиями
Федерального государственного образовательного стандарта высшего
образования (ФГОС).
Дисциплина «Алгоритмы и структуры данных» относится к обязательным
дисциплинам базовой части Блока 1 в структуре образовательной
программы.
Изучение дисциплины направлено на формирование общепрофессиональных
(ОПК) и профессиональных (ПК) компетенций:
ОПК-3.2: Использует современные информационные технологии
при создании программных продуктов и программных комплексов.
ПК-3.1: Использует типовые решения и шаблоны проектирования
интеллектуальных систем.
ПК-3.2: Применяет методы и средства проектирования интеллектуальных
систем, структур данных, баз данных, программных интерфейсов.
В
результате освоения дисциплины обучающийся должен
знать:
методы построения и использования сложных структур данных,
нетрадиционные представления данных;
различные аспекты обработки этих структур данных;
иметь понятие о сложности алгоритмов и методах анализа сложности
и эффективности;
способы представления стеков, очередей, деревьев в памяти
ЭВМ;
методы сортировки (внутренней и внешней);
8
Стр.9
представления графов и алгоритмы на графах;
иметь представление о NP-сложных задачах;
основные задачи поиска и методы их решения;
различные методы разработки алгоритмов.
уметь:
при решении конкретной задачи грамотно формулировать задачу
программирования;
реализовать ее в данной языковой среде, выполнить необходимое
тестирование или верификацию построенной программы;
применять методы построения новых типов при проектировании
информационных моделей;
выбирать оптимальную для данной информационной модели
структуру данных;
для написания программы выбирать в случае необходимости одно
из известных решений;
анализировать трудоемкость метода сортировки данных;
выбирать оптимальный подход для решения задачи.
владеть навыками:
практического программирования конкретных задач в определенной
языковой среде;
использования сложных нетрадиционных структур данных для
решения задач программирования;
тестирования и верификации реализованной программы;
использования классических алгоритмов и методов программирования;
использования систематического и научного подхода к построению
программ со сложными данными.
Основной задачей настоящего издания является систематизация банка
заданий для более глубокого понимания теоретического лекционного материала
дисциплины и получения практических навыков программирования
на лабораторных занятиях.
9
Стр.10
Задачник состоит из двух частей, каждая часть содержит семь глав, в
которых представлены задачи по соответствующим темам дисциплины.
Первая часть задачника содержит задачи по темам: теория чисел,
линейные контейнеры, нелинейные контейнеры, сортировки, поиск, рекурсия,
перебор, линейные алгоритмы. Во второй части представлены задачи по
темам: геометрия, жадные алгоритмы, динамическое программирование,
теория графов, структуры данных, строковые алгоритмы и структуры.
10
Стр.11