Назва: Розв'язок складних і олимпиадных завдань по програмуванню Автор: Долинский М.З. Видавництво: Пітер Рік: 2006 Сторінок: 366 Формат: djvu Розмір: 2,96 + 3% на відновлення Мова: російський У книзі розглядаються розв'язки оригінальних завдань міжнародних і національних олімпіад по інформатиці й програмуванню для школярів і студентів. Завдання згруповані по темах: максимальний потік, мінімальне остовное дерево, дерева, сховані графи, стратегічні ігри, табло Янга. На початку кожної глави лаконічно, але доступно викладається необхідний теоретичний матеріал по темі, потім для кожного завдання приводяться умова, ідея розв'язку й опис конкретної реалізації мовою програмування Паскаль. Для школярів, студентів і їх викладачів. Зміст Введення 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. Дерева вистави складних композицій тривимірних об'єктів 79 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. Завдання «Entropy» 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. Завдання «Перевірка веб-сторінок» 225 4.2.5. Завдання «Play On Words» 230 4.3. Завдання на безлічах відрізків 234 4.3.1. Завдання «Падіння» 235 4.3.2. Завдання «The Doors» 241 4.3.3. Завдання «Борозни» 246 4.3.4. Завдання «N-Credible Mazes» 250 4.4. Завдання для самостійного розв'язку 254 4.4.1. Завдання «Door Man» 254 4.4.2. Завдання «This Sentence is false» 255 4.4.3. Завдання «Will Indiana Jones Get There?» 256 4.4.4. Завдання «I hate SPAM, but some people love it» 257 4.5. Розв'язку завдань 260 Розділ 5. Стратегічні ігри 296 5.1. Завдання «Аліса й Боб» 296 5.2. Завдання «Тура й кінь» 300 5.3. Завдання «Нечесна гра» 305 5.4. Як відіграти переможно? 308 5.5. Завдання «Гра loiwari» 308 5.6. Завдання «Гра Score» 314 5.7. Завдання «Гра-2» 319 5.8. Розв'язку завдань 321 Розділ 6. Діаграма Юнга 333 6.1. Введення в діаграму Юнга 333 6.2. Вставка й видалення елементів діаграми 333 6.3. Кількість возможныхдиаграмм заданої форми (n1, n2 nm) 335 6.4. Завдання «Склад» 336 6.5. Завдання «Twofive» 341 6.6. Розв'язку завдань 353 Література 363 Алфавітний покажчик 364
Розв'язок складних і олимпиадных завдань по програмуванню