Решение сложных и олимпиадных задач по программированию. Долинский М.С.

СПб.: Питер, 2006. — 366 с.

В книге рассматриваются решения оригинальных задач международных и национальных олимпиад по информатике и программированию для школьников и студентов. Задачи сгруппированы по темам: максимальный поток, минимальное остовное дерево, деревья, скрытые графы, стратегические игры, табло Янга. В начале каждой главы лаконично, но доступно излагается необходимый теоретический материал по теме, затем для каждой задачи приводятся условие, идея решения и описание конкретной реализации на языке программирования Паскаль. Для школьников, студентов и их преподавателей.

Формат: djvu / zip

Размер: 2,9 Мб

Скачать / Download файл

Содержание

Введение .............................................................................. 8

От издательства .................................................................................... 11

Глава 1. Максимальный поток............................................. 12

1.1. Примеры задач на максимальный поток ..................................... 12

1.2. Формальная постановка задачи......................................................... 14

1.3. Задача «Новогодняя вечеринка»....................................................... 16

1.4. Задача «Кубики»............................................................................... 18

1.5. Задача «Игра» ............................................................................... 21

1.6. Пример максимального потока на графе....................................... 25

1.7. Алгоритм Форда-Фалкерсона ......................................................... 28

1.8. Решения задач................................................................................. 33

1.9. Замечания по реализации ............................................................... 44

Глава 2. Минимальное остовное дерево............................. 45

2.1. Формальная постановка задачи......................................................... 45

2.2. Алгоритм Прима................................................................................ 47

2.3. Алгоритм Крускала............................................................................ 51

2.4. Быстрая сортировка.......................................................................... 54

2.5. Задача «Secret Pipes»....................................................................... 55

2.6. Задача «Метро» ............................................................................. 59

2.7. Задача «Network» ............................................................................ 61

2.8. Решения задач................................................................................. 63

Глава 3. Решение задач на деревьях и с помощью деревьев........ 76

3.1. Практические примеры деревьев....................................................... 78

3.1.1. Деревья отношений .............................................................. 78

3.1.2. Деревья попиксельного представления

плоских цветных образов........................................................ 78

3.1.3. Деревья представления сложных композиций трехмерных объектов

3.1.4. Деревья кодирования символов.............................................. 79

3.1.5. Деревья сортировки................................................................ 81

3.1.6. Деревья сумм......................................................................... 82

3.1.7. Перечисление деревьев.......................................................... 82

3.1.8. Представление деревьев в памяти компьютера............... 83

3.1.9. Порядок обхода деревьев .................................................... 84

3.1.10. Организация материала и технология

работы с ним ..................................................................... 84

3.2. Задачи на основные свойства деревьев............................................ 84

3.2.1. Задача «Is it a tree?» ............................................................. 85

3.2.2. Задача «Strategic game»......................................................... 89

3.2.3. Задача «Оппозиция»............................................................... 92

3.2.4. Задача «Erdos Numbers»......................................................... 94

3.2.5. Задача «Closest Common Ancestor» ..................................... 96

3.3. Задачи на представление образов..................................................... 98

3.3.1. Задача «Unscrambling Images» ............................................. 99

3.3.2. Задача «BSP Trees» .......................................................... 106

3.4. Задачи на двоичные деревья сортировки........................................ 110

3.4.1. Задача «Дерево» ............................................................... 110

3.4.2. Задача «Parliament» ........................................................... 113

3.4.3. Задача «Falling Leaves»......................................................... 117

3.5. Кодирование последовательностей символов

методом Хаффмана ....................................................................... 120

3.5.1. Задача «Кодирование» ....................................................... 120

3.5.2. Задача «Entroov».................................................................. 124

3.6. Перечисление деревьев.................................................................. 126

3.6.1. Задача «Nextree» ............................................................... 126

3.6.2. Задача «Trees Made to Order»................................................ 132

3.7. Битово-индексированные деревья................................................... 137

3.7.1. Задача «Мобильные телефоны» ......................................... 137

3.7.2. Структура данных BIT............................................................ 141

3.8. Задачи для самостоятельного решения........................................... 145

3.8.1. Задача «Knockout Tournament».............................................. 145

3.8.2. Задача «Split Windows»......................................................... 147

3.8.3. Задача «Huffman Trees» ...................................................... 149

3.8.4. Задача «Pre-Post-erous!» .................................................... 151

3.9. Решения задач............................................................................... 153

Глава 4. Скрытые графы ................................................ 185

4.1. Инцидентность областей ............................................................... 186

4.1.1. Задача «Тетраэдр» .............................................................. 186

4.1.2. Задача «Стены» ................................................................. 192

4.1.3. Задача «Блокада»................................................................. 198

4.1.4. Задача «Мудрый правитель»................................................. 203

4.1.5. Задача «Ременная передача» ............................................. 207

4.2. Отношения других видов .............................................................. 211

4.2.1. Задача «Currency Exchange»................................................. 211

4.2.2. Задача «Exchange Rates» .................................................. 215

4.2.3. Задача «Sorting It All Out» .................................................. 220

4.2.4. Задача «Проверка веб-страниц».........оличество возможных диаграмм заданной

формы (п1, п2....... пМ) ................................................................. 335

6.4. Задача «Склад» .......................................................................... 336

6.5. Задача «Twofive»............................................................................. 341

6.6. Решения задач............................................................................... 353

Литература.................................... 363

Алфавитный указатель........................... 364