Курсовая работа: Задача Y пентамино

1 1 1 7 11 11 11 12 12 12 12 12

3)

7 7 7 7 9 10 10 10 8 1 1 1

5 7 4 4 9 9 10 8 8 2 2 1

5 4 4 11 11 9 10 3 8 8 2 1

5 4 11 11 11 9 3 3 3 2 2 6

5 5 12 12 12 12 12 3 6 6 6 6

Как можно заметить, каждая цифра в области означает номер фигуры, которая поставлена на эту клетку. Т. е. если индекс i фигуры в массиве =7, то клетки, занятые этой фигурой отмечаются этой цифрой.

-Заключение

Итак, мы завершили разработку курсовой работы, а именно её главной цели - создание программного продукта, находящего решения головоломки «Y-пентамино». Подводя итоги, можем сделать несколько важных выводов.

1. Применение метода проб и ошибок, вместо обычного полного перебора, позволяет существенно сократить время выполнения программы, а также объём затрачиваемой памяти. Это было выяснено при анализе сложности алгоритма по алгоритмической мере А.Колмогорова. Вычисления показали, что количество информации алгоритма по методу проб и ошибок, значительно меньше, чем у алгоритма прямого перебора.

2. Важной характеристической особенностью разработки программы для решения головоломок является то, что практически невозможно сократить число переборов за счёт рассмотрения отдельных случаев, не имеющих места быть в том или ином случае. В задаче пентамино была только возможность предотвратить рассмотрение замкнутых областей доски, площадь которых меньше или больше пяти(в такие области фигуру уже ставить нельзя, поэтому просматривать её в программе нет смысла - нужно искать другое решение). Однако даже в этом случае существуют такие варианты, при которых ограничение процесса расстановки этим условием ведёт к появлению ошибок. В остальных же случаях, это сделать крайне сложно, так как далеко не все могут не только выявлять закономерности при решении головоломок, но и даже просто решить их.

3. Основная сложность в программе принадлежит представлению данных и непосредственной работе с ними. Все остальные вопросы возникают именно вследствие специфичности исходных данных и результата. Действительно, каждая фигура пентамино есть двумерный массив, а массив фигур представляет собой уже трёхмерный. Это довольно громоздко. И особенно это видно при проверке возможности вставки фигуры в прямоугольную область, когда приходится оперировать с большим числом циклов, чтобы проверить каждый элемент пентамино. В остальном же, а именно в алгоритме нахождения покрытия доски с фигурками пентамино, эта задача мало, чем отличается от той же известной задаче о расстановке восьми ферзей на шахматной доске.

-Список литературы

1. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003.

2. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си: Учеб. пособие. – Финансы и статистика, 2004.

3. Х.М. Дейтел, П. Дж. Дейтел. Как программировать на С++: Четвёртое издание. Пер. с англ.— М.: ООО «Бином—Пресс», 2005г.

4. Дж. Макконнелл. Основы современных алгоритмов. 2-е дополненное издание. Москва: Техносфера, 2004.

5. Морозов М. Большая книга загадок и головоломок № 5.Эгмонт Россия Лтд, 2004.