В. Рубанцев - Как решать комбинаторные задачи на компьютере

12Валерий РубанцевКак решатькомбинаторные задачина компьютереКомбинаторика для программистовна языке C#3Это издание представляет собой сокращённый вариант книги Как решатькомбинаторные задачи на компьютере. Комбинаторика для программистов на языке C#. Полная версия книги включает 10 глав (369 страниц).Вы можете приобрести её (вместе с исходными кодами всех проектов) насайте издательства:RVGames.de/buy2.htmВсе права защищены. Никакая часть этой книги не может быть воспроизведенав любой форме без письменного разрешения правообладателей.Автор книги не несёт ответственности за возможный вред от использованияинформации, составляющей содержание книги и приложений.Copyright 2013 Валерий РубанцевЛилия Рубанцева4От автораЕсли хочешь быть умным,поступай в программисты!Козьма Прутков-программистКомбинаторика как наука возникла сравнительно недавно.

Первая книгаРассуждения о комбинаторном искусстве вышла в 1666 году. Написал еёизвестный немецкий математик Готфрид Вильгельм фон Лейбниц, который и придумал название для этого раздела математики.Однако решать комбинаторные задачи людям приходилось на протяжении всей своей истории. Как в жизни, так и в программировании комбинаторные задачи встречаются на каждом шагу. Например, сколько различных слов можно составить из букв русского алфавита? Сколько существует различных комбинаций при игре в кости с двумя или тремя кубиками? Сколько разных нарядов можно составить из трёх юбок и четырёхблузок? Сколько существует разбиений числа на отдельные слагаемые?Сколькими способами можно покрыть прямоугольник домино или тримино?Многие детско-спортивные игры начинаются со считалок, бросания монетили жребия.

Гадания также основаны на комбинаторике - раскладываниикарт, вытягивании спичек, отрывании лепестков у ромашки… Или азартные игры! Какое число выпадет на рулетке, какие карты находятся в прикупе, какие числа следует зачеркнуть в карточке лото? Как составить список покупок, расписание соревнований, футбольную команду, фоторобот,пазлы или кубик Рубика, припарковаться, приготовить блюдо, рассадитьучеников по партам, расставить книги по полкам, сервировать стол, декорировать комнату, собрать механизм из деталей… И даже творческие порывы не обходятся без комбинаторики! Написание стихов и музыки, графика и живопись – почти комбинаторные процессы.

Недаром в этих областях искусства «компьютеры» добились впечатляющих успехов. И наконец, все люди – всего лишь комбинация генов в молекулах ДНК!Комбинаторика – это настоящий клад для программистов! Здесь можнонайти не один десяток великолепных задач, но, как вы знаете, любимымвыражением Козьмы Пруткова была фраза Нельзя объять необъятное. Поэтому для этой книги я отобрал только 7 жемчужин из этих комбинаторных сокровищ:5Ожерелья и браслетыЧисловые магические квадратыСловесные магические квадратыЗадача Иосифа ФлавияРасстановка ферзей на шахматной доскеРазмен денегРасстановка знаков между числами, чтобы получилась сотняПо крайней мере, ещё столько же замечательных комбинаторных проблемосталось за бортом, но - нельзя объять необъятное!Почти все задачи увлекательны, поэтому их интересно решать.

Однакоими занимались и такие учёные, как Леонард Эйлер, Карл-Фридрих Гаусс,Эжен Шарль Каталан, Дональд Кнут и многие другие современные учёные,что должно убедить вас в серьёзности и глубине этих задач, многие из которых непосредственно связаны и с практическими комбинаторнымипроблемами, о чём мы не раз будем говорить на страницах этой книги. Ацель её в том и состоит, чтобы показать на этих исторических примерах,как можно решить эти задачи по-современному, с помощью компьютера.Впрочем, этими «большими» задачами не ограничивается список тем книги.

Мы решим и «сопутствующие» комбинаторные проблемы:Раскраска вершин правильного многоугольникаСлова Линдона и де БройнаКружки с цифрамиМаксимальная числовая подпоследовательностьЗадача Макмагона о квадратном доминоРасстановка ладей и задача о назначенияхМагическая таблицаЗадачи Дональда КнутаВ конце каждой главы вы найдёте «домашние» задания для самостоятельного решения, которые помогут вам закрепить знания по комбинаторикеи программированию.6Для решения задач мы будем использовать как общие методы –полный перебор,перебор с возвратами,жадные алгоритмы,динамическое программирование,имитация отжига, так и чисто комбинаторные генерирование перестановок,генерирование сочетаний,генерирование разбиений,генерирование композиций,генерирование браслетов,генерирование ожерелий,генерирование слов Линдона,генерирование слов де Бройна,генерирование чисел Каталана,генерирование расстановок скобок.Все приложения написаны на языке Си-шарп, который идеально подходитдля решения комбинаторных задач, но исходный код без труда можетбыть переведён на любой другой современный язык программирования,поддерживающий платформу .NET.Я надеюсь, что книга будет полезна всем программистам, интересующимся комбинаторикой вообще и комбинаторными алгоритмами в частности,а также школьникам старших классов и студентам.Валерий Рубанцев7Условные обозначения, принятые в книге:Дополнение, примечаниеПредложение, ненавязчивое требованиеЗадания для самостоятельного решенияИсходный кодПапка с исходным кодом приложенияВсе исходные коды находятся в папке _Projects.8ОглавлениеКак решать комбинаторные задачи на компьютере ..................................

2От автора........................................................................................................................... 4Оглавление ...................................................................................................................... 8Полное оглавление ...................................................................................................... 9Глава 5.

Магические квадраты ................................................................................. 11Математические подробности ............................................................................. 13А сколько всего магических квадратов? ..........................................................

15Как составить магический квадрат? ................................................................... 16Проект Магические квадраты (Magic) ............................................................... 19Магические ферзи ................................................................................................... 25Магические квадраты четвёртого порядка ...................................................... 27Проект Чётно-чётные квадраты (DEMS) ........................................................... 33Проект 4 x 4 (_4x4)................................................................................................. 38Глава 6.

Словесные магические квадраты .......................................................... 43Проект Магические слодраты (WordSquares) ............................................... 47Глава 9. Считаем деньги ............................................................................................ 60Проект Разменный пункт (Разбиения) ...............................................................

60Ответы ............................................................................................................................. 86Словесные магические квадраты ........................................................................ 86Литература ..................................................................................................................... 879Полное оглавлениеКак решать комбинаторные задачи на компьютереОт автораОглавление37Глава 1.

Ожерелья и браслетыПроект Стильные стринги (Ожерелья)Проект Ожерелья (Ожерелья)Проект Браслеты (Ожерелья)Слова ЛиндонаСлова де БройнаНемаркированные ожерелья10102339445159Глава 2.Числовая круговертьПроект Вставляем числа! (НиЖ887)Проект Алгоритмические гонки (MaxSequence)1.

Золотая цепочка2. Денежная реформа3. Гнем Бентли в дугу647181909394Глава 3. Треугольное и квадратное доминоПроект Квадратное домино (QDomino)95100Глава 4. Отжигаем!Проект Метод имитации отжига (Simulated Annealing)118119Глава 5. Магические квадратыМатематические подробностиА сколько всего магических квадратов?Как составить магический квадрат?Проект Магические квадраты (Magic)Магические ферзиМагические квадраты четвертого порядкаПроект Чётно-чётные квадраты (DEMS)Проект Универсальный генератор (UniGen)Проект 4 x 4 (_4x4)Проект Уникальные четвёрки (_4x4-880)13713914114214515115315916416817210Пентамагики179Глава 6.

Словесные магические квадратыПроект Магические слодраты (WordSquares)182186Глава 7. Задача Иосифа ФлавияСемеро смелыхПроект Ударим Си-шарпом по… (Josephus Problem)По порядку номеров – рассчитайсь!199200204214Глава 8. Занимательная ГауссианаПроект Ладные ладьи (Ферзи)Задача о назначенияхРешаем задачу ГауссаПроект Ферзевой гамбит (Ферзи)Ищем уникумов!Проект Фокус-покус с числами (Magic Matrix)218221224227230234236Глава 9. Считаем деньгиПроект Разменный пункт (Разбиения)Проект Свои деньги ближе к телу! (Размен)248248271Глава 10. Даёшь сотню!Проект Опять сотня (_100)Проект Рацпредложение (_100_2)Проект Кулибин (_100_3)Проект Кнут и скобки (Скобки)Проект Обратная польская запись, или А нам всё постфикс! (RPN)Первая задача Дональда КнутаВторая задача Дональда Кнута284284293301309320331347ОтветыПентамагикСловесные магические квадратыРасставьте знаки360360360361Литература36311Глава 5.