Введение
С программированием связано много приятного. Мастерство приносит свои маленькие радости - удовлетворение от того, что ты сделал что-то полезное и оно работает. Возбуждение, приходящее от внезапного озарения, позволившего решить упрямую задачу.
Читателю
Задачи для этой книги были выбраны из более чем 1000 задач по программированию, представленных на сайте автоматической тестирующей системы Universidad de Valladolid
Преподавателю
Эта книга разрабатывалась как учебник для трех типов курсов: курсы по алгоритмам, ориентированные на программирование; курсы по программированию, ориентированные на изучение алгоритмов; факультативные курсы для подготовки студентов к участию в таких соревнованиях
Тренеру или участнику соревнований
Эта книга разрабатывалась, в частности, как руководство по подготовке к соревнованиям школьного и студенческого уровней. Мы предлагаем удобный конспект/справочник по важным темам математики и теории алгоритмов, а также соответствующие задачи, которые помогут вам освоить материал.
Начало работы
Мы начнем эту книгу с набора относительно элементарных задач по программированию, ни одна из которых не требует знаний больших, чем знание массивов и циклов.
Начало работы с автоматической тестирующей системой (robot judge)
Эта книга написана для совместного использования с одним или обоими сайтами автоматического оценивания. Тестирующая система (Судья) Programming Challenges (http://www.programming-challenges.com) была настроена специально таким образом, чтобы помочь вам извлечь максимум из задач, приведенных в этой книге.
Автоматический судья Programming Challenges
Сайт Programming Challenges (http://www.programming-challenges.com) обеспечивает специальные возможности, связанные с каждой из задач, представленных в этой книге. Например, описание каждой задачи, приведенной в этой книге, имеется на сайте, так же как и файлы входных и выходных данных, которые можно скачать, чтобы вам не пришлось вводить все эти тестовые данные.
Автоматический судья Universidad de Valladolid
Все задачи этой книги наравне со многими другими находятся на сайте тестирующей системы Universidad de Valladolid (http://online-judge.uva.es), самой большой коллекции задач по программированию в мире. Мы призываем всех, чей аппетит только разгорелся от предложенных нами задач, продолжить свое обучение там.
Ответы тестирующих систем (судей)
Студенты должны знать, что обе тестирующие системы (автоматические судьи) часто очень требовательны к тому, что можно назвать правильным решением. Очень важно правильно понять спецификацию задачи. Никогда не делайте предположения, которые точно не описаны в спецификации.
Выбор оружия - языки программирования
Какой язык программирования вам следует использовать в ваших сражениях с автоматическим судьей? Вероятнее всего, тот язык, который вы лучше всего знаете. На данный момент судья принимает программы, написанные на Pascal, С, С++ и Java, так что, вероятнее всего, ваш любимый язык доступен.
Чтение наших программ
В этой книге вы встретите несколько примеров программ, которые иллюстрируют методики программирования и обеспечивают полную реализацию фундаментальных алгоритмов.
Стандартный ввод/вывод
Программисты, работавшие в UNIX, знакомы с понятием фильтров и программ-каналов, которые получают один входной поток и производят один выходной поток.
Советы по программированию
Цель этой книги не научить вас тому, как программировать, а научить тому, как программировать лучше. Мы полагаем, что вы знакомы с такими фундаментальными понятиями, как переменные, условные выражения (к примеру, if-then-else, case), а также с основами итерации (например, for-do, while-do, repeat- until), подпрограммами и функциями.
Элементарные типы данных
Простые структуры данных, такие, как массивы, имеют важное преимущество перед более сложными структурами данных, такими, как связанные списки: они простые.
О задачах
Каждая глава этой книги заканчивается соответствующим набором задач по программированию. Эти задачи были аккуратно выбраны из более чем 1000 таких задач, собранных на сайте Universidad de Valladolid. Мы выбирали понятные, интересные задачи с различными уровнями сложности.
Задача Зn + 1
Рассмотрим следующий алгоритм генерации последовательности чисел. Начнем с целого числа п. Если п четно, то поделим на 2. Если п нечетно, то умножим на 3 и добавим 1.
Сапер
Играли ли вы когда-нибудь в Сапера (Minesweeper)? Эта приятная маленькая игра поставляется вместе с операционной системой, имя которой мы не помним. Цель игры состоит в том, чтобы найти расположение всех мин на поле размером MxN.
Путешествие
Группа студентов является членами клуба, который ежегодно путешествует в различные места. Предыдущие места их поездок включают Индианаполис, Финикс, Нашвилл, Филадельфию, Сан-Хосе и Атланту. Этой весной они планируют съездить в Айндховен.
LCD-дисплей
Ваш друг только недавно купил себе новый компьютер. До этого самой мощной машиной, которую он когда-либо использовал, был карманный калькулятор. Он немного расстроен, потому что LCD-дисплей его калькулятора ему нравился больше, чем экран его компьютера!
Интерпретатор
Некий компьютер имеет десять регистров и 1000 слов (word) ОЗУ. Каждый регистр или ячейка ОЗУ содержит трехзначное целое число от 0 до 999. Инструкции кодируются как трехзначные целые числа и сохраняются в ОЗУ.
Проверка на шах
Вашей задачей является написание программы, которая считывает положение на шахматной доске и определяет, атакован ли король (находится ли он под шахом). Король находится под шахом, если он может быть взят следующим ходом противника.
Австралийское голосование
Австралийские бюллетени требуют, чтобы избиратели расположили всех кандидатов в порядке предпочтения. Первоначально учитывается только первый кандидат из получившегося списка, и если один из кандидатов набрал более 50% голосов, то он считается избранным.
Замечания
Задача 3п + 1 (или задача Коллаца (Collatz) остается не решенной по нынешний день. Смотрите [Lag85] для замечательного математического обзора.
Структуры данных
Структуры данных - это сердце любой сложной программы. Выбор правильной структуры данных может очень сильно повлиять на сложность итоговой реализации. Выберете правильное представление данных, и вашу задачу будет легко запрограммировать.
Стеки (Stacks)
Стеки и очереди - это контейнеры, из которых вещи извлекаются в зависимости от порядка их поступления и вне зависимости от их содержимого. Стеки поддерживают порядок последний вошел, первый вышел (last-in, first-out - LIFO).
Очереди (Queues)
Очереди поддерживают порядок первый вошел, первый вышел (first-in, first-out - FIFO). Это кажется более честным, чем последний вошел, первый вышел, и именно поэтому очереди в магазинах реализованы как очереди, а не как стеки.
Словари (Dictionaries)
Словари поддерживают извлечение по содержанию, а не по положению, что делают стеки и очереди. Словари поддерживают три основные операции:
Очереди по приоритету (Priority queues)
Очереди по приоритету - это структуры данных на множествах объектов, поддерживающие три операции:
Множества (Sets)
Множества (или, говоря точнее, подмножества) - это неупорядоченные наборы элементов, набранные из данного универсального множества U.
Объектные библиотеки
Пользователи современных объектно-ориентированных языков, таких, как С++ и Java, имеют доступ к реализациям этих базовых структур данных, используя стандартные библиотечные классы.
Пакет java.util для Java
Полезные стандартные объекты Java можно обнаружить в пакете java.util. Почти все из java.util доступно автоматическому судье, за исключением нескольких библиотек, которые представляют чрезмерную мощь участнику состязания. Подробнее смотрите сайт Sun
Пример разработки программы: сборы на войну
В детской карточной игре "Война", стандартная 52-карточная колода делится на двоих игроков (1 и 2) так, чтобы у каждого игрока оказалось по 26 карт. Игроки не смотрят на свои карты, но держат их стопкой рубашкой вверх. Цель игры - выиграть все карты.
Что касается колоды
Какая структура лучше всего подходит для представления колоды карт? Ответ на этот вопрос зависит от того, что вы собираетесь с ними делать. Собираетесь ли вы тасовать их?
Строковый ввод/вывод
Для нашей программы входные данные состоят из двух строк для каждой вводимой колоды, первая строка соответствует картам игрока 1, вторая строка соответствует картам игрока 2.
Победа на войне
После того как мы получили соответствующий "фундамент", разработав наши структуры данных, основная подпрограмма становится достаточно прямолинейной.
Тестирование и отладка
Отладка с программным судьей может быть весьма раздражительной, поскольку у вас никогда не будет возможности увидеть тестовый случай, на котором ошиблась ваша программа.
Jolly Jumpers
Последовательность п > 0 целых чисел называется jolly jumper, если абсолютные значения разностей последовательных элементов принимают все возможные значения от 1 до п - 1. К примеру,
Руки в покере
Колода для покера состоит из 52 карт. Каждая карта имеет масть: кресты, бубны, червы и пики (во входных данных обозначаются С, D, Н, S).
Харталы
Политические партии в Республике Бангладеш показывают свою силу, объявляя регулярные харталы (забастовки), которые наносят значительный ущерб экономике.
Дешифратор
Распространенный, но ненадежный метод шифровки текста состоит в перемене букв алфавита. Другими словами, каждая буква алфавита последовательно заменяется в тексте какой-то другой буквой.
Расположить по порядку
В Большом городе много казино. В одном из них дилер жульничает. Она довела до совершенства несколько перетасовочных трюков; каждый трюк меняет порядок карт одним и тем же образом, когда бы он ни был использован.
Числа Эрдеша
Венгерский ученый Пауль Эрдеш (Paul Erdus, 1913- 1966) был одним из самых известных математиков XX века. Любой математик, имевший честь быть соавтором Эрдеша, глубоко уважаем.
Табло соревнований
Хотите посоревноваться в АСМ ICPC? Тогда вам нужно знать, как вести счет! Участники соревнований ранжируются сначала по числу решенных задач (чем больше, тем лучше), а потом по уменьшению величины штрафного времени.
1.1. Jolly number - это особый случай нумерации изящного графа. Граф называется изящным, если существует способ пронумеровать п вершин целыми числами так, чтобы абсолютные значения разностей конечных точек всех т ребер пробегали все значения от 1 до т. Jolly jumper представляет собой изящную нумерацию пути из п вершин.
Строки
Текстовые строки - это фундаментальная структура данных, чья важность постоянно возрастает. Поисковики в Интернете, такие, как Google, находят миллиарды документов практически мгновенно.
Представление строк
Строки это последовательности символов, причем порядок, очевидно, имеет значение. Важно знать, как ваш любимый язык программирования представляет строки, потому что существует несколько различных возможностей.
Пример разработки программы: корпоративные переименования
Корпоративная смена имен происходит все чаще, так как компании объединяются, покупают друг друга, пытаются скрыться от дурной славы или даже поднимают курс акций - вспомните то время, когда секретом успеха было добавить .com к имени компании.
Поиск шаблонов
Простейший алгоритм определения присутствия шаблонной строки р в тексте t совмещает начало шаблонной строки с каждым символом текста и проверяет, совпадает ли каждый символ шаблонной строки с соответствующим ему символом текста.
Управление строками
Для управления строками требуется точно знать, какое представление строк вы или ваш язык программирования использует. Здесь мы полагаем, что строки представляются последовательностью символов в массиве, заканчивающемся нуль-символом окончания, как принято в С.
Функции библиотеки для работы со строками
Работаете ли вы в С, С++ или в Java, вам нужно знать о возможностях, предоставляемых для работы с символами и строками через библиотеки и классы. Нет никакого смысла снова изобретать колесо.
WERTYU
Обычная ошибка при наборе состоит в том, что вы помещаете ваши руки на клавиатуру на один ряд правее верной позиции. Тогда "Q" печатается как "W", " J" печатается как "К",ит. д. Ваша задача состоит в расшифровке сообщения, набранного таким образом.
Где Waldorf?
По заданной сетке букв размером т х п и списку слов определить позицию в сетке, в которой находится это слово.
Обычная перестановка
Даны две строки а и вывести строку х максимальной длины, состоящую из, букв, таких, что существует перестановка х, являющаяся подстрокой перестановки d и одновременно являющаяся подстрокой перестановки
Автоматизированное судейство
Известно, что люди, являющиеся судьями на состязаниях по программированию, очень придирчивы. Чтобы устранить необходимость в них, напишите сценарий автоматизированного судейства (automated judge script), который будет судить присланные решения.
Осколки файлов
Ваш друг, специалист в области биохимии, споткнулся, когда вез тележку с компьютерными файлами по лаборатории. Все файлы упали на землю и разбились. Ваш друг собрал все осколки и обратился к вам с просьбой снова собрать их вместе.
Дублеты
Дублетом называются два слова, которые отличаются ровно в одной букве (например, "booster" и "rooster", или "rooster" и "roaster", или "roaster" и "roasted").
Fmt
UNIX - программа fmt читает строки текста, комбинируя и разбивая их так, чтобы создать выходной файл со строками, максимально приближающимися по длине к 72 символам, не превышая этого лимита. Правила объединения и разбиения следующие.
Подсказки
Нужно ли вам жестко кодировать логику, чтобы произвести замещение символов, или проще будет использовать стратегию инициализированных таблиц замещения?
Сортировка
Сортировка является наиболее фундаментальной алгоритмической задачей в теории вычислительных машин и систем по двум различным причинам. Во- первых, сортировка - это полезная операция, которая эффективно решает многие задачи, с которыми встречается каждый программист.
Алгоритмы сортировки
Вполне возможно, что вы видели десяток или даже больше алгоритмов сортировки данных.
Пример разработки программы: рейтинг ухажеров
У красотки Полли нет недостатка в прекрасно воспитанных ухажерах. Напротив, самой большой ее проблемой является отслеживание самых лучших из них. Она достаточно умна, чтобы понять, что программа, ранжирующая мужчин от наиболее к наименее желаемому, упростит ее жизнь.
Функции библиотеки сортировки
Когда есть возможность, используйте встроенные в ваш любимый язык программирования библиотеки сортировки/поиска:
Сортировка и поиск С++
С++ Standard Template Library (STL), которая обсуждалась в разделе 2.2.1, включает методы для сортировки, поиска и других задач. Пользователи, собирающиеся серьезно работать с С++, должны хорошо знать STL.
Рейтинг ухажеров
Для решения проблемы Полли со свиданиями мы хотели сделать шаг сортировки по нескольким критериям настолько простым, насколько это возможно.
Семья Вито
PC/UVa IDs: 110401/10041 Популярность: A Частота успехов: высокая Уровень: 1 Знаменитый гангстер Вито Дедстоун переезжает в Нью-Йорк. У него там очень большая семья, и все живут на Лямафия-авеню. Так как он собирается навещать всех своих родственников очень часто, он хочет найти дом рядом с ними.
Мост
Группа из п людей хочет ночью пересечь мост. Одновременно по мосту могут идти максимум два человека, и у каждой группы должен быть фонарик. Фонарик у этих п людей только один, так что кто-то должен приносить фонарик назад, чтобы все люди смогли перейти.
Подремать подольше
Профессора ведут очень активный образ жизни, и их расписания наполнены работой и встречами. Профессор Р. любит подремать днем, но его расписание заполнено настолько плотно, что у него почти нет возможности это сделать.
Задача сапожника
У сапожника имеется N заказов от покупателей, которые он должен выполнить. Сапожник может заниматься в день только одним заказом, и заказы обычно требуют на выполнение несколько дней.
CDVII
Римские дороги известны их безупречной конструкцией. К сожалению, безупречная конструкция стоит недешево, и некоторые современные нео-Цезари решили сэкономить на автоматическом взимании дорожной пошлины.
Сортировка Шелла
Kopoль Йертл (Yertle) хочет перегруппировать свой трон из черепах так, чтобы его самые знатные дворяне и ближайшие советники оказались ближе к вершине.
Футбол
Футбол - это самая популярная игра в мире, даже несмотря на то, что американцы называют его "soccer". В такой стране, как пятикратный чемпион мира Бразилия, так много национальных и региональных турниров, что их очень тяжело отслеживать.
Что правильнее взять в качестве среднего для решения проблемы Вито: среднее по координатам, среднее по пути mean, median или что-либо другое?
Арифметика и алгебра
Связь между умением программировать и математическими способностями хорошо известна. Более того, первые компьютеры были созданы программистами для ускорения вычислений.
Высокоточные целые числа
Для представления действительно огромных целых чисел требуется "сшивать" цифры вместе. Двумя возможными представлениями являются: Массивы цифр.
Высокоточная арифметика
Первые алгоритмы, узнанные нами в школе, были связаны с четырьмя стандартными арифметическими действиями: сложением, вычитанием, умножением и делением. Мы учились с ними работать, не всегда понимая теорию, лежащую в их основе.
Системы счисления и соответствующие переходы
При цифровом представлении числа в заданной системе счисления используется основание системы счисления. Особенно важными являются следующие системы счисления.
Вещественные числа
Области математики, созданные для работы с вещественными числами, действительно важны для понимания окружающего мира. Ньютону пришлось разработать исчисление для того, чтобы он смог сформулировать основные законы движения.
Работа с вещественными числами
Внутреннее представление чисел с плавающей запятой меняется в зависимости от компьютера, языка программирования и компилятора. Из-за этого работа с ними является большой проблемой.
Простые дроби
Точные рациональные числа х/у проще всего представить парой целых чисел х, у, где х - это числитель, а у - это знаменатель дроби.
Десятичные дроби
Десятичное представление вещественных чисел - это особый случай рациональных чисел. Десятичное число представляет сумму двух чисел: целой части, находящейся слева от запятой, и дробной части, находящейся справа от запятой.
Работа с полиномами
Наиболее естественным представлением одномерного (зависящего от одной переменной) полинома п-й степени является массив п + 1 коэффициентов от с0 до сп.
Нахождение корней
При заданном полиноме Р(х) и числе t задача нахождения корней состоит в отыскании всех х таких, что Р(х) = t.
Логарифмы
Возможно, вы замечали клавиши log и ехр на вашем калькуляторе, но, вероятнее всего, никогда ими не пользовались. Возможно, вы даже забыли, для чего они там нужны.
Математические библиотеки
Математические библиотеки в C/C++ В стандартной математической библиотеке C/C++ есть несколько полезных функций для работы с вещественными числами:
Начала арифметики
Детей учат складывать многоразрядные числа справа налево, по одной цифре за один раз. Многие из детей считают операцию "переноса", когда 1 переносится в следующий разряд, достаточно сложной.
Изменение порядка и сложение
Функция изменения порядка и сложения начинает с числа, меняет порядок его цифр на противоположный и складывает получившееся число с начальным.
Дилемма археолога
Археолог, ищущий доказательства того, что инопланетяне в прошлом прилетали на Землю, наткнулся на частично уничтоженную стену, содержащую странные последовательности чисел.
Коэффициенты полинома
PC/UVa IDs: 110506/10105 Популярность: В Частота успехов: высокая Уровень: 1
Комбинаторика
Комбинаторика - это математика счета. Существует несколько основных счетных задач, которые регулярно появляются в вычислительной технике и программировании.
Базовые методики счета
Здесь мы рассмотрим определенные основные правила счета и формулы, которые вы, возможно, видели, но уже забыли. В частности, существует три основных правила счета, из которых получаются многие формулы.
Рекуррентные соотношения
Рекуррентные соотношения значительно облегчают подсчет ряда рекурсивно заданных структур. К рекурсивно заданным структурам относятся деревья, списки, правильно построенные формулы и алгоритмы "разделяй и властвуй", так что они часто встречаются на пути ученых, занимающихся алгоритмами.
Рекурсия и индукция
Одним из удобных инструментов для решения рекуррентных соотношений является математическая индукция. Когда мы впервые узнали о математической индукции в средней школе, она казалась полным шаманством.
Сколько частей земли?
Вам дается кусок земли в виде эллипса и предлагается выбрать п произвольных точек на ее границе. После этого вы соединяете прямыми линиями каждую точку со всеми остальными, образуя п(п - 1)/2 соединений.
Выражения
Пусть Х-это множество правильно построенных скобочных выражений. Элементами Х являются строки, состоящие только из символов " (" и ") ", причем они определяются следующим образом.
Нумерация полного дерева
Полным А-арным деревом называется к-арное дерево, у которого глубина всех листьев одинакова и степень ветвления всех внутренних узлов равна к. Найти число узлов такого дерева совсем несложно.
Самоописывающая последовательность
Самоописывающая последовательность Соломона Голомба (/(1), /(2), /(3),...) - это единственная неубывающая последовательность положительных целых чисел, обладающая тем свойством, что она содержит ровно/(?) экземпляров к для каждого к.
Теория чисел
Теория чисел является, возможно, самым интересным и красивым разделом математики. Доказательство Евклидом существования бесконечного количества простых чисел остается таким же четким и ясным сегодня, каким оно было более двух тысяч лет назад.
Поиск простых чисел
Самым простым способом определения того, простое ли число является многократное деление. Деление проводится на все необходимые числа, начиная с наименьшего возможного делителя.
Подсчет простых чисел
Сколько всего простых чисел? Кажется разумным, что простые числа встречаются все реже и реже по мере рассмотрения все больших и больших чисел, но исчезают ли они совсем?
Делимость
Теория чисел - это учение о делимости чисел. Мы говорим, что а делится на b (обозначается b\а), если для какого-то целого к верно а = bк. Аналогично, если b\а, мы говорим, что b - это делитель а или а кратно b.
Арифметика остатков
В главе 5 мы рассмотрели простейшие арифметические операции, такие, как сложение и умножение, для целых чисел. Но нам не всегда нужен полный ответ.
Сравнимости
Сравнимости - это альтернативный вариант представления модулярной арифметики. Мы говорим, что а = 6(mod m), если t\(а - b). По определению, если a mod b = m, то а = 6(mod t).
Решение линейных сравнимостей
Линейная сравнимость - это уравнение в форме ах = 6(mod n). Решить это уравнение - значит найти все значения х, удовлетворяющие ему.
Библиотеки по теории чисел
Java-ioiacc Biglnteger (java.math.Biglnteger) содержит ряд полезных функций, основанных на теории чисел. Конечно, самыми важными являются функции арифметических операций с произвольной точностью, обсуждавшихся в главе 5.
Света, больше света
В нашем институте есть человек по имени Мабу, который включает/выключает лампы вдоль коридора. Для каждой лампы есть свой выключатель, отвечающий за то, светит лампа или нет.
Задача Евклида
Со времен Евклида известно, что для любых положительных целых чисел А и В существуют такие целые X и У, что АХ+ BY= D, где D - это наибольший общий делитель чисел А и В. Задача состоит в том, чтобы найти соответствующие X,YnD для заданных А и В.
Делители факториалов
Для всех неотрицательных чисел п функция факториала, nl, определяется следующим образом:
Сумма четырех простых чисел
Гипотеза простых чисел Варинга (Waring) утверждает, что любое нечетное число можно представить в виде суммы трех простых чисел. Гипотеза Гольдбаха (Goldbach) утверждает, что любое четное число можно представить в виде суммы двух простых.
Шарики
Я коллекционирую шарики (маленькие, цветные, стеклянные шарики) и хочу купить коробки для их хранения. Коробки бывают двух типов.
Можем ли мы выяснить состояние n- лампы, не проверяя все числа от 1 до n?
Поиск с возвратом
Современные компьютеры обладают настолько высоким быстродействием, что подчас решение задачи полным перебором становится эффективным и достойным уважения способом.
Построение всех подмножеств
Как было отмечено выше, мы можем построить 2п подмножеств п элементов, рассмотрев все 2п возможных векторов длины п, состоящих из элементов истина ложь, что дает возможность i-му элементу задавать, входит или нет объект i в подмножество.
Построение всех перестановок
Задача построения всех перестановок аналогична задаче построения всех подмножеств с тем отличием, что кандидаты на следующее место теперь зависят от значений, содержащихся в частном решении.
Пример разработки программы: задача восьми ферзей
Задача восьми ферзей - это классическая головоломка, в которой требуется расставить восемь ферзей на шахматной доске размером 8x8 так, чтобы они не били друг друга.
Поиск с отсечением вариантов
Экспоненциальный рост поисковых пространств с увеличением числа вариантов носит название комбинаторного взрыва.
Слоны
Слон - это шахматная фигура, которая из текущей позиции может ходить только по диагонали. Два слона атакуют друг друга, если один из них находится на пути другого.
Шеренга
Рассмотрим шеренгу из N людей разного роста. Каждый из них видит все слева, если он или она выше всех людей, стоящих слева; иначе поле зрения перекрыто.
Перетягивание каната
Перетягивание каната - это состязание в грубой силе, когда две группы людей тянут канат в противоположные стороны.
Color hash
Эта головоломка состоит из двух колес. Оба колеса могут вращаться по и против часовой стрелки.
Больший квадрат
У Томи есть много бумажных квадратиков. Длина их стороны (размер) изменяется от 1 до N - 1, и у него есть неограниченное число квадратов любого размера.
Как мы можем изменить наше решение задачи п ферзей для решения задачи о слонах? Может ли помочь разбиение задачи на отдельные задачи по размещению белопольных и чернопольных слонов?
Обходы графов
В теории алгоритмов графы - это одна из универсальных тем, абстрактное представление, которым описывается организация транспортных систем, электрических цепей, взаимодействий людей и сетей телекоммуникации.
Структуры данных для графов
Графы можно представить несколькими способами. Ниже мы обсудим четыре полезных варианта. Мы полагаем, что граф G = (V,E) содержит п вершин и т ребер.
Обход графа: в ширину
Базовой операцией в любом графовом алгоритме является полный и систематический обход графа.
Использование обхода
Точное поведение bfs зависит от функций process_vertex () и process_edge (). Путем задания этих функций мы можем легко определить, что должно происходить при единственном посещении каждого ребра и каждой вершины.
Обход графа: в глубину
В основе поиска в глубину лежит та же идея, что и в переборе с возвратом. Оба алгоритма производят полный перебор всех возможностей, продвигаясь, пока это возможно, и возвращаясь, когда не остается неисследованных вариантов дальнейшего продвижения.
Связные компоненты
Связным компонентом неориентированного графа называется максимальное множество вершин таких, что существует путь между любой парой вершин. Они являются различными, не соединенными "кусками" графа.
Топологическая сортировка
Топологическая сортировка - это фундаментальная операция на ориентированных ациклических графах (DAG). С ее помощью вершины располагаются в таком порядке, что все направленные ребра идут "слева направо" (от вершины с меньшим порядковым номером к вершине с большим).
Раскраска двумя цветами
Теорема четырех красок утверждает, что любую плоскую карту можно раскрасить, используя только четыре цвета, таким образом, что никакие две соседние области не будут покрашены в один цвет.
Экскурсовод
М-р Ж. работает экскурсоводом в Республике Бангладеш. Его текущее задание состоит в том, чтобы показать группе туристов удаленный город. Как и во всех странах, определенные пары городов соединены дорогами с двусторонним движением.
Лабиринт из косых
Заполняя прямоугольник левыми (/) и правыми (\) косыми чертами (слешами), можно строить симпатичные небольшие лабиринты. Вот пример.
Лесенки ступенек редактирования
Назовем ступенькой редактирования (edit step) такое преобразование слова х в слово у, что слова х и у принадлежат словарю и слово х может быть преобразовано в словом путем добавления, удаления или изменения одной буквы.
От заката до рассвета
У Владимира бледная кожа, очень длинные зубы, и ему уже 600 лет, но в этом нет ничего особенного, потому что Владимир - вампир. Ему всегда нравилось быть вампиром.
И снова ханойские башни!
Существует много интересных вариаций задачи о Ханойских башнях. В этой версии у нас имеется п колышков и шарики, содержащие все числа от 1, 2, 3,..., 00.
Графовые алгоритмы
Различные варианты представления графов и алгоритмы обхода из главы 9 являются "кирпичиками" для любого вычисления, основанного на графах. В этой главе мы рассмотрим более продвинутую теорию графов и более продвинутые алгоритмы.
Связность
Граф называется связным, если существует неориентированный путь между любой парой его вершин. Существование остовного дерева доказывает связность графа.
Циклы в графах
Все связанные графы, не являющиеся деревьями, содержат циклы. Особенно интересными являются циклы, включающие в себя все вершины или ребра графа.
Планарные графы
Планарным (плоским) называется граф, который можно изобразить на плоскости так, чтобы никакие два его ребра не пересекались. Планарными являются многие графы, с которыми мы встречаемся.
Минимальные остовные деревья
Остовным деревом графа G = (V,E) называется подмножество ребер из образующее дерево и соединяющее все вершины из К.
Кратчайшие пути
Задача нахождения кратчайшего пути в невзвешенном графе обсуждалась в разделе 9.3.1 - для нее вполне достаточно поиска в ширину.
Кратчайшие пути между всеми парами вершин
Многим приложениям требуется знать длины кратчайших путей между всеми парами вершин заданного графа.
Потоки в сети и паросочетания в двудольных графах
Любой реберно-взвешенный граф можно рассматривать как сеть труб, причем вес ребра (i,j) задает пропускную способность трубы.
Веснушки
В одной из серий шоу Дика ван Дайка (Dick van Dyke) маленький Ричи соединяет веснушки на спине своего отца так, чтобы они образовали изображение колокола Свободы. Увы, одна из веснушек оказалась шрамом, и свидание с Рипли сорвалось.
Пожарное депо
Город обслуживается несколькими пожарными депо. От жителей стали поступать жалобы, что расстояние между некоторыми домами и ближайшим пожарным депо чересчур велико, так что придется построить новое.
Железные дороги
Завтрашним утром Джилл должна поехать из Гамбурга в Дармштадт, чтобы принять участие в региональной олимпиаде по программированию.
Война
Воюют две страны, А и В. Как верный гражданин страны С, вы решили помочь своей стране, секретно посетив мирные переговоры между А и В.
Рио-де-Жанейро очень красивый город, но там столько мест, куда можно поехать, что временами вы просто теряетесь. К счастью, ваш друг Бруно пообещал быть вашим экскурсоводом.
Большой обед
Все команды, участвовавшие в АСМ World Finals, приглашаются на большой банкет, который устраивается после церемонии награждения.
Задача про постановщика задач
В этом году так много студентов решили принять участие в региональных этапах олимпиад по программированию, что мы решили составить отбраковочные тесты, для того чтобы выявить наиболее многообещающих студентов.
Динамическое программирование
Как разработчикам алгоритмов и программистам нам нередко требуется написать программу, которая находит лучшее решение.
Стоимость редактирования
Задача нахождения шаблонов в строках текста имеет очень большое значение, и в главе 3 мы рассматривали соответствующие алгоритмы.
Восстановление пути
Реализация на основе динамического программирования, приведенная выше, возвращает стоимость оптимального решения, но не само решение.
Варианты стоимости редактирования
В процедурах оптимизации и восстановления пути использовались некоторые функции, которые мы пока не определили. Их можно разбить по четырем категориям.
Пример разработки программы: оптимизация лифта
Я работаю в очень высоком здании с очень медленным лифтом. Особенно меня раздражает, когда люди нажимают кнопки нескольких соседних этажей (скажем, 13, 14 и 15-го), а я еду с нижнего этажа на верхний.
Умнее ли больший?
Некоторые люди считают, что чем слон больше, тем он умнее. Чтобы опровергнуть это утверждение, вы хотите проанализировать набор слонов и расположить наибольшее из возможных подмножеств этого набора в последовательность слонов с увеличивающимся весом, но уменьшающимся IQ.
Различные подпоследовательности
Подпоследовательность заданной последовательности S составляется из S путем удаления некоторого числа элементов (возможно, нуля).
Однонаправленная задача коммивояжера
Для заданной матрицы размером m х п вы должны написать программу, которая вычисляет путь с минимальным весом с левого края матрицы до правого.
Распил брусьев
Вам нужно распилить деревянный брус на несколько кусков. Самая удобная компания Analog Cutting Machinery (АСМ) берет плату за пилку в зависимости от размера бруса, который нужно распилить.
Заполнение парома
Паромы используются для перевозки машин через реки или другие водные препятствия. Обычно паромы имеют достаточно большую ширину, поэтому машины выстраиваются в две линии вдоль парома.
Палочки для еды
В Китае для еды люди используют две палочки, но мистер JI не обычный человек. Он использует набор из трех палочек, двух обычных и еще одной дополнительной; это длинная палочка, на которую он насаживает большие куски еды.
Сетки
Дело не в том, что полярные координаты чересчур сложны, а в том, что прямоугольные координаты проще, чем они имеют право быть. - Клеппнер и Коленхау. "Введение в механику".
Обход
Часто бывает необходимым обойти все ячейки прямолинейной сетки п х т. Каждый такой обход можно рассматривать как установление соответствия между каждой из пт упорядоченных пар и одного целого числа от 1 до пт.
Двойственные графы и представления
Естественный выбор для представления плоских прямолинейных сеток - это двумерные массивы. Ячейка m[i][j] может задавать или (i,j) вершину, или (7,у) грань в зависимости от того, что нас интересует.
Треугольные и гексагональные сетки
Существует еще две важные разновидности сеток - треугольные и гексагональные. Они тесно связаны друг с другом - гексагональная решетка получается из треугольной удалением определенных вершин.
Гексагональные решетки
Удалив определенные вершины в треугольной решетке, мы получим гексагональную решетку. Теперь грани решетки - это правильные шестиугольники, и каждый из них соседствует с шестью другими.
Пример разработки программы: Вес тарелки
Производитель обеденных тарелок желает выйти на рынок поставщиков посуды для столовых кампуса. Столовые покупают тарелки одного стандартного размера, чтобы их было удобно составлять вместе.
Упаковка кругов
Существует важная и интересная взаимосвязь между гексагональными решетками и упаковкой круглых дисков.
Широта и долгота
Еще одна достаточно важная система координат - это система широты и долготы, позволяющая однозначно задать любую точку на поверхности Земли.
Муравей на доске
Однажды муравей по имени Алиса пришла на шахматную доску размером Мх М. Ей хотелось исследовать все клетки доски. И она начала идти по доске, начав с угла.
Звезда
Для каждой линии мы можем найти максимальную цифру на ней. В нашем примере наибольшее число для линии А - это 5, В - 7, Е - 6, Н- 0 и для У это 8.
Ограбление
Инспектор Робостоп очень зол. Прошлой ночью был ограблен банк и преступник сумел скрыться с места преступления.
(2/3/4)-D Квад/Прям/Куб...?
Сколько всего квадратов и прямоугольников спрятано в сетке размером 4x4, изображенной ниже? Может, вы и сможете подсчитать их количество в уме для такой небольшой сетки, но что для сетки 100 х 100 или больше?
Авиалинии
Ведущая авиакомпания наняла вас для написания программы, от которой требуется следующим образом обрабатывать запросы: для данного списка городов и прямых перелетов между ними программа должна найти минимальное расстояние, которое нужно пролететь пассажиру, чтобы попасть из одного заданного города в другой.
Геометрия
Над воротами в академию Платона была надпись "Да не войдет сюда несведущий в геометрии".
Прямоугольные треугольники и теорема Пифагора
Прямой угол равен 90°, или Pi/2 радиан. Прямые углы образуются при пересечении перпендикулярных прямых, таких, как оси в прямоугольной системе координат. Такие прямые делят 360° = 2Pi радиан на четыре равные части.
Решение треугольников
Две тригонометрические теоремы позволяют нам рассчитывать важные свойства треугольников. Теорема синусов формулирует соотношения между сторонами и углами в любом треугольнике.
Окружности
Окружность - это геометрическое место точек, находящихся на заданном расстоянии (называемом радиусом) от ее центра (хс, ус). Круг - это окружность и все, что находится внутри нее, иначе говоря,
Пример разработки программы: быстрее пули
Супермен обладает по крайней мере двумя возможностями, недоступными обычным смертным: рентгеновское зрение и возможность летать быстрее пули.
Библиотеки тригонометрических функций
Тригонометрические библиотеки всех языков программирования очень близки. Вам необходимо знать, с градусами или с радианами работают функции вашей библиотеки и в каком диапазоне лежат значения углов, возвращаемые обратными тригонометрическими функциями.
Суслик и собака
На большом поле находятся суслик и собака. Собака хочет суслика съесть, а суслик хочет оказаться в безопасности, добежав до одной из норок, выкопанных в поле.
Проблема с канатами в Канатово
Перетягивание каната - это очень популярная игра в Канатово, почти как крикет в Бангладеш. Две команды игроков тянут канат за разные концы. Та группа, которая сумеет вырвать канат из рук противников, объявляется победителем.
Рыцари Круглого стола
Король Артур собирается поставить круглый стол в комнате с треугольным окном в потолке. Он хочет, чтобы солнце попадало на его круглый стол.
Именинный пирог
Люси и Лили - близнецы. Сегодня у них день рождения, поэтому мама покупает им именинный пирог.
Это интегрирование?
На рисунке ниже показан квадрат ABCD, у которого АВ = ВС = CD = DA = a. Рисуются четыре дуги: точки А, В, С, D берутся в качестве центров, а а в качестве радиуса.
Вычислительная геометрия
В последнее время геометрические расчеты становятся все более и более важными в таких приложениях, как компьютерная графика, робототехника и автоматизированная разработка, потому что форма объекта - это одно из его основных свойств.
Многоугольники и вычисления углов
Многоугольником (полигоном) называется замкнутая цепочка непересекающихся отрезков. Под замкнутостью подразумевается, что первая вершина цепочки одновременно является и последней.
Выпуклые оболочки
Построение выпуклой оболочки для вычислительной геометрии - это как сортировка для других алгоритмических задач - первый шаг, применяемый к неструктурированным данным, позволяющий совершать более сложные операции.
Триангуляция: алгоритмы и смежные задачи
Найти периметр многоугольника просто: достаточно найти длину каждой стороны, используя формулу евклидова расстояния, и сложить все получившиеся значения.
Подсчет площади
Мы можем найти площадь любого триангулированного многоугольника, просуммировав площади всех треугольников. Это легко реализовать, используя уже созданные функции.
Алгоритмы для сеток
Так как многоугольники, построенные на вершинах прямоугольной и шестиугольной сеток, могут быть естественным образом разбиты на отдельные ячейки, имеет смысл знать, как решать определенные вычислительные задачи для этих ячеек.
Запросы на значение области
Запрос на значение прямоугольной области - это обычная операция при работе с прямоугольными сетками п х т.
Решетчатые многоугольники и теорема Пика
Прямоугольные сетки с единичным расстоянием между точками (называемыми также узлами решетки) лежат в основе любой координатной системы, основанной на решетке.
Пасем первокурсников
Однажды наша лужайка в центре кампуса оказалась заполнена новоприбывшими студентами. Чтобы кампус не выглядел так дико, один из наших старшекурсников-отличников решил окружить их куском шелковой нити.
Задача о ближайших точках
Малоизвестная телефонная компания хочет показать, что она в состоянии предоставить клиентам высокоскоростную широкополосную сеть.
Резня бензопилой
Канадское сообщество лесорубов только что провело свои ежегодные состязания по валке леса, и лесные заповедники между Монреалем и Ванкувером разорены.
Теплее - холоднее
Детская игра теплее - холоднее выглядит следующим образом. Игрок А выходит из комнаты, а игрок В в это время прячет там какой-то предмет.
Радиолокация
В системе слежения типа земля-воздух используется антенна, которая вращается в горизонтальной плоскости по часовой стрелке с периодом в две секунды.
Деревья моего острова
Я купил остров, на котором хочу посадить деревья рядами и столбцами. Деревья будут формировать прямоугольную сетку, так что можно считать, что каждое из них имеет целочисленные координаты, если выбрать подходящую точку сетки в качестве начала координат.
Подготовка к олимпиаде
Высокие достижения в соревнованиях по программированию или в любых других спортивных состязаниях зависят не только от таланта.
Ресурсы
Правила АСМ ICPC разрешают студентам пользоваться любым печатным материалом, но запрещают использовать любые сетевые ресурсы.
Представляйте свои возможности.Так как очки даются только за полностью верные решения, выбирайте самые легкие задачи и решайте сначала их.