Задача Y- пентамино

условии задачи повороты фигур не предусмотрены), всё-таки это займёт много места. Так как тест программы заключается в выводе меньшего количества результатов, то я приведу несколько примеров вывода для области 6х10 и5х12.

6х10:


1 1 1 2 2 3 4 4 5 5

6 6 1 2 3 3 3 4 4 5

7 6 1 2 2 3 8 8 4 5

7 6 6 9 9 9 10 8 8 5

7 7 9 9 10 10 10 8 11 11

7 12 12 12 12 12 10 11 11 11

2)

9 4 4 7 7 7 7 11 11 11

9 9 4 4 7 2 2 2 11 11

5 9 10 4 3 2 8 2 6 6

5 9 10 3 3 3 8 8 6 1

5 10 10 10 3 8 8 6 6 1

5 5 12 12 12 12 12 1 1 1

3)

11 11 12 10 9 9 9 1 1 1

11 11 12 10 10 10 9 9 6 1

7 11 12 10 4 4 6 6 6 1

7 7 12 4 4 8 6 3 2 2

7 5 12 4 8 8 3 3 3 2

7 5 5 5 5 8 8 3 2 2


5х12:


1)

7 7 7 7 8 8 10 9 9 9 5 5

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

2 2 2 3 8 1 10 4 4 6 6 5

11 11 3 3 3 1 1 1 4 4 6 5

11 11 11 3 12 12 12 12 12 4 6 6

2)

9 5 5 10 10 10 4 4 6 6 8 8

9 9 5 7 10 4 4 3 2 2 6 8

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

1 9 5 7 7 11 11 3 2 2 6 8

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-пентамино». Подводя итоги, можем сделать несколько важных выводов.

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

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

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

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


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

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

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

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

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


Задача Y- пентаминоЗадача Y- пентаминоЗадача Y- пентамино

18


Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: