Освещены такие вопросы, как комбинаторные алгоритмы, перебор, алгоритмы на графах, алгоритмы вычислительной геометрии. <...> Приводятся избранные олимпиадные задачи по программированию с указаниями к решению. <...> Арифметика многоразрядных целых чисел Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. <...> Арифметика многоразрядных целых чисел 9 Const MaxDig=1000;{*Максимальное количество цифр – четырехзначных. <...> MaxDig] Of Integer;{*Вычислите максимальное количество десятичных цифр в нашем числе. <...> В конечном итоге процедура должна иметь следующий вид: Procedure ReadLong(Var A:TLong); Var ch:Char;i:Integer; Begin FillChar(A,SizeOf(A),0); Repeat Read(ch); Until ch In [’0’. <...> ’9’] Do Begin For i:=A[0] DownTo 1 Do Begin{*“Протаскивание” старшей цифры в числе из А[i] в младшую цифру числа из А[i+1]. <...> Арифметика многоразрядных целых чисел A[1]:=A[1]+Ord(ch)-Ord(’0’); {*Добавляем младшую цифру к числу из А[1]. <...> Процедура вывода имеет вид: Procedure WriteLong(Const A:TLong); Var ls,s:String; i:Integer; Begin Str(Osn Div 10,ls); Write(A[A[0]]);{*Выводим старшие цифры числа. <...> Тогда программа ввода двух чисел и вывода результата их сложения будет иметь следующий вид: 11 12 Var A,B,C:TLong; Begin Assign(Input,’Input.txt’); Reset(Input); ReadLong(A);ReadLong(B); Close(Input); SumLongTwo(A,B,C); Assign(Output,’Output.txt’); Rewrite(Output); WriteLong(C); Close(Output); End. <...> Function More(A,B:TLong):Boolean; Var i:Integer; Begin If A[0]<B[0] Then More:=False Else If A[0]>B[0] Then More:=True Else Begin i:=A[0]; While (i>0) And (A[i]=B[i]) Do Dec(i); If i <...>
Программирование_в_алгоритмах.pdf
С. М. Окулов
ПРОГРАММИРОВАНИЕ
В АЛГОРИТМАХ
7-е издание, электронное
Москва
Лаборатория знаний
2021
Стр.2
УДК 519.85(023)
ББК 22.18
О-52
С е р и я о с н о в а н а в 2008 г.
Окулов С. М.
О-52
Программирование в алгоритмах / С. М. Окулов.—
7-е изд., электрон.—М. : Лаборатория знаний, 2021.—
386 с.—(Развитие интеллекта школьников).—Систем.
требования: Adobe Reader XI ; экран 10".—Загл.
с титул. экрана.—Текст : электронный.
ISBN 978-5-93208-521-9
Искусство программирования представлено в виде учебного
курса, раскрывающего секреты наиболее популярных
алгоритмов. Освещены такие вопросы, как комбинаторные
алгоритмы, перебор, алгоритмы на графах, алгоритмы вычислительной
геометрии. Приводятся избранные олимпиадные
задачи по программированию с указаниями к решению.
Практические рекомендации по тестированию программ
являются необходимым дополнением курса.
Для старших школьников, студентов и специалистов,
серьезно изучающих программирование, а также для преподавателей
учебных заведений.
УДК 519.85(023)
ББК 22.18
Деривативное издание на основе печатного аналога: Программирование
в алгоритмах / С. М. Окулов.—4-е изд.—
М. : БИНОМ. Лаборатория знаний, 2013.—383 с. : ил.—
(Развитие интеллекта школьников).
ISBN 978-5-9963-0848-4.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации
ISBN 978-5-93208-521-9
© Лаборатория знаний, 2015
Стр.3
Содержание
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1. Арифметика многоразрядных целых чисел . . . . . . 8
1.1. Основные арифметические операции . . . . . . . . . . . . . . 8
1.2. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2. Комбинаторные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1. Классические задачи комбинаторики . . . . . . . . . . . . . . 27
2.2. Генерация комбинаторных объектов . . . . . . . . . . . . . . 34
2.2.1. Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.2. Размещения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2.3. Сочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.2.4. Разбиение числа на слагаемые . . . . . . . . . . . . . . 58
2.2.5. Последовательности из нулей и единиц
длины N без двух единиц подряд . . . . . . . . . . . 64
2.2.6. Подмножества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.2.7. Скобочные последовательности . . . . . . . . . . . . . 71
2.3. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3. Перебор и методы его сокращения . . . . . . . . . . . . . . . . 87
3.1. Перебор с возвратом (общая схема) . . . . . . . . . . . . . . . . 87
3.2. Примеры задач для разбора общей схемы перебора 89
3.3. Динамическое программирование . . . . . . . . . . . . . . . . . 106
3.4. Примеры задач для разбора идеи метода динамического
программирования . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.5. Метод ветвей и границ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.6. Метод «решета» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.7. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4. Алгоритмы на графах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
4.1. Представление графа в памяти компьютера . . . . . . . . 158
4.2. Поиск в графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4.2.1. Поиск в глубину . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4.2.2. Поиск в ширину . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Стр.4
4
Содержание
4.3. Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.3.1. Основные понятия. Стягивающие деревья . . 162
4.3.2. Порождение всех каркасов графа . . . . . . . . . . . 163
4.3.3. Каркасминимального веса. МетодДж.Краскала
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.3.4. Каркас минимального веса. Метод Р. Прима168
4.4. Связность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
4.4.1. Достижимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
4.4.2. Определение связности . . . . . . . . . . . . . . . . . . . . . 172
4.4.3. Двусвязность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
4.5. Циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
4.5.1. Эйлеровы циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
4.5.2. Гамильтоновы циклы . . . . . . . . . . . . . . . . . . . . . . 177
4.5.3. Фундаментальное множество циклов . . . . . . . 179
4.6. Кратчайшие пути . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
4.6.1. Постановка задачи. Вывод пути . . . . . . . . . . . . 180
4.6.2. Алгоритм Дейкстры . . . . . . . . . . . . . . . . . . . . . . . 182
4.6.3. Пути в бесконтурном графе . . . . . . . . . . . . . . . . . 183
4.6.4. Кратчайшие пути между всеми парами
вершин. Алгоритм Флойда . . . . . . . . . . . . . . . . . 186
4.7. Независимые и доминирующие множества . . . . . . . . 188
4.7.1. Независимые множества . . . . . . . . . . . . . . . . . . . 188
4.7.2. Метод генерации всех максимальных независимых
множеств графа . . . . . . . . . . . . . . . . . . . 189
4.7.3. Доминирующие множества . . . . . . . . . . . . . . . . 194
4.7.4. Задача о наименьшем покрытии . . . . . . . . . . . . 195
4.7.5. Метод решения задачи о наименьшем разбиении
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
4.8. Раскраски . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
4.8.1. Правильные раскраски . . . . . . . . . . . . . . . . . . . . . 202
4.8.2. Поиск минимальной раскраски вершин
графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
4.8.3. Использование задачи о наименьшем покрытии
при раскраске вершин графа . . . . . . . 207
4.9. Потоки в сетях, паросочетания . . . . . . . . . . . . . . . . . . . . 208
4.9.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . 208
4.9.2. Метод построения максимального потока
в сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
4.9.3. Наибольшее паросочетание в двудольном
графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
Стр.5
Содержание
5
4.10. Методы приближенного решения задачи коммивояжера
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
4.10.1. Метод локальной оптимизации . . . . . . . . . . . . 219
4.10.2. Алгоритм Эйлера . . . . . . . . . . . . . . . . . . . . . . . . . 222
4.10.3. Алгоритм Кристофидеса . . . . . . . . . . . . . . . . . . 225
4.11. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
5. Алгоритмы вычислительной геометрии . . . . . . . . . . 249
5.1. Базовые процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
5.2. Прямая линия и отрезок прямой . . . . . . . . . . . . . . . . . . 255
5.3. Треугольник . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
5.4. Многоугольник . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
5.5. Выпуклая оболочка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
5.6. Задачи о прямоугольниках . . . . . . . . . . . . . . . . . . . . . . . . 284
5.7. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
6. Избранные олимпиадные задачи по программированию
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
7. Заметки о тестировании программ . . . . . . . . . . . . . . . . 358
7.1. О программировании . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
7.2. Практические рекомендации . . . . . . . . . . . . . . . . . . . . . . 360
7.3. Тестирование программы решения задачи (на примере)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
Библиографический указатель . . . . . . . . . . . . . . . . . . . . . . . . 382
Стр.6