# Программирование: теоремы и задачи

Alexander Shen

► To cite this version:

Alexander Shen. Программирование: теоремы и задачи. MCCME publishers, 2021, 978-5-4439-1560-9.
<lirmm-03377918>

HAL Id: lirmm-03377918

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03377918

Submitted on 14 Oct 2021

HAL is a multi-disciplinary open access archive
for the deposit and dissemination of scientific re-
search documents, whether they are published or not.
The documents may come from teaching and research
institutions in France or abroad, or from public or pri-
vate research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
А. ШЕНЬ

# ПРОГРАММИРОВАНИЕ
теоремы и задачи

Издание седьмое, дополненное

Москва
Издательство МЦНМО
2021
Шень А.

Ш47 Программирование: теоремы и задачи. — 7-е изд., дополненное. — М.: МЦНМО, 2021. — 320 с.: ил.

ISBN 978-5-4439-1560-9

Книга содержит задачи по программированию различной трудности. Большинство задач приводятся с решениями. Цель книги — научить основным методам построения корректных и быстрых алгоритмов.

Для учителей информатики, старшеклассников, студентов младших курсов высших учебных заведений. Пособие может быть использовано на кружковых и факультативных занятиях в общеобразовательных учреждениях, в школах с углублённым изучением математики и информатики, а также в иных целях, не противоречащих законодательству РФ.

Предыдущее издание книги вышло в 2017 г.

ББК 22.18

<figure><img src="image_2.png" /></figure>

**Предупреждение.** Автор является научным сотрудником лаборатории LIRMM в г. Монпелье (Франция) и может рассматриваться de facto правительством России как «иностранный агент» в смысле поправок к «закону об иностранных агентах», принятых 21.11.2019.
Несколько замечаний вместо предисловия

Книга написана по материалам занятий программированием со школьниками математических классов школы № 57 г. Москвы и студентами младших курсов (Московский государственный университет, Независимый московский университет, университет г. Uppsala, Швеция).

Книга написана в убеждении, что программирование имеет свой предмет, не сводящийся ни к конкретным языкам и системам, ни к методам построения быстрых алгоритмов.

Кто-то однажды сказал, что можно убедить в правильности алгоритма, но не в правильности программы. Одна из целей книги — попытаться продемонстрировать, что это не так.

В принципе, возможность практического исполнения программ не является непременным условием изучения программирования. Однако она является сильнейшим стимулом — без такого стимула вряд ли у кого хватит интереса и терпения.

Выбранный жанр книги по необходимости ограничивает её «программированием в малом», оставляя в стороне необходимую часть программистского образования — работу по модификации больших программ. Автор продолжает мечтать о наборе учебных программных систем эталонного качества, доступных для модификации школьниками.

Кажется, Хоар сказал, что эстетическая прелесть программы — это не архитектурное излишество, а то, что отличает в программировании успех от неудачи. Если, решая задачи из этой книги, читатель почувствует прелесть хорошо написанной программы, в которой «ни убавить, ни прибавить», и сомнения в правильности которой кажутся нелепыми, то автор будет считать свою цель достигнутой.

Характер глав различен: в одних предлагается набор мало связанных друг с другом задач с решениями, в других по существу излагается один-единственный алгоритм. Темы глав во многом пересекаются, и мы предпочли кое-какие повторения формальным ссылкам.

Уровень трудности задач и глав весьма различен. Мы старались включить как простые задачи, которые могут быть полезны для начинающих, так и трудные задачи, которые могут посадить в лужу сильного школьника. (Хоть и редко, но это бывает полезно.)
В качестве языка для записи программ был выбран паскаль. Он достаточно прост и естествен, имеет неплотие реализации (например, старые компьютеры Turbo Pascal фирмы Borland были были были вложены для бесплатного скачивания) и позволяет записать решения всех рассматриваемых задач. Возможно, Модула-2 или Оберон были бы более изящным выбором, но они менее доступны.

Практически все задачи и алгоритмы, разумеется, не являются новыми. (В некоторых редких случаях приведены ссылки на конкретную книгу или конкретного человека. См. также список книг для дальнейшего чтения.) Вместе с тем мы надеемся, что в некоторых случаях алгоритмы (и особенно доказательства) изложены более коротко и отчётливо.

Это не только и не столько учебник для школьника, сколько справочник и задачник для преподавателя, готовящегося к занятию.

Об «авторских правах»: право формулировать задачу и объяснять её решение является неотчуждаемым естественным правом всякого, кто на это способен. В соответствии с этим текст является свободно распространяемым. Адреса автора: shen@mccme.ru, sasha.shen@gmail.com, alexander.shen@lirmm.fr. Сказанное относится к русскому тексту; все права на переводы переданы издательству Springer.

При подготовке текста использовалась (свободно распространяемая) версия LATEX, включающая стилевые файлы, составленные С. М. Львовским (см. ftp://ftp.mccme.ru/pub/tex/).

Я рад случаю поблагодарить всех, с кем имел честь сотрудничать, преподавая программирование, особенно тех, кто был «по другую сторону баррикады», а также всех приславших мне замечания и исправления (специальная благодарность — Ю. В. Матиясевичу). Автор благодарит В. Шувалова за хлопоты по вёрстке, а также издательство МЦНМО. Благодарю также Институт проблем передачи информации РАН, Американское математическое общество (фонд помощи бывшему СССР), фонд Сороса, университет г. Бордо, фонд «Культурная инициатива», фонды STINT (Швеция), CNRS (Франция), Ecole Normale (Лион, Франция), LIF (Марсель, Франция), LIRMM (Монпелье, Франция), университет г. Уппсала (Швеция), агентство ANR (грант RaCAF, ANR-15-CE40-0016-01), Российский фонд фундаментальных исследований (гранты 02-01-22001 НЦНИа, 03-01-00475 и другие), а также Совет поддержки научных школ при Президенте РФ (грант НШ-358.2003.1) за поддержку. Вместе с тем содержание книги отражает точку зрения автора, за ошибки которого указанные организации и лица ответственности не несут (и наоборот).
# Содержание

<table><tr><td>1. Переменные, выражения, присваивания</td><td>8</td></tr><tr><td>1.1. Задачи без массивов</td><td>8</td></tr><tr><td>1.2. Массивы</td><td>23</td></tr><tr><td>1.3. Индуктивные функции (по А.Г. Кушниренко)</td><td>38</td></tr></table>

<table><tr><td>2. Порождение комбинаторных объектов</td><td>43</td></tr><tr><td>2.1. Размещения с повторениями</td><td>43</td></tr><tr><td>2.2. Перестановки</td><td>44</td></tr><tr><td>2.3. Подмножества</td><td>45</td></tr><tr><td>2.4. Разбиения</td><td>48</td></tr><tr><td>2.5. Коды Грея и аналогичные задачи</td><td>49</td></tr><tr><td>2.6. Несколько замечаний</td><td>55</td></tr><tr><td>2.7. Подсчёт количеств</td><td>57</td></tr></table>

<table><tr><td>3. Обход дерева. Переребор с возвратами</td><td>60</td></tr><tr><td>3.1. Ферзи, не бьющие друг друга: обход дерева позиций</td><td>60</td></tr><tr><td>3.2. Обход дерева в других задачах</td><td>70</td></tr></table>

<table><tr><td>4. Сортировка</td><td>72</td></tr><tr><td>4.1. Квадратичные алгоритмы</td><td>72</td></tr><tr><td>4.2. Алгоритмы порядка n log n</td><td>73</td></tr><tr><td>4.3. Применения сортировки</td><td>80</td></tr><tr><td>4.4. Нижние оценки для числа сравнений при сортировке</td><td>82</td></tr><tr><td>4.5. Родственные сортировке задачи</td><td>84</td></tr></table>

<table><tr><td>5. Конечные автоматы и обработка текстов</td><td>90</td></tr><tr><td>5.1. Составные символы, комментарии и т. п.</td><td>90</td></tr><tr><td>5.2. Ввод чисел</td><td>92</td></tr></table>
6. Типы данных 96

6.1. Стеки 96

6.2. Очереди 103

6.3. Множества 111

6.4. Разные задачи 115

7. Рекурсия 117

7.1. Примеры рекурсивных программ 117

7.2. Рекурсивная обработка деревьев 120

7.3. Порождение комбинаторных объектов, перебор 123

7.4. Другие применения рекурсии 127

8. Как обойтись без рекурсии 135

8.1. Таблица значений (динамическое программирование) 135

8.2. Стек отложенных заданий 140

8.3. Более сложные случаи рекурсии 143

9. Разные алгоритмы на графах 146

9.1. Кратчайшие пути 146

9.2. Связные компоненты, поиск в глубину и ширину 152

9.3. Сети, потоки и разрезы 157

10. Сопоставление с образцом 177

10.1. Простейший пример 177

10.2. Повторения в образце — источник проблем 180

10.3. Вспомогательные утверждения 182

10.4. Алгоритм Кнута-Морриса-Пратта 182

10.5. Алгоритм Бойера-Мура 185

10.6. Алгоритм Рабина 187

10.7. Более сложные образцы и автоматы 189

10.8. Суффиксные деревья 196

11. Анализ игр 209

11.1. Примеры игр 209

11.2. Цена игры 211

11.3. Вычисление цены: полный обход 219

11.4. Альфа-бета-процедура 222

11.5. Ретроспективный анализ 226
12. Оптимальное кодирование 229

12.1. Коды 229

12.2. Неравенство Крафта-Макмиллана 230

12.3. Код Хаффмана 234

12.4. Код Шеннона-Фано 236

13. Представление множеств. Хеширование 240

13.1. Хеширование с открытой адресацией 240

13.2. Хеширование со списками 243

14. Деревья. Сбалансированные деревья 249

14.1. Представление множеств с помощью деревьев 249

14.2. Сбалансированные деревья 257

15. Контекстно-свободные грамматики 268

15.1. Общий алгоритм разбора 268

15.2. Метод рекурсивного спуска 274

15.3. Алгоритм разбора для LL(1)-грамматик 285

16. Синтаксический разбор слева направо (LR) 293

16.1. LR-процессы 293

16.2. LR(0)-грамматики 299

16.3. SLR(1)-грамматики 305

16.4. LR(1)-грамматики, LALR(1)-грамматики 306

16.5. Общие замечания о разных методах разбора 309

Книги для чтения 311

Предметный указатель 312

Указатель имён 318
# 1. ПЕРЕМЕННЫЕ, ВЫРАЖЕНИЯ, ПРИСВАИВАНИЯ

## 1.1. Задачи без массивов

1.1.1. Даны две целые переменные a, b. Составьте фрагмент программы, после исполнения которого значения переменных поменялись бы местами (новое значение a равно старому значению b и наоборот).

**Решение.** Введём дополнительную целую переменную t.

t := a;

a := b;

b := t;

☐

Попытка обойтись без дополнительной переменной, написав

a := b;

b := a;

не приводит к цели (безвозвратно утрачивается начальное значение переменной a).

1.1.2. Решите предыдущую задачу, не используя дополнительных переменных (и предполагая, что значениями целых переменных могут быть произвольные целые числа).

**Решение.** Начальные значения a и b обозначим a0, b0.

a := a + b; {a = a0 + b0, b = b0}

b := a - b; {a = a0 + b0, b = a0}

a := a - b; {a = b0, b = a0}

☐
1.1.3. Дано целое число a и натуральное (целое неотрицательное) число n. Вычислите an. Другими словами, необходимо составить программу, при исполнении которой значения переменных a и n не меняются, а значение некоторой другой переменной (например, b) становится равным an. (При этом разрешается использовать и другие переменные.)

**Решение.** Введём целую переменную k, которая меняется от 0 до n, причём поддерживается такое свойство: $b = a^k$.

```
k := 0; b := 1;
{b = a в степени k}
while k <> n do begin
  k := k + 1;
  b := b * a;
end;
```

<figure><img src="image_3.png" /></figure>

Другое решение той же задачи:

```
k := n; b := 1;
{а в степени n = b * (а в степени k)}
while k <> 0 do begin
  k := k - 1;
  b := b * a;
end;
```

1.1.4. Решите предыдущую задачу, если требуется, чтобы число действий (выполняемых операторов присваивания) было порядка $log n$ (то есть не превосходило бы $C \log n$ для некоторой константы $C$; $\log n$ — это степень, в которую нужно возвести 2, чтобы получить $n$).

**Решение.** Внесём некоторые изменения во второе из предложенных решений предыдущей задачи:

```
k := n; b := 1; c:=a;
{а в степени n = b * (c в степени k)}
while k <> 0 do begin
  if k mod 2 = 0 then begin
    k := k div 2;
    c := c*c;
  end else begin
    k := k - 1;
    b := b * c;
  end;
end;
```
Каждый второй раз (не реже) будет выполняться первый вариант оператора выбора (если k нечётно, то после вычитания единицы становится чётным), так что за два цикла величина k уменьшается по крайней мере в двое. ☐

**1.1.5.** Даны натуральные числа a, b. Вычислите произведение a · b, используя в программе лишь операции +, -, =, <>.

**Решение.**

```pascal
k := 0; c := 0;
{инвариант: c = a * k}
while k <> b do begin
  k := k + 1;
  c := c + a;
end;
{c = a * k и k = b, следовательно, c = a * b}
```

**1.1.6.** Даны натуральные числа a и b. Вычислите их сумму a + b. Используйте операторы присваивания лишь вида

```
<переменная1> := <переменная2>,
<переменная> := <число>,
<переменная1> := <переменная2> + 1.
```

**Решение.**

```pascal
... {инвариант: c = a + k}
...
```

**1.1.7.** Дано натуральное (целое неотрицательное) число a и целое положительное число d. Вычислите частное q и остаток r при делении a на d, не используя операций div и mod.

**Решение.** Согласно определению, $a = q \cdot d + r$, $0 \le r < d$.

```pascal
{a >= 0; d > 0}
r := a; q := 0;
{инвариант: a = q * d + r, 0 <= r}
while not (r < d) do begin
  {r >= d}
  r := r - d; {r >= 0}
  q := q + 1;
end;
```

<figure><img src="image_4.png" /></figure>
1.1.8. Дано натуральное $n$, вычислите $n! (0! = 1, n! = n \cdot (n-1)!)$. $\square$

1.1.9. Последовательность Фибоначчи определяется так: $a_0 = 0$, $a_1 = 1$, $a_k = a_{k-1} + a_{k-2}$ при $k \ge 2$. Дано $n$, вычислите $a_n$. $\square$

1.1.10. Та же задача, если требуется, чтобы число операций было пропорционально $\log n$. (Переменные должны быть целочисленными.)

[Указание. Пара соседних чисел Фибоначчи получается из предыдущей умножением на матрицу

$$ \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix} $$

— так что задача сводится к возведению матрицы в степень $n$. Это можно сделать за $C \log n$ действий тем же способом, что и для чисел.] $\square$

1.1.11. Дано натуральное $n$, вычислите

$$ \frac{1}{0!} + \frac{1}{1!} + \dots + \frac{1}{n!} \quad \square $$

1.1.12. То же, если требуется, чтобы количество операций (выполненных команд присваивания) было бы порядка $n$ (не более $Cn$ для некоторой константы $C$).

**Решение.** Инвариант: $sum = 1/1! + \dots + 1/k!$, $last = 1/k!$ (важно не вычислять заново каждый раз $k!$). $\square$

1.1.13. Даны два натуральных числа $a$ и $b$, не равные нулю одно- временно. Вычислите НОД($a$, $b$) — наибольший общий делитель $a$ и $b$.

**Решение.** Вариант 1.

```python
if a < b then begin
    k := a;
end else begin
    k := b;
end;
{k = min(a,b)}
{инвариант: никакое число, большее k, не является
    общим делителем (оно больше одного из чисел a,b)}
while not ((a mod k == 0) and (b mod k == 0)) do begin
    k := k - 1;
end;
{k - общий делитель, большие - нет}
```
Вариант 2 (алгоритм Евклида). Будем считать, что НОД(0,0)=0. Тогда НОД(а,b) = НОД(а-б,b) = НОД(а,b-a); НОД(а,0) = НОД(0,а) = а для всех а, b ≥ 0.

```pascal
m := a; n := b;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
while not ((m=0) or (n=0)) do begin
  if m >= n then begin
    m := m - n;
  end else begin
    n := n - m;
  end;
end;
{m = 0 или n = 0}
if m = 0 then begin
  k := n;
end else begin {n = 0}
  k := m;
end;
```

<figure><img src="image_5.png" /></figure>

### 1.1.14. Напишите модифицированный вариант алгоритма Евклида, использующий соотношения НОД(a,b) = НОД(a mod b, b) при a ≥ b, НОД(a,b) = НОД(a, b mod a) при b ≥ a.

<figure><img src="image_6.png" /></figure>

### 1.1.15. Даны натуральные a и b, не равные 0 одновременно. Найдите d = НОД(a,b) и такие целые x и y, что d = a · x + b · y.

**Решение.** Добавим в алгоритм Евклида переменные p, q, r, s и впишем в инвариант условия m = p*a+q*b; n = r*a+s*b.

```pascal
m:=a; n:=b; p := 1; q := 0; r := 0; s := 1;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0
  m = p*a + q*b; n = r*a + s*b.}
while not ((m=0) or (n=0)) do begin
  if m >= n then begin
    m := m - n; p := p - r; q := q - s;
  end else begin
    n := n - m; r := r - p; s := s - q;
  end;
end;
if m = 0 then begin
  k :=n; x := r; y := s;
end else begin
  k := m; x := p; y := q;
end;
```

<figure><img src="image_7.png" /></figure>
1.1.16. Решите предыдущую задачу, используя в алгоритме Евклида деление с остатком. □

1.1.17. (Э. Дейкстра) Добавим в алгоритм Евклида дополнительные переменные u, v, z:

```pascal
m := a; n := b; u := b; v := a;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
while not ((m=0) or (n=0)) do begin
    if m >= n then begin
        m := m - n; v := v + u;
        end else begin
            n := n - m; u := u + v;
        end;
    end;
    if m = 0 then begin
        z := v;
    end else begin {n=0}
        z := u;
    end;
```

Докажите, что после исполнения алгоритма значение z равно удвоенному наименьшему общему кратному чисел a, b: $z = 2 \cdot НОК(a,b)$.

Решение. Заметим, что величина $m \cdot u + n \cdot v$ не меняется в ходе выполнения алгоритма. Остаётся воспользоваться тем, что вначале она равна $2ab$ и что $НОД(a,b) \cdot НОК(a,b) = ab$. □

1.1.18. Напишите вариант алгоритма Евклида, использующий соотношения

$$ 
\begin{gather*}
НОД(2a, 2b) = 2 \cdot НОД(a, b), \\
НОД(2a, b) = НОД(a, b) \text{ при нечётном b,}
\end{gather*}
$$

не включающий деления с остатком, а использующий лишь деление на 2 и проверку чётности. (Число действий должно быть порядка $\log k$ для исходных данных, не превосходящих k.)

Решение.

```pascal
m := a; n := b; d := 1;
{НОД(a,b) = d * НОД(m,n)}
while not ((m=0) or (n=0)) do begin
    if (m mod 2 = 0) and (n mod 2 = 0) then begin
        d := d*2; m := m div 2; n := n div 2;
    end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
```
```pascal
m:= m div 2;
end else if (m mod 2 = 1) and (n mod 2 = 0) then begin
  n:= n div 2;
end else if (m mod 2=1) and (n mod 2=1) and (m>=n) then begin
  m:= m-n;
end else if (m mod 2=1) and (n mod 2=1) and (m<=n) then begin
  n:= n-m;
end;
end;
{m=0 => ответ=d*n; n=0 => ответ=d*m}
```

Оценка числа действий: каждое второе действие делит хотя бы одно из чисел m и n пополам. ☐

**1.1.19.** Дополните алгоритм предыдущей задачи поиском х и у, для которых $ax + by = НОД(a, b)$.

**Решение.** (Идея сообщена Д. Звонкиным.) Прежде всего заметим, что одновременное деление a и b пополам не меняет искомых х и у. Поэтому можно считать, что с самого начала одно из чисел a и b нечётно. (Это свойство будет сохраняться и далее.)

Теперь попытаемся, как и раньше, хранить такие числа p, q, r, s, что

$$m = ap + bq,$$

$$n = ar + bs.$$

Проблема в том, что при делении, скажем, m на 2 надо разделить p и q на 2, и они перестанут быть целыми (а станут двочно-рациональными). Двочно-рациональное число естественно хранить в виде пары (числитель, показатель степени двойки в знаменателе). В итоге мы получаем d в виде комбинации a и b с двочно-рациональными коэффициентами. Иными словами, мы имеем

$$2^i d = ax + by$$

для некоторых целых x, y и натурального i. Что делать, если $i > 1$? Если x и у чётны, то на 2 можно сократить. Если это не так, положение можно исправить преобразованием

$$x := x + b,$$

$$y := y - a$$

(оно не меняет $ax + by$). Убедимся в этом. Напомним, что мы считаем, что одно из чисел a и b нечётно. Пусть это будет a. Если при этом
у чётно, то и х должно быть чётным (иначе ax + by будет нечётным). А при нечётном у вычитание из него нечётного a делает у чётным. ☐

1.1.20. Составьте программу, печатающую квадраты всех натуральных чисел от 0 до заданного натурального n.

Решение.

```python
k:=0;
writeln (k*k);
{инвариант: k<=n, напечатаны все
квадраты до k включительно}
while not (k=n) do begin
    k:=k+1;
    writeln (k*k);
end;
```

<figure><img src="image_8.png" /></figure>

1.1.21. Та же задача, но разрешается использовать из арифметических операций лишь сложение и вычитание, причём общее число действий должно быть порядка n.

Решение. Введём переменную k_square (square — квадрат), связанную с k соотношением $k_square = k^2$:

```python
k := 0; k_square := 0;
writeln (k_square);
while not (k = n) do begin
    k := k + 1;
    {k_square = (k-1) * (k-1) = k*k - 2*k + 1}
    k_square := k_square + k + k - 1;
    writeln (k_square);
end;
```

<figure><img src="image_9.png" /></figure>

Замечание. Можно обойтись без вычитания с помощью такой хитрости:

```python
while not (k = n) do begin
    k_square := k_square + k;
    {k_square = k*k + k}
    k := k + 1;
    {k_square = (k-1)*(k-1)+(k-1)=k*k-k}
    k_square := k_square + k;
end;
```

1.1.22. Составьте программу, печатающую разложение на простые множители заданного натурального числа $n > 0$ (другими словами, требуется печатать только простые числа и произведение напечатанных чисел должно быть равно $n$; если $n = 1$, печатать ничего не надо).
Решение. Вариант 1.

```pascal
k := n;
{инвариант: произведение напечатанных чисел и k равно
  n, напечатаны только простые числа}
while not (k = 1) do begin
  l := 2;
  {инвариант: k не имеет делителей в интервале (1,1)}
  while k mod l <> 0 do begin
    l := l + 1;
    end;
    {l - наименьший делитель k, больший 1, следовательно,
     простой}
   >writeln (1);
    k:=k div 1;
  end;
```

Вариант 2.

```pascal
k := n; l := 2;
{произведение k и напечатанных чисел равно n; напечатанные
  числа просты; k не имеет делителей, меньших l}
while not (k = 1) do begin
  if k mod l = 0 then begin
    {к делится на l и не имеет делителей,
     меньших l, значит, l просто}
    k := k div l;
   >writeln (1);
  end else begin
    { k не делится на l }
    l := l+1;
  end;
end;
```

<figure><img src="image_10.png" /></figure>

1.1.23. Составьте программу решения предыдущей задачи, использующую тот факт, что составное число имеет делитель, не превосходящий квадратного корня из этого числа.

Решение. Во втором варианте решения вместо $1:=1+1$ можно написать

```pascal
if l*1 > k then begin
  l:=k;
end else begin
  l:=l+1;
end;
```

<figure><img src="image_11.png" /></figure>
1.1.24. Проверьте, является ли заданное натуральное число $n > 1$ простым. ☐

1.1.25. (Для знакомых с основами алгебры) Дано целое гауссово число $n + m$ ($\mathbb{Z}[i]$).

(а) Проверьте, является ли оно простым (в $\mathbb{Z}[i]$).

(б) Напечатайте его разложение на простые (в $\mathbb{Z}[i]$) множители. ☐

1.1.26. Разрешим применять команды `write(i)` лишь при $i = 0, 1, 2, ..., 9$. Составьте программу, печатающую десятичную запись заданного натурального числа $n > 0$. (Случай $n = 0$ явился бы некоторым исключением, так как обычно нули в начале числа не печатаются, а для $n = 0$ — печатаются.)

Решение.

```python
base:=1;
{base - степень 10, не превосходящая n}
while 10 * base <= n do begin
    base:= base * 10;
end;
{base - максимальная степень 10, не превосходящая n}
k:=n;
{инвариант: осталось напечатать k с тем же числом
    знаков, что в base; base = 100...00}
while base <> 1 do begin
    write(k div base);
    k:= k mod base;
    base:= base div 10;
end;
{base=1; осталось напечатать однозначное число k}
write(k);
```

Типичная ошибка при решении этой задачи: неправильно обрабатываются числа с нулями посередине. Приведённый инвариант допускает случай, когда $k < base$; в этом случае печатание $k$ начинается со старших нулей.

1.1.27. То же самое, но надо напечатать десятичную запись в обратном порядке. (Для $n = 173$ надо напечатать 371.)

Решение.

```python
k:= n;
{инвариант: осталось напечатать k в обратном порядке}
```
```pascal
while k <> 0 do begin
  write (k mod 10);
  k:= k div 10;
end;
```

## 1.1.28. Дано натуральное n. Подсчитайте количество решений неравенства $x^2 + y^2 < n$ в натуральных (неотрицательных целых) числах, не используя действий с вещественными числами.

### Решение.

```pascal
k := 0; s := 0;
{инвариант: s = количество решений неравенства
           x*x + y*y < n c x < k}
while k*k < n do begin
  ...
  {t = число решений неравенства k*k + y*y < n
     c y>=0 (при данном k) }
  k := k + 1;
  s := s + t;
end;
{k*k >= n, поэтому s = количество всех решений
     неравенства}
```

Здесь ... — пока ещё не написанный кусок программы, который будет таким:

```pascal
l := 0; t := 0;
{инвариант: t = число решений
           неравенства k*k + y*y < n c 0<=y<1 }
while k*k + l*1 < n do begin
  l := l + 1;
  t := t + 1;
end;
{k*k + l*1 >= n, поэтому t = число
           всех решений неравенства k*k + y*y < n}
```

## 1.1.29. Та же задача, но количество операций должно быть порядка $\sqrt{n}$. (В предыдущем решении, как можно подсчитать, порядка n операций.)

### Решение.
Нас интересуют точки решётки (с целыми координатами) в первом квадранте, попадающие внутрь круга радиуса $\sqrt{n}$. Интересующее нас множество (назовём его X) состоит из объединения
вертикальных столбцов убывающей высоты.

<figure><img src="image_12.png" /></figure>

Идея решения состоит в том, чтобы «двигаться вдоль его границы», спускаясь по верхнему его краю, как по лестнице. Координаты движущейся точки обозначим <k,1>. Введём ещё одну переменную s и будем поддерживать истинность такого условия:

<k,1> находится сразу над k-м столбцом;

s — число точек в предыдущих столбцах.

Формально:

• 1 — минимальное среди тех 1 ≥ 0, для которых <k,1> не принадлежит X;

• s — число пар натуральных x, y, для которых x < k и <x,y> принадлежит X.

Обозначим эти условия через (И).

```pascal
k := 0; l := 0;
while <0,1> принадлежит X do begin
  l := l + 1;
end;
{k = 0, l - минимальное среди тех 1 >= 0,
   для которых <k,1> не принадлежит X}
s := 0;
{инвариант: И}
while not (l = 0) do begin
  s := s + 1;
  {s - число точек в столбцах до k-го включительно}
  k := k + 1;
  {точка <k,1> лежит вне X, но, возможно, её надо сдвинуть
     вниз, чтобы восстановить И}
  while (l <> 0) and (<k, 1-1> не принадлежит X) do begin
    l := l - 1;
  end;
end;
{И, l = 0, поэтому k-ый столбец и все следующие пусты, а
  s равно искомому числу}
```
Оценка числа действий очевидна: сначала мы движемся вверх не более чем на $\sqrt{n}$ шагов, а затем вниз и вправо — в каждую сторону не более чем на $\sqrt{n}$ шагов. ☐

### 1.1.30. Даны натуральные числа $n$ и $k$, $n > 1$. Напечатайте $k$ десятичных знаков числа $1/n$. (При наличии двух десятичных разложений выбирается то из них, которое не содержит девятки в периоде.) Программа должна использовать только целые переменные.

**Решение.** Сдвинув в десятичной записи числа $1/n$ запятую на $k$ мест вправо, получим число $10^k/n$. Нам надо напечатать его целую часть, то есть разделить $10^k$ на $n$ нацело. Стандартный способ требует использования больших по величине чисел, которые могут выйти за границы диапазона представимых чисел. Поэтому мы сделаем иначе (следуя обычному методу «деления уголком») и будем хранить «остаток» $r$:

```pascal
l := 0; r := 1;
{инв.: напечатано 1 разрядов 1/n, осталось напечатать
   k - 1 разрядов дроби r/n}
while l <> k do begin
  write ( (10 * r) div n);
  r := (10 * r) mod n;
  l := l + 1;
end;
```

<figure><img src="image_13.png" /></figure>

### 1.1.31. Дано натуральное число $n > 1$. Определите длину периода десятичной записи дроби $1/n$.

**Решение.** Период дроби равен периоду в последовательности остатков (докажите это; в частности, надо доказать, что он не может быть меньше). Кроме того, в этой последовательности все периодически повторяющиеся члены различны, а предпериод имеет длину не более $n$. Поэтому достаточно найти $(n+1)$-й член последовательности остатков и затем минимальное $k$, при котором $(n+1+k)$-й член совпадает с $(n+1)$-м.

```pascal
l := 0; r := 1;
{инвариант: r/n = результат отбрасывания 1 знаков в 1/n}
while l <> n+1 do begin
  r := (10 * r) mod n;
  l := l + 1;
end;
c := r;
```
```
{c = (n+1)-ый член последовательности остатков}
r := (10 * r) mod n;
k := 1;
{r = (n+k+1)-ый член последовательности остатков}
while r <> c do begin
  r := (10 * r) mod n;
  k := k + 1;
end;
```

<figure><img src="image_14.png" /></figure>

**1.1.32.** (Сообщил Ю. В. Матиясевич) Дана функция `f : {1...N} → → {1...N}`. Найдите период последовательности `1`, `f(1)`, `f(f(1))`, ... Количество действий должно быть пропорционально суммарной длине предпериода и периода (эта сумма может быть существенно меньше N).

**Решение.** Если отбросить начальный кусок, последовательность периодична, причём все члены периода различны.

```
{Обозначение: f[n,1]=f(f(...f(1)...)) (n раз)}
k:=1; a:=f(1); b:=f(f(1));
{a=f[k,1]; b=f[2k,1]}
while a <> b do begin
  k:=k+1; a:=f(a); b:=f(f(b));
end;
{a=f[k,1]=f[2k,1]; f[k,1] входит в периодическую часть}
l:=1; b:=f(a);
{b=f[k+1,1]; f[k,1],...,f[k+1-1,1] различны}
while a <> b do begin
  l:=l+1; b:=f(b);
end;
{период равен 1}
```

<figure><img src="image_15.png" /></figure>

**1.1.33.** (Э. Дейкстра) Функция `f` с натуральными аргументами и значениями определена так: `f(0) = 0`, `f(1) = 1`, `f(2n) = f(n)`, `f(2n + 1) = f(n) + f(n + 1)`. Составьте программу вычисления `f(n)` по заданному `n`, требующую порядка `log n` операций.

**Решение.**

```
k := n; a := 1; b := 0;
{инвариант: 0 <= k, f(n) = a * f(k) + b * f(k+1)}
while k <> 0 do begin
  if k mod 2 = 0 then begin
    l := k div 2;
  end
```
```pascal
{k=21, f(k)=f(1), f(k+1) = f(21+1) = f(1) + f(1+1),
   f(n) = a*f(k) + b*f(k+1) = (a+b)*f(1) + b*f(1+1)}
a := a + b; k := 1;
end else begin
   l := k div 2;
   {k = 2l + 1, f(k) = f(1) + f(1+1),
    f(k+1) = f(2l+2) = f(1+1),
    f(n) = a*f(k) + b*f(k+1) = a*f(1) + (a+b)*f(1+1)}
   b := a + b; k := 1;
end;
end;
{k = 0, f(n) = a * f(0) + b * f(1) = b, что и требовалось} ☐
```

**1.1.34.** То же, если $f(0) = 13$, $f(1) = 17$, $f(2) = 20$, $f(3) = 30$, $f(2n) = 43f(n) + 57f(n+1)$, $f(2n+1) = 91f(n) + 179f(n+1)$ при $n \ge 2$.

[Указание. Храните коэффициенты в выражении $f(n)$ через три со- седних числа.] ☐

**1.1.35.** Даны натуральные числа a и b, причём $b > 0$. Найдите част- ное и остаток при делении a на b, оперируя лишь с целыми числами и не используя операции div и mod, за исключением деления на 2 чёт- ных чисел; число шагов не должно превосходить $C_1 \log(a/b) + C_2$ для некоторых констант $C_1, C_2$.

Решение.

```pascal
b1 := b;
while b1 <= a do begin
  b1 := b1 * 2;
end;
{b1 > a, b1 = b * (некоторая степень 2)}
q:=0; r:=a;
{инвариант: q, r - частное и остаток при делении a на b1,
   b1 = b * (некоторая степень 2)}
while b1 <> b do begin
  b1 := b1 div 2; q := q * 2;
  { a = b1 * q + r, 0 <= r, r < 2 * b1}
  if r >= b1 then begin
    r := r - b1;
    q := q + 1;
  end;
end;
{q, r - частное и остаток при делении a на b}
```
## 1.2. Массивы

В следующих задачах переменные х, у, z предполагаются описанными как `array[1..n] of integer` (где n — некоторое натуральное число, большее 0), если иное не оговорено явно.

**1.2.1.** Заполните массив х нулями. (Это означает, что нужно составить фрагмент программы, после выполнения которого все значения `x[1]..x[n]` равнялись бы нулю, независимо от начального значения переменной х.)

**Решение.**

```pascal
i := 0;
{инвариант: первые i значений x[1]..x[i] равны 0}
while i <> n do begin
  i := i + 1;
  {x[1]..x[i-1] = 0}
  x[i] := 0;
end;
```

**1.2.2.** Подсчитайте количество нулей в массиве х. (Составьте фрагмент программы, не меняющий значения х, после исполнения которого значение некоторой целой переменной k равнялось бы числу нулей среди компонент массива х.)

**Решение.**

```pascal
...
{инвариант: k = число нулей среди x[1]..x[i] }
...
```

**1.2.3.** Не используя оператора присваивания для массивов, составьте фрагмент программы, эквивалентный оператору `x:=y`.

**Решение.**

```pascal
i := 0;
{инвариант: значение y не изменилось, x[1]=y[1] при 1<=i}
while i <> n do begin
  i := i + 1;
  x[i] := y[i];
end;
```

**1.2.4.** Найдите максимум из `x[1]..x[n]`.
## Решение.

```c
i := 1; max := x[1];
{инвариант: max = максимум из x[1]..x[i]}
while i <> n do begin
    i := i + 1;
    {max = максимум из x[1]..x[i-1]}
    if x[i] > max then begin
        max := x[i];
    end;
end;
```

<figure><img src="image_16.png" /></figure>

### 1.2.5. Дан массив x: array[1..n] of integer, причём известно, что $x[1] \le x[2] \le \dots \le x[n]$. Найдите количество различных чисел среди элементов этого массива.

## Решение. Вариант 1.

```c
i := 1; k := 1;
{инвариант: k - количество различных среди x[1]..x[i]}
while i <> n do begin
    i := i + 1;
    if x[i] <> x[i-1] then begin
        k := k + 1;
    end;
end;
```

## Вариант 2. Искомое число на 1 больше количества тех чисел i из 1..n-1, для которых x[i] не равно x[i+1].

```c
k := 1;
for i := 1 to n-1 do begin
    if x[i] <> x[i+1] then begin
        k := k + 1;
    end;
end;
```

<figure><img src="image_17.png" /></figure>

### 1.2.6. Дан массив x: array[1..n] of integer. Найдите количество различных чисел среди элементов этого массива. (Число действий должно быть порядка $n^2$.)

### 1.2.7. Та же задача, если требуется, чтобы количество действий было порядка $n \log n$.

[Указание. См. главу 4 (Сортировка).]

<figure><img src="image_18.png" /></figure>
1.2.8. Та же задача, если известно, что все элементы массива — числа от 1 до k и число действий должно быть порядка $n+k$. ☐

1.2.9. (Сообщил А.Л. Брудно) Прямоугольное поле $m \times n$ разбито на mn квадратных клеток. Некоторые клетки покрашены в чёрный цвет. Известно, что все чёрные клетки могут быть разбиты на несколько непересекающихся и не имеющих общих вершин чёрных прямоугольников. Считая, что цвета клеток даны в виде массива типа

```
array [1..m] of array [1..n] of boolean;
```

подсчитайте число чёрных прямоугольников, о которых шла речь. Число действий должно быть порядка mn.

**Решение.** Число прямоугольников равно числу их левых верхних углов. Является ли клетка верхним углом, можно узнать, посмотрев на её цвет, а также цвет верхнего и левого соседей. (Не забудьте, что их может не быть, если клетка с краю.) ☐

1.2.10. Дан массив `x[1]..x[n]` целых чисел. Не используя других массивов, переставьте элементы массива в обратном порядке.

**Решение.** Элементы `x[i]` и `x[n+1-i]` нужно поменять местами для всех `i`, для которых `i < n + 1 - i`, то есть `2i < n + 1` ⇔ `2i ≤ n` ⇔ `i ≤ n` div 2:

```
for i := 1 to n div 2 do begin
  ...поменять местами x[i] и x[n+1-i];
end;
```

1.2.11. (Из книги Д. Гриса) Дан массив целых чисел `x[1]..x[m+n]`, рассматриваемый как соединение двух его отрезков: начала `x[1]..x[m]` длины `m` и конца `x[m+1]..x[m+n]` длины `n`. Не используя дополнительных массивов, переставьте начало и конец. (Число действий порядка `m+n`.)

**Решение.** Вариант 1. Перевернём (расположим в обратном порядке) отдельно начало и конец массива, а затем перевернём весь массив как единое целое.

Вариант 2. (А. Г. Кушниренко) Рассматривая массив записанным по кругу, видим, что требуемое действие — поворот круга. Как известно, поворот есть композиция двух осевых симметрий.

Вариант 3. Рассмотрим более общую задачу — обмен двух участков массива `x[p+1]..x[q]` и `x[q+1]..x[r]`. Предположим, что длина левого участка (назовём его А) не больше длины правого (назовём
его В). Выделим в В начало той же длины, что и А, назовём его $B_1$, а остаток $B_2$. (Так что $B = B_1 + B_2$, если обозначать плюсом приписывание массивов друг к другу.) Нам надо из $A + B_1 + B_2$ получить $B_1 + B_2 + A$. Меняя местами участки А и $B_1$ — они имеют одинаковую длину, и сделать это легко, — получаем $B_1 + A + B_2$, и осталось поменять местами А и $B_2$. Тем самым мы свели дело к перестановке двух отрезков меньшей длины. Итак, получаем такую схему программы:

```p
p := 0; q := m; r := m + n;
{инвариант: осталось переставить x[p+1..q], x[q+1..r]}
while (p <> q) and (q <> r) do begin
    {оба участка непусты}
    if (q - p) <= (r - q) then begin
        ..переставить x[p+1]..x[q] и x[q+1]..x[q+(q-p)]
        pnew := q; qnew := q + (q - p);
        p := pnew; q := qnew;
    end else begin
        ..переставить x[q-(r-q)+1]..x[q] и x[q+1]..x[r]
        qnew := q - (r - q); rnew := q;
        q := qnew; r := rnew;
    end;
end;
```

Оценка времени работы: на очередном шаге оставшийся для обработки участок становится короче на длину А; число действий при этом также пропорционально длине А. ☐

### 1.2.12. Коэффициенты многочлена лежат в массиве a: `array[0..n] of integer (n — натуральное число, степень многочлена)`. Вычислите значение этого многочлена в точке x, то есть $a[n]x^n + ... + a[1]x + a[0]$.

**Решение.** (Описываемый алгоритм называется схемой Горнера.)

```p
k := 0; y := a[n];
{инвариант: 0 <= k <= n,
           y = a[n]*(x в степени k)+...+a[n-1]*(x в степени k-1)+...
                      + a[n-k]*(x в степени 0)}
while k<>n do begin
    k := k + 1;
    y := y * x + a[n-k];
end;
```

### 1.2.13. (Для знакомых с основами анализа; сообщил А.Г. Кушниренко) Дополните алгоритм вычисления значения многочлена в задан-
ной точке по схеме Горнера вычислением значения его производной в той же точке.

**Решение.** Добавление нового коэффициента соответствует переходу от многочлена $P(x)$ к многочлену $xP(x) + c$. Его производная в точке $x$ равна $xP'(x) + P(x)$. (Это решение обладает забавным свойством: не надо знать заранее степень многочлена. Если требовать выполнения этого условия, да ещё просить вычислять только значение производной, не упоминая о самом многочлене, получается не такая уж простая задача.) ☐

Общее утверждение о сложности вычисления производных таково:

1.2.14. (В. Баур, Ф. Штрассен) Дана программа вычисления значения некоторого многочлена $P(x_1, \dots, x_n)$, содержащая только команды присваивания. Их правые части — выражения, содержащие сложение, умножение, константы, переменные $x_1, \dots, x_n$ и ранее встречавшиеся (в левой части) переменные. Докажите, что существует программа того же типа, вычисляющая все $n$ производных $\partial P/\partial x_1, \dots, \partial P/\partial x_n$, причём общее число арифметических операций не более чем в $C$ раз превосходит число арифметических операций в исходной программе. Константа $C$ не зависит от $n$.

[Указание. Можно считать, что каждая команда — сложение двух чисел, умножение двух чисел или умножение на константу. Используйте индукцию по числу команд, применяя индуктивное предположение к программе, получающейся отбрасыванием первой команды.] ☐

1.2.15. В массивах $a: array[0..k] of integer$ и $b: array[0..1] of integer$ хранятся коэффициенты двух многочленов степеней $k$ и $1$. Полместите в массив $c: array[0..m] of integer$ коэффициенты их произведения. (Числа $k, 1, m$ — натуральные, $m = k + 1$; элемент массива $c$ индексом $i$ содержит коэффициент при степени $i$.)

**Решение.**

```
for i:=0 to m do begin
  c[i]:=0;
end;

for i:=0 to k do begin
  for j:=0 to l do begin
    c[i+j] := c[i+j] + a[i]*b[j];
  end;
end;
```

<figure><img src="image_19.png" /></figure>
**1.2.16.** Предложенный выше алгоритм перемножения многочленов требует порядка $n^2$ действий для перемножения двух многочленов степени $n$. Придумайте более эффективный (для больших $n$) алгоритм, которому достаточно порядка $n^{\log 4 / \log 3}$ действий.

[Указание. Представим себе, что надо перемножить два многочлена степени 2k. Их можно представить в виде

$$A(x) x^k + B(x) \text{ и } C(x) x^k + D(x).$$

Произведение их равно

$$A(x)C(x) x^{2k} + (A(x)D(x) + B(x)C(x)) x^k + B(x)D(x).$$

Естественный способ вычисления $AC, AD + BC, BD$ требует четырёх умножений многочленов степени $k$, однако их количество можно сократить до трёх с помощью такой хитрости: вычислить $AC, BD$ и $(A+B)(C+D)$, а затем заметить, что $AD + BC = (A+B)(C+D) - AC - BD$. $\square$

**1.2.17.** Даны два возрастающих массива $x: array[1..k]$ of integer и $y: array[1..1]$ of integer. Найдите количество общих элементов в этих массивах, то есть количество тех целых $t$, для которых $t = x[i] = y[j]$ для некоторых $i$ и $j$. (Число действий порядка $k+1$.)

Решение.

```
k1:=0; l1:=0; n:=0;
{инвариант: 0<=k1<=k; 0<=l1<=l;
               искомый ответ = n + количество общих
               элементов в x[k1+1]..x[k] и y[l1+1]..y[l]}
while (k1 <> k) and (l1 <> l) do begin
  if x[k1+1] < y[l1+1] then begin
    k1 := k1 + 1;
  end else if x[k1+1] > y[l1+1] then begin
    l1 := l1 + 1;
  end else begin {x[k1+1] = y[l1+1]}
    k1 := k1 + 1;
    l1 := l1 + 1;
    n := n + 1;
  end;
end;
{k1 = k или l1 = l, поэтому одно из множеств, упомянутых
в инварианте, пусто, а n равно искомому ответу} $\square$
```
**Замечание.** В третьей альтернативе достаточно было бы увеличивать одну из переменных k1, 11; вторая добавлена для симметрии.

**1.2.18.** Решите предыдущую задачу, если про массивы известно лишь, что $x[1] \le ... \le x[k]$ и $y[1] \le ... \le y[1]$ (возрастание заменено неубыванием).

**Решение.** Слово возрастания было использовано в третьей альтернативе выбора: сдвинув k1 и 11 на 1, мы тем самым уменьшали на 1 количество общих элементов в $x[k+1]...x[k]$ и $x[11+1]...x[1]$. Теперь это придётся делать сложнее.

```pascal
... 
end else begin {x[k+1] = y[11+1]}
  t := x[k+1];
  while (k1<k) and (x[k+1]=t) do begin
    k1 := k1 + 1;
  end;
  while (11<l1) and (x[11+1]=t) do begin
    l1 := l1 + 1;
  end;
  n := n + 1;
end;
```

<figure><img src="image_20.png" /></figure>

**Замечание.** Эта программа имеет дефект: при проверке условия

$(k1<k) and (x[k+1]=t)$

(или второго, аналогичного) при ложной первой скобке вторая окажется бессмысленной (индекс выйдет за границы массива) и возникнет ошибка. Некоторые версии паскаля, вычисляя А and В, сначала вычисляют А и при ложном А не вычисляют В. (Так ведёт себя, например, система Turbo Pascal версии 5.0 — но не 3.0.) Тогда описанная ошибка не возникнет.

Но если мы не хотим полагаться на такое свойство используемой нами реализации паскаля (не предусмотренное его автором Н. Виртом), то можно поступить так. Введём дополнительную переменную b: boolean и напишем:

```pascal
if k1 < k then b := (x[k1+1]=t) else b:=false;
{b = (k1<k) and (x[k1+1] = t)}
while b do begin
  k1:=k1+1;
  if k1 < k then b := (x[k1+1]=t) else b:=false;
end;
```
Можно также сделать иначе:

```pascal
end else begin {x[k1+1] = y[11+1]}
    if k1 + 1 = k then begin
        k1 := k1 + 1;
        n := n + 1;
    end else if x[k1+1] = x[k1+2] then begin
        k1 := k1 + 1;
    end else begin
        k1 := k1 + 1;
        n := n + 1;
    end;
end;
```

Так будет короче, хотя менее симметрично.

Наконец, можно увеличить размер массива в его описании, включив в него фиктивные элементы.

1.2.19. Даны два неубывающих массива х: array[1..k] of integer и у: array[1..l] of integer. Найдите число различных элементов среди х[1],..., х[k], у[1],..., у[1]. (Число действий порядка k + 1.) ☐

1.2.20. Даны два массива х[1] ≤ ... ≤ х[k] и у[1] ≤ ... ≤ у[1]. «Соедините» их в массив z[1] ≤ ... ≤ z[m] (m = k + 1; каждый элемент должен входить в массив z столько раз, сколько раз он входит в общей сложности в массивы х и у). Число действий порядка m.

Решение.

```pascal
k1 := 0; l1 := 0;
{инвариант: ответ получится, если k z[1]..z[k1+1] добавить
  справа соединение массивов х[k1+1]..х[k] и у[l1+1]..у[l1]}
while (k1 <> k) or (l1 <> 1) do begin
    if k1 = k then begin
        {l1 < 1}
        l1 := l1 + 1;
        z[k1+1] := y[l1];
    end else if l1 = 1 then begin
        {k1 < k}
        k1 := k1 + 1;
        z[k1+1] := x[k1];
    end else if x[k1+1] <= y[l1+1] then begin
        k1 := k1 + 1;
        z[k1+1] := x[k1];
    end else if x[k1+1] >= y[l1+1] then begin
```
```pascal
l1 := l1 + 1;
z[k1+l1] := y[l1];
end else begin
    { такого не бывает }
end;
end;
{k1 = k, l1 = l, массивы соединены}
```

Этот процесс можно пояснить так. Пусть у нас есть две стопки карточек, отсортированных по алфавиту. Мы соединяем их в одну стопку, выбирая каждый раз ту из верхних карточек обеих стопок, которая идёт раньше в алфавитном порядке. Если в одной стопке карточки кончились, берём их из другой стопки.

1.2.21. Даны два массива `x[1]` `≤...≤x[k]` и `y[1]` `≤...≤y[1]`. Найдите их «пересечение», то есть массив `z[1]` `≤...≤z[m]`, содержащий их общие элементы, причём кратность каждого элемента в массиве `z` равняется минимуму из его кратностей в массивах `x` и `y`. Число действий порядка `k+1`.

1.2.22. Даны два массива `x[1]` `≤...≤x[k]` и `y[1]` `≤...≤y[1]` и число `q`. Найдите сумму вида `x[i] + y[j]`, наиболее близкую к числу `q`. (Число действий порядка `k+1`, дополнительная память — фиксированное число целых переменных, сами массивы менять не разрешается.)

[Указание. Надо найти минимальное расстояние между элементами `x[1] ≤...≤x[k]` и `q - y[1] ≤...≤q - y[1]`, что нетрудно сделать в ходе их слияния в один (воображаемый) массив.]

1.2.23. (Из книги Д. Гриса) Некоторое число содержится в каждом из трёх целочисленных неубывающих массивов `x[1] ≤...≤x[p]`, `y[1] ≤...≤y[q]`, `z[1] ≤...≤z[r]`. Найдите одно из таких чисел. Число действий должно быть порядка `p+q+r`.

Решение.

```pascal
p1:=1; q1:=1; r1:=1;
{инвариант: x[p1..x[p], y[q1..y[q], z[r1..z[r]
содержат общий элемент}
while not ((x[p1]=y[q1]) and (y[q1]=z[r1])) do begin
    if x[p1]<y[q1] then begin
        p1:=p1+1;
    end else if y[q1]<z[r1] then begin
        q1:=q1+1;
    end else if z[r1]<x[p1] then begin
```
```pascal
r1:=r1+1;
end else begin
    { так не бывает }
end;
end;
{x[p1] = y[q1] = z[r1]}
writeln (x[p1]);
```

### 1.2.24. Та же задача, только заранее не известно, существует ли общий элемент в трёх неубывающих массивах и требуется это выяснить (и найти один из общих элементов, если они есть). ☐

### 1.2.25. Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел:

```pascal
a: array [1..n] of array [1..m] of integer;
a[1][1] ≤ ... ≤ a[1][m], ..., a[n][1] ≤ ... ≤ a[n][m].
```

Известно, что существует число, входящее во все массивы a[i] (существует такое x, что для всякого i из 1..n найдётся j из 1..m, для которого a[i][j] = x). Найдите одно из таких чисел x.

Решение. Введём массив b[1]...b[n], отмечающий начало «остающейся части» массивов a[1], ..., a[n].

```pascal
for k:=1 to n do begin
  b[k]:=1;
end;
eq := true;
for k := 2 to n do begin
  eq := eq and (a[1][b[1]] = a[k][b[k]]);
end;
{инвариант: оставшиеся части пересекаются, т.е. существует такое x, что для всякого i из [1..n] найдётся j из [1..m], не меньше b[i], для которого a[i][j] = x; eq <=> первые элементы оставшихся частей равны}
while not eq do begin
  s := 1; k := 1;
  {a[s][b[s]] - минимальное среди a[1][b[1]]..a[k][b[k]]}
  while k <> n do begin
    k := k + 1;
    if a[k][b[k]] < a[s][b[s]] then begin
      s := k;
    end;
```
```pascal
end;
{a[s][b[s]] - минимальное среди a[1][b[1]]..a[n][b[n]]}
b[s] := b[s] + 1;
for k := 2 to n do begin
  eq := eq and (a[1][b[1]] = a[k][b[k]]);
end;
end;
writeln (a[1][b[1]]);
```

### 1.2.26. Приведённое решение предыдущей задачи требует порядка $mn^2$ действий. Придумайте способ с числом действий порядка $mn$.

[Указание. Придётся пожертвовать симметрией и выбрать одну из строк за основную. Двигаясь по основной строке, поддерживаем такое соотношение: во всех остальных строках отмечен максимальный элемент, не превосходящий текущего элемента основной строки.] ☐

### 1.2.27. (Двоичный поиск)
Дана последовательность $x[1] \le \dots \le x[n]$ целых чисел и число $a$. Выясните, содержится ли $a$ в этой последовательности, то есть существует ли $i$ из $1..n$, для которого $x[i] = a$. (Количество действий порядка $\log n$.)

**Решение.** (Предполагаем, что $n > 0$.)

```pascal
l := 1; r := n+1;
{r > l, если а есть вообще, то есть и среди x[1]..x[r-1]}
while r - l <> 1 do begin
  m := l + (r-l) div 2;
  {l < m < r}
  if x[m] <= a then begin
    l := m;
    end else begin {x[m] > a}
      r := m;
    end;
end;
```

(Обратите внимание, что и в случае $x[m] = a$ инвариант не нарушается.)

Каждый раз $r-1$ уменьшается примерно вдвое, откуда и вытекает требуемая оценка числа действий. ☐

**Замечание.**

$$1 + (r-1) \text{ div } 2 = (21 + (r-1)) \text{ div } 2 = (r+1) \text{ div } 2.$$
В этой задаче существенно, что массив упорядочен — поиск в неупорядоченном массиве требует времени, пропорционального длине массива. (Чтобы убедиться, что какого-то числа нет в массиве, надо просмотреть все его элементы.)

**1.2.28.** (Из книги Д.Гриса) Имеется массив `x: array[1..n] of array[1..m] of integer`, упорядоченный по строкам и по столбцам:

$$ 
\begin{aligned}
x[i][j] &\le x[i][j+1], \\
x[i][j] &\le x[i+1][j],
\end{aligned}
 $$

и число `a`. Требуется выяснить, встречается ли `a` среди `x[i][j]`.

**Решение.** Представляя себе массив `x` как матрицу (прямоугольник, заполненный числами), мы выберем прямоугольник, в котором только и может содержаться `a`, и будем его сужать. Прямоугольник этот будет содержать `x[i][j]` при $1 \le i \le l$ и $k \le j \le m$

<figure><img src="image_21.png" /></figure>

(допускаются пустые прямоугольники при $1=0$ и $k=m+1$).

```pascal
l:=n; k:=1;
{1>=0, k<=m+1, если а есть, то в описанном прямоугольнике}
while (1 > 0) and (k < m+1) and (x[1][k] <> a) do begin
  if x[1][k] < a then begin
    k := k + 1; {левый столбец не содержит a, удаляем его}
    end else begin {x[1][k] > a}
      l := l - 1; {нижняя строка не содержит a, удаляем её}
    end;
  end;
  {x[1][k] = a или прямоугольник пуст}
answer:= (1 > 0) and (k < m+1) ;
```

**Замечание.** Здесь же ошибка: `x[1][k]` может оказаться неопределинным. (Её исправление предоставляется читателю.) □
**1.2.29.** (Московская олимпиада по программированию) Дан неубывающий массив положительных целых чисел $a[1] \le a[2] \le \dots \le a[n]$. Найдите наименьшее целое положительное число, не представимое в виде суммы нескольких элементов этого массива (каждый элемент массива может быть использован не более одного раза). Число действий порядка $n$.

**Решение.** Пусть известно, что числа, представимые в виде суммы элементов $a[1]...a[k]$, заполняют отрезок от 1 до некоторого $N$. Если $a[k+1] > N+1$, то $N+1$ и будет минимальным числом, не представимым в виде суммы элементов массива $a[1]...a[n]$. Если же $a[k+1] \le N+1$, то числа, представимые в виде суммы элементов $a[1]...a[k+1]$, заполняют отрезок от 1 до $N+a[k+1]$.

```
k := 0; N := 0;
{инвариант: числа, представимые в виде суммы элементов
  массива a[1]..a[k], заполняют отрезок 1..N}
while (k <> n) and (a[k+1] <= N+1) do begin
  N := N + a[k+1];
  k := k + 1;
end;
{(k = n) или (a[k+1] > N+1); в обоих случаях ответ N+1}
writeln (N+1);
```

(Снова тот же дефект: в условии цикла при ложном первом условии второе не определено.) ☐

**1.2.30.** (Для знакомых с основами алгебры) В целочисленном массиве $a[1]...a[n]$ хранится перестановка чисел $1...n$ (каждое из чисел встречается по одному разу).

(а) Определите чётность перестановки. (И в (а), и в (б) количество действий порядка $n$.)

(б) Не используя других массивов, замените перестановку на обратную (если до работы программы $a[i] = j$, то после должно быть $a[j] = i$).

**[Указание.]** (а) Чётность перестановки определяется количеством клов. Чтобы отличать уже пройденные циклы, у их элементов можно, например, менять знак. (б) Обращение производим по циклам.) ☐

**1.2.31.** Дан массив $a[1..n]$ и число $b$. Переставьте числа в массиве таким образом, чтобы слева от некоторой границы стояли числа, меньшие или равные $b$, а справа от границы — большие или равные $b$. Число действий порядка $n$.
## Решение.

```python
l:=0; r:=n;
{инвариант: a[1]..a[1]<=b; a[r+1]..a[n]>=b}
while l <> r do begin
    if a[1+l] <= b then begin
        l:=l+1;
    end else if a[r] >=b then begin
        r:=r-1;
    end else begin {a[1+l]>b; a[r]<b}
        ..поменять a[1+l] и a[r]
    l:=l+1; r:=r-1;
end;
end;
```

<figure><img src="image_22.png" /></figure>

### 1.2.32. Та же задача, но требуется, чтобы сначала шли элементы, меньшие b, затем равные b, а лишь затем большие b.

## Решение. 
Теперь потребуются три границы: до первой будут идти элементы, меньшие b, от первой до второй — равные b, затем неизвестно какие до третьей, а после третьей — большие b. (Более символичное решение использовало бы четыре границы, но вряд ли игра стоит свеч.) В качестве очередного рассматриваемого элемента берём элемент справа от средней границы.

```python
l:=0; m:=0; r:=n;
{инвариант: a[1..1]<b; a[1+1..m]=b; a[r+1]..a[n]>b}
while m <> r do begin
    if a[m+1]=b then begin
        m:=m+1;
    end else if a[m+1]>b then begin
        ..обменять a[m+1] и a[r]
    r:=r-1;
    end else begin {a[m+1]<b}
        ..обменять a[m+1] и a[1+l]
    l:=l+1; m:=m+1;
end;
end;
```

<figure><img src="image_23.png" /></figure>

### 1.2.33. (Вариант предыдущей задачи, названный в книге Дейкстры задачей о голландском флаге.) В массиве длины n стоят числа 0, 1 и 2. Переставьте их в порядке возрастания, если единственной разрешённой операцией (помимо чтения) над массивом является перестановка двух элементов. Число действий порядка n. ☐
**1.2.34.** Дан массив `a[1..n]` и число `m ≤ n`. Для каждого участка из `m` стоящих рядом членов (таких участков, очевидно, `n - m + 1`) вычислите его сумму. Общее число действий должно быть порядка `n`.

**Решение.** Переходя от участка к соседнему, мы добавляем один член, а другой вычитаем. ☐

В этом решении ключевую роль играет возможность вычитания — скажем, если бы надо было вычислять не сумму, а максимум, то так действовать было нельзя. Тем не менее это тоже возможно, как показывает следующая задача (сообщил А. Г. Коган):

**1.2.35.** Дан массив `a[1..n]` и число `m ≤ n`. Для каждого участка из `m` стоящих рядом членов (таких участков, очевидно, `n - m + 1`) вычислите максимум значений на этом участке. Общее число действий должно быть порядка `n`.

**Решение.** Разобьём массив на блоки по `m` элементов, и для каждого элемента вычислим максимум элементов, стоящих в том же блоке слева от него, а также максимум элементов, стоящих в том же блоке справа от него (включая сам этот элемент). Это можно сделать, пройдя по каждому блоку слева направо, а также справа налево. Осталось замetить, что каждый участок длины `m` либо совпадает с одним из блоков, либо разбивается границей блока на две части, для каждой из которых максимум мы уже вычислили. ☐

Такой способ годится для любой ассоциативной операции (а не только для максимума).

**1.2.36.** Дана квадратная таблица `a[1..n][1..n]` и число `m ≤ n`. Для каждого квадрата `m × n` в этой таблице вычислите сумму стоящих в нём чисел. Общее число действий порядка `n²`.

**Решение.** Сначала для каждого горизонтального прямоугольника размером `m × 1` вычисляем сумму стоящих в нём чисел. (При сдвиге такого прямоугольника по горизонтали на 1 нужно добавить одно число и одно вычество.) Затем, используя эти суммы, вычисляем суммы в квадратах. (При сдвиге квадрата по вертикали добавляется полоска, а другая полоска убавляется.) ☐

**1.2.37.** Как решить предыдущую задачу, если сумма по квадрату заменена на максимум?

[Указание. Сравните задачи 1.2.34 и 1.2.35.]

<figure><img src="image_24.png" /></figure>
1.2.38. В массиве a[1]...a[n] встречаются по одному разу все це-
лые числа от 0 до n, кроме одного. Найдите пропущенное число за время
порядка n и с конечной дополнительной памятью.

[Указание. Сложите все числа в массиве.]

<figure><img src="image_25.png" /></figure>

1.3. Индуктивные функции (по А. Г. Кушниренко)

Пусть М — некоторое множество. Функция f, аргументами которой
являются последовательности элементов множества М, а значениями —
элементы некоторого множества N, называется индуктивной, если её
значение на последовательности х[1]...х[n] можно восстановить по
её значению на последовательности х[1]...х[n-1] и по х[n], то есть
если существует функция F: N × M → N, для которой

$$
f(\langle x[1], \dots, x[n] \rangle) = F(f(\langle x[1], \dots, x[n-1] \rangle), x[n]).
$$

Напимер, функция sum (сумма всех членов последовательности) ин-
дуктивна, поскольку очередной член последовательности прибавляется
к её сумме:

$$
\operatorname{sum}(\langle x[1], \dots, x[n] \rangle) = \operatorname{sum}(\langle x[1], \dots, x[n-1] \rangle) + x[n].
$$

Другой пример индуктивной функции — длина последовательности.
В этом случае F(n, m) = n + 1.

Напротив, среднее арифметическое не является индуктивной функцией: если мы знаем среднее арифметическое некоторой последовательности, но не знаем её длины, то не можем предсказать, каким станет среднее арифметическое после дописывания некоторого (известного нам) числа.

Схема алгоритма вычисления индуктивной функции:

```pascal
k := 0; f := f0;
{инвариант: f — значение функции на <x[1],...,x[k]>}
while k<n do begin
  k := k + 1;
  f := F(f, x[k]);
end;
```

Здесь f0 — значение функции на пустой последовательности (по-
следовательности длины 0). Если функция f определена только на не-
пустых последовательностях, то первая строка заменяется на

k:=1; f:=f(<x[1]>);

Если функция f не является индуктивной, полезно искать её индуктивное расширение — такую индуктивную функцию g, значения которой определяют значения f (это значит, что существует такая функция t, что

$$f(\langle x[1] \dots x[n] \rangle) = t(g(\langle x[1] \dots x[n] \rangle))$$

при всех $\langle x[1] \dots x[n] \rangle$). Можно доказать, что среди всех индуктивных расширений существует минимальное расширение F (минимальность означает, что для любого индуктивного расширения g значения F определяются значениями g).

**1.3.1.** Укажите индуктивные расширения для следующих функций:

(а) среднее арифметическое последовательности чисел;

(б) число элементов последовательности целых чисел, равных её максимальному элементу;

(в) второй по величине элемент последовательности целых чисел (тот, который будет вторым, если переставить члены в неубывающем порядке);

(г) максимальное число идущих подряд одинаковых элементов;

(д) максимальная длина монотонного (неубывающего или невозрастающего) участка из идущих подряд элементов в последовательности целых чисел;

(е) число групп из единиц, разделённых нулями (в последовательности нулей и единиц).

### Решение.

(а) $\langle$сумма всех членов последовательности; длина$\rangle$;

(б) $\langle$число элементов, равных максимальному; значение максимального$\rangle$;

(в) $\langle$наибольший элемент последовательности; второй по величине элемент$\rangle$;

(г) $\langle$максимальное число идущих подряд одинаковых элементов; число идущих подряд одинаковых элементов в конце последовательности; последний элемент последовательности$\rangle$;

(д) $\langle$максимальная длина монотонного участка; максимальная длина неубывающего участка в конце последовательности; максимальная длина невозрастающего участка в конце последовательности; последний член последовательности$\rangle$;

(е) $\langle$число групп из единиц, последний член$\rangle$. □

<figure><img src="image_26.png" /></figure>
### 1.3.2. (Сообщил Д. В. Варсанофьев)
Даны две последовательности целых чисел х[1]...х[n] и у[1]...у[k]. Выясните, является ли вторая последовательность подпоследовательностью первой, то есть можно ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. Число действий порядка n + k.

**Решение.** Вариант 1. Будем сводить задачу к задаче меньшего размера.

```pascal
n1:=n;
k1:=k;
{инвариант: искомый ответ <=> возможность из х[1]..х[n1]
получить y[1]..y[k1] }
while (n1 > 0) and (k1 > 0) do begin
    if x[n1] = y[k1] then begin
        n1 := n1 - 1;
        k1 := k1 - 1;
    end else begin
        n1 := n1 - 1;
    end;
end;
{n1 = 0 или k1 = 0; если k1 = 0, то ответ - да, если k1<>0
(и n1 = 0), то ответ - нет}
answer := (k1 = 0);
```

Мы использовали то, что если х[n1] = у[k1] и у[1]...у[k1] — подпоследовательность х[1]...х[n1], то у[1]...у[k1-1] — подпоследовательность х[1]...х[n1-1].

Вариант 2. Функция ⟨x[1]...x[n1]⟩ ↦ [максимальное k1, для которого у[1]...у[k1] есть подпоследовательность х[1]...х[n1]] индуктивна. □

### 1.3.3. (сообщено М. Н. Вайнцвайгом, А. М. Диментманом)
Даны две последовательности х[1]...х[n] и у[1]...у[k] целых чисел. Найдите максимальную длину последовательности, являющейся подпоследовательностью обеих последовательностей. Количество операций порядка n · k.

**Решение** (сообщено М. Н. Вайнцвайгом, А. М. Диментманом). Обозначим через f(p, q) максимальную длину общей подпоследовательности последовательностей х[1]...х[p] и у[1]...у[q]. Тогда

x[p] ≠ y[q] ⇒ f(p, q) = max(f(p, q-1), f(p-1, q));
x[p] = y[q] ⇒ f(p, q) = max(f(p, q-1), f(p-1, q), f(p-1, q-1)+1).
(Поскольку $f(p-1,q-1)+1 \ge f(p,q-1), f(p-1,q)$, во втором слу-
чае максимум трёх чисел можно заменить на третье из них.) Поэтому
можно заполнять таблицу значений функции $f$, имеющую размер $n \cdot k$.
Можно обойтись и памятью порядка $k$ (или $n$), если индуктивно (по р)
вычислять $\langle f(p,0), \dots, f(p,k) \rangle$ (как функция от р этот набор индук-
тивен). $\square$

1.3.4. (Из книги Д.Гриса) Дана последовательность целых чисел $x[1], \dots, x[n]$. Найдите максимальную длину её возрастающей подпоследовательности (число действий порядка $n \log n$).

Решение. Искомая функция не индуктивна, но имеет следующее индуктивное расширение: в него входят помимо максимальной длины возрастающей подпоследовательности (обозначим её $k$) также и числа $u[1], \dots, u[k]$, где $u[i]$ — минимальный из последних членов возрастающих подпоследовательностей длины $i$. Очевидно, $u[1] \le \dots \le u[k]$. При добавлении нового члена в $x$ значения $u$ и $k$ корректируются.

n1 := 1; k := 1; u[1] := x[1];
{инвариант: k и u соответствуют данному выше описанию}
while n1 <> n do begin
  n1 := n1 + 1;
  ...
  {i - наибольшее из тех чисел отрезка 1..k, для
   которых u[i] < x[n1]; если таких нет, то i=0 }
  if i = k then begin
    k := k + 1;
    u[k+1] := x[n1];
  end else begin {i < k, u[i] < x[n1] <= u[i+1] }
    u[i+1] := x[n1];
  end;
end;

Фрагмент ... использует идею двочного поиска; в инварианте условно полагаем $u[0]$ равным минус бесконечности, а $u[k+1]$ — плюс бесконечности. Наша цель: $u[i] < x[n1] \le u[i+1]$.

i:=0; j:=k+1;
{u[i] < x[n1] <= u[j], j > i}
while (j - i) <> 1 do begin
  s := i + (j-i) div 2; {i < s < j}
  if x[n1] <= u[s] then begin
    j := s;
  end else begin {u[s] < x[n1]}
```c
| | i := s;
end;
end;
{u[i] < x[n1] <= u[j], j-i = 1}
```

**Замечание.** Более простое (но не минимальное) индуктивное расширение получится, если для каждого i хранить максимальную длину возрастающей подпоследовательности, оканчивающейся на x[i]. Это расширение приводит к алгоритму с числом действий порядка n². Есть и другой изящный алгоритм с квадратичным временем работы (сообщил М. В. Вьюгин): найти максимальную общую подпоследовательность исходной последовательности и отсортированной последовательности с помощью предыдущей задачи.

**1.3.5.** Какие изменения нужно внести в решение предыдущей задачи, если надо искать максимальную неубывающую последовательность? ☐
## 2. ПОРОЖДЕНИЕ КОМБИНАТОРНЫХ ОБЪЕКТОВ

Здесь собраны задачи, в которых требуется получить один за друг- гим все элементы некоторого множества.

### 2.1. Размещения с повторениями

**2.1.1. Напечатайте все последовательности длины k из чисел 1..n.**

**Решение.** Будем печатать их в лексикографическом порядке (после- довательность a предшествует последовательности b, если для некото- рого s их начальные отрезки длины s равны, а (s+1)-й член последова- тельности a меньше). Первой будет последовательность <1,1,...,1>, последней — последовательность <n,n,...,n>. Будем хранить послед- нюю напечатанную последовательность в массиве x[1]..x[k].

```c
...x[1]..x[k] положить равными 1
...напечатать x
...last[1]..last[k] положить равным n
{напечатаны все до x включительно}
while x <> last do begin
    ...x := следующая за x последовательность
    ...напечатать x
end;
```

Опишем, как можно перейти от x к следующей последовательности. Согласно определению, у следующей последовательности первые s чле- нов должны быть такими же, а (s+1)-й — больше. Это возможно, если x[s+1] меньше n. Среди таких s нужно выбрать наибольшее (иначе полученная последовательность не будет непосредственно следующей).
Соответствующее $x[s+1]$ нужно увеличить на 1. Итак, надо, двигаясь с конца последовательности, найти самый правый член, меньший $n$ (он найдётся, т. к. по предположению $x<\text{last}$), увеличить его на 1, а идущие за ним члены положить равными 1.

```pascal
p:=k;
while not (x[p] < n) do begin
  p := p-1;
end;
{x[p] < n, x[p+1] = ... = x[k] = n}
x[p] := x[p] + 1;
for i := p+1 to k do begin
  x[i]:=1;
end;
```

**Замечание.** Если членами последовательности считать числа не от 1 до $n$, а от 0 до $n-1$, то переход к следующему соответствует прибавлению единицы в $n$-ичной системе счисления.

2.1.2. В предложенном алгоритме используется сравнение двух массивов ($x < \text{last}$). Устраните его, добавив булевскую переменную 1 и включив в инвариант соотношение

$1 \Leftrightarrow \text{последовательность } x \text{ — последняя.}$

2.1.3. Напечатайте все подмножества множества $\{1..k\}$.

**Решение.** Подмножества находятся во взаимно однозначном соответствии с последовательностями нулей и единиц длины $k$. ☐

2.1.4. Напечатайте все последовательности положительных целых чисел длины $k$, у которых $i$-й член не превосходит $i$. ☐

## 2.2. Перестановки

2.2.1. Напечатайте все перестановки чисел $1..n$ (то есть последовательности длины $n$, в которые каждое из этих чисел входит по одному разу).

**Решение.** Перестановки будем хранить в массиве $x[1..n]$ и печатать в лексикографическом порядке. (Первой при этом будет перестановка $\langle 12...n \rangle$, последней — $\langle n...21 \rangle$. Для составления алгоритма перехода к следующей перестановке зададимся вопросом: в каком случае $k$-й член перестановки можно увеличить, не меняя предыдущих?
Ответ: если он меньше какого-либо из следующих членов (т. е. членов с номерами больше k). Мы должны найти наибольшее k, при котором это так, т. е. такое k, что

$$x[k] < x[k+1] > \dots > x[n]$$

После этого значение x[k] нужно увеличить минимальным возможным способом, т. е. найти среди x[k+1]..x[n] наименьшее число, большее его. Поменяв x[k] с ним, остаётся расположить числа с номерами k+1..n так, чтобы перестановка была наименьшей, т. е. в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке.

Алгоритм перехода к следующей перестановке:

```pascal
{<x[1] ... x[n]> <> <n ... 2 1>}
k:=n-1;
{последовательность справа от k убывающая: x[k+1]...>x[n]}
while x[k] > x[k+1] do begin
  k:=k-1;
end;
{x[k] < x[k+1] > ... > x[n]}
t:=k+1;
{т <=n, все члены отрезка x[k+1] > ... > x[t] больше x[k]}
while (t < n) and (x[t+1] > x[k]) do begin
  t:=t+1;
end;
{x[k+1] > ... > x[t] > x[k] > x[t+1] > ... > x[n]}
... обменять x[k] и x[t]
{x[k+1] > ... > x[n]}
... переставить участок x[k+1]..x[n] в обратном порядке
```

**Замечание.** Программа имеет знакомый дефект: если t=n, то x[t+1] не определено.

### 2.3. Подмножества

#### 2.3.1. Для заданных n и k (k ≤ n) перечислите все k-элементные подмножества множества {1..n}.

**Решение.** Будем представлять каждое подмножество последовательностью x[1]..x[n] нулей и единиц длины n, в которой ровно k единиц. (Другой способ представления разберём позже.) Такие последовательности упорядочим лексикографически (см. выше). Очевидный способ решения задачи — перебирать все последовательности как раньше,
а затем отбирать среди них те, у которых k единиц — мы отбросим, считая его неэкономичным (число последовательностей с k единицами может быть много меньше числа всех последовательностей). Будем искать такой алгоритм, чтобы получение очередной последовательности требовало не более C·n действий.

В каком случае s-й член последовательности можно увеличить, не меняя предыдущие? Если $x[s]$ меняется с 0 на 1, то для сохранения общего числа единиц нужно справа от $x[s]$ заменить 1 на 0. Для этого надо, чтобы справа от $x[s]$ единицы были. Если мы хотим перейти к непосредственно следующему, то $x[s]$ должен быть первым справа нулём, за которым стоят единицы. Легко видеть, что $x[s+1]=1$ (иначе $x[s]$ не первый). Таким образом надо искать наибольшее s, для которого $x[s]=0$, $x[s+1]=1$:

<figure><img src="image_27.png" /></figure>

За $x[s+1]$ могут идти ещё несколько единиц, а после них несколько нулей. Заменив $x[s]$ на 1, надо выбрать идущие за ним члены так, чтобы последовательность была бы минимальна с точки зрения нашего порядка, т.е. чтобы сначала шли нули, а потом единицы. Вот что получается:

первая последовательность: 0..01..1 (n-k нулей, k единиц);

последняя последовательность: 1..10..0 (к единиц, n-k нулей);

алгоритм перехода к следующей за $x[1]..x[n]$ последовательности (предполагаем, что она есть):

```pascal
s := n - 1;
while not ((x[s]=0) and (x[s+1]=1)) do begin
  s := s - 1;
end;
{s - член, подлежащий изменению с 0 на 1}
num:=0;
for k := s to n do begin
  num := num + x[k];
end;
{num - число единиц на участке x[s]..x[n], число нулей
  равно (длина - число единиц), т.е. (n-s+1) - num}
x[s]:=1;
for k := s+1 to n-num+1 do begin
  x[k] := 0;
end;
```
```
{осталось поместить num-1 единиц в конце}
for k := n-num+2 to n do begin
  | x[k] :=1;
end;
```

Другой способ представления подмножеств — это перечисление их элементов. Чтобы каждое подмножество имело ровно одно представление, договоримся перечислять элементы в возрастающем порядке. Приходим к такой задаче.

**2.3.2.** Перечислите все возрастающие последовательности длины k из чисел 1..n в лексикографическом порядке. (Пример: при n=5, k=2 получаем: 12 13 14 15 23 24 25 34 35 45.)

**Решение.** Минимальной будет последовательность $\langle 12...k \rangle$; максимальной — $\langle (n-k+1)...(n-1)n \rangle$. В каком случае s-й член последовательности можно увеличить? Ответ: если он меньше n-k+s. После увеличения s-го элемента все следующие должны возрастать с шагом 1. Получаем такой алгоритм перехода к следующему:

```
s:=k;
while not (x[s] < n-k+s) do begin
  | s:=s-1;
end;
{s - номер элемента, подлежащего увеличению};
x[s] := x[s]+1;
for i := s+1 to k do begin
  | x[i] := x[i-1]+1;
end;
```

**2.3.3.** Пусть мы решили представлять k-элементные подмножества множества $\{1..n\}$ убывающими последовательностями длины k, упорядоченными по-прежнему лексикографически. (Пример: 21 31 32 41 42 43 51 52 53 54.) Как выглядит тогда алгоритм перехода к следующей?

**Ответ.** Ищем наибольшее s, для которого $x[s+1]+1 < x[s]$. (Если такого s нет, полагаем $s=0$.) Увеличив $x[s+1]$ на 1, кладём остальные минимально возможными ($x[t]=k+1-t$ для $t>s$).

**2.3.4.** Решите две предыдущие задачи, заменив лексикографический порядок на обратный (раньше идут те, которые больше в лексикографическом порядке).

**2.3.5.** Перечислите все вложения (функции, переводящие разные элементы в разные) множества $\{1..k\}$ в $\{1..n\}$ (предполагается, что
k ≤ n). Порождение очередного элемента должно требовать не более C · k действий.

[Указание. Эта задача может быть сведена к перечислению подмножеств и перестановок элементов каждого подмножества.] ☐

### 2.4. Разбиения

#### 2.4.1. Перечислите все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). (Пример: n=4, разбиения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.)

**Решение.** Договоримся, что (1) в разбиениях слагаемые идут в невозрастающем порядке, (2) сами разбиения мы перечисляем в лексикографическом порядке. Разбиение храним в начале массива х[1]..х[n], при этом количество входящих в него чисел обозначим k. В начале х[1]=...=х[n]=1, k=n, в конце х[1]=n, k=1.

В каком случае х[s] можно увеличить, не меняя предыдущих? Во-первых, должно быть х[s-1]>х[s] или s=1. Во-вторых, s должно быть не последним элементом (увеличение s надо компенсировать уменьшением следующих). Увеличив s, все следующие элементы надо взять минимально возможными.

```pascal
s := k - 1;
while not ((s=1) or (x[s-1] > x[s])) do begin
  s := s-1;
end;
{s - подлежащее увеличению слагаемое}
x[s] := x[s] + 1;
sum := 0;
for i := s+1 to k do begin
  sum := sum + x[i];
end;
{sum - сумма членов, стоявших после x[s]}
for i := 1 to sum-1 do begin
  x[s+i] := 1;
end;
k := s+sum-1;
```

#### 2.4.2. Представляя по-прежнему разбиения как невозрастающие последовательности, перечислите их в порядке, обратном лексикографическому (для n=4, например, должно быть 4, 3+1, 2+2, 2+1+1, 1+1+1+1).
> [Указание. Уменьшать можно первый справа член, не равный 1; найдя его, уменьшим на 1, а следующие возьмём максимально возможными (равными ему, пока хватает суммы, а последний — сколько остается).] [ ]

2.4.3. Представляя разбиения как неубывающие последовательности, перечислите их в лексикографическом порядке. Пример для $n=4$: 1+1+1+1, 1+1+2, 1+3, 2+2, 4.

> [Указание. Последний член увеличить нельзя, а предпоследний — можно; если после увеличения на 1 предпоследнего члена за счёт последнего нарушится возрастание, то из двух членов надо сделать один, если нет, то последний член надо разбить на слагаемые, равные предыдущему, и остаток, не меньший его.] [ ]

2.4.4. Представляя разбиения как неубывающие последовательности, перечислите их в порядке, обратном лексикографическому. Пример для $n=4$: 4, 2+2, 1+3, 1+1+2, 1+1+1+1.

> [Указание. Чтобы элемент $x[s]$ можно было уменьшить, необходимо, чтобы $s=1$ или $x[s-1]<x[s]$. Если $x[s]$ не последний, то этого и достаточно. Если он последний, то нужно, чтобы $x[s-1] \le [x[s]/2]$ или $s=1$. (Здесь $[\alpha]$ обозначает целую часть $\alpha$.)] [ ]

## 2.5. Коды Грея и аналогичные задачи

Иногда бывает полезно перечислять объекты в таком порядке, чтобы каждый следующий минимально отличался от предыдущего. Расмотрим несколько задач такого рода.

2.5.1. Перечислите все последовательности длины $n$ из чисел $1..k$ в таком порядке, чтобы каждая следующая отличалась от предыдущей в единственной цифре, причём не более, чем на 1.

**Решение.** Рассмотрим прямоугольную доску ширины $n$ и высоты $k$. На каждой вертикали будет стоять шашка. Таким образом, положения шашек соответствуют последовательностям из чисел $1..k$ длины $n$ ($s$-й член последовательности соответствует высоте шашки на $s$-й вертикали). На каждой шашке нарисуем стрелочку, которая может быть направлена вверх или вниз. Вначале все шашки поставим на нижнюю горизонталь стрелочкой вверх. Далее двигаем шашки по такому правилу: найдя самую правую шашку, которую можно подвинуть в направлении (нарисованной на ней) стрелки, двигаем её на одну клетку в этом
направлении, а все стоящие правее неё шашки (они упёрлись в край) разворачиваем кругом.

Ясно, что на каждом шаге только одна шашка сдвигается, т. е. один член последовательности меняется на 1. Докажем индукцией по n, что проходятся все последовательности из чисел 1..k. Случай n=1 очевиден. Пусть $n>1$. Все ходы поделим на те, где двигается последняя шашка, и те, где двигается не последняя. Во втором случае последняя шашка стоит у стены, и мы её поворачиваем, так что за каждым ходом второго типа следует $k-1$ ходов первого типа, за время которых последняя шашка побывает во всех клетках. Если мы теперь забудем о последней шашке, то движения первых $n-1$ по предположению индукции пробегают все последовательности длины $n-1$ по одному разу; движения же последней шашки из каждой последовательности длины $n-1$ делают $k$ последовательностей длины $n$.

В программе, помимо последовательности $x[1]..x[n]$, будем хранить массив $d[1]..d[n]$ из чисел $+1$ и $-1$ ($+1$ соответствует стрелке вверх, $-1$ — стрелке вниз).

Начальное состояние: $x[1]=...=x[n]=1$; $d[1]=...=d[n]=1$.

Приведём алгоритм перехода к следующей последовательности (одновременно выясняется, возможен ли переход — ответ становится значением булевской переменной $p$).

```pascal
{если можно, сделать шаг и положить p := true, если нет,
положить p := false }

i := n;
while (i > 1) and
     (((d[i]=1) and (x[i]=n)) or ((d[i]=-1) and (x[i]=1)))
     do begin
     i:=i-1;
end;

if (d[i]=1 and x[i]=n) or (d[i]=-1 and x[i]=1) then begin
  p:=false;
end else begin
  p:=true;
  x[i] := x[i] + d[i];
  for j := i+1 to n do begin
    d[j] := - d[j];
  end;
end;
```

**Замечание.** Для последовательностей нулей и единиц возможно другое решение, использующее двоичную систему. (Именно оно связывается обычно с названием «коды Грея».)
Запишем подряд все числа от 0 до $2^n - 1$ в двоичной системе. Например, для $n = 3$ напишем:

000 001 010 011 100 101 110 111

Затем каждое из чисел подвергнем преобразованию, заменив каждую цифру, кроме первой, на её сумму с предыдущей цифрой (по модулю 2). Иными словами, число $a_1, a_2, \dots, a_n$ преобразуем в $a_1, a_1 + a_2, a_2 + a_3, \dots, a_{n-1} + a_n$ (сумма по модулю 2). Для $n = 3$ получим:

000 001 011 010 110 111 101 100

Легко проверить, что описанное преобразование чисел обратимо (и тем самым даёт все последовательности по одному разу). Кроме того, двоичные записи соседних чисел отличаются заменой конца 011...1 на конец 100...0, что — после преобразования — приводит к изменению единственной цифры.

**Применение кода Грея.** Пусть есть вращающаяся ось, и мы хотим поставить датчик угла поворота этой оси. Насадим на ось барабан, выкрасим половину барабана в чёрный цвет, половину в белый и установим фотоэлемент. На его выходе будет в половине случаев 0, а в половине 1 (т. е. мы измеряем угол «с точностью до 180°»).

Развёртка барабана:

<figure><img src="image_28.png" /></figure>

Сделав рядом другую дорожку из двух чёрных и белых частей и поставив второй фотоэлемент, получаем возможность измерить угол с точностью до 90°:

<figure><img src="image_29.png" /></figure>

Сделав третью,

<figure><img src="image_30.png" /></figure>
мы измерим угол с точностью до 45° и т. д. Эта идея имеет, однако, не-
достаток: в момент пересечения границ сразу несколько фотоэлементов
меняют сигнал, и если эти изменения произойдут не совсем одновре-
менно, на какое-то время показания фотоэлементов будут бессмыслен-
ными. Коды Грея позволяют избежать этой опасности. Сделаем так,
чтобы на каждом шаге менялось показание лишь одного фотоэлемента
(в том числе и на последнем, после целого оборота).

<figure><img src="image_31.png" /></figure>

Написанная нами формула позволяет легко преобразовать данные
от фотоэлементов в двоичный код угла поворота.

Заметим также, что геометрически существование кода Грея озна-
чает наличие «гамильтонова цикла» в *n*-мерном кубе (возможность
обойти все вершины куба по разу, двигаясь по рёбрам, и вернуться
в исходную вершину).

2.5.2. Напечатайте все перестановки чисел 1..n так, чтобы каждая следующая получалась из предыдущей обменом (транспозицией) двух соседних чисел. Например, при n=3 допустим такой порядок:

$$3.2.1 \rightarrow 2.3.1 \rightarrow 2.1.3 \rightarrow 1.2.3 \rightarrow 1.3.2 \rightarrow 3.1.2$$

(между переставляемыми числами вставлены точки).

**Решение.** Наряду с множеством перестановок рассмотрим множе-
ство последовательностей $y[1]..y[n]$ целых неотрицательных чисел,
для которых $y[1] \le 0, ..., y[n] \le n-1$. В нём столько же элементов,
сколько в множестве всех перестановок, и мы сейчас установим между
ними взаимно однозначное соответствие. Именно, каждой перестановке
поставим в соответствие последовательность $y[1]..y[n]$, где $y[i]$ —
количество чисел, меньших $i$ и стоящих левее $i$ в этой перестановке.
Взаимная однозначность вытекает из такого замечания. Перестанов-
ка чисел $1..n$ получается из перестановки чисел $1..n-1$ добавлением
числа $n$, которое можно вставить на любое из $n$ мест. При этом к сопо-
ставляемой с ней последовательности добавляется ещё один член, при-
нимающий значения от 0 до $n-1$, а предыдущие члены не меняются.
При этом оказывается, что изменение на единицу одного из членов по-
следовательности $y$ соответствует транспозиции двух соседних чисел,
если все следующие числа последовательности у принимают максимально или минимально возможные для них значения. Именно, увеличение $y[i]$ на 1 соответствует транспозиции числа $i$ с его правым соседом, а уменьшение — с левым.

Теперь вспомним решение задачи о перечислении всех последовательностей, на каждом шаге которого один член меняется на единицу. Заменив прямоугольную доску доской в форме лестницы (высота $i$-й вертикали равна $i$) и двигая шашки по тем же правилам, мы перечислим все последовательности $y$, причём $i$-й член будет меняться как раз только если все следующие шашки стоят у края. Надо ещё уметь параллельно с изменением у корректировать перестановку. Очевидный способ требует отыскания в ней числа $i$; это можно облегчить, если помимо самой перестановки хранить функцию

$i \mapsto$ позиция числа $i$ в перестановке,

т.е. обратное к перестановке отображение, и соответствующим образом её корректировать. Вот какая получается программа:

```pascal
program test;
const n=...;
var
  x: array [1..n] of 1..n; {перестановка}
  inv_x: array [1..n] of 1..n; {обратная перестановка}
  y: array [1..n] of integer; {y[i] < i}
  d: array [1..n] of -1..1; {направления}
  b: boolean;
procedure print_x;
  var i: integer;
begin
  for i:=1 to n do begin
    write (x[i], ' ');
  end;
  writeln;
end;
procedure set_first; {первая: y[i]=0 при всех i}
  var i : integer;
begin
  for i := 1 to n do begin
    x[i] := n + 1 - i;
    inv_x[i] := n + 1 - i;
    y[i]:=0;
```
```pascal
d[i] := 1;
end;
end;

procedure move (var done : boolean);
  var i, j, pos1, pos2, val1, val2, tmp : integer;
begin
  i := n;
  while (i > 1) and (((d[i]=1) and (y[i]=i-1)) or
                    ((d[i]=-1) and (y[i]=0))) do begin
    i := i-1;
  end;
  done := (i>1); {упрощение: первый член нельзя менять}
  if done then begin
    y[i] := y[i]+d[i];
    for j := i+1 to n do begin
      d[j] := -d[j];
      end;
      pos1 := inv_x[i];
      val1 := i;
      pos2 := pos1 + d[i];
      val2 := x pos2;
      {pos1, pos2 - номера переставляемых элементов;
       val1, val2 - их значения; val2 < val1}
      tmp := x pos1;
      x pos1 := x pos2;
      x pos2 := tmp;
      tmp := inv_x(val1);
      inv_x(val1) := inv_x(val2);
      inv_x(val2) := tmp;
    end;
  end;
end;
```

```pascal
begin
  set_first;
  print_x;
  b := true;
  {напечатаны все перестановки до текущей включительно;
   если в ложе, то текущая - последняя}
  while b do begin
    move (b);
    if b then print_x;
  end;
end.
```

<figure><img src="image_32.png" /></figure>
### 2.6. Несколько замечаний

Посмотрим ещё раз на использованные нами приёмы. Вначале уда-
валось решить задачу по такой схеме: определяем порядок на подле-
жащих перечислению объектах и явно описываем процедуру перехода
от данного объекта к следующему (в смысле этого порядка). В задаче
о кодах Грея потребовалось хранить, помимо текущего объекта, и неко-
торую дополнительную информацию (направления стрелок). Наконец,
в задаче о перечислении перестановок (на каждом шаге допустима одна
транспозиция) мы применили такой приём: установили взаимно одно-
значное соответствие между перечисляемым множеством и другим, бо-
лее просто устроенным. Таких соответствий в комбинаторике известно
много. Мы приведём несколько задач, связанных с так называемыми
«числами Каталана».

**2.6.1.** Перечислите все последовательности длины $2n$, составленные из $n$ единиц и $n$ минус единиц, у которых сумма любого начального отрезка неотрицательна, т. е. число минус единиц в нём не превосходит числа единиц. (Число таких последовательностей называют **числом Каталана**; формулу для чисел Каталана см. в следующем разделе.)

**Решение.** Изображая единицу вектором $(1,1)$, а минус единицу вектором $(1,-1)$, можно сказать, что мы ищем пути из точки $(0,0)$ в точку $(n,0)$, не опускающиеся ниже оси абсцесс.

Будем перечислять последовательности в лексикографическом порядке, считая, что $-1$ предшествует $1$. Первой последовательностью будет «пила»

$1, -1, 1, -1, \dots$

а последней — «горка»

$1, 1, 1, \dots, 1, -1, -1, \dots, -1.$

Как перейти от последовательности к следующей? До некоторого места они должны совпадать, а затем надо заменить $-1$ на $1$. Место замены должно быть расположено как можно правее. Но заменять $-1$ на $1$ можно только в том случае, если справа от неё есть единица (которую можно заменить на $-1$). После замены $-1$ на $1$ мы приходим к такой задаче: фиксирован начальный кусок последовательности, надо найти минимальное продолжение. Её решение: надо приписывать $-1$, если это не нарушит условия неотрицательности, а иначе приписывать $1$. Получаем
такую программу:

```pascal
... 
type array2n = array [1..2n] of integer;
... 
procedure get_next (var a: array2n; var last: Boolean);
| {в a помещается следующая последовательность, если}
| {она есть (при этом last:=false), иначе last:=true}
var k, i, sum: integer;
begin
  k:=2*n;
  {инвариант: в a[k+1..2n] только минус единицы}
  while a[k] = -1 do begin k:=k-1; end;
  {k - максимальное среди тех, для которых a[k]=1}
  while (k>0) and (a[k] = 1) do begin k:=k-1; end;
  {a[k] - самая правая -1, за которой есть 1;
   если таких нет, то k=0}
  if k = 0 then begin
    last := true;
  end else begin
    last := false;
    i:=0; sum:=0;
    {sum = a[1] + ... + a[i]}
    while i<>k do begin
      i:=i+1; sum:= sum+a[i];
    end;
    {sum = a[1] + ... + a[k], a[k]=-1}
    a[k]:= 1; sum:= sum+2;
    {вплоть до a[k] всё изменено, sum=a[1] + ... + a[k]}
    while k <> 2*n do begin
      k:=k+1;
      if sum > 0 then begin
        a[k]:=-1
      end else begin
        a[k]:=1;
      end;
      sum:= sum+a[k];
    end;
    {k=2n, sum=a[1] + ... + a[2n]=0}
  end;
end;
```

### 2.6.2. Перечислите все расстановки скобок в произведении п сомножителей. Порядок сомножителей не меняется, скобки полностью опре-
деляют порядок действий. Например, для $n=4$ есть 5 расстановок:

((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).

[Указание. Каждому порядку действий соответствует последовательность команд стекового калькулятора, описанного на с. 144.] ☐

**2.6.3.** На окружности задано $2n$ точек, пронумерованных от 1 до $2n$. Перечислите все способы провести $n$ непересекающихся хорд с вершинами в этих точках. ☐

**2.6.4.** Перечислите все способы разрезать $n$-угольник на треугольники, проведя $n-2$ его диагонали. ☐

(Мы вернёмся к разрезанию многоугольника в разделе о динамическом программировании, с. 137.)

Ещё один класс задач на перечисление всех элементов заданного множества мы рассмотрим ниже, обсуждая метод поиска с возвратами (backtracking).

### 2.7. Подсчёт количеств

Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: $C_n^k$ — число всех $k$-элементных подмножеств $n$-элементного множества — можно найти,Заполняя таблицу по формулам

$$C_n^0 = C_n^n = 1 \qquad (n \ge 1)$$

$$C_n^k = C_{n-1}^{k-1} + C_{n-1}^k \qquad (n > 1, 0 < k < n)$$

или по формуле

$$C_n^k = \frac{n!}{k! \cdot (n-k)!}$$

(Первый способ эффективнее, если нужно сразу много значений $C_n^k$.)
Приведём другие примеры.

**2.7.1.** (Число разбиений; предлагалась на Всесоюзной олимпиаде по программированию 1988 года) Пусть $P(n)$ — число разбиений целого положительного $n$ на целые положительные слагаемые (без учёта порядка, $1+2$ и $2+1$ — одно и то же разбиение). При $n=0$ положим $P(n)=1$ (единственное разбиение не содержит слагаемых). Постройте алгоритм вычисления $P(n)$ для заданного $n$.
**Решение.** Можно доказать (это нетривиально) такую формулу для $P(n)$:

$$P(n)=P(n-1)+P(n-2)-P(n-5)-P(n-7)+P(n-12)+P(n-15)+...$$

(знаки у пар членов чередуются, вычитаемые в одной паре равны $(3q^2 - q)/2$ и $(3q^2 + q)/2$; сумма конечна — мы считаем, что $P(k) = 0$ при $k < 0$).

Однако и без её использования можно придумать способ вычисления $P(n)$, который существенно эффективнее перебора и подсчёта всех разбиений.

Обозначим через $R(n, k)$ (для $n \ge 0, k \ge 0$) число разбиений $n$ на це- лые положительные слагаемые, не превосходящие $k$. (При этом $R(0, k)$ считаем равным 1 для всех $k \ge 0$.) Очевидно, $P(n) = R(n, n)$. Все разби- ения $n$ на слагаемые, не превосходящие $k$, разобьём на группы в завис- имости от максимального слагаемого (обозначим его $i$). Число $R(n, k)$ равно сумме (по всем $i$ от 1 до $k$) количеств разбиений со слагаемыми не больше $k$ и максимальным слагаемым, равным $i$. А разбиения $n$ на слагаемые не более $k$ с первым слагаемым, равным $i$, по существу пред- ставляют собой разбиения $n-i$ на слагаемые, не превосходящие $i$ (при $i \le k$). Так что

$$R(n, k) = \sum_{i=1}^{k} R(n - i, i) \quad \text{при } k \le n,$$

$$R(n, k) = R(n, n) \quad \text{при } k \ge n,$$

что позволяет заполнять таблицу значений функции $R$. $\square$

<figure><img src="image_33.png" /></figure>

### 2.7.2. (Счастливые билеты; предлагалась на Всесоюзной олимпиаде по программированию 1989 года.) Последовательность из $2n$ цифр (каждая цифра от 0 до 9) называется счастливым билетом, если сумма первых $n$ цифр равна сумме последних $n$ цифр. Найдите число счастливых последовательностей данной длины.

**Решение.** (Сообщено одним из участников олимпиады; к сожалению, не могу указать фамилию, так как работы проверялись зашифрован- ными.) Рассмотрим более общую задачу: найти число последователь- ностей, где разница между суммой первых $n$ цифр и суммой послед- них $n$ цифр равна $k$ ($k = -9n, ..., 9n$). Пусть $T(n, k)$ — число таких последовательностей.

Разобьём множество таких последовательностей на классы в зависи- мости от разницы между первой и последней цифрами. Если эта разни- ца равна $t$, то разница между суммами групп из оставшихся $n-1$ цифр
равна $k-t$. Учитывая, что пар цифр с разностью $t$ бывает $10 - |t|$, получаем формулу

$$T(n, k) = \sum_{t=-9}^{9} (10 - |t|)T(n-1, k-t).$$

(Некоторые слагаемые могут отсутствовать, так как $k-t$ может быть слишком велико.) □

В некоторых случаях ответ удаётся получить в виде явной формулы.

### 2.7.3. Докажите, что число Каталана (количество последовательно длины $2n$ из $n$ единиц и $n$ минус единиц, в любом начальном отрезке которых не меньше единиц, чем минус единиц) равно $C_{2n}^n/(n+1)$.

[Указание. Число Каталана есть число ломаных, идущих из $(0,0)$ в $(2n,0)$ шагами $(1,1)$ и $(1,-1)$, не опускающихся в нижнюю полуплоскость, т. е. разность числа всех ломаных (которое есть $C_{2n}^n$) и числа ломаных, опускающихся в нижнюю полуплоскость. Последние можно описать также как ломаные, пересекающие прямую $y = -1$. Отразив их кусок справа от самой правой точки пересечения относительно указанной прямой, мы установим взаимно однозначное соответствие между ними и ломаными из $(0,0)$ в $(2n,-2)$. Остаётся проверить, что $C_{2n}^n - C_{2n}^{n+1} = C_{2n}^n/(n+1)$.] □
### 3. ОБХОД ДЕРЕВА.
ПЕРЕБОР С ВОЗВРАТАМИ

#### 3.1. Ферзи, не бьющие друг друга:
обход дерева позиций

В предыдущей главе мы рассматривали несколько задач одного и того же типа: «перечислить все элементы некоторого множества А». Схема решения была такова: на множестве А вводился порядок и описывалась процедура перехода от произвольного элемента множества А к следующему за ним (в этом порядке). Такую схему не всегда удаётся реализовать непосредственно, и в этой главе мы рассмотрим другой полезный приём перечисления всех элементов некоторого множества. Его называют «поиск с возвратами», «метод ветвей и границ», «backtracking». На наш взгляд, наиболее точное название этого метода — обход дерева.

##### 3.1.1. Перечислите все способы расстановки $n$ ферзей на шахматной доске $n \times n$, при которых они не бьют друг друга.

**Решение.** Очевидно, на каждой из $n$ горизонталей должно стоять по ферзю. Будем называть $k$-позицией (для $k = 0, 1, ..., n$) произвольную расстановку $k$ ферзей на $k$ нижних горизонталях (ферзи могут бить друг друга). Нарисуем «дерево позиций»: его корнем будет единственная 0-позиция, а из каждой $k$-позиции выходит $n$ стрелок вверх в $(k+1)$-позиции. Эти $n$ позиций отличаются положением ферзя на $(k+1)$-й горизонтали. Будем считать, что расположение их на рисунке соответствует положению этого ферзя: левее та позиция, в которой ферзь расположен левее.

Среди позиций этого дерева нам надо отобрать те $n$-позиции, в которых ферзи не бьют друг друга. Программа будет «обходить дерево» и искать их. Чтобы не делать лишней работы, заметим вот что: если в какой-то $k$-позиции ферзи бьют друг друга, то ставить дальнейших
<figure><img src="image_34.png" /><figcaption>Дерево позиций для $n = 2$</figcaption></figure>

ферзей смысла нет. Поэтому, обнаружив это, мы будем прекращать построение дерева в этом направлении.

Точнее, назовём $k$-позицию допустимой, если после удаления верхнего ферзя оставшиеся не бьют друг друга. Наша программа будет рассматривать только допустимые позиции.

<figure><img src="image_35.png" /><figcaption>Дерево допустимых позиций для $n = 3$</figcaption></figure>

Разобьём задачу на две части: (1) обход произвольного дерева и (2) реализацию дерева допустимых позиций.
Сформулируем задачу обхода произвольного дерева. Будем считать, что у нас имеется Робот, который в каждый момент находится в одной из вершин дерева (вершины изображены на рисунке кружочками). Он умеет выполнять команды:

* **вверх_налево** (идти по самой левой из выходящих вверх стрелок)

* **вправо** (перейти в соседнюю справа вершину)

* **вниз** (спуститься вниз на один уровень)

(На рисунках стрелками показано, какие перемещения соответствуют этим командам.)

<figure><img src="image_36.png" /></figure>

<figure><img src="image_37.png" /></figure>

<figure><img src="image_38.png" /></figure>

Кроме того, в репертуар Робота входят проверки (соответствующие возможности выполнить каждую из команд):

* есть_сверху;

* есть_справа;

* есть_снизу;

(последняя проверка истинна всюду, кроме корня). Обратите внимание, что команда **вправо** позволяет перейти лишь к «родному брату», но не к «двоюродному».

<figure><img src="image_39.png" /></figure>

Так команда
**вправо**
**не** действует!

Будем считать, что у Робота есть команда обработать и что его задача — обработать все листья (вершины, из которых нет стрелок
вверх, то есть где условие есть_сверху ложно). Для нашей шахматной задачи команде обработать будет соответствовать проверка и печать позиции ферзей.

Доказательство правильности приводимой далее программы использует такие определения. Пусть фиксировано положение Робота в одной из вершин дерева. Тогда все листья дерева разбиваются на три категории: над Роботом, левее Робота и правее Робота. (Путь из корня в лист может проходить через вершину с Роботом, сворачивать влево, не доходя до неё и сворачивать вправо, не доходя до неё.) Через (ОЛ) обозначим условие «обработаны все листья левее Робота», а через (ОЛН) — условие «обработаны все листья левее и над Роботом».

<figure><img src="image_40.png" /></figure>

Нам понадобится такая процедура:

procedure вверх_до_упора_и_обработать;
| {дано: (ОЛ), надо: (ОЛН)}
begin
| {инвариант: ОЛ}
| while есть_сверху do begin
| | вверх_налево;
| end
| {ОЛ, Робот в листе}
| обработать;
| {ОЛН}
end;

Основной алгоритм:

дано: Робот в корне, листья не обработаны
надо: Робот в корне, листья обработаны

{ОЛ}
вверх_до_упора_и_обработать;
{инвариант: ОЛН}
```pascal
while есть_снизу do begin
    if есть_справа then begin {ОЛН, есть справа}
        вправо;
        {ОЛ}
        вверх_до_упора_и_обработать;
    end else begin
        {ОЛН, не есть_справа, есть_снизу}
        вниз;
    end;
end;
{ОЛН, Робот в корне => все листья обработаны}
```

Осталось воспользоваться следующими свойствами команд Робота (в каждой строке в первой фигурной скобке записаны условия, в которых выполняется команда, во второй — утверждения о результате её выполнения):

(1) `{ОЛ, не есть_сверху}` обработать `{ОЛН}`

(2) `{ОЛ, есть_сверху}` вверх_налево `{ОЛ}`

(3) `{есть_справа, ОЛН}` вправо `{ОЛ}`

(4) `{не есть_справа, есть_снизу, ОЛН}` вниз `{ОЛН}`

**3.1.2. Докажите, что приведённая программа завершает работу (на любом конечном дереве).**

**Решение.** Процедура вверх_до_упора_и_обработать завершает работу (высота Робота не может увеличиваться бесконечно). Если программа работает бесконечно, то, поскольку листья не обрабатываются по-вторно, начиная с некоторого момента ни один лист не обрабатывается. А это возможно, только если Робот всё время спускается вниз. Против-воречие. (Об оценке числа действий см. далее.) ☐

**3.1.3. Докажите правильность такой программы обхода дерева:**

```pascal
var state: (WL, WLU);
state := WL;
while есть_снизу or (state <> WLU) do begin
    if (state = WL) and есть_сверху then begin
        вверх_налево;
        end else if (state = WL) and not есть_сверху then begin
            обработать; state := WLU;
        end else if (state = WLU) and есть_справа then begin
            вправо; state := WL;
        end else begin {state = WLU, not есть_справа, есть_снизу}
            вниз;
        end;
end;
```
**Решение.** Инвариант цикла:

$$ 
\begin{aligned}
state &= WL \Rightarrow ОЛ \\
state &= WLU \Rightarrow ОЛН
\end{aligned}
 $$

Доказательство завершения работы: переход из состояния ОЛ в ОЛН возможен только при обработке вершины, поэтому если программа работает бесконечно, то с некоторого момента значение state не меняется, что невозможно. ☐

**3.1.4.** Напишите программу обхода дерева, использующую процедуру перехода в следующий лист (с выходным параметром, сообщающим, удалось ли это сделать или лист оказался последним). ☐

**3.1.5.** Решите задачу об обходе дерева, если мы хотим, чтобы обрабатывались все вершины (не только листья).

**Решение.** Пусть х — некоторая вершина. Тогда любая вершина у относится к одной из четырёх категорий. Рассмотрим путь из корня в у. Он может:

(а) быть частью пути из корня в х (у ниже х);

(б) свернуть налево с пути в х (у левее х);

(в) пройти через х (у над х);

(г) свернуть направо с пути в х (у правее х);

В частности, сама вершина х относится к категории (в). Условия теперь будут такими:

(ОНЛ) обработаны все вершины ниже и левее;

(ОЛН) обработаны все вершины ниже, левее и над.

Вот как будет выглядеть программа:

```pascal
procedure вверх_до_упора_и_обработать;
  {дано: (ОНЛ), надо: (ОЛН)}
begin
  {инвариант: ОНЛ}
  while есть_сверху do begin
    обработать;
    вверх_налево;
  end
  {ОНЛ, Робот в листе}
    обработать;
  {ОНЛН}
end;
```
Основной алгоритм:

дано: Робот в корне, ничего не обработано
надо: Робот в корне, все вершины обработаны

{ОНЛ}
вверх_до_упора_и_обработать;
{инвариант: ОНЛН}
while есть_снизу do begin
    if есть_справа then begin {ОНЛН, есть справа}
        вправо;
        {ОНЛ}
        вверх_до_упора_и_обработать;
    end else begin
        {ОНЛ, не есть_справа, есть_снизу}
        вниз;
    end;
end;
{ОНЛН, Робот в корне => все вершины обработаны}

<figure><img src="image_41.png" /></figure>

3.1.6. Приведённая только что программа обрабатывает вершину до того, как обработан любой из её потомков. Как изменить программу, чтобы каждая вершина, не являющаяся листом, обрабатывалась дважды: один раз до, а другой раз после всех своих потомков? (Листья по-прежнему обрабатываются по разу.)

Решение. Под «обработано ниже и левее» будем понимать «ниже обработано по разу, слева обработано полностью (листья по разу, остальные по два)». Под «обработано ниже, левее и над» будем понимать «ниже обработано по разу, левее и над — полностью».

Программа будет такой:

procedure вверх_до_упора_и_обработать;
    {дано: (ОНЛ), надо: (ОНЛН)}
begin
    {инвариант: ОНЛ}
    while есть_сверху do begin
        обработать;
        вверх_налево;
    end
    {ОНЛ, Робот в листе}
    обработать;
    {ОНЛН}
end;
Основной алгоритм:

дано: Робот в корне, ничего не обработано
надо: Робот в корне, все вершины обработаны

{ОНЛ}
вверх_до_упора_и_обработать;
{инвариант: ОНЛН}
while есть_снизу do begin
    if есть_справа then begin {ОНЛН, есть справа}
        вправо;
        {ОНЛ}
        вверх_до_упора_и_обработать;
    end else begin
        {ОНЛ, не есть_справа, есть_снизу}
        вниз;
        обработать;
    end;
end;
{ОНЛН, Робот в корне => все вершины обработаны полностью} ☐

3.1.7. Докажите, что число операций в этой программе по порядку равно числу вершин дерева. (Как и в других программах, которые отличаются от этой лишь пропуском некоторых команд обработать.)

[Указание. Примерно каждое второе действие при исполнении этой программы — обработка вершины, а каждая вершина обрабатывается максимум дважды.] ☐

Вернёмся теперь к нашей задаче о ферзях (где из всех программ обработки дерева понадобится лишь первая, самая простая). Реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной k: 0..n (число ферзей) и массива c: array[1..n] of 1..n (c[i] — координаты ферзя на i-й горизонтали; при i > k значение c[i] роли не играет). Предполагается, что все позиции допустимы (если убрать верхнего ферзя, остальные не бьют друг друга).

program queens;
    const n = ...;
    var
        k: 0..n;
        c: array [1..n] of 1..n;
procedure begin_work; {начать работу}

begin
k := 0;
end;

function danger: boolean; {верхний ферзь под боем}

var b: boolean; i: integer;
begin

if k <= 1 then begin
  danger := false;
end else begin

b := false;
i := 1;
{b <=> верхний ферзь под боем ферзей с номерами < i}
while i <> k do begin

b := b or (c[i]=c[k]) {вертикаль}
or (abs(c[i]-c[k]))=abs(i-k); {диагональ}
i := i+1;

end;
danger := b;
end;

end;

function is_up: boolean; {есть_сверху}

begin
  is_up := (k < n) and not danger;
end;

function is_right: boolean; {есть_справа}

begin
  is_right := (k > 0) and (c[k] < n);
end;

{возможна ошибка: при k=0 не определено с[k]}

function is_down: boolean; {есть_снизу}

begin
  is_down := (k > 0);
end;

procedure up; {вверх_налево}

begin {k < n, not danger}

k := k + 1;
c [k] := 1;
end;
procedure right; {вправо}
begin {k > 0, c[k] < n}
  c[k] := c[k] + 1;
end;

procedure down; {вниз}
begin {k > 0}
  k := k - 1;
end;

procedure work; {обрабатать}
  var i: integer;
begin
  if (k = n) and not danger then begin
    for i := 1 to n do begin
      write ('<', i, ' ', c[i], ' > ');
    end;
    writeln;
  end;
end;

procedure UW; {вверх_до_упора_и_обрабатать}
begin
  while is_up do begin
    up;
  end;
  work;
end;

begin
  begin_work;
  UW;
  while is_down do begin
    if is_right then begin
      right;
      UW;
    end else begin
      down;
    end;
  end;
end.
**3.1.8.** Приведённая программа тратит довольно много времени на выполнение проверки есть_сверху (проверка, находится ли верхний ферзь под боем, требует числа действий порядка n). Измените ре- ализацию операций с деревом позиций так, чтобы все три провер- ки есть_сверху/справа/снизу и соответствующие команды требова- ли бы количества действий, ограниченного не зависящей от n конс- тантой.

**Решение.** Для каждой вертикали, каждой восходящей и каждой нис- ходящей диагонали будем хранить булевское значение — сведения о том, находится ли на этой линии ферзь (верхний ферзь не учитывает- ся). (Заметим, что в силу допустимости позиции на каждой из линий может быть не более одного ферзя.) ☐

## 3.2. Обход дерева в других задачах

**3.2.1.** Используйте метод обхода дерева для решения следующей за- дачи: дан массив из n целых положительных чисел $a[1]...a[n]$ и чи- сло $s$; требуется узнать, может ли число $s$ быть представлено как сумма некоторых из чисел массива $a$. (Каждое число можно использовать не более чем по одному разу.)

**Решение.** Будем задавать k-позицию последовательностью из k бу- левских значений, определяющих, входят ли в сумму числа $a[1]...a[k]$ или не входят. Позиция допустима, если её сумма не превосходит $s$. ☐

**Замечание.** По сравнению с полным перебором всех $2^n$ подмножеств тут есть некоторый выигрыш. Можно также предварительно отсорти- ровать массив $a$ в убывающем порядке, а также считать недопусти- мыми те позиции, в которых сумма отброшенных членов больше, чем разность суммы всех членов и $s$. Последний приём называют «методом ветвей и границ». Но принципиального улучшения по сравнению с пол- ным перебором тут не получается (эта задача, как говорят, NP-пол- на, подробности см. в книге Ахо, Хопкрофта и Ульмана «Построение и анализ вычислительных алгоритмов», Мир, 1979, а также в книге Гэ- ри и Джонсона «Вычислительные машины и труднорешаемые задачи», Мир, 1982). Традиционное название этой задачи — «задача о рюкза- ке» (рюкзак общей грузоподъёмностью $s$ нужно упаковать под связ- ку, располагая предметами веса $a[1]...a[n]$). См. также в главе 8 (Как обойтись без рекурсии) алгоритм её решения, полиномиальный по $n+s$ (использующий «динамическое программирование»).
3.2.2. Перечислите все последовательности из $n$ нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида ХХ). ☐

3.2.3. Аналогичная задача для последовательностей нулей и единиц, в которых никакая группа цифр не повторяется три раза подряд (нет куска вида ХХХ). ☐

К этой же категории относятся задачи типа «можно ли сложить данную фигуру из пентамино» и им подобные. В них важно умелое сокращение перебора (вовремя распознать, что имеющееся расположение фигурок уже противоречит требованиям, и по этой ветви поиск не продолжать).
## 4. СОРТИРОВКА

### 4.1. Квадратичные алгоритмы

**4.1.1.** Пусть $a[1],...,a[n]$ — целые числа. Требуется построить массив $b[1],...,b[n]$, содержащий те же числа, для которого $b[1] \le ... \le b[n]$.

**Замечание.** Среди чисел $a[1]...a[n]$ могут быть равные. Требуется, чтобы каждое целое число входило в $b[1]...b[n]$ столько же раз, сколько и в $a[1]...a[n]$.

**Решение.** Удобно считать, что числа $a[1]...a[n]$ и $b[1]...b[n]$ представляют собой начальное и конечное значения массива $x$. Требование «а и $b$ содержат одни и те же числа» будет заведомо выполнено, если в процессе работы мы ограничимся перестановками элементов $x$.

```pascal
k := 0;
{k наименьших элементов массива установлены на свои места}
while k <> n do begin
  s := k + 1; t := k + 1;
  {x[s] - наименьший среди x[k+1]..x[t] }
  while t<>n do begin
    t := t + 1;
    if x[t] < x[s] then begin
      s := t;
      end;
    end;
  {x[s] - наименьший среди x[k+1]..x[n] }
  ...переставить x[s] и x[k+1];
  k := k + 1;
end;
```

<figure><img src="image_42.png" /></figure>

**4.1.2.** Дайте другое решение задачи сортировки, использующее инвариант «первые $k$ элементов упорядочены» ($x[1] \le ... \le x[k]$).
### Решение.

```pascal
k:=1;
{первые k элементов упорядочены}
while k <> n do begin
    t := k+1;
    {k+1-мый элемент продвигается к началу, пока не займёт
     надлежащего места, t - его текущий номер}
    while (t > 1) and (x[t] < x[t-1]) do begin
        ...поменять x[t-1] и x[t];
        t := t - 1;
    end;
end;
```

<figure><img src="image_43.png" /></figure>

**Замечание.** Дефект программы: при ложном выражении (t>1) проверка х[t] < x[t-1] требует несуществующего значения х[0].

Оба предложенных решения требуют числа действий, пропорционального $n^2$. Существуют более эффективные алгоритмы.

## 4.2. Алгоритмы порядка $n \log n$

**4.2.1.** Предложите алгоритм сортировки за время $n \log n$ (число операций при сортировке $n$ элементов не больше $Cn \log n$ для некоторого $C$ и для всех $n$).

Мы приведём два решения.

### Решение 1 (сортировка слиянием).

Пусть $k$ — положительное целое число. Разобьём массив $x[1]...x[n]$ на отрезки длины $k$. (Первый — $x[1]...x[k]$, затем $x[k+1]...x[2k]$ и так далее.) Последний отрезок будет неполным, если $n$ не делится на $k$. Назовём массив $k$-упорядоченным, если каждый из этих отрезков в отдельности упорядочен. Любой массив 1-упорядочен. Если массив $k$-упорядочен и $n \le k$, то он упорядочен.

Мы опишем, как преобразовать $k$-упорядоченный массив в $2k$-упорядоченный (из тех же элементов). С помощью этого преобразования алгоритм записывается так:

```pascal
k:=1;
{массив x является k-упорядоченным}
while k < n do begin
    ...преобразовать k-упорядоченный массив в 2k-упорядоченный;
    k := 2 * k;
end;
```
Требуемое преобразование состоит в том, что мы многократно «сливаем» два упорядоченных отрезка длины не больше k в один упорядоченный отрезок. Пусть процедура

слияние `(p,q,r: integer)`

при `p ≤ q ≤ r` сливает отрезки `x[p+1]...x[q]` и `x[q+1]...x[r]` в упорядоченный отрезок `x[p+1]...x[r]` (не затрагивая других частей массива `x`).

<table><thead><tr><th>p</th><th>q</th><th>r</th></tr></thead><tbody><tr><td colspan="2">упорядоченный</td><td>упорядоченный</td></tr><tr><td colspan="3">↓</td></tr><tr><td colspan="3">упорядоченный</td></tr></tbody></table>

Тогда преобразование k-упорядоченного массива в 2k-упорядоченный осуществляется так:

```pascal
t:=0;
{t кратно 2k или t = n, x[1]..x[t] является
  2k-упорядоченным; остаток массива x не изменился}
while t + k < n do begin
  p := t;
  q := t+k;
  r := min (t+2*k, n);
  {min(a,b) - минимум из a и b}
  слияние (p,q,r);
  t := r;
end;
```

Слияние требует вспомогательного массива для записи результатов слияния — обозначим его b. Через `p0` и `q0` обозначим номера последних элементов участков, подвергшихся слиянию, `s0` — последний записанный в массив b элемент. На каждом шаге слияния производится одно из двух действий:

```
b[s0+1] := x[p0+1];
p0 := p0+1;
s0 := s0+1;
```
или

```
b[s0+1] := x[q0+1];
q0 := q0+1;
s0 := s0+1;
```

(Любители языка С написали бы в этом случае $b[ ++s0 ] = x[ ++p0 ]$ и $b[ ++s0 ] = x[ ++q0 ]$.)

Первое действие (взятие элемента из первого отрезка) может производиться при одновременном выполнении двух условий:

(1) первый отрезок не кончился ($p0 < q$);

(2) второй отрезок кончился ($q0 = r$) или не кончился, но элемент в нём не меньше очередного элемента первого отрезка [($q0 < r$) и ($x[p0+1] \le x[q0+1]$)].

Аналогично для второго действия. Итак, получаем

```
p0 := p; q0 := q; s0 := p;
while (p0 <> q) or (q0 <> r) do begin
    if (p0 < q) and ((q0 = r) or ((q0 < r) and
                             (x[p0+1] <= x[q0+1])) then begin
        b [s0+1] := x [p0+1];
        p0 := p0+1;
        s0 := s0+1;
    end else begin
        {(q0 < r) and ((p0 = q) or ((p0<q) and
                                     (x[p0+1] >= x[q0+1])))}
        b [s0+1] := x [q0+1];
        q0 := q0 + 1;
        s0 := s0 + 1;
    end;
end;
```

(Если оба отрезка не кончены и первые невыбранные элементы в них равны, то допустимы оба действия; в программе выбрано первое.)

Остаётся лишь переписать результат слияния обратно в массив х. (Предупреждение. Если обратное копирование выполняется вне процедуры слияния, то не забудьте про последний отрезок.)

Программа имеет привычный дефект: обращение к несуществующим элементам массива при вычислении булевских выражений.

**Решение 2** (сортировка деревом).

Нарисуем «полное двоичное дерево» — картинку, в которой снизу один кружок, из него выходят стрелки в два других, из каждого —
в два других и так далее:

<figure><img src="image_44.png" /></figure>

Будем говорить, что стрелки ведут «от отцов к сыновьям»: у каждого кружка два сына и один отец (если кружок не в самом верху или низу). Предположим для простоты, что количество подлежащих сортировке чисел есть степень двойки, и они могут заполнить один из рядов целиком. Запишем их туда. Затем заполним часть дерева под ними по правилу:

число в кружке = минимум из чисел в кружках-сыновьях

Тем самым в корне дерева (нижнем кружке) будет записано минимальное число во всем массиве.

Изымем из сортируемого массива минимальный элемент. Для этого его надо вначале найти. Это можно сделать, идя от корня: от отца переходим к тому сыну, где записано то же число. Изъяв минимальный элемент, заменим его символом $+\infty$ и скорректируем более низкие ярусы (для этого надо снова пройти путь к корню). При этом считаем, что $\min(t, +\infty) = t$. Тогда в корне появится второй по величине элемент, мы изымаем его, заменяя бесконечностью и корректируя дерево. Так постепенно мы изымем все элементы в порядке возрастания, пока в корне не останется бесконечность.

При записи этого алгоритма полезно нумеровать кружки числами 1, 2, ... — при этом сыновьями кружка номер $n$ являются кружки $2n$ и $2n + 1$. Подробное изложение этого алгоритма мы опустим, поскольку мы изложим более эффективный вариант, не требующий дополнительной памяти, кроме конечного числа переменных (в дополнение к сортируемому массиву).

Мы будем записывать сортируемые числа во всех вершинах дерева, а не только на верхнем уровне. Пусть $x[1]...x[n]$ — масив, подлежащий сортировке. Вершинами дерева будут числа от 1 до $n$; о числе $x[i]$ мы будем говорить как о числе, стоящем в вершине $i$. В процессе сортировки количество вершин дерева будет сокращаться. Число вершин текущего дерева будем хранить в пе-
ременной k. Таким образом, в процессе работы алгоритма массив x[1]...x[n] делится на две части: в x[1]...x[k] хранятся числа на дереве, а в x[k+1]...x[n] хранится уже отсортированная в порядке возрастания часть массива — элементы, уже занявшие своё законное место.

На каждом шаге алгоритм будет изымать максимальный элемент дерева и помещать его в отсортированную часть, на освободившееся в результате сокращения дерева место.

Договоримся о терминологии. Вершинами дерева считаются числа от 1 до текущего значения переменной k. У каждой вершины s могут быть сыновья 2s и 2s+1. Если оба этих числа больше k, то сыновей нет; такая вершина называется листом. Если 2s = k, то вершина s имеет ровно одного сына (2s).

Для каждого s из 1...k рассмотрим «поддерево» с корнем в s: оно содержит вершину s и всех её потомков (сыновей, внуков и так далее — до тех пор, пока мы не выйдем из отрезка 1...k). Вершину s будем называть регулярной, если стоящее в ней число — максимальный элемент s-поддерева; s-поддерево назовём регулярным, если все его вершины регулярны. (В частности, любой лист образует регулярное одноэлементное поддерево.)

Заметим, что истинность утверждения «s-поддерево регулярно» за висит не только от s, но от текущего значения k.

Схема алгоритма такова:

```
k:= n
...Сделать 1-поддерево регулярным;
{x[1],...,x[k] <= x[k+1] <=..<= x[n]; 1-поддерево регулярно,
в частности, x[1] - максимальный элемент среди x[1]..x[k]}
while k <> 1 do begin
    ...обменять местами x[1] и x[k];
    k := k - 1;
    {x[1],...,x[k-1] <= x[k] <=...<= x[n]; 1-поддерево
     регулярно везде, кроме, возможно, самого корня }
    ...восстановить регулярность 1-поддерева всюду
end;
```

В качестве вспомогательной процедуры нам понадобится процедура восстановления регулярности s-поддерева в корне. Вот она:

```
{s-поддерево регулярно везде, кроме, возможно, корня}
t := s;
{s-поддерево регулярно везде, кроме, возможно, вершины t}
```
```pascal
while ((2*t+1 <= k) and (x[2*t+1] > x[t])) or
    ((2*t <= k) and (x[2*t] > x[t])) do begin
    if (2*t+1 <= k) and (x[2*t+1] >= x[2*t]) then begin
        ...обменять x[t] и x[2*t+1];
        t := 2*t + 1;
    end else begin
        ...обменять x[t] и x[2*t];
        t := 2*t;
    end;
end;
```

Чтобы убедиться в правильности этой процедуры, посмотрим на неё повнимательнее. Пусть в s-поддереве все вершины, кроме разве что вершины t, регулярны. Рассмотрим сыновей вершины t. Они регулярны, и потому содержат наибольшие числа в своих поддеревьях. Таким образом, на роль наибольшего числа в t-поддереве могут претендовать число в самой вершине t и числа в её сыновьях. (В первом случае вершина t регулярна, и всё в порядке.) В этих терминах цикл можно записать так:

```pascal
while наибольшее число не в t, а в одном из сыновей do begin
    if оно в правом сыне then begin
        поменять t с её правым сыном; t:= правый сын
    end else begin {наибольшее число - в левом сыне}
        поменять t с её левым сыном; t:= левый сын
    end
end
```

После обмена вершина t становится регулярной (в неё попадает максимальное число t-поддерева). Не принявший участия в обмене сын остаётся регулярным, а принявший участие может и не быть регулярным. В остальных вершинах s-поддерева не изменились ни числа, ни поддеревья их потомков (разве что два элемента поддерева переставились), так что регулярность не нарушилась.

Эта же процедура может использоваться для того, чтобы сделать 1-поддерево регулярным на начальной стадии сортировки:

```pascal
k := n; u := n;
{все s-поддеревья с s>u регулярны}
while u<0 do begin
    {u-поддерево регулярно везде, кроме разве что корня}
    ...восстановить регулярность u-поддерева в корне;
    u:=u-1;
end;
```
Теперь запишем процедуру сортировки на паскалe (предполагая,
что $n$ — константа, $x$ имеет тип $arr = array [1..n] of integer$).

procedure sort (var x: arr);
  var u, k: integer;
  procedure exchange(i, j: integer);
    var tmp: integer;
    begin
      tmp := x[i];
      x[i] := x[j];
      x[j] := tmp;
    end;
  procedure restore (s: integer);
    var t: integer;
    begin
      t:=s;
      while ((2*t+1 <= k) and (x[2*t+1] > x[t])) or
             ((2*t <= k) and (x[2*t] > x[t])) do begin
                 if (2*t+1 <= k) and (x[2*t+1] >= x[2*t]) then begin
                   exchange (t, 2*t+1);
                   t := 2*t+1;
                 end else begin
                   exchange (t, 2*t);
                   t := 2*t;
                 end;
               end;
    end;
begin
  k:=n;
  u:=n;
  while u <> 0 do begin
    restore (u);
    u := u - 1;
  end;
  while k <> 1 do begin
    exchange (1, k);
    k := k - 1;
    restore (1);
  end;
end;

<figure><img src="image_45.png" /></figure>

Несколько замечаний.

Метод, использованный при сортировке деревом, бывает полезным
в других случаях. (См. в главе 6 (Типы данных) об очереди с приори-
тетами.)
Сортировка слиянием хороша тем, что она на требует, чтобы весь
сортируемый массив помещался в оперативной памяти. Можно сначала
отсортировать такие куски, которые помещаются в памяти (например,
с помощью дерева), а затем сливать полученные файлы.

Ещё один практически важный алгоритм сортировки (быстрая сор-
тировка Хоара) таков: чтобы отсортировать массив, выберем случай-
ный его элемент b, и разобьём массив на три части: меньшие b, равные b
и большие b. (Эта задача приведена в главе 1.) Теперь осталось отсор-
тировать первую и третью части: это делается тем же способом. Время
работы этого алгоритма — случайная величина; можно доказать, что
в среднем он работает не больше Cn log n. На практике — он один из
самых быстрых. (Мы ещё вернёмся к нему, приведя его рекурсивную
и нерекурсивную реализации.)

Наконец, отметим, что сортировка за время порядка Cn log n мо-
жет быть выполнена с помощью техники сбалансированных деревьев
(см. главу 14), однако программы тут сложнее и константа C довольно
велика.

4.3. Применения сортировки

4.3.1. Найдите количество различных чисел среди элементов дан-
ного массива. Число действий порядка n log n. (Эта задача уже была
в главе 1.)

Решение. Отсортируйте числа, а затем посчитайте количество раз-
личных, просматривая элементы массива по порядку. □

4.3.2. Дано n отрезков [a[i], b[i]] на прямой (i = 1... n). Найди-
те максимальное k, для которого существует точка прямой, покрытая
k отрезками («максимальное число слоёв»). Число действий — порядка
n log n.

Решение. Упорядочим все левые и правые концы отрезков вместе
(при этом левый конец считается меньше правого конца, расположен-
ного в той же точке прямой). Далее двигаемся слева направо, считая
число слоёв. Встреченный левый конец увеличивает число слоёв на 1,
правый — уменьшает. Отметим, что примыкающие друг к другу от-
резки обрабатываются правильно: сначала идёт левый конец (правого
отрезка), а затем — правый (левого отрезка). □

4.3.3. Дано n точек на плоскости. Укажите (n - 1)-звенную неса-
мопересекающуюся незамкнутую ломаную, проходящую через все эти
точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Число действий порядка $n \log n$.

**Решение.** Упорядочим точки по х-координате, а при равных х-координатах — по у-координате. В таком порядке и можно проводить ломаную. ☐

### 4.3.4. Та же задача, если ломаная должна быть замкнутой.

**Решение.** Возьмём самую левую точку (то есть точку с наименьшей х-координатой) и проведём из неё лучи во все остальные точки. Теперь упорядочим эти лучи снизу вверх, а точки на одном луче упорядочим по расстоянию от начала луча (это делается для всех лучей, кроме нижнего и верхнего). Ломаная выходит из выбранной (самой левой) точки по нижнему лучу, затем по всем остальным лучам (в описанном порядке) и возвращается по верхнему лучу. ☐

### 4.3.5. Дано $n$ точек на плоскости. Постройте их выпуклую оболочку — минимальную выпуклую фигуру, их содержащую. (Резиновое колечко, натянутое на вбитые в доску гвозди — их выпуклая оболочка.) Число операций порядка $n \log n$.

> [Указание. Упорядочим точки — годится любой из порядков, использованных в двух предыдущих задачах. Затем, рассматривая точки по очереди, будем строить выпуклую оболочку уже рассмотренных точек. (Для хранения выпуклой оболочки полезно использовать дек, см. главу 6. Впрочем, при упорядочении точек по углам это излишне.)] ☐

### 4.3.6. На прямой дано $n$ точек. Найдите минимальное число отрезков длины 1, которые покрывают все эти точки. Число операций порядка $n \log n$.

> [Указание. Упорядочим все точки; один из отрезков должен покрывать последнюю $x[n]$, поскольку справа ничего нет, его правый конец можно считать равным $x[n]$, и задача сводится к меньшему числу точек (выбросим те, которые покрыты).] ☐

### 4.3.7. На прямой дано $n$ отрезков $[a[i], b[i]]$ ($i = 1, ..., n$). Какое наибольшее число непересекающихся (и не имеющих общих концов) отрезков можно выбрать среди них? Число операций порядка $n \log n$.

> [Указание. Можно упорядочить правые концы отрезков и рассмотреть два случая: последний отрезок выбран или нет.] ☐
### 4.4. Нижние оценки для числа сравнений при сортировке

Пусть имеется $n$ различных по весу камней и весы, которые позволяют за одно взвешивание определить, какой из двух выбранных нами камней тяжелее. (В программистских терминах: мы имеем до-ступ к функции `тяжелее(i,j:1..n):boolean`.) Надо упорядочить кам-ни по весу, сделав как можно меньше взвешиваний (вызовов функции `тяжелее`).

Разумеется, число взвешиваний зависит не только от выбранного нами алгоритма, но и от того, как оказались расположены камни. Слож-ностью алгоритма назовём число взвешиваний при наихудшем расположении камней.

#### 4.4.1. Докажите, что сложность произвольного алгоритма сортировки $n$ камней не меньше $\log_2 n!$ (где $n! = 1 \cdot 2 \cdot \dots \cdot n$).

**Решение.** Пусть имеется алгоритм сложности не более $d$. Для каждого из $n!$ возможных расположений камней запротоколируем результата-ты взвешиваний (обращений к функции `тяжелее`); их можно записать в виде последовательности из не более чем $d$ нулей и единиц. Для еди-нообразия дополним последовательность нулями, чтобы её длина стала равной $d$. Тем самым у нас имеется $n!$ последовательностей из $d$ нулей и единиц. Все эти последовательности разные — иначе наш алгоритм дал бы одинаковые ответы для разных порядков (и один из ответов был бы неправильным). Получаем, что $2^d \ge n!$ — что и требовалось доказать. $\square$

Другой способ объяснить то же самое — рассмотреть дерево вариантов, возникающее в ходе выполнения алгоритма, и сослаться на то, что дерево высоты $d$ не может иметь более $2^d$ листьев.

Несложно заметить, что $\log_2 n! \ge cn \log n$ при подходящем $c > 0$, скольку в сумме

$$ \log n! = \log 1 + \log 2 + \log 3 + \dots + \log n $$

вторая половина слагаемых не меньше $\log_2(n/2) = \log_2 n - 1$ каждое.

Тем самым любой алгоритм сортировки, использующий только сравнения элементов массива и их перестановки, требует не менее $cn \log n$ действий, так что наши алгоритмы близки к оптимальным. Однако алгоритм сортировки, использующий другие операции, может действовать и быстрее. Вот один из примеров.
4.4.2. Имеется массив целых чисел $a[1]...a[n]$, причём все числа неотрицательны и не превосходят $m$. Отсортируйте этот массив; число действий порядка $m+n$.

**Решение.** Для каждого числа от 0 до $m$ подсчитываем, сколько раз оно встречается в массиве. После этого исходный массив можно стереть и заполнить заново в порядке возрастания, используя сведения о кратности каждого числа. $\square$

Отметим, что этот алгоритм не переставляет числа в массиве, как большинство других, а «записывает их туда заново».

Есть также метод сортировки, в котором последовательно проводится ряд «частичных сортировок» по отдельным битам. Начнём с такой задачи.

4.4.3. В массиве $a[1]...a[n]$ целых чисел переставьте элементы так, чтобы чётные числа шли перед нечётными (не меняя взаимный порядок в каждой из групп).

**Решение.** Сначала спишем (во вспомогательный массив) все чётные, а потом — все нечётные. $\square$

4.4.4. Имеется массив из $n$ чисел от 0 до $2^k - 1$, каждое из которых мы будем рассматривать как $k$-битовое слово из нулей и единиц. Используя проверки «*i*-й бит равен 0» и «*i*-й бит равен 1» вместо сравнений, отсортируйте все числа за время порядка $nk$.

**Решение.** Отсортируем числа по последнему биту (см. предыдущую задачу), затем по предпоследнему и так далее. В результате они будут отсортированы. В самом деле, индукцией по *i* легко доказать, что после *i* шагов любые два числа, отличающиеся только в *i* последних битах, идут в правильном порядке. (Вариант: после *i* шагов *i*-битовые концы чисел идут в правильном порядке.) $\square$

Аналогичный алгоритм может быть применён для *m*-ичной системы счисления вместо двоичной. При этом полезна такая вспомогательная задача:

4.4.5. Даны $n$ чисел и функция $f$, принимающая (на них) значения $1...m$. Требуется переставить числа в таком порядке, чтобы значения функции $f$ не убывали (сохраняя порядок для чисел с равными значениями $f$). Число действий порядка $m+n$.

[Указание. Завести $m$ списков суммарной длины $n$ (как это сделать, см. в главе 6 о типах данных) и помещать в *i*-й список числа, для которых значение функции $f$ равно *i*. Вариант: посчитать для всех *i*, сколько
имеется чисел $x$ с $f(x) = i$, после чего легко определить, с какого места нужно начинать размещать числа $x$ с $f(x) = i$. ☐

4.4.6. Даны $n$ целых чисел в диапазоне от 1 до $n^2$. Как отсортировать их, сделав порядка $n$ действий? ☐

### 4.5. Родственные сортировке задачи

4.5.1. Какова минимально возможная сложность (число сравнений в наихудшем случае) алгоритма отыскания самого тяжёлого из $n$ камней?

**Решение.** Очевидный алгоритм с инвариантом «найден самый тяжёлый камень среди первых $i$» требует $n-1$ сравнений. Алгоритма меньшей сложности нет. Это вытекает из следующего более сильного утверждения. ☐

4.5.2. Эксперт хочет убедить суд, что данный камень — самый тяжёлый среди $n$ камней, сделав менее $n-1$ взвешиваний. Докажите, что это невозможно. (Веса камней неизвестны суду, но известны эксперту.)

**Решение.** Изобразим камни точками, а взвешивания — линиями между ними. Получим граф с $n$ вершинами и менее чем $n-1$ рёбрами. Такой граф несвязен (добавление каждого следующего ребра уменьшает число связных компонент не более чем на 1). Поэтому суд ничего не знает относительно соотношения весов камней в различных связных компонентах и может допустить, что самый тяжёлый камень — в любой из них.

Более простое объяснение: будем следить за тем, сколько камней к данному моменту не «проиграли» (то есть не оказались легче других). Вначале их $n$; при каждом взвешивании проигрывает только один камень, а если есть двое не проигравших никому, любой из них может (с точки зрения суда) оказаться самым тяжёлым. ☐

Разница между этой задачей и предыдущей: в этой задаче мы доказываем, что $n-2$ взвешиваний не достаточно не только для нахождения самого тяжёлого, но даже для того, чтобы убедиться, что данный камень является таковым — если предположительный ответ известен. (В случае сортировки, зная предположительный ответ, мы можем убедиться в его правильности, сделав всего $n-1$ сравнений — каждый сравниваем со следующим по весу. Напомним, что сортировка требует в худшем случае значительно больше сравнений.)
**4.5.3.** Докажите, что можно найти самый лёгкий и самый тяжёлый из $2n$ камней (одновременно), сделав $3n-2$ взвешиваний.

**Решение.** Разобьём камни произвольным образом на $n$ пар и сравним камни в каждой паре ($n$ взвешиваний). Отложим отдельно «победителей» (более тяжёлых в своей паре) и «проигравших» (более лёгких). Ясно, что самый лёгкий камень надо искать среди проигравших ($n-1$ сравнений), а самый тяжёлый — среди победителей (ещё $n-1$ сравнений). □

**4.5.4.** Докажите, что не существует алгоритма, позволяющего гарантированно найти самый лёгкий и самый тяжёлый среди $2n$ камней (одновременно), сделав менее $3n-2$ взвешиваний.

**Решение.** Пусть такой алгоритм существует. Наблюдая за его применением к какой-то группе из $2n$ камней, мы будем следить за четырьмя параметрами. А именно, мы будем смотреть, сколько камней

(а) кому-то уже проиграли, а у кого-то уже выиграли;

(б) кому-то уже проиграли, но ещё ни у кого не выиграли;

(с) у кого-то уже выиграли, но ещё никому не проиграли;

(д) ни у кого не выиграли и никому не проиграли (то есть ни с кем не сравнивались).

(Напомним, что выигравшим в сравнении мы считаем более тяжёлый камень.) Камни типа (а), очевидно, не могут уже оказаться ни самыми лёгкими, ни самыми тяжёлыми, каковы бы ни были результаты дальнейших сравнений. Любой камень типа (b) имеет шанс оказаться самым лёгким (в самом деле, его можно произвольно облегчить, не меняя результатов уже выполненных сравнений), но уже не может быть самым тяжёлым; для камней типа (с) наоборот. Наконец, любой камень типа (d) может быть и самым лёгким, и самым тяжёлым.

Обозначим через $a, b, c, d$ количества камней в соответствующих категориях и проследим, как меняются эти параметры при очередном сравнении в зависимости от того, камни какого типа сравниваются и с каким результатом (см. таблицу на следующей странице). Последний столбец таблицы показывает, как меняется величина $s = b + c + (3/2)d$ (которую можно рассматривать в качестве меры «оставшейся работы»: камень, про который не известно ничего, с точки зрения этой меры в полтора раза сложнее камня, для которого есть односторонняя оценка). Изначально $s = 3n$, а в конце $s = 2$ (про все камни, кроме двух, известно, что они относятся к категории (а)). Из таблицы видно, что при любом взвешивании есть «неудачный исход», при котором $s$ уменьшается не более чем на единицу. Такие исходы действительно возможны
<table><thead><tr><th>сравнение</th><th>a</th><th>b</th><th>c</th><th>d</th><th>b+c+(3/2)d</th></tr></thead><tbody><tr><td>a-a</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>a > b</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>a < b</td><td>+1</td><td>-1</td><td>0</td><td>0</td><td>-1</td></tr><tr><td>a < c</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>a > c</td><td>+1</td><td>0</td><td>-1</td><td>0</td><td>-1</td></tr><tr><td>a > d</td><td>0</td><td>+1</td><td>0</td><td>-1</td><td>-1/2</td></tr><tr><td>a < d</td><td>0</td><td>0</td><td>+1</td><td>-1</td><td>-1/2</td></tr><tr><td>b-b</td><td>+1</td><td>-1</td><td>0</td><td>0</td><td>-1</td></tr><tr><td>b < c</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>b > c</td><td>+2</td><td>-1</td><td>-1</td><td>0</td><td>-2</td></tr><tr><td>b < d</td><td>0</td><td>0</td><td>+1</td><td>-1</td><td>-1/2</td></tr><tr><td>b > d</td><td>+1</td><td>0</td><td>0</td><td>-1</td><td>-3/2</td></tr><tr><td>c-c</td><td>+1</td><td>0</td><td>-1</td><td>0</td><td>-1</td></tr><tr><td>c < d</td><td>+1</td><td>0</td><td>0</td><td>-1</td><td>-3/2</td></tr><tr><td>c > d</td><td>0</td><td>+1</td><td>0</td><td>-1</td><td>-1/2</td></tr><tr><td>d-d</td><td>0</td><td>+1</td><td>+1</td><td>-2</td><td>-1</td></tr></tbody></table>

(не противоречат результатам предыдущих взвешиваний): при сравнении b-камня и c-камня может оказаться, что c-камень тяжелее (его вес не ограничен сверху предыдущими взвешиваниями), а при сравнении с участием d-камня результат может быть любым, поскольку про d-камень ничего не известно. (Кроме того, можно заметить, что если один из исходов взвешивания невозможен, то это взвешивание вообще излишне и его можно не делать.) А если исходы всех взвешиваний неудачны, то уменьшение s с 3n до 2 потребует как минимум 3n - 2 взвешиваний, что и требовалось доказать. □

**4.5.5.** Дано $n$ различных по весу камней. Найдите самый тяжёлый и второй по весу камни, сделав не более $n + [\log_2 n] - 2$ взвешиваний ($[\log_2 n]$ — наименьшее целое $k$, при котором $2^k \ge n$).

**Решение.** Сначала найдём победителя (самый тяжёлый камень), а потом будем искать второй по весу. Ясно, что второго можно искать лишь среди тех, кто проиграл лично победителю (проигравшие кому-то ещё легче сразу двух камней). Если определять победителя в турнире по олимпийской системе (все делятся на пары, проигравшие выбывают, потом снова делятся на пары и так далее), то для $2^k$ участников понадобится $k$ раундов, а для $n$ участников — $[\log_2 n]$ раундов. В камедой игре турнира выбывает один участник, поэтому всего будет $n - 1$
игр для определения победителя и ещё $\lfloor \log_2 n \rfloor - 1$ в турнире за второе место среди проигравших победителю. $\square$

**4.5.6. Докажите, что никакой алгоритм нахождения самого тяжёлого и второго по весу среди $n$ камней не может гарантированно сделать это менее чем за $n + \lfloor \log_2 n \rfloor - 2$ звешиваний.**

**Решение.** Пусть дан такой алгоритм. В каждый момент его исполнения рассмотрим число $k_i$ камней-участников, проигравших не менее $i$ игр-сравнений. (Косвенные проигрыши — если $a$ проиграл $b$, а $b$ проиграл $c$, — не учитываются.) Легко понять, что сумма $k_i$ по всем $i$ равна числу игр, так как после каждой игры одно из $k_i$ увеличивается на единицу.

Поэтому достаточно показать, что каков бы ни был алгоритм, при неудачных для него результатах игр будет выполнено неравенство $k_1 + k_2 \ge n + \lfloor \log_2 n \rfloor - 2$. Будем называть «лидерами» тех участников, которые ещё никому не проиграли. В начале их $n$, а в конце остаётся только один лидер (поскольку любой из лидеров может быть победителем). Поэтому $k_1 \ge n - 1$ (все игроки, кроме одного, кому-то проиграли). Объясним, как надо выбирать результаты матчей, чтобы добиться неравенства $k_2 \ge \lfloor \log_2 n \rfloor - 1$. Результат встречи двух не-лидеров может быть выбран любым. Если лидер встречается с не-лидером, то выигрывает лидер. При встрече двух лидеров выигрывает более опытный, то есть тот, кто выиграл к этому моменту больше игр (при равенстве — любой).

Чтобы доказать, что в этом случае выполнено искомое неравенство на $k_2$, введём отношения подчинения, считая при этом, что каждый игрок в любой момент игры подчинён ровно одному лидеру. В начале каждый сам себе лидер и подчинён только себе. При встрече лидера с не-лидером (или двух не-лидеров) подчинение не меняется; при встрече двух лидеров проигравший и все его подчинённые переподчиняются выигравшему.

Легко доказать по индукции, что если лидер выиграл $k$ игр, то группа его подчинённых (включая его самого) содержит не более $2^k$ человек. Вначале $k=0$ и в его группе только он сам. Если лидер выиграл $k$ игр и побеждает лидера, выигравшего не более $k$ игр, то в каждой из групп не более $2^k$ игроков, а в объединении не более $2^{k+1}$ игроков.

Следовательно, по окончании турнира лидер выиграл не менее $\lfloor \log_2 n \rfloor$ игр, поскольку в его группе все $n$ игроков. Все побеждённые им, кроме второго по силе игрока, проиграли ещё кому-то (иначе почему мы уверены, что они не вторые по силе?). Отсюда и получается требуемая оценка на $k_2$. $\square$
**4.5.7.** Докажите, что оценка предыдущей задачи остаётся в силе, если требуется найти лишь второй по весу камень, а самый тяжёлый искать не обязательно.

[Указание. Если по окончанию турнира определился второй по силе игрок, то он кому-то проиграл (откуда мы знаем иначе, что он не первый?), и тем самым известен и победитель.] ☐

**4.5.8.** Дано $n$ различных по весу камней и число $k$ (от 1 до $n$). Требуется найти $k$-й по весу камень, сделав не более $Cn$ взвешиваний, где $C$ — некоторая константа, не зависящая от $k$ и $n$.

**Замечание.** Сортировка позволяет сделать это за $Cn \log n$ взвешиваний. Указание к этой (трудной) задаче приведено в главе про рекурсию. ☐

Следующая задача имеет неожиданно простое решение.

**4.5.9.** Имеется $n$ одинаковых на вид камней, некоторые из которых на самом деле различны по весу. Имеется прибор, позволяющий по двум камням определить, одинаковы они или различны (но не говорящий, какой тяжелее). Известно, что среди этих камней большинство (более $n/2$) одинаковых. Сделав не более $n$ взвешиваний, найдите хотя бы один камень из этого большинства. (Предостережение. Если два камня одинаковые, это не гарантирует их принадлежности к большинству.)

[Указание. Если найдены два различных камня, то их оба можно выбросить — хотя бы один из них плохой и большинство останется большинством.]

**Решение.** Программа просматривает камни по очереди, храня в пе-ременной $i$ число просмотренных камней. (Считаем камни пронумерованными от 1 до $n$.) Помимо этого программа хранит номер «текущего кандидата» $c$ и его «кратность» $k$. Смысл этих названий объясняется инвариантом (И):

если к непросмотренным камням (с номерами $i+1...n$) добрались бы $k$ копий с-го камня, то наиболее частым среди них был бы такой же камень, что и для исходного массива.

Получаем такую программу:

```pascal
k:=0; i:=0;
{(И)}
while i<n do begin
  if k=0 then begin
```
```pascal
k:=1; c:=i+1; i:=i+1;
end else if (i+1-й камень одинаков с с-ым) then begin
  i:=i+1; k:=k+1;
  {заменяем материальный камень идеальным}
end else begin
  i:=i+1; k:=k-1;
  {выкидываем один материальный и один идеальный камень}
end;
end;
```
искомым является с-ый камень

**Замечание.** Поскольку во всех трёх вариантах выбора стоит команда `i:=i+1`, её можно вынести наружу. ☐

Заметим также, что эта программа гарантирует отыскание наиболее частого камня, лишь если он составляет большинство.

Следующая задача не имеет на первый взгляд никакого отношения к сортировке.

### 4.5.10. Имеется квадратная таблица a[1..n, 1..n]. Известно, что для некоторого i строка с номером i заполнена одними нулями, а столбец с номером i — одними единицами (за исключением их пересечения на диагонали, где стоит неизвестно что). Найдите такое i (оно, очевидно, единственно). Число действий порядка n. (Заметим, что это существенно меньше числа элементов в таблице.)

> [Указание. Рассмотрите a[i][j] как результат «сравнения» i с j и вспомните, что самый тяжёлый из n камней может быть найден за n сравнений. (Заметим, что таблица может не быть «транзитивной», но всё равно при «сравнении» двух элементов один из них отпадает.)] ☐
# 5. КОНЕЧНЫЕ АВТОМАТЫ И ОБРАБОТКА ТЕКСТОВ

## 5.1. Составные символы, комментарии и т. п.

5.1.1. В тексте возведение в степень обозначалось двумя идущими подряд звёздочками. Решено заменить это обозначение на ˇ (так что, к примеру, x**y заменится на x^y). Как это проще всего сделать? Исходный текст читается символ за символом, получающийся текст требуется печатать символ за символом.

**Решение.** В каждый момент программа находится в одном из двух состояний: «основное» и «после» (звёздочки):

<table><thead><tr><td>Состояние</td><td>Очередной входной символ</td><td>Новое состояние</td><td>Действие</td></tr></thead><tbody><tr><td>основное</td><td>*</td><td>после</td><td>нет</td></tr><tr><td>основное</td><td>x ≠ *</td><td>основное</td><td>печатать x</td></tr><tr><td>после</td><td>*</td><td>основное</td><td>печатать ˇ</td></tr><tr><td>после</td><td>x ≠ *</td><td>основное</td><td>печатать *, x</td></tr></tbody></table>

Если в конце текста программа оказывается в состоянии «после», то следует напечатать звёздочку (и кончить работу). ☐

**Замечание.** Наша программа заменяет *** на ˇ* (но не на *^). В условии задачи мы не оговаривали деталей, как это часто делается — предполагается, что программа «должна действовать разумно». В данном случае, пожалуй, самый простой способ объяснить, как программа действует — это описать её состояния и действия в них.

5.1.2. Напишите программу, удаляющую из текста все подслова вида abc. ☐
5.1.3. В паскале комментарии заключаются в фигурные скобки:

```
begin {начало цикла}
i:=i+1; {увеличиваем i на 1}
```

Напишите программу, которая удаляла бы комментарии и вставляла бы вместо исключённого комментария пробел (чтобы `1{один}2` превратилось не в `12`, а в `1 2`).

**Решение.** Программа имеет два состояния: «основное» и «внутри» (комментария).

<table><thead><tr><th>Состояние</th><th>Очередной входной символ</th><th>Новое состояние</th><th>Действие</th></tr></thead><tbody><tr><td>основное</td><td>{</td><td>внутри</td><td>нет</td></tr><tr><td>основное</td><td>x ≠ {</td><td>основное</td><td>печатать x</td></tr><tr><td>внутри</td><td>}</td><td>основное</td><td>печатать пробел</td></tr><tr><td>внутри</td><td>x ≠ }</td><td>внутри</td><td>нет</td></tr></tbody></table>

<figure><img src="image_46.png" /></figure>

**Замечание.** Эта программа не воспринимает вложенные комментарии: строка вроде

`{{комментарий внутри} комментария}`

превратится в

`комментария}`

(в начале стоят два пробела). Обработка вложенных комментариев конечным автоматом невозможно (нужно «помнить число скобок» — а произвольное натуральное число не помещается в конечную память).

5.1.4. В паскалевских программах бывают также строки, заключённые в кавычки. Если фигурная скобка встречается внутри строки, то она не означает начала или конца комментария. В свою очередь, кавычки в комментарии не означает начала или конца строки. Как изменить программу, чтобы это учесть?

[Указание. Состояний будет три: основное, внутри комментария, внутри строки.]

<figure><img src="image_47.png" /></figure>

5.1.5. Ещё одна возможность многих реализаций паскаля — это комментарии вида

`i:=i+1; (* here i is increased by 1 *)`

при этом закрывающая скобка должна соответствовать открывающей (то есть `{...*}` не разрешается). Как удалять такие комментарии?

<figure><img src="image_48.png" /></figure>
## 5.2. Ввод чисел

Пусть десятичная запись числа подаётся на вход программы символ за символом. Мы хотим «прочесть» это число (поместить в переменную типа real его значение). Кроме того, надо сообщить об ошибке, если число записано неверно.

Более конкретно, представим себе такую ситуацию. Последовательность символов на входе делится на прочитанную и оставшуюся части. Мы можем пользоваться функцией `Next:char`, которая даёт первый символ оставшейся части, а также процедурой `Move`, которая забирает первый символ из оставшейся части, переводя его в категорию прочитанных.

<table><tr><td>прочитанная часть</td><td>Next</td><td>?</td><td>?</td></tr></table>

Будем называть десятичной записью такую последовательность символов:

```
(0 или более пробелов) (1 или более цифр),
```

а также такую:

```
(0 или более пробелов) (1 или более цифр). (1 или более цифр).
```

Заметим, что согласно этому определению

1. .1 1.1 1.1

не являются десятичными записями. Сформулируем теперь задачу точно:

### 5.2.1. Прочтите из входной строки максимальную часть, которая может быть началом десятичной записи. Определите, является ли эта часть десятичной записью или нет.

### Решение.
Запишем программу на паскале (используя «перечислимый тип» для наглядности записи: переменная `state` может принимать одно из значений, указанных в скобках).

```
var state:
(Accept, Error, Initial, IntPart, DecPoint, FracPart);
```

```
state := Initial;
```
```pascal
while (state <> Accept) or (state <> Error) do begin
    if state = Initial then begin
        if Next = ' ' then begin
            state := Initial; Move;
        end else if Digit(Next) then begin
            state := IntPart; {после начала целой части}
            Move;
        end else begin
            state := Error;
        end;
    end else if state = IntPart then begin
        if Digit(Next) then begin
            state := IntPart; Move;
        end else if Next = '.' then begin
            state := DecPoint; {после десятичной точки}
            Move;
        end else begin
            state := Accept;
        end;
    end else if state = DecPoint then begin
        if Digit(Next) then begin
            state := FracPart; Move;
        end else begin
            state := Error; {должна быть хоть одна цифра}
        end;
    end else if state = FracPart then begin
        if Digit(Next) then begin
            state := FracPart; Move;
        end else begin
            state := Accept;
        end;
    end else if
        {такого быть не может}
        state:=Accept
    end;
end;
```

Заметьте, что присваивания `state:=Accept` и `state:=Error` не сопровождаются сдвигом (символ, который не может быть частью числа, не забирается). ☐

Приведённая программа не запоминает значение прочитанного числа.

### 5.2.2. Решите предыдущую задачу с дополнительным требованием: если прочитанный кусок является десятичной записью, то в переменную `val:real` следует поместить её значение.
**Решение.** При чтении дробной части переменная step хранит многоитель при следующей десятичной цифре.

```pascal
state := Initial; val:= 0;
while (state <> Accept) or (state <> Error) do begin
    if state = Initial then begin
        if Next = ' ' then begin
            state := Initial; Move;
        end else if Digit(Next) then begin
            state := IntPart; {после начала целой части}
            val := DigitValue(Next); Move;
        end else begin
            state := Error;
        end;
    end else if state = IntPart then begin
        if Digit(Next) then begin
            state := IntPart; val := 10*val + DigitVal(Next);
            Move;
        end else if Next = '.' then begin
            state := DecPoint; {после десятичной точки}
            step := 0.1;
            Move;
        end else begin
            state := Accept;
        end;
    end else if state = DecPoint then begin
        if Digit(Next) then begin
            state := FracPart;
            val := val + DigitVal(Next)*step; step := step/10;
            Move;
        end else begin
            state := Error; {должна быть хоть одна цифра}
        end;
    end else if state = FracPart then begin
        if Digit(Next) then begin
            state := FracPart;
            val := val + DigitVal(Next)*step; step := step/10;
            Move;
        end else begin
            state := Accept;
        end;
    end else if
        {такого быть не может}
        state = Error;
end;
```
5.2.3. Та же задача, если перед числом может стоять знак - или знак + (а может ничего не стоять).

Формат чисел в этой задаче обычно иллюстрируют такой картинкой:

<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /></figure>

5.2.4. Та же задача, если к тому же после числа может стоять показатель степени десяти, как в 254E-4 (= 0.0254) или в 0.123E+9 (= 123 000 000). Нарисуйте соответствующую картинку. ☐

<figure><img src="image_51.png" /></figure>

5.2.5. Что надо изменить в приведённой выше программе, чтобы разрешить пустые целую и дробную части (как в «1.», «.1» или да-же «.» — последнее число считаем равным нулю)? ☐

<figure><img src="image_52.png" /></figure>

Мы вернёмся к конечным автоматам в главе 10 (Сравнение с образцом).
# 6. ТИПЫ ДАННЫХ

## 6.1. Стеки

Пусть T — некоторый тип. Рассмотрим (отсутствующий в паскале) тип «стек элементов типа T». Его значениями являются последовательности значений типа T.

Операции:

* Сделать_пустым (var s: стек элементов типа T)

* Добавить (t:T; var s: стек элементов типа T)

* Взять (var t:T; var s: стек элементов типа T)

* Пуст (s: стек элементов типа T): boolean

* Вершина (s: стек элементов типа T): T

(Мы пользуемся обозначениями, напоминающими паскаль, хотя в паскале типа «стек» нет.) Процедура «Сделать_пустым» делает стек s пустым. Процедура «Добавить» добавляет t в конец последовательности s. Процедура «Взять» применима, если последовательность s непуста; она забирает из неё последний элемент, который становится значением переменной t. Выражение «Пуст(s)» истинно, если последовательность s пуста. Выражение «Вершина(s)» определено, если последовательность s непуста, и равно последнему элементу последовательности s.

Мы покажем, как моделировать стек в паскале и для чего он может быть нужен.

### Моделирование ограниченного стека в массиве

Будем считать, что количество элементов в стеке не превосходит некоторого числа n. Тогда стек можно моделировать с помощью двух
переменных:

Содержание: array [1..n] of T;

Длина: integer;

считая, что в стеке находятся элементы

Содержание [1], ..., Содержание [Длина].

* Чтобы сделать стек пустым, достаточно положить

Длина := 0

* Добавить элемент t:

{Длина < n}

Длина := Длина+1;

Содержание [Длина] :=t;

* Взять элемент в переменную t:

{Длина > 0}

t := Содержание [Длина];

Длина := Длина - 1;

* Стек пуст, если Длина = 0.

* Вершина стека равна Содержание [Длина].

Таким образом, вместо переменной типа стек в программе на па-
скале можно использовать две переменные Содержание и Длина. Можно
также определить тип stack, записав

const N = ...

type

stack = record

Содержание: array [1..N] of T;
Длина: integer;

end;

(Мы позволяем себе использовать имена переменных из русских букв,
хотя обычно паскаль этого не любит.) После этого могут быть — в со-
ответствии с правилами паскаля — описаны процедуры работы со сте-
ком. Например, можно написать

procedure Добавить (t: T; var s: stack);

begin

{s.Длина < N}
s.Длина := s.Длина + 1;
s.Содержание [s.Длина] := t;

end;
### Использование стека

Будем рассматривать последовательности открывающихся и закрывающихся круглых и квадратных скобок ( ) [ ]. Среди всех таких последовательностей выделим правильные — те, которые могут быть получены по таким правилам:

* пустая последовательность правильна.

* если А и В правильны, то и AB правильна.

* если А правильна, то [А] и (А) правильны.

**Пример.** Последовательности (), [[]], ([])[()][] правильны, а последовательности ], )(), (], ([]] — нет.

**6.1.1.** Проверьте правильность последовательности за время, не превосходящее константы, умноженной на её длину. Предполагается, что члены последовательности законодированы числами:

( 1
[ 2
) -1
] -2

**Решение.** Пусть a[1]...a[n] — проверяемая последовательность. Разрешим хранить в стеке открывающиеся круглые и квадратные скобки (т. е. 1 и 2).

Вначале стек делаем пустым. Далее просматриваем члены последовательности слева направо. Встретив открывающуюся скобку (круглую или квадратную), помещаем её в стек. Встретив закрывающуюся, проверяем, что вершина стека — парная её скобка; если это не так, то можно утверждать, что последовательность неправильна, если скобка парная, то заберём её (вершину) из стека. Последовательность правильна, если в конце стек оказывается пуст.

Сделать_пустым (s);
i := 0; Обнаружена_ошибка := false;
{прочитано i символов последовательности}
while (i < n) and not Обнаружена_ошибка do begin
  i := i + 1;
  if (a[i] = 1) or (a[i] = 2) then begin
    Добавить (a[i], s);
  end else begin {a[i] равно -1 или -2}
```pascal
if Пуст (s) then begin
  Обнаружена_ошибка := true;
end else begin
  Взять (t, s);
  Обнаружена_ошибка := (t <> - a[i]);
end;
end;
end;
Правильно := (not Обнаружена_ошибка) and Пуст (s);
```

Убедимся в правильности программы.

(1) Если последовательность построена по правилам, то программа даст ответ «да». Это легко доказать индукцией по построению правильной последовательности. Надо проверить для пустой, для последовательности АВ в предположении, что для А и В уже проверено, и, наконец, для последовательностей [А] и (А) — в предположении, что для А уже проверено. Для пустой очевидно. Для АВ действия программы происходят как для А и кончаются с пустым стеком; затем всё происходит как для В. Для [А] сначала помещается в стек открывающая квадратная скобка и затем всё идёт как для А — с той разницей, что в глубине стека лежит лишняя скобка. По окончании А стек становится пустым — если не считать этой скобки — а затем и совсем пустым. Аналогично для (А).

(2) Покажем, что если программа завершает работу с ответом «да», то последовательность правильна. Рассуждаем индукцией по длине последовательности. Проследим за состоянием стека в процессе работы программы. Если он в некоторый промежуточный момент пуст, то последовательность разбивается на две части, для каждой из которых программа даёт ответ «да»; остаётся воспользоваться предположением индукции и определением правильности. Пусть стек всё время непуст. Это значит, что положенная в него на первом шаге скобка будет вынута лишь на последнем шаге. Тем самым, первый и последний символы последовательности — это парные скобки, и последовательность имеет вид (А) или [А], а работа программы (кроме первого и последнего шагов) отличается от её работы на А лишь наличием лишней скобки на дне стека (раз её не вынимают, она никак не влияет на работу программы). Снова ссылаемся на предположение индукции и определение правильности. ☐

### 6.1.2. Как упростится программа, если известно, что в последовательности могут быть только круглые скобки?
**Решение.** В этом случае от стека остаётся лишь его длина, и мы фактически приходим к такому утверждению: последовательность круглых скобок правильна тогда и только тогда, когда в любом её начальном отрезке число закрывающихся скобок не превосходит числа открывающихся, а для всей последовательности эти числа равны. ☐

**6.1.3.** Реализуйте с помощью одного массива два стека, суммарное количество элементов в которых ограничено длиной массива; все действия со стеками должны выполняться за время, ограниченное константой, не зависящей от длины стеков.

**Решение.** Стеки должны расти с концов массива навстречу друг другу: первый должен занимать места

Содержание [1] ... Содержание [Длина1],

а второй —

Содержание [n] ... Содержание [n-Длина2+1]

(вершины обоих стеков записаны последними). ☐

**6.1.4.** Реализуйте k стеков с элементами типа T, общее количество элементов в которых не превосходит n, с использованием массивов суммарной длины $C(n+k)$, затрачивая на каждое действие со стеками (кроме начальных действий, делающих все стеки пустыми) время не более некоторой константы $C$. (Как говорят, общая длина массивов должна быть $O(m+n)$, а время на каждую операцию — $O(1)$.)

**Решение.** Применяемый метод называется «ссылочной реализацией». Он использует три массива:

Содержание: array [1..n] of T;
Следующий: array [1..n] of 0..n;
Вершина: array [1..k] of 0..n.

Удобно изображать массив **Содержание** как n ячеек с номерами 1...n, каждая из которых содержит элемент типа T. Массив **Следующий** изобразим в виде стрелок, проведя стрелку из i в j, если **Следующий**[i]=j. (Если **Следующий**[i]=0, стрелок из i не проводим.) **Содержимое** s-го стека ($s \in 1...k$) хранится так: вершина равна **Содержание**[Вершина[s]], остальные элементы s-го стека можно найти, идя по стрелкам — до тех пор, пока они не кончатся. При этом

$(s-й стек пуст) \Leftrightarrow Вершина[s]=0.$
Стрелочные траектории, выходящие из

Вершина [1], ..., Вершина [k]

(из тех, которые не равны 0) не должны пересекаться. Помимо них, нам понадобится ещё одна стрелочная траектория, содержащая все неиспользуемые в данный момент ячейки. Её начало мы будем хранить в переменной Свободная (равенство Свободная = 0 означает, что пустого места не осталось). Вот пример:

<figure><img src="image_53.png" /></figure>

Стеки: первый содержит p, t, q, a (a — вершина); второй содержит s, v (v — вершина).

```pascal
procedure Начать_работу; {Делает все стеки пустыми}
  var i: integer;
begin
  for i := 1 to k do begin
    Вершина [i] := 0;
  end;
  for i := 1 to n-1 do begin
    Следующий [i] := i+1;
  end;
  Следующий [n] := 0;
```
```
| Свободная:=1;
end;
```

```
function Есть_mесто: boolean;
begin
| Есть_mесто := (Свободная <> 0);
end;
```

```
procedure Добавить (t: T; s: integer);
| {Добавить t к s-му стеку}
var i: 1..n;
begin
| {Есть_mесто}
  i := Свободная;
  Свободная := Следующий [i];
  Следующий [i] := Вершина [s];
  Вершина [s] := i;
  Содержание [i] := t;
end;
```

```
function Пуст (s: integer): boolean;
| {с-ый стек пуст}
begin
| Пуст := (Вершина [s] = 0);
end;
```

```
procedure Взять (var t: T; s: integer);
| {взять из s-го стека в t}
var i: 1..n;
begin
| {not Пуст (s)}
  i := Вершина [s];
  t := Содержание [i];
  Вершина [s] := Следующий [i];
  Следующий [i] := Свободная;
  Свободная := i;
end;
```

```
function Вершина_стека (s: integer): T;
| {вершина s-го стека}
begin
| Вершина_стека := Содержание[Вершина[s]];
end;
```

<figure><img src="image_54.png" /></figure>
### 6.2. Очереди

Значениями типа «очередь элементов типа T», как и для стеков, являются последовательности значений типа T. Разница состоит в том, что берутся элементы не с конца, а с начала (а добавляются по-прежнему в конец).

Операции с очередями:

* Сделать пустой (var x: очередь элементов типа T);

* Добавить (t:T, var x: очередь элементов типа T);

* Взять (var t:T, var x: очередь элементов типа T);

* Пуста (x: очередь элементов типа T): boolean;

* Очередной (x: очередь элементов типа T): T.

При выполнении команды «Добавить» указанный элемент добавляется в конец очереди. Команда «Взять» выполняма, лишь если очередь непуста, и забирает из неё первый (положенный туда раньше всех) элемент, помещая его в t. Значением функции «Очередной» (определённой для непустой очереди) является первый элемент очереди.

Английские названия стеков — Last In First Out (последним вошёл — первым вышел), а очередей — First In First Out (первым вошёл — первым вышел). Сокращения: LIFO, FIFO.

#### Реализация очередей в массиве

**6.2.1. Реализуйте операции с очередью ограниченной длины так, чтобы количество действий для каждой операции было ограничено константой, не зависящей от длины очереди.**

**Решение.** Будем хранить элементы очереди в соседних элементах массива. Тогда очередь будет прирастать справа и убывать слева. Покольку при этом она может дойти до края, свернём массив в окружность.

**Введём массив**

Содержание: array [0..n-1] of T

и переменные

Первый: 0..n-1,

Длина : 0..n.
При этом элементами очереди будут

Содержание [Первый], Содержание [Первый+1], ..., Содержание [Первый+Длина-1],

где сложение выполняется по модулю $n$. (Предупреждение. Если вместо этого ввести переменные Первый и Последний, значения которых — вычеты по модулю $n$, то пустая очередь может быть спутана с очередью из $n$ элементов.)

Операции выполняются так:

Сделать пустой:

Длина := 0;
Первый := 0;

Добавить элемент:

{Длина < n}
Содержание [(Первый + Длина) mod n] := элемент;
Длина := Длина + 1;

Взять элемент:

{Длина > 0}
элемент := Содержание [Первый];
Первый := (Первый + 1) mod n;
Длина := Длина - 1;

Пуста:

Длина = 0

Очередной:

Содержание [Первый]

☐

6.2.2. (Сообщил А.Г. Кушниренко) Придумайте способ моделирования очереди с помощью двух стеков (и фиксированного числа переменных типа $T$). При этом отработка $n$ операций с очередью (начатых, когда очередь была пуста) должна требовать порядка $n$ действий.

**Решение.** Инвариант: стеки, составленные концами, образуют очередь. (Перечисляя элементы одного стека вглубь и затем элементы второго наружу, мы перечисляем все элементы очереди от первого до последнего.) Ясно, что добавление сводится к добавлению к одному из
стеков, а проверка пустоты — к проверке пустоты обоих стеков. Если мы хотим взять элемент, есть два случая. Если стек, где находится начало очереди, не пуст, то берём из него элемент. Если он пуст, то предварительно переписываем в него все элементы второго стека, меняя порядок (это происходит само собой при перекладывании из стека в стек) и сводим дело к первому случаю. Хотя число действий на этом шаге и не ограничено константой, но требование задачи выполнено, так как каждый элемент очереди может участвовать в этом процессе не более одного раза. ☐

#### 6.2.3. Деком называют структуру, сочетающую очередь и стек: класть и забирать элементы можно с обоих концов. Как реализовать дек ограниченного размера на базе массива так, чтобы каждая операция требовала ограниченного числа действий? ☐

#### 6.2.4. (Сообщил А.Г. Кушниренко.) Имеется дек элементов типа Т и конечное число переменных типа Т и целого типа. В начальном состоянии в деке некоторое число элементов. Составьте программу, после исполнения которой в деке остались бы те же самые элементы, а их число было бы в одной из целых переменных.

> [Указание. (1) Элементы дека можно циклически переставлять, выбирая с одного конца и помещая в другой. После этого, сделав столько же шагов в обратном направлении, можно вернуть всё на место. (2) Как понять, прошли мы полный круг или не прошли? Если бы какой-то элемент заведомо отсутствовал в деке, то можно было бы его подсунуть и ждать вторичного появления. Но таких элементов нет. Вместо этого можно для данного п выполнить циклический сдвиг на дважды, подсунув разные элементы, и посмотреть, появятся ли разные элементы через п шагов.] ☐

### Применение очередей

#### 6.2.5. Напечатайте в порядке возрастания первые n натуральных чисел, в разложение которых на простые множители входят только числа 2, 3, 5.

**Решение.** Введём три очереди x2, x3, x5, в которых будем хранить элементы, которые в 2 (3, 5) раз больше напечатанных, но ещё не напечатаны. Определим процедуру

```pascal
procedure напечатать_и_Добавить (t: integer);
begin
  writeln (t);
```
```
```
| Добавить (2*t, x2);
| Добавить (3*t, x3);
| Добавить (5*t, x5);
end;
```

Вот схема программы:

```pascal
...сделать x2, x3, x5 пустыми
напечатать_и_Добавить (1);
k := 1; { k - число напечатанных }
{инвариант: напечатано в порядке возрастания k минимальных
членов нужного множества; в очередях элементы, вдвое,
втрое и впятеро большие напечатанных, но не напечатанные,
расположенные в возрастащем порядке}
while k <> n do begin
    x := min (очередной(x2), очередной(x3), очередной(x5));
    напечатать_и_Добавить (x);
    k := k+1;
    ...взять x из тех очередей, где он был очередным;
end;
```

Пусть инвариант выполняется. Рассмотрим наименьший из ненапечатанных элементов множества; пусть это х. Тогда он делится нацело на одно из чисел 2, 3, 5, и частное также принадлежит множеству. Значит, оно напечатано. Значит, х находится в одной из очередей и, следовательно, является в ней первым (меньшие напечатаны, а элементы очередей не напечатаны). Напечатав х, мы должны его изъять и добавить его кратные.

Длины очередей не превосходят числа напечатанных элементов. ☐

Следующая задача связана с графами (к которым мы вернёмся в главе 9).

Пусть задано конечное множество, элементы которого называют вершинами, а также некоторое множество упорядоченных пар вершин, называемых рёбрами. В этом случае говорят, что задан ориентированный граф. Пару (p, q) называют ребром с началом p и концом q; говорят также, что оно выходит из вершины p и входит в вершину q. Обычно вершины графа изображают точками, а рёбра — стрелками, ведущими из начала в конец. (В соответствии с определением из данной вершины в данную ведёт не более одного ребра; возможны рёбра, у которых начало совпадает с концом.)

### 6.2.6. Известно, что ориентированный граф связан, т.е. из любой вершины можно пройти в любую по рёбрам. Кроме того, из каждой
вершины выходит столько же рёбер, сколько входит. Докажите, что существует замкнутый цикл, проходящий по каждому ребру ровно один раз. Составьте алгоритм отыскания такого цикла.

**Решение.** Змеёй будем называть непустую очередь из вершин, в которой любые две вершины соединены ребром графа (началом является та вершина, которая ближе к началу очереди). Стоящая в начале очереди вершина будет хвостом змеи, последняя — головой. На рисунке змея изобразится в виде цепи рёбер графа, стрелки ведут от хвоста к голове. Добавление вершины в очередь соответствует росту змеи с головы, взятие вершины — отрезанию кончика хвоста.

Вначале змея состоит из единственной вершины. Далее мы следуем такому правилу:

```pascal
while змея включает не все рёбра do begin
    if из головы выходит не входящее в змею ребро then begin
        удлинить змею этим ребром
    end else begin
        {голова змеи в той же вершине, что и хвост}
        отрезать конец хвоста и добавить его к голове
        {"змея откусывает конец хвоста"}
    end;
end;
```

Докажем, что мы достигнем цели.

(1) Идя по змее от хвоста к голове, мы входим в каждую вершину столько же раз, сколько выходим. Так как в любую вершину входит столько же рёбер, сколько выходит, то невозможность выйти означает, что голова змеи в той же точке, что и хвост.

(2) Змея не укорачивается, поэтому либо она охватит все рёбра, либо, начиная с некоторого момента, будет иметь постоянную длину. Во втором случае змея будет бесконечно «скользить по себе». Это возможно, только если из всех вершин змеи не выходит неиспользованных рёбер. В этом случае из связи следует, что змея проходит по всем рёбрам.

Замечание по реализации на паскале. Вершинами графа будем считать числа $1...n$. Для каждой вершины $i$ будем хранить число $Out[i]$ выходящих из неё рёбер, а также номера $Num[i][1],...,Num[i][Out[i]]$ тех вершин, куда эти рёбра ведут. В процессе построения змея будем выбирать первое свободное ребро. Тогда достаточно хранить для каждой вершины число выходящих из неё использованных рёбер — это будут рёбра, идущие в начале списка. □
**6.2.7. Докажите, что для всякого $n$ существует последовательность нулей и единиц длины $2^n$ со следующим свойством: если «свернуть её в кольцо» и рассмотреть все фрагменты длины $n$ (их число равно $2^n$), то мы получим все возможные последовательности нулей и единиц длины $n$. Постройте алгоритм отыскания такой последовательности, требующий не более $C^n$ действий для некоторой константы $C$**

[Указание. Рассмотрим граф, вершинами которого являются последовательности нулей и единиц длины $n-1$. Будем считать, что из вершины $x$ ведёт ребро в вершину $y$, если $x$ может быть началом, а $y$ — концом некоторой последовательности длины $n$. Тогда из каждой вершины входит и выходит два ребра. Цикл, проходящий по всем рёбрам, и даст требуемую последовательность.] ☐

**6.2.8. Реализуйте $k$ очередей с ограниченной суммарной длиной $n$, используя память $O(n+k) [= не более $C(n+k)$ для некоторой константы $C$], причём каждая операция (кроме начальной, делающей все очереди пустыми) должна требовать ограниченного константой числа действий.**

**Решение.** Действуем аналогично ссылочной реализации стеков: мы помним (для каждой очереди) первого, каждый участник очереди помнит следующего за ним (для последнего считается, что за ним стоит фиктивный элемент с номером 0). Кроме того, мы должны для каждой очереди знать последнего (если он есть) — иначе не удастся добавлять. Как и для стеков, отдельно есть цепь свободных ячеек. Заметим, что для пустой очереди информация о последнем элементе теряет смысл — но она и не используется при добавлении.

Содержание: array [1..n] of T;
Следующий: array [1..n] of 0..n;
Первый: array [1..k] of 0..n;
Последний: array [1..k] of 0..n;
Свободная : 0..n;

procedure Сделать_пустым;
  var i: integer;
begin
  for i := 1 to n-1 do begin
    Следующий [i] := i + 1;
  end;
  Следующий [n] := 0;
  Свободная := 1;
  for i := 1 to k do begin
```
| | Первый [i] := 0;
| |
end;
end;
```

```
function Есть_mесто: boolean;
begin
```

```
| Есть_mесто := Свободная <> 0;
end;
```

```
function Пуста (номер_очереди: integer): boolean;
begin
```

```
| Пуста := Первый [номер_очереди] = 0;
end;
```

```
procedure Взять (var t: T; номер_очереди: integer);
| var перв: integer;
begin
```

```
| {not Пуста (номер_очереди)}
| перв := Первый [номер_очереди];
| t := Содержание [перв]
| Первый [номер_очереди] := Следующий [перв];
| Следующий [перв] := Свободная;
| Свободная := перв;
end;
```

```
procedure Добавить (t: T; номер_очереди: integer);
| var нов, посл: 1..n;
begin
```

```
| {Есть_mесто }
| нов := Свободная; Свободная := Следующий [Свободная];
| {из списка свободного места изъят номер нов}
| if Пуста (номер_очереди) then begin
| | Первый [номер_очереди] := нов;
| | Последний [номер_очереди] := нов;
| | Следующий [нов] := 0;
| | Содержание [нов] := t;
| end else begin
| | посл := Последний [номер_очереди];
| | {Следующий [посл] = 0}
| | Следующий [посл] := нов;
| | Следующий [нов] := 0;
| | Содержание [нов] := t
| | Последний [номер_очереди] := нов;
| end;
| end;
```
```pascal
function Очередной (номер_очереди: integer): T;
begin
  Очередной := Содержание [Первый [номер_очереди]];
end;
```

### 6.2.9. Та же задача для деков вместо очередей.

[Указание. Дек — структура симметричная, поэтому надо хранить ссылки в обе стороны (вперёд и назад). При этом удобно к каждому деку добавить фиктивный элемент, замкнув его в кольцо, и точно такое же кольцо образовать из свободных позиций.]

В следующей задаче дек используется для хранения вершин выпуклого многоугольника.

### 6.2.10. На плоскости задано $n$ точек, пронумерованных слева направо (а при равных абсциссах — снизу вверх). Составьте программу, которая строит многоугольник, являющийся их выпуклой оболочкой, за $O(n)$ [= не более чем $Cn$] действий.

**Решение.** Будем присоединять точки к выпуклой оболочке одна за другой. Легко показать, что последняя присоединённая точка будет одной из вершин выпуклой оболочки. Эту вершину мы будем называть выделенной. Очередная присоединяемая точка видна из выделенной (почему?). Дополним наш многоугольник, выпустив из выделенной вершины «иглу», ведущую в присоединяемую точку. Получится вырожденный многоугольник, и остаётся ликвидировать в нём «впуклости».

<figure><img src="image_55.png" /></figure>

Будем хранить вершины многоугольника в деке в порядке обхода его периметра по часовой стрелке. При этом выделенная вершина является началом и концом (головой и хвостом) дека. Присоединение «иглы» теперь состоит в добавлении присоединяемой вершины в голову и в
хвост дека. Устранение впуклостей несколько более сложно. Назовём подхвостом и подподхвостом элементы дека, стоящие за его хвостом. Устранение впуклости у хвоста делается так:

```pascal
while по дороге из хвоста в подподхвост мы поворачиваем
    у подхвоста влево ("впускость") do begin
    выкинуть подхвост из дека
end
```

Таким же способом устраняется впускость у головы дека.

**Замечание.** Действия с подхвостом и подподхвостом не входят в определение дека, однако сводятся к небольшому числу манипуляций с деком (надо забрать три элемента с хвоста, сделать что надо и вернуть).

Ещё одно замечание. Есть два вырожденных случая: если мы вообще не поворачиваем у подхвоста (т. е. три соседние вершины лежат на одной прямой) и если мы поворачиваем на 180° (так бывает, если наш многоугольник есть двуугольник). В первом случае подхвост стоит удалить (чтобы в выпуклой оболочке не было лишних вершин), а во втором случае — обязательно оставить. ☐

### 6.3. Множества

Пусть T — некоторый тип. Существует много способов хранить (кочечные) множества элементов типа T; выбор между ними определяется типом T и набором требуемых операций.

**Подмножества множества $\{1...n\}$**

**6.3.1.** Как, используя память размера $O(n)$ [пропорциональную $n$], хранить подмножества множества $\{1...n\}$?

<table><thead><tr><td>Операции</td><td>Число действий</td></tr></thead><tbody><tr><td>Сделать пустым</td><td>Cn</td></tr><tr><td>Проверить принадлежность</td><td>C</td></tr><tr><td>Добавить</td><td>C</td></tr><tr><td>Удалить</td><td>C</td></tr><tr><td>Минимальный элемент</td><td>Cn</td></tr><tr><td>Проверка пустоты</td><td>Cn</td></tr></tbody></table>

**Решение.** Храним множество как array [1..n] of Boolean. ☐

<figure><img src="image_56.png" /></figure>
**6.3.2.** То же, но проверка пустоты должна выполняться за время C.

**Решение.** Храним дополнительно количество элементов. ☐

**6.3.3.** То же при следующих ограничениях на число действий:

<table><thead><tr><td>Операции</td><td>Число действий</td></tr></thead><tbody><tr><td>Сделать пустым</td><td>Cn</td></tr><tr><td>Проверить принадлежность</td><td>C</td></tr><tr><td>Добавить</td><td>C</td></tr><tr><td>Удалить</td><td>Cn</td></tr><tr><td>Минимальный элемент</td><td>C</td></tr><tr><td>Проверка пустоты</td><td>C</td></tr></tbody></table>

**Решение.** Дополнительно храним минимальный элемент множества. ☐

**6.3.4.** То же при следующих ограничениях на число действий:

<table><thead><tr><td>Операции</td><td>Число действий</td></tr></thead><tbody><tr><td>Сделать пустым</td><td>Cn</td></tr><tr><td>Проверить принадлежность</td><td>C</td></tr><tr><td>Добавить</td><td>Cn</td></tr><tr><td>Удалить</td><td>C</td></tr><tr><td>Минимальный элемент</td><td>C</td></tr><tr><td>Проверка пустоты</td><td>C</td></tr></tbody></table>

**Решение.** Храним минимальный, а для каждого — следующий и предыдущий по величине. ☐

### Множества целых чисел

В следующих задачах величина элементов множества не ограничена, но их количество не превосходит $n$.

**6.3.5.** Память $Cn$.

<table><thead><tr><td>Операции</td><td>Число действий</td></tr></thead><tbody><tr><td>Сделать пустым</td><td>C</td></tr><tr><td>Число элементов</td><td>C</td></tr><tr><td>Проверить принадлежность</td><td>Cn</td></tr><tr><td>Добавить новый (заведомо отсутствующий)</td><td>C</td></tr><tr><td>Удалить</td><td>Cn</td></tr><tr><td>Минимальный элемент</td><td>Cn</td></tr><tr><td>Взять какой-то элемент</td><td>C</td></tr></tbody></table>
**Решение.** Множество представляем с помощью переменных

a:array [1..n] of integer, k: 0..n;

множество содержит k элементов a[1],...a[k]; все они различны. По существу мы храним элементы множества в стеке (без повторений). С тем же успехом можно было бы воспользоваться очередью вместо стека. ☐

### 6.3.6. Память Cn.

<table><thead><tr><td>Операции</td><td>Число действий</td></tr></thead><tbody><tr><td>Сделать пустым</td><td>C</td></tr><tr><td>Проверить пустоту</td><td>C</td></tr><tr><td>Проверить принадлежность</td><td>C log n</td></tr><tr><td>Добавить</td><td>Cn</td></tr><tr><td>Удалить</td><td>Cn</td></tr><tr><td>Минимальный элемент</td><td>C</td></tr></tbody></table>

**Решение.** См. решение предыдущей задачи с дополнительным условием a[1] < ... < a[k]. При проверке принадлежности используем двоичный поиск. ☐

В следующей задаче полезно комбинировать разные способы.

### 6.3.7. Используя описанные способы представления множеств, найдите все вершины ориентированного графа, доступные из данной по рёбрам. (Вершины считаем числами 1...n.) Время не больше C·(общее число рёбер, выходящих из доступных вершин).

**Решение.** (Другое решение см. в главе о рекурсии, задача 7.4.6) Пусть num[i] — число рёбер, выходящих из i, а out[i][1],... ..., out[i][num[i]] — вершины, куда ведут рёбра из вершины i.

procedure Доступные (i: integer);
  {напечатать все вершины, доступные из i, включая i}
  var X: подмножество 1..n;
     P: подмножество 1..n;
     q, v, w: 1..n;
     k: integer;
begin
  ...сделать X, P пустыми;
  writeln (i);
  ...Добавить i к X, P;
  {(1) P = множество напечатанных вершин; P содержит i;
(2) напечатаны только доступные из i вершины;
(3) X - подмножество P;
(4) все напечатанные вершины, из которых выходит
ребро в ненапечатанную вершину, принадлежат X}
while X непусто do begin
...взять какой-нибудь элемент X в v;
for k := 1 to num [v] do begin
  w := out [v][k];
  if w не принадлежит P then begin
    writeln (w);
    добавить w в P;
    добавить w в X;
  end;
end;
end;
end;

Свойство (1) не нарушается, так как печать происходит одновременно с добавлением в P. Свойство (2): раз v было в X, то v доступно, поэтому w доступно. Свойство (3) очевидно. Свойство (4): мы удалили из X элемент v, но все вершины, куда из v идут рёбра, перед этим напечатаны. ☐

### 6.3.8. Покажите, что можно использовать и другой инвариант: P — напечатанные вершины; X ⊂ P; осталось напечатать вершины, доступные из X по ненапечатанным вершинам. ☐

Оценка времени работы. Заметим, что изъятые из X элементы больше туда не добавляются, так как они в момент изъятия (и, следовательно, всегда позже) принадлежат P, а добавляются только элементы не из P. Поэтому тело цикла while для каждой доступной вершины выполняется не более, чем по разу, при этом тело цикла for выполняется столько раз, сколько из вершины выходит рёбер.

Для X надо использовать представление со стеком или очередью (см. выше), для P — булевский массив. ☐

### 6.3.9. Решите предыдущую задачу, если требуется, чтобы доступные вершины печатались в таком порядке: сначала заданная вершина, потом её соседи, потом соседей (ещё не напечатанные) и т. д.

> [Указание. Так получится, если использовать очередь для хранения X в приведённом выше решении: докажите индукцией по k, что существует момент, в который напечатаны все вершины на расстоянии не больше k, а в очереди находятся все вершины, удалённые ровно на k.] ☐
Более сложные способы представления множеств будут разобраны в главах 13 (хеширование) и 14 (деревья).

### 6.4. Разные задачи

#### 6.4.1. Реализуйте структуру данных, которая имеет все те же операции, что массив длины $n$, а именно

* начать работу;

* положить в $i$-ю ячейку число $x$;

* узнать, что лежит в $i$-й ячейке;

а также операцию

* указать номер минимального элемента

(точнее, одного из минимальных элементов). Количество действий для всех операций должно быть не более $C \log n$, не считая операции «начать работу» (которая требует не более $Cn$ действий).

**Решение.** Используется приём, изложенный в разделе о сортировке деревом. Именно, надстроим над элементами массива как над листьями двоичное дерево, в каждой вершине которого храним минимум элементов соответствующего поддерева. Корректировка этой информации, а также прослеживание пути из корня к минимальному элементу требуют логарифмического числа действий. ☐

#### 6.4.2. Приоритетная очередь — это очередь, в которой важно не то, кто встал последним (порядок помещения в неё не играет роли), а кто главнее. Более точно, при помещении в очередь указывается приоритет помещаемого объекта (будем считать приоритеты целыми числами), а при взятии из очереди выбирается элемент с наибольшим приоритетом (или один из таких элементов). Реализуйте приоритетную очередь так, чтобы помещение и взятие элемента требовали логарифмического числа действий (от размера очереди).

**Решение.** Следуя алгоритму сортировки деревом (в его окончательном варианте), будем размещать элементы очереди в массиве $x[1..k]$, поддерживая такое свойство: $x[i]$ старше (имеет больший приоритет) своих сыновей $x[2i]$ и $x[2i+1]$, если таковые существуют — и, следовательно, всякий элемент старше своих потомков. (Сведения о приоритетах также хранятся в массиве, так что мы имеем дело с массивом пар (элемент, приоритет).) Удаление элемента с сохранением этого
свойства описано в алгоритме сортировки. Надо ещё уметь восстанав-
вливать свойство после добавления элемента в конец. Это делается так:

t:= номер добавленного элемента
{инвариант: в дереве любой предок приоритетнее потомка,
если этот потомок - не t}
while t - не корень и t старше своего отца do begin
| поменять t с его отцом
end;

Если очередь образуют граждане, стоящие в вершинах дерева,
т. е. за каждым стоит двое, а перед каждым (кроме первого) — один, то
смысл этого алгоритма ясен: встав в конец, приоритетный гражданин
начинает пробираться к началу, вытесняя впереди стоящих — пока не
встретит более приоритетного. ☐

**Замечание.** Приоритетную очередь естественно использовать при моделировании протекающих во времени процессов. При этом элементы очереди — это ожидаемые события, а их приоритет определяется временем, когда они произойдут.
# 7. РЕКУРСИЯ

## 7.1. Примеры рекурсивных программ

При анализе рекурсивной программы возникает, как обычно, два вопроса:

(а) почему программа заканчивает работу?

(б) почему она работает правильно, если заканчивает работу?

Для (б) достаточно проверить, что (содержащая рекурсивный вызов) программа работает правильно, предположив, что вызываемая ею одноимённая программа работает правильно. В самом деле, в этом случае в цепочке рекурсивно вызываемых программ все программы работают правильно (убеждаемся в этом, идя от конца цепочки к началу).

Чтобы доказать (а), обычно проверяют, что с каждым рекурсивным вызовом значение какого-то параметра уменьшается, и это не может продолжаться бесконечно.

### 7.1.1. Напишите рекурсивную процедуру вычисления факториала целого положительного числа $n$ (т. е. произведения $1 \cdot 2 \cdot \dots \cdot n$, обозначаемого $n!$).

**Решение.** Используем равенства $1! = 1$, $n! = (n-1)! \cdot n$.

```
procedure factorial (n: integer; var fact: integer);
  {положить fact равным факториалу числа n}
begin
  if n=1 then begin
    fact:=1;
  end else begin {n>1}
    factorial (n-1, fact);
    {fact = (n-1)!}
    fact:= fact*n;
  end;
end;
```

<figure><img src="image_57.png" /></figure>
С использованием процедур-функций можно написать так:

```pascal
function factorial (n: integer): integer;
begin
  if n=1 then begin
    factorial:=1;
  end else begin {n>1}
    factorial:= factorial (n-1)*n;
  end;
end;
```

Обратите внимание на некоторую двойственность использования име-
ни *factorial* внутри описания функции: оно обозначает как перемен-
ную, так и вызываемую рекурсивно функцию. К счастью, в нашем слу-
чае они различаются по скобкам после имени, но если бы функция была
без параметров, то дело было бы плохо. (Стандартная, но трудно нахо-
димая ошибка возникает, если автор программы на паскале полагает,
что он использует значение переменной, а компилятор в этом месте
видит рекурсивный вызов.)

7.1.2. Обычно факториал определяют и для нуля, считая, что $0! = 1$.
Измените программы соответственно. ☐

7.1.3. Напишите рекурсивную программу возведения в целую нео-
трицательную степень. ☐

7.1.4. То же, если требуется, чтобы глубина рекурсии не превосхо-
дила $C \log n$, где $n$ — показатель степени.

Решение.

```pascal
function power (a,n: integer): integer;
begin
  if n = 0 then begin
    power:= 1;
  end else if n mod 2 = 0 then begin
    power:= power(a*a, n div 2);
  end else begin
    power:= power(a, n-1)*a;
  end;
end;
```

<figure><img src="image_58.png" /></figure>
**7.1.5.** Что будет, если изменить программу, приведённую в решении предыдущей задачи, заменив строку

power:= power(a*a, n div 2)

на

power:= power(a, n div 2)* power(a, n div 2)?

**Решение.** Программа останется правильной. Однако она станет работать медленнее. Дело в том, что теперь вызов может породить два вызова (хотя и одинаковых) вместо одного — и число вызовов быстро растёт с глубиной рекурсии. Программа по-прежнему имеет логарифмическую глубину рекурсии, но число шагов работы становится линейным вместо логарифмического.

Этот недостаток можно устранить, написав

t:= power(a, n div 2);
power:= t*t;

или воспользовавшись функцией возведения в квадрат (sqr). ☐

**7.1.6.** Используя команды write(x) лишь при x = 0...9, напишите рекурсивную программу печати десятичной записи целого положительного числа n.

**Решение.** Здесь использование рекурсии облегчает жизнь (проблема была в том, что цифры легче получать с конца, а печатать надо с начала).

procedure print (n:integer); {n>0}
begin
  if n<10 then begin
    write (n);
  end else begin
    print (n div 10);
    write (n mod 10);
  end;
end;

**7.1.7.** Игра «Ханойские башни» состоит в следующем. Есть три стержня. На первый из них надета пирамидка из N колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составьте программу, указывающую требуемые действия.
**Решение.** Напишем рекурсивную процедуру перемещения i верхних колец с m-го стержня на n-й (остальные кольца предполагаются большими по размеру и лежат на стержнях без движения).

```pascal
procedure move(i,m,n: integer);
  var s: integer;
begin
  if i = 1 then begin
    writeln ('сделать ход ', m, '->', n);
  end else begin
    s:=6-m-n; {s - третий стержень: сумма номеров равна 6}
    move (i-1, m, s);
    writeln ('сделать ход ', m, '->', n);
    move (i-1, s, n);
  end;
end;
```

(Сначала переносится пирамидка из i-1 колец на третью палочку. По-сле этого i-е кольцо освобождается, и его можно перенести куда следу- ет. Остаётся положить на него пирамидку.) ☐

**7.1.8.** Напишите рекурсивную программу суммирования массива `a: array [1..n] of integer`.

[Указание. Рекурсивно определяемая функция должна иметь дополнительный параметр — число складываемых элементов.] ☐

## 7.2. Рекурсивная обработка деревьев

Двоичным деревом называется картинка вроде такой:

<figure><img src="image_59.png" /></figure>

Нижняя вершина называется корнем. Из каждой вершины могут ид- ти две линии: влево вверх и вправо вверх. Вершины, куда они ведут,
называются левым и правым сыновьями исходной вершины. Вершина может иметь двух сыновей, а может иметь только одного сына (левого или правого). Она может и вовсе не иметь сыновей, и в этом случае называется листом.

Пусть $x$ — какая-то вершина двоичного дерева. Она сама вместе с сыновьями, внуками, правнуками и т. д. образует поддерево с корнем в $x$ — поддерево потомков $x$.

В следующих задачах мы предполагаем, что вершины дерева пронумерованы целыми положительными числами, причём номера всех вершин различны. Мы считаем, что номер корня хранится в переменной root. Мы считаем, что имеются два массива

1, r: array [1..N] of integer

и левый и правый сын вершины с номером $i$ имеют соответственно номера $l[i]$ и $r[i]$. Если вершина с номером $i$ не имеет левого (или правого) сына, то $l[i]$ (соответственно $r[i]$) равно 0. (По традиции при записи программ мы используем вместо нуля константу nil, равную нулю.)

Здесь $N$ — достаточно большое натуральное число (номера всех вершин не превосходят $N$). Отметим, что номер вершины никак не связан с её положением в дереве и что не все числа от 1 до $N$ обязаны быть номерами вершин (и, следовательно, часть данных в массивах $l$ и $r$ — это мусор).

7.2.1. Пусть $N = 7$, $root = 3$, массивы $l$ и $r$ таковы:

<table><thead><tr><th>i</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><th>l[i]</th><td>0</td><td>0</td><td>1</td><td>0</td><td>6</td><td>0</td><td>7</td></tr><tr><th>r[i]</th><td>0</td><td>0</td><td>5</td><td>3</td><td>2</td><td>0</td><td>7</td></tr></tbody></table>

Нарисуйте соответствующее дерево.

Ответ.

<figure><img src="image_60.png" /></figure>

<figure><img src="image_61.png" /></figure>
### 7.2.2. Напишите программу подсчёта числа вершин в дереве.

**Решение.** Рассмотрим функцию `n(x)`, равную числу вершин в поддереве с корнем в вершине номер `x`. Считаем, что `n NIL = 0` (полагая соответствующее поддерево пустым), и не заботимся о значениях `nil(s)` для чисел `s`, не являющихся номерами вершин. Рекурсивная программа для `n` такова:

```pascal
function n(x:integer):integer;
begin
  if x = nil then begin
    n:= 0;
  end else begin
    n:= n(1[x]) + n(r[x]) + 1;
  end;
end;
```

(Число вершин в поддереве над вершиной `x` равно сумме чисел вершин над её сыновьями плюс она сама.) Глубина рекурсии конечна, так как с каждым шагом высота соответствующего поддерева уменьшается. ☐

### 7.2.3. Напишите программу подсчёта числа листьев в дереве.

**Ответ.**

```pascal
function n (x:integer):integer;
begin
  if x = nil then begin
    n:= 0;
  end else if (l[x]=nil) and (r[x]=nil) then begin {лист}
    n:= 1;
  end else begin
    n:= n(l[x]) + n(r[x]);
  end;
end;
```

### 7.2.4. Напишите программу подсчёта высоты дерева (корень имеет высоту 0, его сыновья — высоту 1, внуки — 2 и т. п.; высота дерева — это максимум высот его вершин).

[Указание. Рекурсивно определяется функция `f(x) = высота поддерева с корнем в х.] ☐

### 7.2.5. Напишите программу, которая по заданному `n` считает число всех вершин высоты `n` (в заданном дереве). ☐
Вместо подсчёта количества вершин того или иного рода можно
просить напечатать список этих вершин (в том или ином порядке).

7.2.6. Напишите программу, которая печатает (по одному разу) все вершины дерева.

Решение. Процедура print_subtree(x) печатает все вершины под-
дерева с корнем в x по одному разу; главная программа содержит вызов
print_subtree(root).

procedure print_subtree (x:integer);
begin
  if x = nil then begin
    {ничего не делать}
  end else begin
    writeln (x);
    print_subtree (l[x]);
    print_subtree (r[x]);
  end;
end;

Данная программа печатает сначала корень поддерева, затем подде-
рево над левым сыном, а затем над правым. Три строки в else-части
могут быть переставлены 6 способами, и каждый из этих способов даёт
свой порядок печати вершин. ☐

7.3. Порождение комбинаторных объектов,
перебор

Рекурсивные программы являются удобным способом порождения
комбинаторных объектов заданного вида. Мы решим заново несколько
задач соответствующей главы.

7.3.1. Напишите программу, которая печатает по одному разу все последовательности длины n, составленные из чисел 1...k (их количество равно k^n).

Решение. Программа будет оперировать с массивом a[1]...a[n]
и числом t. Рекурсивная процедура generate печатает все последо-
вательности, начинающиеся на a[1]...a[t]; после её окончания t и
a[1]...a[t] имеют то же значение, что и в начале:

procedure generate;
  var i,j : integer;
```pascal
begin
    if t = n then begin
        for i:=1 to n do begin
            write(a[i]);
        end;
        writeln;
    end else begin {t < n}
        for j:=1 to k do begin
            t:=t+1;
            a[t]:=j;
            generate;
            t:=t-1;
        end;
    end;
end;
```

Основная программа теперь состоит из двух операторов:

```
t:=0; generate;
```

<figure><img src="image_62.png" /></figure>

**Замечание.** Команды `t:=t+1` и `t:=t-1` для экономии можно вынести из цикла `for`.

7.3.2. Напишите программу, которая печатала бы все перестановки чисел 1...n по одному разу.

**Решение.** Программа оперирует с массивом `a[1]...a[n]`, в котором хранится перестановка чисел 1...n. Рекурсивная процедура `generate` в такой ситуации печатает все перестановки, которые на первых t по-зияциях совпадают с перестановкой `a`; по выходе из неё переменные `t` и `a` имеют те же значения, что и до входа. Основная программа такова:

```pascal
for i:=1 to n do begin a[i]:=i; end;
t:=0;
generate;
```

Вот описание процедуры:

```pascal
procedure generate;
    var i,j : integer;
begin
    if t = n then begin
        for i:=1 to n do begin
            write(a[i]);
        end;
        writeln;
    end;
end;
```
```pascal
end else begin {t < n}
  for j:=t+1 to n do begin
    поменять местами a[t+1] и a[j]
    t:=t+1;
    generate;
    t:=t-1;
    поменять местами a[t+1] и a[j]
  end;
end;
end;
```
□

7.3.3. Напечатайте все последовательности из n нулей и единиц, собердащие ровно k единиц (по одному разу каждую). □

7.3.4. Напечатайте все возрастающие последовательности длины k, элементами которых являются натуральные числа от 1 до n. (Предполагается, что $k \le n$, иначе таких последовательностей не существует.)

**Решение.** Программа оперирует с массивом `a[1]...a[k]` и целой переменной `t`. Предполагая, что `a[1]...a[t]` — возрастающая последовательность натуральных чисел из отрезка `1...n`, рекурсивно определённая процедура `generate` печатает все её возрастающие продолжения длины `k`. (При этом `t` и `a[1]...a[t]` в конце такие же, как в начале.)

```pascal
procedure generate;
  var i: integer;
begin
  if t = k then begin
    печатать a[1]..a[k]
  end else begin
    t:=t+1;
    for i:=a[t-1]+1 to t-k+n do begin
      a[t]:=i;
      generate;
    end;
    t:=t-1;
  end;
end;
```

**Замечание.** Цикл `for` мог бы иметь верхней границей `n` (вместо $t-k+n$). Наш вариант экономит часть работы, учитывая тот факт, что предпоследний `((k-1)-й)` член не может превосходить $n-1$, `(k-2)-й` член не может превосходить $n-2$ и т. п.
Основная программа теперь выглядит так:

```pascal
t:=1;
for j:=1 to 1-k+n do begin
  a[1]:=j;
  generate;
end;
```

Можно было бы добавить к массиву `a` слева фиктивный элемент `a[0] = 0`, положить `t = 0` и ограничиться единственным вызовом процедуры `generate`. ☐

7.3.5. Перечислите все представления положительного целого числа `n` в виде суммы последовательности невозрастающих целых положительных слагаемых.

**Решение.** Программа оперирует с массивом `a[1..n]` (максимальное число слагаемых равно `n`) и с целой переменной `t`. Предполагая, что `a[1]...a[t]` — невозрастающая последовательность целых чисел, сумма которых не превосходит `n`, процедура `generate` печатает все представления требуемого вида, продолжающие эту последовательность. Для экономии вычислений сумма `a[1] + ... + a[t]` хранится в специальной переменной `s`.

```pascal
procedure generate;
  var i: integer;
begin
  if s = n then begin
    печатать последовательность a[1]..a[t]
  end else begin
    for i:=1 to min(a[t], n-s) do begin
      t:=t+1;
      a[t]:=i;
      s:=s+i;
      generate;
      s:=s-i;
      t:=t-1;
    end;
    end;
  end;
```

Основная программа при этом может быть такой:

```pascal
t:=1;
for j:=1 to n do begin
  a[1]:=j
```
```pascal
s:=j;
generate;
end;
```

**Замечание.** Можно немного сэкономить, вынеся операции увеличения и уменьшения t из цикла, а также не возвращая s каждый раз к исходному значению (увеличивая его на 1 и возвращая к исходному значению в конце). Кроме того, добавив фиктивный элемент a[0] = n, можно упростить основную программу:

```pascal
t:=0; s:=0; a[0]:=n; generate;
```

<figure><img src="image_63.png" /></figure>

**7.3.6.** Напишите рекурсивную программу обхода дерева (используя те же команды и проверки, что и в главе 3 (Обход дерева).

**Решение.** Процедура обработать_над обрабатывает все листья над текущей вершиной и заканчивает работу в той же вершине, что и начала. Вот её рекурсивное описание:

```pascal
procedure обработать_над;
begin
  if есть_сверху then begin
    вверх_налево;
    обработать_над;
    while есть_справа do begin
      вправо;
      обработать_над;
    end;
    вниз;
  end else begin
    обработать;
  end;
end;
```

<figure><img src="image_64.png" /></figure>

## 7.4. Другие применения рекурсии

**Топологическая сортировка.** Представим себе n чиновников, каждый из которых выдаёт справки определённого вида. Мы хотим получить все эти справки, соблюдая установленные ограничения: у каждого чиновника есть список справок, которые нужно собрать перед обращением к нему. Дело безнадёжно, если схема зависимостей имеет цикл (справку А нельзя получить без В, В без С, ..., У без Z и Z без А).
Предполагая, что такого цикла нет, требуется составить план, указывавший один из возможных порядков получения справок.

Изображая чиновников точками, а зависимости — стрелками, приходим к такой формулировке. Имеется $n$ точек, пронумерованных от 1 до $n$. Из каждой точки ведёт несколько (возможно, 0) стрелок в другие точки. (Такая картинка называется ориентированным графом.) Циклов нет. Требуется расположить вершины графа (точки) в таком порядке, чтобы конец любой стрелки предшествовал её началу. Эта задача называется топологической сортировкой.

### 7.4.1. Докажите, что это всегда возможно.

**Решение.** Из условия отсутствия циклов вытекает, что есть вершина, из которой вообще не выходит стрелок (иначе можно двигаться по стрелкам, пока не зациклимся). Её будем считать первой. Выкидывая эту вершину и все соседние стрелки, мы сводим задачу к графу с меньшим числом вершин и продолжаем рассуждение по индукции. ☐

### 7.4.2. Предположим, что ориентированный граф без циклов хранится в такой форме: для каждого $i$ от 1 до $n$ в $num[i]$ хранится число выходящих из $i$ стрелок, в $adr[i][1], \dots, adr[i][num[i]]$ — номера вершин, куда эти стрелки ведут. Составьте (рекурсивный) алгоритм, который производит топологическую сортировку не более чем за $C \cdot (n+m)$ действий, где $m$ — число рёбер графа (стрелок).

**Замечание.** Непосредственная реализация приведённого выше доказательства существования не даёт требуемой оценки; её приходится немного подправить.

**Решение.** Наша программа будет печатать номера вершин. В масиве

```
printed: array[1..n] of boolean
```

мы будем хранить сведения о том, какие вершины напечатаны (и корректировать их одновременно с печатью вершины). Будем говорить, что напечатанная последовательность вершин корректна, если никакая вершина не напечатана дважды и для любого номера $i$, входящего в эту последовательность, все вершины, в которые ведут стрелки из $i$, напечатаны, и притом до $i$.

```
procedure add (i: 1..n);
    {дано: напечатанное корректно;}
    {надо: напечатанное корректно и включает вершину i}
```
```pascal
begin
    if printed [i] then begin {вершина i уже напечатана}
        {ничего делать не надо}
    end else begin
        {напечатанное корректно}
        for j:=1 to num[i] do begin
            add(adr[i][j]);
        end;
        {напечатанное корректно, все вершины, в которые из
         i ведут стрелки, уже напечатаны - так что можно
         печатать i, не нарушая корректности}
        if not printed[i] then begin
            writeln(i); printed [i]:= TRUE;
        end;
    end;
end;
```

Основная программа:

```pascal
for i:=1 to n do begin
    printed[i]:= FALSE;
end;

for i:=1 to n do begin
    add(i)
end;
```

К оценке времени работы мы вскоре вернёмся.

7.4.3. В приведённой программе можно выбросить проверку, заменить

```pascal
if not printed[i] then begin
    writeln(i); printed [i]:= TRUE;
end;
```

на

```pascal
writeln(i); printed [i]:= TRUE;
```

Почему? Как изменится спецификация процедуры?

Решение. Спецификацию можно выбрать такой:

дано: напечатанное корректно

надо: напечатанное корректно и включает вершину i;

все вновь напечатанные вершины доступны из i.

<figure><img src="image_65.png" /></figure>
### 7.4.4. Где использован тот факт, что граф не имеет циклов?

**Решение.** Мы опустили доказательство конечности глубины рекурсии. Для каждой вершины рассмотрим её «глубину» — максимальную длину пути по стрелкам, из неё выходящего. Условие отсутствия циклов гарантирует, что эта величина конечна. Из вершины нулевой глубины стрелок не выходит. Глубина конца стрелки по крайней мере на 1 меньше, чем глубина начала. При работе процедуры `add(i)` все рекурсивные вызовы `add(j)` относятся к вершинам меньшей глубины. ☐

Вернёмся к оценке времени работы. Сколько вызовов `add(i)` возможно для какого-то фиксированного i? Прежде всего ясно, что первый из них печатает i, остальные сведутся к проверке того, что i уже напечатано. Ясно также, что вызовы `add(i)` индуцируются «печататющими» (первыми) вызовами `add(j)` для тех j, из которых в i ведёт ребро. Следовательно, число вызовов `add(i)` равно числу входящих в i рёбер (стрелок). При этом все вызовы, кроме первого, требуют $O(1)$ операций, а первый требует времени, пропорционального числу исходящих из i стрелок. (Не считая времени, уходящего на выполнение `add(j)` для концов j выходящих рёбер.) Отсюда видно, что общее время пропорционально числу рёбер (плюс число вершин). ☐

**Связная компонента графа.** Неориентированный граф — набор точек (вершин), которые из которых соединены линиями (рёбрами). Неориентированный граф можно считать частным случаем ориентированного графа, в котором для каждой стрелки есть обратная.

**Связной компонентой вершины i называется множество всех тех вершин, в которые можно попасть из i, идя по рёбрам графа. (Поскольку граф неориентированный, отношение «j принадлежит связной компоненте i» является отношением эквивалентности.)**

### 7.4.5. Дан неориентированный граф (для каждой вершины указано число соседей и массив номеров соседей, как в задаче о топологической сортировке). Составьте алгоритм, который по заданному i печатает все вершины связанной компоненты i по одному разу (и только их). Число действий не должно превосходить $C$ · (общее число вершин и рёбер в связанной компоненте).

**Решение.** Программа в процессе работы будет «закрашивать» некоторые вершины графа. Незакрашенной частью графа будем называть то, что останется, если выбросить все закрашенные вершины и ведущие в них рёбра. Процедура `add(i)` закрашивает связанную компоненту i в незакрашенной части графа (и не делает ничего, если вершина i уже закрашена).