Автокликер
Блог
Библиотека
Еще...

Математика

Консервирование

Салаты

Физкультура и спорт

Теория программирования

AJAX

Напитки

Assembler

Выпечка

Национальная кухня

Интернет

Кулинария

Компьютерная графика и дизайн

Плавание

Баскетбол

Рыбы

Гимнастика, фитнес, йога

Шахматы

Компьютерная литература

Теория автоматов

Беременность и уход за ребенком

Дефектология, логопедия

Массаж

Дискретная математика

Позвоночник, суставы

Книги Малахова Г.П.

Детская психология

Общая психология

ВАЗ

Ремонтная мастерская

Детская литература

Психология

Воспитателям

MatLab

Дайвинг

Книги для родителей

Кошки

Хомячки

Собаки

Фотография

Практическая и прикладная психология

Рукоделие

Попугаи

Боевые искусства, самооборона

Linux, Unix, FreeBSD, MacOS

Мир животных

Вождение

Ремонт и строительство

Здоровый образ жизни

Книги для девочек

Цветоводство

Автотранспорт

Энциклопедии, познавательная литература

Зрение

Здоровое питание и диеты

SQL и MySQL

Гастроэнтерология

Фастфуд

JavaScript

Mathcad

Мода, стиль и красота

Flash

Железо

Тяжелая атлетика

PHP

Эзотерика. Парапсихология. Тайны

Книги Болотова Б.В.

Бизнес-книги

Системное программирование

Диетическая кухня

Психология общения

Художественная литература

Сказки

Дизайн, интерьер

ЗАЗ

История бизнеса

Менеджмент

Медицина и здоровье

Зарубежная литература

Развитие и воспитание детей

Компьютерные сети

Ландшафтный дизайн

Педагогика

Возрастная психология

Авто-право

HTML

XML

Python

Perl

Windows

Excel

Правила дорожного движения

Visual Basic

Хобби, увлечения, досуг

Сад, огород

Рисование

Художественная кулинария

Лечебная физкультура

Барбекю. Гриль. Мангал

Книги для мальчиков

Экономика

Нетрадиционная медицина

Маркетинг, реклама и PR

Очищение организма

Банковское дело

Коллекционирование

Бухгалтерский учет, аудит

Финансы, инвестиции

Физика

Генетика

Психодиагностика и тестирование

Механика

Термодинамика

Электромагнетизм, электроника

Оптика

Авторское право

Квантовая физика

MicroSoft Office, OpenOffice

Колебания и волны

C, C , C#

Право

Статистика

CSS

jQuery

Тайм-менеджмент

Трехмерная графика

Социальная психология

Сердце и сосуды

BIOS

DELPHI и Pascal

История психологии

Java, J2ME

Гинекология

Праздники, игры, развлечения

Мотоциклы

Психология личности

Футбол

История педагогики

Десерты

Молекулярная физика

Социальная педагогика

Теория обучения и воспитания

Уголовное право

Фармакология

Малый бизнес

Недвижимость

Теория бизнеса

iPhone и iPad

Ruby

Криптография

CMS

Android

Раскрутка и продвижение сайта

Литература

Личности в истории

ASP.NET

Системное администрирование

САПР

Дом, семья, дети

Здоровое и раздельное питание

Биографии

Путешествия

Современная проза

Саморазвитие

Анатомия и физиология

Семейное и жилищное право

Торговля, продажи, логистика

Словари

Химия

Психотерапия

Oracle

Музыка и танцы

Видеомонтаж

Международное право

Математический анализ

Английский язык

Философия

История России

Изучение языков

Французский язык

Музыка и звук на компьютере

Поэзия

Немецкий язык

Биографии, мемуары

Хирургия

Школьный психолог

Испанский язык

Публицистика

История

Коррекционная педагогика

Культура и искусство

Социология

Политология

Религия

Финансовое право

Всемирная история

1C

Литературоведение

Естествознание

Линейная алгебра

Прокуратура, адвокатура

Русский язык

Итальянский язык

Краткое изложение произведений

Школьный курс

Биология, экология

Промышленная экология

Архитектура

Алгоритмы и программы. Решение олимпиадных задач

Алгоритмы и программы. Решение олимпиадных задач

Порублев И.Н., Ставровский А.Б.

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

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

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

М.: ООО "И.Д. Вильямс", 2007.

ISBN 978-5-8459-1244-2

Количество страниц: 480.

Содержание книги «Алгоритмы и программы. Решение олимпиадных задач»:

  • 13 Предисловие
    • 15 От издательства «Диалектика»
  • 17 Глава 1. Разминка (понемногу о разном)
    • 17 1.1. Три простые задачи
      • 17 1.1.1. Совпадения стрелок часов
      • 18 1.1.2. Последовательности с одинаковыми суммами
      • 19 1.1.3. Ребус
    • 23 1.2. Знакомство со сложностью алгоритмов
      • 23 1.2.1. Простые и составные числа
      • 25 1.2.2. Понятие сложности алгоритма
      • 27 1.2.3. Характер возрастания сложности
      • 28 1.2.4. Алгоритм Евклида и его современная версия
      • 29 1.2.5. Бинарный алгоритм
      • 30 1.2.6. Понятие сложности задачи
      • 31 1.2.7. Что выбирать?
    • 31 1.3. Несколько технических вопросов
      • 31 1.3.1. Проектирование сверху вниз, подпрограммы и структурное кодирование
      • 32 1.3.2. Когда уместны безусловные переходы
      • 34 1.3.3. Несколько замечаний о стиле
      • 35 1.3.4. Отладка программы
      • 37 1.3.5. Директивы компилятору
      • 38 1.3.6. Проверка программы
    • 40 1.4. Ввод последовательностей данных
      • 40 1.4.1. Организация данных и вид цикла ввода
      • 43 1.4.2. Изменение источника данных
    • 44 Упражнения
  • 47 Глава 2. Однопроходные алгоритмы
    • 47 2.1. Попутные вычисления
      • 47 2.1.1. Три простых примера
      • 49 2.1.2. Максимальная сумма отрезка числовой последовательности
      • 50 2.1.3. Инопланетная армия
      • 53 2.1.4. Стрельба из двуствольной пушки
    • 55 2.2. Чтение и обработка символов
      • 55 2.2.1. Удаление пробелов
      • 57 2.2.2. Удаление комментариев
      • 59 2.2.3. Чтение и вычисление многочлена
      • 67 2.2.4. Языки скобок
      • 72 2.2.5. Линейный поиск подстроки в тексте
    • 76 Упражнения
  • 79 Глава 3. Рекурсия
    • 79 3.1. Основные понятия
      • 79 3.1.1. Рекурсивные определения
      • 80 3.1.2. Простейший пример рекурсивной подпрограммы
      • 81 3.1.3. Глубина рекурсии и общее количество рекурсивных вызовов
      • 83 3.1.4. Косвенная рекурсия
    • 85 3.2. Быстрое возведение в степень
    • 88 3.3. Рисование самоподобных ломаных
      • 89 3.3.1. Снежинка Коха
      • 90 3.3.2. Треугольник Серпиньского
      • 93 3.3.3. Драконова ломаная
    • 95 Упражнения
  • 97 Глава 4. Нестандартная обработка чисел
    • 97 4.1. Длинная целочисленная арифметика
      • 98 4.1.1. Представление длинных чисел
      • 100 4.1.2. Сравнение, сложение и вычитание длинных целых
      • 102 4.1.3. Организация ввода-вывода
      • 103 4.1.4. Умножение длинных целых
      • 105 4.1.5. Деление длинных целых
      • 107 4.1.6. Целая часть квадратного корня длинного числа
    • 109 4.2. Два магических числа
      • 109 4.2.1. Число e
      • 112 4.2.2. Число π
    • 112 4.3. Остатки от деления
      • 113 4.3.1. Плиты в треугольнике
      • 115 4.3.2. Кратное число с одинаковыми цифрами
    • 116 4.4. Отслеживание циклических повторений
      • 116 4.4.1. Десятичное представление дроби ρ-алгоритм
      • 119 4.4.2. Остатки от деления чисел Фибоначчи
    • 121 4.5. Нули в конце факториала
    • 124 Упражнения
  • 127 Глава 5. Бинарный поиск, слияние и сортировка
    • 127 5.1. Бинарный поиск
      • 127 5.1.1. Идея бинарного поиска
      • 128 5.1.2. «Оптический танк»
    • 130 5.2. Слияние упорядоченных последовательностей
      • 130 5.2.1. Слияние двух участков массива
      • 131 5.2.2. Слияние файлов
    • 135 5.3. Основные способы сортировки
      • 135 5.3.1. Два простейших алгоритма
      • 137 5.3.2. Сортировка слиянием
      • 140 5.3.3. Быстрая сортировка
      • 142 5.3.4. Пирамидальная сортировка
      • 145 5.3.5. Линейная сортировка подсчетом
      • 148 5.3.6. Поразрядная сортировка
    • 150 5.4. Применение сортировки
      • 150 5.4.1. Проверка уникальности
      • 151 5.4.2. Проход в заборе
      • 153 5.4.3. Транзитивность
    • 154 Упражнения
  • 159 Глава 6. Вычислительная геометрия на плоскости
    • 159 6.1. Точки, векторы, прямые, отрезки
      • 159 6.1.1. Точки, векторы, углы и ориентированная площадь
      • 162 6.1.2. Представление прямых и отрезков
      • 164 6.1.3. Взаимное расположение прямых, отрезков и точек
      • 169 6.1.4. Две задачи о треугольниках
    • 173 6.2. Многоугольники (полигоны)
      • 173 6.2.1. Основные определения
      • 174 6.2.2. Площадь полигона
      • 176 6.2.3. Принадлежность точки полигону
      • 177 6.2.4. Принадлежность точки выпуклому полигону
      • 178 6.2.5. Построение полигонов
      • 182 6.2.6. Сумма и разность полигонов
    • 185 6.3. Окружности и круги
      • 185 6.3.1. Прямая и круг
      • 186 6.3.2. Отрезок и окружность
      • 187 6.3.3. Общие касательные
      • 188 6.3.4. Пересечение двух кругов
    • 191 Упражнения
  • 195 Глава 7. Выметание
    • 195 7.1. Интернет-провайдер
    • 199 7.2. Мера объединения отрезков
    • 201 7.3. Линия горизонта
    • 205 7.4. Мера объединения треугольников
    • 209 Упражнения
  • 211 Глава 8. Графы
    • 211 8.1. Графы и способы их представления
      • 211 8.1.1. Неориентированные графы: основные понятия
      • 213 8.1.2. Ориентированные графы
      • 214 8.1.3. Представления графа
      • 215 8.1.4. Пример: задача о центре дерева
    • 221 8.2. Алгоритмы обхода графов
      • 221 8.2.1. Обход в глубину
      • 224 8.2.2. Обход в ширину
      • 225 8.2.3. Реализация очереди
    • 226 8.3. Применение алгоритмов обхода
      • 226 8.3.1. Построение остовного дерева и остовного леса
      • 228 8.3.2. Расстояния между вершинами
      • 230 8.3.3. Проверка ацикличности и топологическая сортировка ациклического орграфа
      • 233 8.3.4. Эйлеровы циклы и цепи
      • 236 8.3.5. Обход графа достижимых состояний
    • 240 Упражнения
  • 243 Глава 9. Графы клеток и графы с нагруженными ребрами
    • 243 9.1. Графы на клетчатых полях
      • 243 9.1.1. Фигуры на клетчатом поле
      • 246 9.1.2. Минимальный путь в лабиринте
      • 252 9.1.3. Подсчет клеток в областях
    • 258 9.2. Остовное дерево минимального веса
    • 261 9.3. Алгоритм Дейкстры и его применение
      • 261 9.3.1. Задача с одним источником и положительным весом ребер
      • 264 9.3.2. Максимальный груз
      • 265 9.3.3. Зал Круглых Столов
    • 270 9.4. Скоростная алхимия
    • 274 Упражнения
  • 279 Глава 10. Комбинаторика
    • 280 10.1. «Амебы» комбинаторики
      • 280 10.1.1. Правила суммы и произведения
      • 281 10.1.2. Перестановки, размещения и сочетания без повторений
      • 282 10.1.3. Перестановки, размещения и сочетания с повторениями
      • 284 10.1.4. Размещения и сочетания как отображения
      • 285 10.1.5. Биномиальные коэффициенты
    • 286 10.2. Рекуррентные соотношения и таблицы
      • 286 10.2.1. Пути в квадратных кварталах
      • 288 10.2.2. Правильные скобочные выражения
      • 289 10.2.3. Счастливые билеты
      • 292 10.2.4. Белые и черные кубики
      • 295 10.2.5. Велосипедные гонки
    • 296 10.3. Рекурсия в задаче о русском лото
    • 299 10.4. Включения и исключения
      • 299 10.4.1. Принцип включений и исключений
      • 301 10.4.2. «Батарея, огонь!»
      • 303 10.4.3. Беспорядок в шляпах
    • 304 10.5. Количество раскладок и разбиений
      • 304 10.5.1. Разбиения множества
      • 305 10.5.2. Разбиения множества с учетом порядка классов
      • 306 10.5.3. Разбиения числа на слагаемые
    • 307 Упражнения
  • 309 Глава 11. Перебор вариантов
    • 309 11.1. Порождение подмножеств
      • 309 11.1.1. Все подмножества
      • 313 11.1.2. Подмножества с заданным числом элементов
    • 315 11.2. Порождение последовательностей
      • 315 11.2.1. Размещения ферзей
      • 317 11.2.2. Дерево размещений и его обход
      • 318 11.2.3. Обход дерева с помощью магазина
      • 320 11.2.4. Порождение всех перестановок
    • 322 11.3. Попытки сократить перебор
      • 323 11.3.1. Подмножества положительных чисел с заданной суммой
      • 324 11.3.2. Псевдополиномиальный приближенный алгоритм поиска подмножества
      • 325 11.3.3. Идея метода ветвей и границ в задаче коммивояжера
      • 326 11.3.4. Решение задачи коммивояжера методом ветвей и границ
      • 327 11.3.5. Упрощенный алгоритм
    • 328 11.4. Послесловие
    • 329 Упражнения
  • 333 Глава 12. Жадные алгоритмы
    • 333 12.1. Знакомство с жадными алгоритмами
      • 333 12.1.1. Быстрый выбор упорядоченных вариантов
      • 335 12.1.2. Сортировка и выбор в динамическом множестве
      • 338 12.1.3. Понятие жадного алгоритма
    • 339 12.2. Матроиды и жадные алгоритмы
      • 339 12.2.1. Понятие матроида
      • 340 12.2.2. Жадный поиск допустимого подмножества с максимальным весом
      • 340 12.2.3. Взвешенный матроид и жадный алгоритм
      • 341 12.2.4. Матричный матроид
    • 342 12.3. Некорректная «жадность» вместо перебора
      • 342 12.3.1. Поспешная укладка рюкзака
      • 343 12.3.2. Распределение заданий
    • 344 Упражнения
  • 347 Глава 13. Динамическое программирование
    • 347 13.1. Принцип оптимальности
      • 347 13.1.1. Путь по клеткам с максимальной суммой
      • 351 13.1.2. Общие замечания по методологии динамического программирования
      • 353 13.1.3. Количество путей с суммой, близкой к максимальной
    • 358 13.2. Монотонная подпоследовательность
      • 358 13.2.1. Поиск монотонной подпоследовательности
      • 362 13.2.2. Бинарный поиск начала подпоследовательности
      • 365 13.2.3. Вложенные коробки
    • 366 13.3. Табличная техника и рекурсия с запоминанием
      • 366 13.3.1. Расстановка скобок в произведении матриц
      • 372 13.3.2. Минимальное количество монет
      • 374 13.3.3. Разбиение алфавита
      • 376 13.3.4. Абзац с блоками разной высоты
      • 378 13.3.5. Максимальное значение выражения
      • 381 13.3.6. Вычеркивание из строки
    • 383 Упражнения
  • 387 Глава 14. Игры двух лиц
    • 388 14.1. Анализ позиций и выбор хода
      • 388 14.1.1. Выигрышные и проигрышные позиции
      • 390 14.1.2. Золотое сечение
      • 394 14.1.3. Ним
      • 397 14.1.4. Таблица ходов
    • 398 14.2. Оценивание позиций: максимальная сумма
    • 399 Упражнения
  • 403 Глава 15. Японский кроссворд
    • 403 15.1. Итерационный анализ линий
      • 403 15.1.1. Постановка задачи и основные идеи решения
      • 407 15.1.2. Ввод, вывод и основные структуры данных
      • 409 15.1.3. Реализация итерационного анализа линий
    • 410 15.2. Анализ линии на основе конечного автомата
      • 410 15.2.1. Описание линии в виде конечного автомата
      • 412 15.2.2. Обработка линии и уточнение клеток
      • 414 15.2.3. Реализация
    • 419 15.3. Решение задачи с помощью перебора
      • 419 15.3.1. Итерационный анализ линий не решает задачу
      • 421 15.3.2. Перебор и исследование состояний клеток с помощью ИАЛ
      • 423 15.3.3. Решение задачи и анализ решения
  • 427 Приложение А. Указания по решению упражнений
    • 427 Глава 1
    • 429 Глава 2
    • 431 Глава 3
    • 433 Глава 4
    • 436 Глава 5
    • 440 Глава 6
    • 442 Глава 7
    • 443 Глава 8
    • 446 Глава 9
    • 450 Глава 10
    • 455 Глава 11
    • 459 Глава 12
    • 461 Глава 13
    • 464 Глава 14
  • 469 Список литературы
  • 471 Предметный указатель

Скачать книгу Алгоритмы и программы. Решение олимпиадных задач / Порублев И.Н., Ставровский А.Б. в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.