Программирование в алгоритмах

7-е издание, электронное

Москва
Лаборатория знаний
2021

С. М. Окулов

ПРОГРАММИРОВАНИЕ
В АЛГОРИТМАХ

УДК 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

Содержание

Предисловие ............................................
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.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

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

Единственной женщине посвящаю

Курс «Программирование в алгоритмах» является естественным продолжением курса «Основы программирования». Его содержание достаточно традиционно: структурное программирование, технологии «сверху — вниз» и «снизу — вверх». Освоению
обязательной
программы
курса
автор
придает
огромное
значение. Она обязана стать естественной схемой решения задач, если хотите — культурой мышления или познания.
Только после этого, по нашему глубокому убеждению, разумно переходить на объектно-ориентированное программирование,
работу в визуальных средах, на машинно-ориентированное программирование и т. д. Практика подтвердила жизненность данной схемы изучения информатики. Ученики физико-математического лицея г. Кирова многие годы представляют регион на
различных соревнованиях по информатике, включая Международные олимпиады. Возвращение их без дипломов или медалей — редкое исключение. Переходя в разряд студентов, выпускники лицея без особых хлопот изучают дисциплины по
информатике в любом высшем учебном заведении России, а также успешно выступают в командных чемпионатах мира среди
студентов по программированию.
Для кого предназначен учебник? Во-первых, для учителей и
учащихся
школ
с
углубленным
изучением
информатики.
Во-вторых, для студентов высших учебных заведений, изучающих программирование и стремящихся достичь профессионального уровня. Особенно он будет полезен тем, кто готовится принять участие в олимпиадах по программированию, включая
широко известный чемпионат мира по программированию,
проводимый под эгидой международной организации ACM (Association for Computing Machinery).
О благодарностях, ибо не так часто вслух предоставляется
возможность сказать коллегам о том, что ты их безмерно уважаешь. Во-первых, это касается моих учеников и учителей одновременно. Без сотрудничества с ними вряд ли автор смог написать
что-то
подобное.
Первая
попытка
написания
книг
такого рода была предпринята в 1993 году с Антоном Валерьевичем Лапуновым. То было совместное вхождение в данную
проблематику. Для Антона более легкое, для автора достаточно

Предисловие

трудное. Затем последовало сотрудничество с Виталием Игоревичем Беровым. Наверное, благодаря ему автор нашел ту схему
изложения алгоритмов на графах, которую он затем применял
в работе даже с восьмиклассниками. Сотрудничество с Виктором Александровичем Матюхиным в пору его ученичества
было
не таким явным, но после того, как он стал студентом
МГУ и в настоящее время, оно, на мой взгляд, очень плодотворно. Влияние Виктора на развитие олимпиадной информатики в г. Кирове просто огромно. С братьями Пестовыми, Андреем
и
Олегом,
написаны
книги.
Более
трудолюбивых
и
отзывчивых учеников автору не приходилось встречать. Сотрудничество с такими ребятами не было бы возможным без
высочайшего профессионализма
Владислава Владимировича
Юферева и Галины Константиновны Корякиной, директора и
завуча физико-математического лицея г. Кирова. Особые слова
признательности хотелось бы выразить Владимиру Михайловичу Кирюхину, руководителю сборной команды школьников
России по информатике. В 1994 году он привлек автора к работе в жюри российской олимпиады школьников. За эти годы автор воочию увидел весь тот тяжелейший труд, который стоит
за победами российских школьников на Международных олимпиадах. Иосиф Владимирович Романовский сделал ряд ценных
замечаний по газетной версии главы 5, за что автор благодарит
его и желает дальнейших творческих успехов в деле обучения
петербургских студентов. Многие годы главный редактор газеты «Информатика» Сергей Львович Островский поддерживал
автора в его работе, и признательность за это остается неизменной.
Об ошибках. Учебники такого плана не могут не содержать
ошибок. Для многих алгоритмов можно, естественно, найти
другие схемы реализации. Автор с признательностью примет
все замечания. Присылайте их, пожалуйста, по адресу
okulov@vspu.kirov.ru

7

Известно,
что
арифметические
действия,
выполняемые
компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены
размером (величиной) чисел, с которыми можем работать. А
если нам необходимо выполнить арифметические действия над
очень большими числами, например
30!= 265252859812191058636308480000000?
В таких случаях мы сами должны позаботиться о представлении чисел и о точном выполнении арифметических операций
над ними.

1.1. Основные арифметические операции

Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются иногда «длинными». В этом случае программисту
приходится самостоятельно
создавать
подпрограммы
выполнения арифметических операций. Рассмотрим один из
возможных способов их реализации.
Представим в виде:
30!=2(104)8+6525(104)7+2859(104)6+8121(104)5+9105(104)4+
+8636(104)3+3084(104)2+8000(104)1+0000(104)0.
Это представление наталкивает на мысль о массиве.

Номер
элемента
в массиве А

0
1
2
3
4
5
6
7
8
9

Значение
9
0
8000
3084
8636
9105
8121
2859
6525
2

Возникают вопросы. Что за 9 в А[0], почему число хранится
«задом наперед»? Ответы очевидны, но подождем с ними. Будет ясно из текста.

Примечание
Мы работаем с положительными числами!

Первая задача. Ввести число из файла.
Но прежде описание данных.

1. Арифметика многоразрядных
целых чисел

Const MaxDig=1000;{*Максимальное количество цифр –
четырехзначных.*}
Osn=10000;{*Основание нашей системы счисления, в
элементах массива храним четырехзначные числа.*}
Type TLong=Array[0..MaxDig] Of Integer;{*Вычислите
максимальное количество десятичных цифр в нашем числе.*}

Прежде чем рассмотреть процедуру ввода, приведем пример. Пусть в файле записано число 23851674 и основанием
(Osn) является 1000 (храним по три цифры в элементе массива
А). Изменение значений элементов массива А в процессе ввода
отражено в таблице 1.1. В основу положен посимвольный ввод,
для этого используется переменная ch.

Таблица 1.1

А[0]
А[1]
А[2]
А[3]
ch
Примечание

3
674
851
23
Конечное состояние

0
0
0
0
2
Начальное
состояние

1
2
0
0
3
1й шаг

1
23
0
0
8
2й шаг

1
238
0
0
5
3й шаг

2
385
2
0
1
4й шаг

2
851
23
0
6
5й шаг

2
516
238
0
7
6й шаг

3
167
385
2
4
7й шаг

3
674
851
23

Итак, в А[0] храним количество задействованных (ненулевых) элементов массива А — это уже очевидно. И при обработке каждой очередной цифры входного числа старшая цифра
элемента массива с номером i становится младшей цифрой числа в элементе i+1, а вводимая цифра будет младшей цифрой
числа из А[1].

Примечание (методическое)
Можно ограничиться этим объяснением и разработку процедуры
вынести на самостоятельное задание. Можно продолжить объяснение. Например, выписать фрагмент текста процедуры переноса
старшей цифры из A[i] в младшую цифру A[i+1], т. е. сдвиг уже
введенной части на одну позицию вправо:

1. Арифметика многоразрядных целых чисел
9

For i:=A[0] DownTo 1 Do
Begin
A[i+1]:=A[i+1]+(LongInt(A[i])*10) Div Osn;
A[i]:=(LongInt(A[i])*10) Mod Osn;
End;

Пусть мы вводим число 23851674 и первые 6 цифр уже разместили «задом наперед» в массиве А. В символьную переменную ch считали очередную цифру многоразрядного числа — это
«7». По нашему алгоритму она должна быть размещена как
младшая цифра в А[1]. Выписанный фрагмент программы освобождает место для этой цифры. В таблице 1.2 отражены результаты работы этого фрагмента.

Таблица 1.2

i
A[1]
A[2]
A[3]
ch

2
516
238
0
7

2
516
380
2

1
160
385
2

После этого остается только добавить текущую цифру к A[1]
и изменить значение A[0].
В конечном итоге процедура должна иметь следующий вид:

Procedure ReadLong(Var A:TLong);
Var ch:Char;i:Integer;
Begin
FillChar(A,SizeOf(A),0);
Repeat
Read(ch);
Until ch In [’0’..’9’]
{*Пропуск не цифр в начале файла.*}
While ch In [’0’..’9’] Do
Begin
For i:=A[0] DownTo 1 Do
Begin{*“Протаскивание”
старшей цифры в числе из А[i] в младшую
цифру числа из А[i+1].*}
A[i+1]:=A[i+1]+(LongInt(A[i])*10) Div Osn;
A[i]:=(LongInt(A[i])*10) Mod Osn;
End;

10
1. Арифметика многоразрядных целых чисел