анти. Guide to Competitive

• Название: Guide to Competitive
• Дата: 20.12.2022
• Размер: 2.39 Mb.
• Имя файла: анти.pdf
• Тип: Guide; #854732
• страница: 3 из 26

Глава
1
Введение
В этой главе рассказывается, что такое олимпиадное программирование, представлен план книги и обсуждаются дополнительные образователь- ные ресурсы.
В разделе 1.1 описаны элементы олимпиадного программирования, пе- речислены некоторые популярные соревнования по программированию и даны рекомендации о том, как готовиться к соревнованиям.
В разделе 1.2 обсуждаются цели этой книги и рассматриваемые в ней темы, а также кратко излагается содержание каждой главы.
В разделе 1.3 мы познакомимся со сборником задач CSES. Решение за- дач параллельно чтению этой книги – отличный способ научиться олим- пиадному программированию.
В разделе 1.4 обсуждаются другие книги по олимпиадному программи- рованию и проектированию алгоритмов.
1.1. Что такое олимпиадное программирование?
Олимпиадное программирование состоит из двух частей – проектирова- ния алгоритмов и реализации алгоритмов.
Проектирование алгоритмов. По сути своей, олимпиадное програм- мирование – это придумывание эффективных алгоритмов решения кор- ректно поставленных вычислительных задач. Для проектирования ал- горитмов необходимы навыки в решении задач и знание математики.
Зачастую решение появляется в результате сочетания хорошо известных методов и новых идей.
Важную роль в олимпиадном программировании играет математика.
На самом деле четких границ между проектированием алгоритмов и ма- тематикой не существует. Эта книга не требует глубокой математической подготовки. В приложении, которое можно использовать как справочник, описаны некоторые встречающиеся в книге математические понятия и методы, например множества, математическая логика и функции.
Реализация алгоритмов. В олимпиадном программировании реше- ние задачи оценивается путем проверки реализованного алгоритма на ряде тестов. Поэтому придумать алгоритм недостаточно, его еще нуж-

1.1. Что такое олимпиадное программирование?

19
но корректно реализовать, для чего требуется умение программировать.
Олимпиадное программирование сильно отличается от традиционной программной инженерии: программы короткие (несколько сотен строк – уже редкость), писать их нужно быстро, а сопровождение после соревно- вания не требуется.
В настоящее время на соревнованиях по программированию популяр- нее всего языки C++, Python и Java. Например, среди 3000 лучших участ- ников Google Code Jam 2017 79 % писали на C++, 16 % – на Python и 8 % – на
Java. Многие считают C++ самым подходящим выбором для олимпиадного программиста. К его достоинствам можно отнести очень высокую эффек- тивность и тот факт, что в стандартной библиотеке много разнообразных структур данных и алгоритмов.
Все примеры в книге написаны на C++, в них часто используются струк- туры данных и алгоритмы из стандартной библиотеки. Код отвечает стан- дарту C++11, который разрешен в большинстве современных соревнова- ний. Если вы еще не знаете C++, самое время начать его изучение.
1.1.1. Соревнования по программированию
Международная олимпиада по информатике (IOI) – ежегодное соревно- вание для старшеклассников. От каждой страны допускается команда из четырех человек. Обычно набирается около 300 участников из 80 стран.
IOI проводится в течение двух дней. В каждый день участникам пред- лагается решить три трудные задачи, на решение отводится пять часов.
Задачи разбиты на подзадачи, за каждую из которых начисляются баллы.
Хотя участники являются членами команды, соревнуются они самостоя- тельно.
Участники IOI отбираются на национальных олимпиадах. IOI предшест- вует множество региональных соревнований, например: Балтийская олимпиада по информатике (BOI), Центрально-Европейская олимпиада по информатике (CEOI) и Азиатско-Тихоокеанская олимпиада по инфор- матике (
APIO
).
ICPC
(Международная студенческая олимпиада по программированию) проводится ежегодно для студентов университетов. В каждой команде три участника; в отличие от IOI, студенты работают вместе, и каждой команде выделяется только один компьютер.
ICPC включает несколько этапов, лучшие команды приглашаются на финальный этап мирового первенства. Хотя в соревновании принимают участие тысячи студентов, количество участников финала ограничено
1
, поэтому даже сам выход в финал считается большим достижением.
На соревновании ICPC у команды есть пять часов на решение примерно десяти алгоритмических задач. Решение засчитывается, только если прог-
1
Точное количество участников финала от года к году меняется. В 2017 году их было 133.

20 
Глава 1. Введение рамма прошла все тесты и показала свою эффективность. В ходе соревно- вания участники могут видеть результаты соперников, но в начале пятого часа табло замораживается, и результаты последних прогонов не видны.
Онлайновые соревнования. Существует также много онлайновых со- ревнований, куда допускаются все желающие. В настоящий момент наибо- лее активен сайт Codeforces, который организует конкурсы почти каждую неделю. Отметим также сайты AtCoder, CodeChef, CS Academy, HackerRank и Topcoder.
Некоторые компании организуют онлайновые соревнования с очными финалами, например: Facebook Hacker Cup, Google Code Jam и Yandex.Algo- rithm. Разумеется, компании используют такие соревнования для подбора кадров: достойно выступить в соревновании – хороший способ доказать свои таланты в программировании.
1.1.2. Рекомендации желающим поучаствовать
Чтобы научиться олимпиадному программированию, нужно напряжен- но работать. Но способов приобрести практический опыт много, одни луч- ше, другие хуже.
Решая задачи, нужно иметь в виду, что не так важно количество решен- ных задач, как их качество. Возникает соблазн выбирать красивые и лег- кие задачи, пропуская те, что кажутся трудными и требующими кропотли- вого труда. Но чтобы отточить свои навыки, нужно отдавать предпочтение именно задачам второго типа.
Важно и то, что большинство олимпиадных задач решается с помощью простого и короткого алгоритма, самое трудное – придумать этот алго- ритм. Смысл олимпиадного программирования – не в заучивании слож- ных и малопонятных алгоритмов, а в том, чтобы научиться решать труд- ные задачи, обходясь простыми средствами.
Наконец, есть люди, презирающие реализацию алгоритмов, им достав- ляет удовольствие проектировать алгоритмы, а реализовывать их скучно.
Однако умение быстро и правильно реализовать алгоритм – важное пре- имущество, и этот навык поддается тренировке. Будет очень плохо, если вы потратите большую часть отведенного времени на написание кода и поиск ошибок, а не на обдумывание того, как решить задачу.
1.2. Об этой книге
Программа IOI [17] определяет, какие темы могут предлагаться на Меж- дународных олимпиадах по информатике. Именно эта программа стала отправной точкой при отборе материала. Но обсуждаются также более сложные темы, которые исключены из IOI (по состоянию на 2017 год), но могут встречаться в других соревнованиях. К ним относятся, например, максимальные потоки, игра ним и суффиксные массивы.

1.2. Об этой книге

21
Многие темы олимпиадного программирования обсуждаются в стан- дартных учебниках по алгоритмам, но есть и отличия. Например, во многих книгах реализация алгоритмов сортировки и основных структур данных рассматривается с нуля, но такие знания на олимпиаде несущественны, потому что можно пользоваться средствами из стандартной библиотеки.
С другой стороны, некоторые темы хорошо известны в олимпиадном со- обществе, но редко встречаются в учебниках. Примером может служить дерево отрезков – структура данных, которая используется для решения многих задач без привлечения более хитроумных алгоритмов.
Одна из целей этой книги – документировать приемы олимпиадного программирования, которые обычно обсуждаются только на форумах и в блогах. Там, где возможно, даются ссылки на научную литературу по таким методам. Но сделать это можно не всегда, потому что многие методы ныне стали частью фольклора, и никто не знает имени перво- открывателя.
Книга организована следующим образом.
• В главе 2 рассматриваются средства языка программирования C++, а затем обсуждаются рекурсивные алгоритмы и поразрядные опе- рации.
• Глава 3 посвящена эффективности: как создавать алгоритмы, спо- собные быстро обрабатывать большие наборы данных.
• В главе 4 обсуждаются алгоритмы сортировки и двоичного поиска с упором на их применение в проектировании алгоритмов.
• В главе 5 дается обзор избранных структур данных в стандартной библиотеке C++: векторов, множеств и отображений.
• Глава 6 представляет собой введение в один из методов проекти- рования алгоритмов – динамическое программирование. Здесь же приводятся примеры задач, которые можно решить этим методом.
• В главе 7 рассматриваются элементарные алгоритмы на графах, в т. ч. поиск кратчайших путей и минимальные остовные деревья.
• В главе 8 речь пойдет о более сложных вопросах проектирования ал- горитмов, в частности об алгоритмах с параллельным просмотром разрядов и амортизационном анализе.
• Тема главы 9 – эффективная обработка запросов по диапазонам массива, таких как вычисление сумм элементов и нахождение ми- нимальных элементов.
• В главе 10 представлены специальные алгоритмы для деревьев, в т. ч. методы обработки запросов к дереву.
• В главе 11 обсуждаются разделы математики, часто встречающиеся в олимпиадном программировании.

22 
Глава 1. Введение
• В главе 12 описываются дополнительные алгоритмы на графах, на- пример поиск компонент сильной связности и вычисление макси- мального потока.
• Глава 13 посвящена геометрическим алгоритмам, в ней описаны методы, позволяющие удобно решать геометрические задачи.
• В главе 14 рассматриваются методы работы со строками, в т. ч. хеши- рование, Z-алгоритм и суффиксные массивы.
• В главе 15 обсуждаются избранные дополнительные темы, напри- мер алгоритмы, основанные на идее квадратного корня, и оптими- зация динамического программирования.
1.3. Сборник задач CSES
В сборнике задач CSES представлены задачи для практики в олимпиадном программировании. Расположены они в порядке возрастания трудности, а в этой книге обсуждаются все методы, необходимые для их решения.
Сборник задач доступен по адресу:
https://cses.fi/problemset/
Посмотрим, как решить первую задачу из него. Она называется «Стран- ный алгоритм» и формулируется следующим образом.
Рассмотрим алгоритм, принимающий на входе целое положительное число n. Если n четно, то алгоритм делит его на два, а если нечетно, то ум- ножает на три и прибавляет 1. Например, для n = 3 получается следующая последовательность:
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1.
Ваша задача заключается в том, чтобы промоделировать выполнение этого алгоритма для любого заданного n.
Вход
Единственная строка, содержащая целое число n.
Выход
Печатает строку, содержащую все значения, вычисляемые алгоритмом.
Ограничения
• 1 ≤ n ≤ 10 6
Пример
Вход:
3
Выход:
3 10 5 16 8 4 2 1

1.3. Сборник задач CSES

23
Эта проблема имеет отношение к знаменитой гипотезе Коллатца, кото- рая утверждает, что описанный выше алгоритм завершается для любого
n
. До сих пор она остается недоказанной. Но в этой задаче мы знаем, что начальное значение n не превышает миллиона, что существенно упроща- ет проблему.
Это простая задача моделирования, не требующая глубоких размышле- ний. Вот как ее можно было бы решить на C++:
#include
using namespace std;
int main() {
int n;
cin >> n;
while (true) {
cout << n << " ";
if (n == 1) break;
if (n%2 == 0) n /= 2;
else n = n*3+1;
}
cout << "\n";
}
Сначала программа читает входное число n, затем моделирует алгоритм и печатает значение n после каждого шага. Легко проверить, что этот код правильно обрабатывает случай n = 3, приведенный в формулировке за- дачи.
Теперь время отправить этот код в CSES. Для каждого теста CSES сообща- ет, пройден он или нет, и показывает вход, ожидаемый и реальный выход.
По результатам тестирования CSES формирует следующий отчет:
test verdict time (s)
#1
ACCEPTED
0.06 / 1.00
#2
ACCEPTED
0.06 / 1.00
#3
ACCEPTED
0.07 / 1.00
#4
ACCEPTED
0.06 / 1.00
#5
ACCEPTED
0.06 / 1.00
#6
TIME LIMIT EXCEEDED
_ / 1.00
#7
TIME LIMIT EXCEEDED
_ / 1.00
#8
WRONG ANSWER
0.07 / 1.00
#9
TIME LIMIT EXCEEDED
_ / 1.00
#10
ACCEPTED
0.06 / 1.00

24 
Глава 1. Введение
Это означает, что некоторые тесты наш код прошел (ACCEPTED), на не- которых оказался слишком медленным (TIME LIMIT EXCEEDED), а в одном случае дал неверный результат (WRONG ANSWER). Вот уж действительно неожиданно!
Первым не прошел тест для n = 138 367. Локально прогнав программу в этом случае, мы убедимся, что она действительно работает долго. На са- мом деле она вообще не завершается.
Причина ошибки в том, что в процессе моделирования n может оказать- ся слишком большим, в том числе больше максимального значения, пред- ставимого типом int
. Чтобы решить проблему, достаточно заменить тип int на long long
. Тогда получится то, что нужно:
test verdict time (s)
#1
ACCEPTED
0.05 / 1.00
#2
ACCEPTED
0.06 / 1.00
#3
ACCEPTED
0.07 / 1.00
#4
ACCEPTED
0.06 / 1.00
#5
ACCEPTED
0.06 / 1.00
#6
ACCEPTED
0.05 / 1.00
#7
ACCEPTED
0.06 / 1.00
#8
ACCEPTED
0.05 / 1.00
#9
ACCEPTED
0.07 / 1.00
#10
ACCEPTED
0.06 / 1.00
Как видно из этого примера, даже в очень простые алгоритмы могут вкрасться тонкие ошибки. Олимпиадное программирование учит, как пи- сать алгоритмы, которые действительно работают.
1.4. Другие ресурсы
Помимо этой, уже есть и другие книги по олимпиадному программиро- ванию. Первой была книга Skiena, Revilla «Programming Challenges» [32], вышедшая в 2003 году. Позже вышла книга Halim, Halim «Competitive Pro- gramming 3» [16]. Обе ориентированы на читателя, не имеющего опыта олимпиадного программирования.
Книга «Looking for a Challenge?» [8] – сборник трудных задач, предлагав- шихся на польских олимпиадах, – рассчитана на более подготовленного читателя. Самое интересное в ней – подробный анализ решений.
Разумеется, для подготовки к олимпиадам подойдут и общие книги по алгоритмам. Самая всеобъемлющая из них – книга Cormen, Leiserson,

1.4. Другие ресурсы

25
Rivest, Stein «Introduction to Algorithms»
2
[7], которую также называют прос то CLRS. Это прекрасный источник для тех, кто хочет узнать обо всех деталях алгоритма и познакомиться со строгим доказательством.
В книге Kleinberg, Tardos «Algorithm Design» [22] основное внимание уделяется технике проектирования алгоритмов и во всех деталях обсуж- даются такие темы, как метод «разделяй и властвуй», жадные алгоритмы, динамическое программирование и вычисление максимального потока.
Книга Skiena «The Algorithm Design Manual» [31] – практическое руководст- во, содержащее обширный каталог вычислительных задач и способов их решения.
2
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ. М.: Вильямс, 2016.

Глава
2
Техника программирования
В этой главе представлены некоторые средства языка C++, полезные в олимпиадном программировании, а также приведены примеры исполь- зования рекурсии и поразрядных операций.
В разделе 2.1 рассматриваются избранные вопросы C++, включая ввод и вывод, работу с числами и способы сокращения кода.
Раздел 2.2 посвящен рекурсивным алгоритмам. Сначала мы рассмот- рим элегантный способ порождения всех подмножеств и перестано- вок множест ва с применением рекурсии. А затем с помощью перебора с возвра том подсчитаем, сколькими способами можно расположить n фер- зей на шахматной доске n×n, так чтобы они не били друг друга.
В разделе 2.3 обсуждаются основы поразрядных операций и их приме- нение для представления подмножеств множества.
2.1. Языковые средства
Типичная олимпиадная программа на C++ устроена по такому образцу:
#include
using namespace std;
int main() {
// здесь находится решение
}
Строка
#include в начале программы – специфика компилятора g++
, она служит для включения всей стандартной библиотеки. Таким образом, не нужно по отдельности включать такие библиотеки, как iostream
, vector и algorithm
; все они автоматически становятся доступны.
В строке using объявляется, что все классы и функции из стандартной библиотеки можно использовать без указания пространства имен. Не будь using
, нужно было бы писать, к примеру, std::cout
, а так достаточно просто cout
Для компиляции программы используется команда вида:

Использование функционального теста для определения дееспособного приложения

27
g++ -std=c++11 -O2 -Wall test.cpp -o test
Она порождает двоичный файл test из исходного файла test.cpp
. Флаги означают, что компилятор должен следовать стандарту C++11 (
-std=c++11
), оптимизировать код (
-O2
) и выводить предупреждения о возможных проб- лемах (
-Wall
).
2.1.1. Ввод и вывод
В большинстве олимпиадных задач для ввода и вывода используются стандартные потоки. В C++ стандартный поток ввода называется cin
, а стандартный поток вывода – cout
. Можно также использовать C-функции, например scanf и printf
Входными данными для программы обычно являются числа и строки, разделенные пробелами и знаками новой строки. Из потока cin они чита- ются следующим образом:
int a, b;
string x;
cin >> a >> b >> x;
Такой код работает в предположении, что элементы потока разделены хотя бы одним пробелом или знаком новой строки. Например, приведен- ный выше код может прочитать как входные данные:
123 456 monkey так и входные данные:
123 456
monkey
Поток cout используется для вывода:
int a = 123, b = 456;
string x = "monkey";
cout << a << " " << b << " " << x << "\n";
Ввод и вывод часто оказываются узкими местами программы. Чтобы повысить эффективность ввода-вывода, можно поместить в начало про- граммы такие строки:
ios::sync_with_stdio(0);
cin.tie(0);
Отметим, что знак новой строки "\n"
работает быстрее, чем endl
, пото- му что endl всегда сопровождается сбросом буфера.

28 
Глава 2. Техника программирования
C-функции scanf и printf
– альтернатива стандартным потокам C++.
Обычно они работают немного быстрее, но и использовать их сложнее.
Вот как можно прочитать из стандартного ввода два целых числа:
int a, b;
scanf("%d %d", &a, &b);
А вот как их можно напечатать:
int a = 123, b = 456;
printf("%d %d\n", a, b);
Иногда программа должна прочитать целую входную строку, быть может, содержащую пробелы. Это можно сделать с помощью функции getline
:
string s;
getline(cin, s);
Если объем данных заранее неизвестен, то полезен такой цикл:
while (cin >> x) {
// код
}
Этот цикл читает из стандартного ввода элементы один за другим, пока входные данные не закончатся.
В некоторых олимпиадных системах для ввода и вывода используются файлы. В таком случае есть простое решение: писать код так, будто рабо- таешь со стандартными потоками, но в начало программы добавить такие строки:
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
После этого программа будет читать данные из файла «input.txt», а записы вать в файл «output.txt».
2.1.2. Работа с числами
Целые числа. Из целых типов в олимпиадном программировании чаще всего используется int
– 32-разрядный тип
1
, принимающий значения из диапазона −2 31
…2 31
− 1 (приблизительно −2 · 10 9
…2 · 10 9
). Если типа int не- достаточно, то можно взять 64-разрядный тип long long
. Диапазон его значений −2 63
…2 63
− 1 (приблизительно −9 · 10 18
…9 · 10 18
).
Ниже определена переменная типа long long
:
1
На самом деле стандарт С++ не определяет точные размеры числовых типов, а границы диапазонов зависят от платформы и компилятора. В этом разделе указаны размеры, с которыми вы, вероятнее всего, встретитесь в современных системах.

2.1. Языковые средства

29
long long x = 123456789123456789LL;
Суффикс
LL
означает, что число имеет тип long long
Типичная ошибка при использовании типа long long возникает, когда где-то в программе встречается еще и тип int
. Например, в следующем коде есть тонкая ошибка:
int a = 123456789;
long long b = a*a;
cout << b << "\n"; // -1757895751
Хотя переменная b
имеет тип long long
, оба сомножителя в выражении a*a имеют тип int
, поэтому тип результата тоже int
. Из-за этого значе- ние b
оказывается неверным. Проблему можно решить, изменив тип a
на long long или изменив само выражение на
(long long)a*a
Обычно олимпиадные задачи формулируются так, что типа long long достаточно. Но все же полезно знать, что компилятор g++
поддерживает также 128-разрядный тип
__int128_t с диапазоном значений −2 127
…2 127
− 1
(приблизительно −10 38
…10 38
). Однако этот тип доступен не во всех олим- пиадных системах.
Арифметика по модулю. Иногда ответом является очень большое число, но достаточно вывести результат «по модулю m», т. е. остаток от деления на m (например, «7 по модулю 10 9
»). Идея в том, что даже когда истинный ответ очень велик, типов int и long long все равно достаточ- но.
Остаток x от деления на m обозначается x mod m. Например, 17 mod 5 = 2, поскольку 17 = 3 · 5 + 2. Важные свойства остатков выражаются следующи- ми формулами:
(a + b)mod m = (a mod m + b mod m)mod m;
(a − b)mod m = (a mod m − b mod m)mod m;
(a · b)mod m = (a mod m · b mod m)mod m.
Это значит, что можно брать остаток после каждой операции, поэтому числа никогда не станут слишком большими.
Например, следующий код вычисляет n! (n факториал) по модулю m:
long long x = 1;
for (int i = 1; i <= n; i++) {
x = (x*i)%m;
}
cout << x << "\n";
Обычно мы хотим, чтобы остаток находился в диапазоне 0…m − 1. Но в C++ и в других языках остаток от деления отрицательного числа равен

30 
Глава 2. Техника программирования нулю или отрицателен. Чтобы не возникали отрицательные остатки, мож- но поступить следующим образом: сначала вычислить остаток, а если он отрицателен, прибавить m:
x = x%m;
if (x < 0) x += m;
Но это стоит делать, только если в программе встречается операция вы- читания, так что остаток может стать отрицательным.
Числа с плавающей точкой. В большинстве олимпиадных задач целых чисел достаточно, но иногда возникает потребность в числах с плавающей точкой. В C++ наиболее полезен 64-разрядный тип double
, а в компиляторе g++
имеется расширение – 80-разрядный тип long double
. Чаще всего типа double достаточно, но long double дает более высокую точность.
Требуемая точность ответа обычно указывается в формулировке задачи.
Проще всего для вывода ответа использовать функцию printf и указать количество десятичных цифр в форматной строке. Например, следующий код печатает значение x с 9 цифрами после запятой:
printf("%.9f\n", x);
С использованием чисел с плавающей точкой связана одна сложность: некоторые числа невозможно точно представить в таком формате, поэто- му неизбежны ошибки округления. Например, в следующем коде получа- ется значение x, немного меньшее1, тогда как правильное значение равно в точности 1.
double x = 0.3*3+0.1;
printf("%.20f\n", x); // 0.99999999999999988898
Числа с плавающей точкой рискованно сравнивать с помощью операто- ра ==, потому что иногда равные значения оказываются различны из-за ошибок округления. Более правильно считать, что два числа равны, если разность между ними меньше ε, где ε мало. Например, в следующем коде
ε
= 10
−9
:
if (abs(a-b) < 1e-9) {
// a и b равны
}
Отметим, что хотя числа с плавающей точкой, вообще говоря, не точны, не слишком большие целые числа представляются точно. Так, тип double позволяет точно представить все целые числа, по абсолютной величине не большие 2 53

2.1. Языковые средства

31
2.1.3. Сокращение кода
Имена типов. Ключевое слово typedef позволяет сопоставить типу дан- ных короткое имя. Например, имя long long слишком длинное, поэтому можно определить для него короткий псевдоним ll
:
typedef long long ll;
После этого код
long long a = 123456789;
long long b = 987654321;
cout << a*b << "\n";
можно немного сократить:
ll a = 123456789;
ll b = 987654321;
cout << a*b << "\n";
Ключевое слово typedef применимо и к более сложным типам. Напри- мер, ниже мы сопоставляем вектору целых чисел имя vi
, а паре двух целых чисел – тип pi
typedef vector<int> vi;
typedef pair<int,int> pi;
Макросы. Еще один способ сократить код – макросы. Макрос говорит, что определенные строки кода следует подменить до компиляции. В C++ макросы определяются с помощью ключевого слова
#define
Например, мы можем определить следующие макросы:
#define F first
#define S second
#define PB push_back
#define MP make_pair
После чего код v.push_back(make_pair(y1,x1));
v.push_back(make_pair(y2,x2));
int d = v[i].first+v[i].second;
можно сократить до:
v.PB(MP(y1,x1));
v.PB(MP(y2,x2));
int d = v[i].F+v[i].S;

32 
Глава 2. Техника программирования
У макроса могут быть параметры, что позволяет сокращать циклы и другие структуры. Например, можно определить такой макрос:
#define REP(i,a,b) for (int i = a; i <= b; i++)
После этого код
for (int i = 1; i <= n; i++) {
search(i);
}
можно сократить следующим образом:
REP(i,1,n) {
search(i);
}
2.2. Рекурсивные алгоритмы
Благодаря рекурсии часто удается элегантно реализовать алгоритм. В этом разделе мы обсудим рекурсивные алгоритмы, которые систематически перебирают потенциальные решения задачи. Сначала рассмотрим по- рождение подмножеств и перестановок множества, а затем обсудим более общую технику перебора с возвратом.
2.2.1. Порождение подмножеств
В качестве первого применения рекурсии рассмотрим порождение всех подмножеств множества из n элементов. Например, подмножествами
{1, 2, 3} являются
0
, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3} и {1, 2, 3}. Следующая ре- курсивная функция search генерирует подмножества. Функция манипу- лирует вектором vector<int> subset;
который содержит элементы подмножества. Чтобы начать поиск, следует вызвать функцию с параметром 1.
void search(int k) {
if (k == n+1) {
// обработать подмножество
} else {
// включить k в подмножество subset.push_back(k);
search(k+1);
subset.pop_back();
// не включать k в подмножество

2.2. Рекурсивные алгоритмы

33
search(k+1);
}
}
При вызове с параметром k функция search решает, следует ли включать элемент k в множество или нет, но в обоих случаях вызывает себя с пара- метром k + 1. Если оказывается, что k = n + 1, то функция понимает, что все элементы обработаны и подмножество сгенерировано.
На рис. 2.1 показано порождение подмножеств при n = 3. При каждом вызове функции выбирается либо верхняя ветвь (k включается в подмно- жество), либо нижняя (k не включается в подмножество).
Рис. 2.1. Дерево рекурсии при порождении подмножеств множества {1, 2, 3}
2.2.2. Порождение перестановок
Теперь рассмотрим задачу о порождении всех перестановок множества из n элементов. Например, перестановками {1, 2, 3} будут (1, 2, 3), (1, 3, 2),
(2, 1, 3), (2, 3, 1), (3, 1, 2) и (3, 2, 1). И снова для решения можно применить рекурсию. Следующая функция манипулирует вектором vector<int> permutation;
который содержит перестановку, и массивом
bool chosen[n+1];
который для каждого элемента показывает, включен он уже в перестановку или нет. Поиск начинается, когда эта функция вызывается без парамет ров.
void search() {
if (permutation.size() == n) {
// обработать перестановку

34 
Глава 2. Техника программирования
} else {
for (int i = 1; i <= n; i++) {
if (chosen[i]) continue;
chosen[i] = true;
permutation.push_back(i);
search();
chosen[i] = false;
permutation.pop_back();
}
}
}
При каждом вызове функция добавляет новый элемент в вектор permutation и запоминает в массиве chosen
, что он был добавлен. Если размер permutation оказывается равен размеру множества, то генерируется перестановка.
Отметим, что в стандартной библиотеке C++ имеется функция next_permutation
, которую также можно использовать для порождения перестановок. Этой функции передается перестановка, а она порождает следующую за ней в лексикографическом порядке. Следующая программа перебирает все перестановки множества {1, 2, …, n}:
for (int i = 1; i <= n; i++) {
permutation.push_back(i);
}
do {
// обработать перестановку
} while (next_permutation(permutation.begin(), permutation.end()));
2.2.3. Перебор с возвратом
Алгоритм перебора с возвратом начинает работу с пустого решения и шаг за шагом расширяет его. Рекурсивно перебираются все возможные способы построения решения.
В качестве примера рассмотрим задачу о вычислении количества спосо- бов расставить n ферзей на доске n×n, так чтобы никакие два не били друг друга. Так, на рис. 2.2 показано два возможных решения для n = 4.
Рис. 2.2. Возможные способы расстановки 4 ферзей на доске 4×4

2.2. Рекурсивные алгоритмы

35
Задачу можно решить методом перебора с возвратом, рассматривая горизонтали одну за другой. Точнее, на каждой горизонтали можно раз- местить ровно одного ферзя, так чтобы он не оказался под боем ранее поставленных ферзей. Очередное решение будет найдено, когда на доску поставлены все n ферзей.
Например, на рис. 2.3 показано несколько частичных решений, сгенери- рованных алгоритмом перебора с возвратом при n = 4. Первые три расста- новки на нижнем уровне недопустимы, поскольку ферзи бьют друг друга.
Но четвертая расстановка допустима, и ее можно дополнить до решения, поставив на доску еще двух ферзей. Сделать это можно единственным способом.
Рис. 2.3. Частичные решения задачи о расстановке ферзей, полученные методом перебора с возвратом
Алгоритм можно реализовать следующим образом:
void search(int y) {
if (y == n) {
count++;
return;
}
for (int x = 0; x < n; x++) {
if (col[x] || diag1[x+y] || diag2[x-y+n-1]) continue;
col[x] = diag1[x+y] = diag2[x-y+n-1] = 1;
search(y+1);
col[x] = diag1[x+y] = diag2[x-y+n-1] = 0;
}
}

36 
Глава 2. Техника программирования
Поиск начинается вызовом search(0)
. Размер доски равен n, функция подсчитывает количество решений в переменной count
. В коде предпола- гается, что горизонтали и вертикали доски пронумерованы от 0 до n − 1.
Будучи вызвана с параметром y, функция search помещает ферзя на гори- зонталь y и вызывает себя с параметром y + 1. Когда y = n, решение найдено, поэтому значение count увеличивается на 1.
В массиве col запоминаются вертикали, уже занятые ферзями, а в мас- сивах diag1
и diag2
запоминаются диагонали. Запрещается ставить ферзя на вертикаль или диагональ, в которой уже находится другой ферзь. На рис. 2.4 показана нумерация вертикалей и диагоналей для доски 4×4.
Рис. 2.4. Нумерация массивов при подсчете комбинаций на доске 4×4
Показанный выше алгоритм перебора с возвратом говорит, что сущест- вует 92 способа расставить 8 ферзей на доске 8×8. С ростом n поиск быст ро замедляется, поскольку число решений возрастает экспоненциально. Так, на современном компьютере требуется около минуты, чтобы вычислить количество расстановок 16 ферзей на доске 16×16 – 14 772 512.
На самом деле до сих пор неизвестен эффективный способ подсчета числа расстановок ферзей для больших n. В настоящее время наибольшее
n
, для которого результат известен, равно 27: в этом случае существует
234 907 967 154 122 528 расстановок. Это было установлено в 2016 году группой исследователей, использовавших для решения кластер компью- теров [29].
2.3. Побитовые операции
В программировании n-разрядное целое число хранится в виде двоично- го числа, содержащего n бит. Например, тип int в C++ 32-разрядный, т. е. любое число типа int содержит 32 бита. Так, двоичное представление чис- ла 43 типа int имеет вид
00000000000000000000000000101011.
Биты в этом представлении нумеруются справа налево. Преобразование двоичного представления b
k
… b
2
b
1
b
0
в десятичное число производится по формуле

2.3. Побитовые операции

37
b
k
2
k
+ … + b
2 2
2
+ b
1 2
1
+ b
0 2
0
.
Например:
1 · 2 5
+ 1 · 2 3
+ 1 · 2 1
+ 1 · 2 0
= 43.
Двоичное представление числа может быть со знаком и без знака. Обыч- но используется представление со знаком, позволяющее представить по- ложительные и отрицательные числа. n-разрядная переменная со знаком может содержать любое целое число в диапазоне от −2
n
−1
до 2
n
−1
− 1. Напри- мер, тип int в C++ знаковый, поэтому переменная типа int может содер- жать любое целое число от −2 31
до 2 31
− 1.
Первый разряд в представлении со знаком содержит знак числа (0 для неотрицательных чисел, 1 – для отрицательных), а остальные n − 1 разря- дов – абсолютную величину числа. Используется дополнительный код, т. е. для получения противоположного числа нужно сначала инвертировать все его биты, а затем прибавить к результату единицу. Например, двоич- ное представление числа –43 типа int имеет вид
11111111111111111111111111010101.
Представление без знака позволяет представить только неотрицатель- ные числа, но верхняя граница диапазона больше. n-разрядная перемен- ная без знака может содержать любое целое число от 0 до 2
n
− 1. Например, в C++ переменная типа unsigned int может содержать любое целое число от 0 до 2 32
− 1.
Между обоими представлениям существует связь: число со знаком –x равно числу без знака 2
n
− x. К примеру, следующая программа показывает, что число со знаком x = −43 равно числу без знака y = 2 32
− 43:
int x = -43;
unsigned int y = x;
cout << x << "\n"; // -43
cout << y << "\n"; // 4294967253
Если число больше верхней границы допустимого диапазона, то воз- никает переполнение. В представлении со знаком число, следующее за
2
n
−1
– 1, равно −2
n
−1
, а в представлении без знака за 2
n
− 1 следует 0. Рассмот- рим следующий код:
int x = 2147483647
cout << x << "\n"; // 2147483647
x++;
cout << x << "\n"; // -2147483648

38 
Глава 2. Техника программирования
Первоначально x принимает значение 2 31
− 1. Это наибольшее значение, которое можно сохранить в переменной типа int
, поэтому следующее за
2 31
− 1 значение равно −2 31
2.3.1. Поразрядные операции
Операция И. Результатом операции И x & y является число, двоичное представление которого содержит единицы в тех позициях, на которых в представлениях x и y находятся единицы. Например, 22 & 26 = 18, поскольку
10110 (22)
& 11010 (26)
= 10010 (18)
С помощью операции И можно проверить, является ли число x четным, т. к. x & 1 = 0, если x четно, и x & 1 = 1, если x нечетно. Вообще, x нацело делится на 2
k
, если x & (2
k
− 1) = 0.
Операция ИЛИ. Результатом операции ИЛИ x | y является число, двоич- ное представление которого содержит единицы в тех позициях, на кото- рых хотя бы в одном из представлений x и y находятся единицы. Напри- мер, 22 | 26 = 30, поскольку
10110 (22)
| 11010 (26)
= 11110 (30)
Операция ИСКЛЮЧАЮЩЕЕ ИЛИ. Результатом операции ИСКЛЮЧАЮ-
ЩЕЕ ИЛИ x ^ y является число, двоичное представление которого содержит единицы в тех позициях, на которых ровно в одном из представлений x и y находятся единицы. Например, 22 ^ 26 = 12, поскольку
10110 (22)
ˆ
11010 (26)
= 01100 (12)
Операция НЕ. Результатом операции НЕ

x является число, в двоичном представлении которого все биты x инвертированы. Справедлива формула

x = −x – 1, например 29 = −30. Результат операции НЕ на битовом уровне зависит от длины двоичного представления, поскольку инвертируются все биты. Например, в случае 32-разрядных чисел типа int имеем:
x = 29 00000000000000000000000000011101
x
= −30 11111111111111111111111111100010
Поразрядный сдвиг. Операция поразрядного сдвига влево x << k дописы вает в конец числа k нулей, а операция поразрядного сдвига вправо

2.3. Побитовые операции

39
x
>> k удаляет k последних бит. Например, 14 << 2 = 56, поскольку двоичные представления 14 и 56 равны соответственно 1110 и 111000. Аналогично
49 >> 3 = 6, потому что 49 и 6 в двоичном виде равны соответственно 110001 и 110. Отметим, что операция x << k соответствует умножению x на 2
k
, а x >> k – делению x на 2
k
с последующим округлением с недостатком до целого.
Битовые маски. Битовой маской называется число вида 1 << k, содер- жащее в позиции k единицу, а во всех остальных позициях – нули. Такую маску можно использовать для выделения одиночных битов. В частности,
k-й бит числа равен единице тогда и только тогда, когда x & (1 << k) не равно нулю. В следующем фрагменте печатается двоичное представление числа x типа int
:
for (int k = 31; k >= 0; k--) {
if (x&(1< else cout << "0";
}
Аналогичным образом можно модифицировать отдельные биты чис- ла. Выражение x | (1 << k)устанавливает k-й бит x в единицу, выражение
x & (1 << k)сбрасывает k-й бит x в нуль, а выражение x ˆ (1 << k)инвертиру- ет k-й бит x. Далее выражение x & (x − 1)сбрасывает последний единичный бит x в нуль, а выражение x & −x сбрасывает в нуль все единичные биты, кроме последнего. Выражение x | (x − 1)инвертирует все биты после по- следнего единичного. Наконец, положительное число x является степенью двойки тогда и только тогда, когда x & (x − 1)= 0.
При работе с битовыми масками нужно помнить, что
1<. Самый простой способ создать битовую маску типа long long
– напи сать
1LL<Дополнительные функции. Компилятор g++ предлагает также следую- щие функции для подсчета битов:
•
__builtin_clz
(x): количество нулей в начале двоичного представле- ния;
•
__builtin_ctz
(x): количество нулей в конце двоичного представления;
•
__builtin_popcount
(x): количество единиц в двоичном представле- нии;
•
__builtin_parity
(x): четность количества единиц в двоичном пред- ставлении.
Эти функции используются следующим образом:
int x = 5328; // 00000000000000000001010011010000
cout << __builtin_clz(x) << "\n"; // 19

40 
Глава 2. Техника программирования cout << __builtin_ctz(x) << "\n”; // 4
cout << __builtin_popcount(x) << "\n"; // 5
cout << __builtin_parity(x) << "\n"; // 1
Отметим, что данные функции поддерживают только числа типа int
, но есть также их варианты для типа long long
, их имена заканчиваются суф- фиксом ll
2.3.2. Представление множеств
Любое подмножество множества {0, 1, 2, …, n − 1} можно представить
n
-разрядным целым числом, в котором единичные биты соответствуют элементам, принадлежащим подмножеству. Такой способ представления эффективен, поскольку для каждого элемента требуется всего один бит памяти, а теоретико-множественные операции можно реализовать с по- мощью поразрядных операций.
Например, поскольку тип int
32-разрядный, числом типа int можно представить любое подмножество множества {0, 1, 2, …, 31}. Двоичное представление множества {1, 3, 4, 8} имеет вид
00000000000000000000000100011010,
что соответствует числу 2 8
+ 2 4
+ 2 3
+ 2 1
= 282.
В показанном ниже коде объявлена переменная x типа int
, которая мо- жет содержать подмножество множества {0, 1, 2, …, 31}. Затем в это под- множество добавляются элементы 1, 3, 4, 8 и печатается его размер.
int x = 0;
x |= (1<<1);
x |= (1<<3);
x |= (1<<4);
x |= (1<<8);
cout << __builtin_popcount(x) << "\n"; // 4
Далее печатаются все элементы, принадлежащие множеству:
for (int i = 0; i < 32; i++) {
if (x&(1<}
// выводится: 1 3 4 8
Операции над множествами. В табл. 2.1 показано, как реализовать теоре тико-множественные операции с помощью побитовых. Так, следу- ющий код сначала конструирует множества x = {1, 3, 4, 8} и y = {3, 6, 8, 9}, а затем множество z = x ∪ y = {1, 3, 4, 6, 8, 9}:

2.3. Побитовые операции

41
int x = (1<<1)|(1<<3)|(1<<4)|(1<<8);
int y = (1<<3)|(1<<6)|(1<<8)|(1<<9);
int z = x|y;
cout << __builtin_popcount(z) << "\n"; // 6
Таблица 2.1. Реализация теоретико-множественных операций с помощью побитовых
Операция
Теоретико-множественная запись
Побитовая запись
Пересечение
a
∩ b
a
& b
Объединение
a
∪ b
a
| b
Дополнение

a
Разность
a
\ b
a
&(b)
Следующий код перебирает подмножества множества {0, 1, …, n − 1}:
for (int b = 0; b < (1< // обработать подмножество b
}
А этот код перебирает только подмножества, содержащие ровно k эле- ментов:
for (int b = 0; b < (1< if (__builtin_popcount(b) == k) {
// обработать подмножество b
}
}
Наконец, следующий код перебирает все подмножества множества x:
int b = 0;
do {
// обработать подмножество b
} while (b=(b-x)&x);
Битовые множества в C++. В стандартной библиотеке C++ имеется структура bitset
, соответствующая массиву, все элементы которого равны
0 или 1. Например, следующий код создает битовое множество из 10 эле- ментов:
bitset<10> s;
s[1] = 1;
s[3] = 1;
s[4] = 1;
s[7] = 1;

42 
Глава 2. Техника программирования cout << s[4] << "\n"; // 1
cout << s[5] << "\n"; // 0
Функция count возвращает количество единичных битов в битовом мно- жестве:
cout << s.count() << "\n"; // 4
К битовым множествам также применимы побитовые операции:
bitset<10> a, b;
// ...
bitset<10> c = a&b;
bitset<10> d = a|b;
bitset<10> e