Решение сложных и олимпиадных задач по программированию.
СПб.:
2006. — 366 с.
В
книге рассматриваются решения оригинальных задач международных и
национальных олимпиад по информатике и программированию для
школьников и студентов. Задачи сгруппированы по темам: максимальный
поток, минимальное остовное дерево, деревья, скрытые графы,
стратегические игры, табло Янга. В начале каждой главы лаконично, но
доступно излагается необходимый теоретический материал по теме,
затем для каждой задачи приводятся условие, идея решения и описание
конкретной реализации на языке программирования Паскаль. Для
школьников, студентов и их преподавателей.
Содержание Введение .............................................................................. 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...
2006. — 366 с.
В
книге рассматриваются решения оригинальных задач международных и
национальных олимпиад по информатике и программированию для
школьников и студентов. Задачи сгруппированы по темам: максимальный
поток, минимальное остовное дерево, деревья, скрытые графы,
стратегические игры, табло Янга. В начале каждой главы лаконично, но
доступно излагается необходимый теоретический материал по теме,
затем для каждой задачи приводятся условие, идея решения и описание
конкретной реализации на языке программирования Паскаль. Для
школьников, студентов и их преподавателей.
Содержание Введение .............................................................................. 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...
Другие файлы:
Решение олимпиадных задач по математике в начальной школе
Подбор комплекса олимпиадных задач по математике для детей младшего школьного возраста. Структура и виды олимпиадных задач, способы их решения. Обучен...
Решение сложных и олимпиадных задач по программированию
В книге рассматриваются решения оригинальных задач международных и национальных олимпиад по информатике и программированию для школьников и студентов....
PascalABC.NET: Решение олимпиадных задач
Мастер-класс по программированию на современном паскале...
Подготовка к решению олимпиадных задач по математике
Решение олимпиадных задач принципиально отличается от решения школьных, даже очень сложных, задач! Это обусловлено прежде всего выбором разделов, трад...
ЕГЭ по информатике. Решение задач по программированию
Описание: Книга предназначена для подготовки учащихся к Единому государственному экзамену по информатике в части решения задач по программированию. Ра...
