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

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 (As-
sociation 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. Арифметика многоразрядных целых чисел

A[1]:=A[1]+Ord(ch)-Ord(’0’);
{*Добавляем младшую цифру к числу из А[1].*}
If A[A[0]+1]>0 Then Inc(A[0]);
{*Изменяем длину, число задействованных
элементов массива А.*}
Read(ch);
End;
End;

Вторая задача. Вывод многоразрядного числа в файл или
на экран.
Казалось бы, нет проблем — выводи число за числом. Одна-
ко в силу выбранного нами представления числа необходимо
всегда помнить, что в каждом элементе массива хранится не
последовательность цифр числа, а значение числа, записанного
этими цифрами. Пусть в элементах массива хранятся четырех-
значные числа. И есть число, например, 128400583274. При
выводе нам необходимо вывести не 58, а 0058, иначе будет по-
теря цифр. Итак, нули также необходимо выводить. Процедура
вывода имеет вид:

Procedure WriteLong(Const A:TLong);
Var ls,s:String;
i:Integer;
Begin
Str(Osn Div 10,ls);
Write(A[A[0]]);{*Выводим старшие цифры числа.*}
For i:=A[0]-1 DownTo 1 Do
Begin
Str(A[i],s);
While Length(s)<Length(ls) Do s:=’0’+s;
{*Дополняем незначащими нулями.*}
Write(s);
End;
WriteLn;
End;

Третья задача. Сложение двух положительных чисел.
Предварительная работа по описанию способа хранения,
вводу и выводу многоразрядных чисел выполнена. У нас есть
все необходимые «кирпичики», например, для написания про-
граммы сложения двух положительных чисел. Исходные числа
и результат храним в файлах. Назовем процедуру сложения
SumLongTwo. Тогда программа ввода двух чисел и вывода ре-
зультата их сложения будет иметь следующий вид:

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

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.

Трудно ли объяснить процедуру сложения? Используя про-
стой пример — нет.
Пусть А=870613029451, В=3475912100517461.
Результат — С=3476782713546912. Алгоритм имитирует
привычное сложение столбиком, начиная с младших разрядов.
И именно для простоты реализации арифметических операций
над многоразрядными числами используется машинное пред-
ставление «задом наперед». Ниже приведен текст процедуры
сложения двух чисел.

Procedure SumLongTwo(Const A,B:TLong;Var C:TLong);
Var i,k:Integer;
Begin
FillChar(C,SizeOf(C),0);
If A[0]>B[0] Then k:=A[0] Else k:=B[0];
For i:=1 To k Do
Begin
C[i+1]:=(C[i]+A[i]+B[i])Div Osn;
C[i]:=(C[i]+A[i]+B[i]) Mod Osn;
{*Есть ли в этих операторах ошибка?*}
End;
If C[k+1]=0 Then C[0]:=k Else C[0]:=k+1;
End;

Таблица 1.3

i
A[i]
B[i]
C[1]
C[2]
C[3]
C[4]

1
9451
7461
6912
1
0
0

2
1302
51
6912
1354
0
0

3
8706
9121
6912
1354
7827
1

4
0
3475
6912
1354
7827
3476

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

Четвертая задача. Реализация операций сравнения чисел:
А=В, А<B, A>B, AB, AB.
Функция А=В имеет вид.

Function Eq(Const A,B:TLong):Boolean;
Var i:Integer;
Begin
Eq:=False;
If A[0]=B[0] Then
Begin
i:=1;
While (i<=A[0]) And (A[i]=B[i]) Do Inc(i);
Eq:=(i=A[0]+1);
End;
End;

Реализация функции A>B также прозрачна.

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=0
Then More:=False
Else
If A[i]>B[i]
Then More:=True
Else More:=False;
End;
End;

Остальные функции реализуются через функции Eq и More.

Function Less(A,B:TLong):Boolean;{A<B}
Begin
Less:=Not(More(A,B) Or Eq(A,B));
End;

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