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

-Введение

Широкое распространение идей структурного программирования в последние 20-30 лет оказало большое влияние на теорию и практику программирования и привело к пересмотру роли типа и структуры данных при разработке соответствующих алгоритмов и программ. В связи с этим в последние десятилетия при производстве сложных программных систем требуется подго­товка высококвалифицированных специалистов, в совершенстве владеющих современной теорией построения систем обработки данных. В этой теории важное место занимают методы органи­зации и обработки данных. Решение любой задачи сводится к обработке множества данных, которые представляют собой аб­стракцию некоторого фрагмента реального мира.

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

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

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

Целью этой курсовой работы является создание программной реализации алгоритма, который находит решения геометрической головоломки: Y-пентамино. Игра "Пентамино" - это очень увлекательное и полезное занятие, развивающее множество способностей. Фигурки представляют собой все односвязные комбинации из пяти квадратиков. Всего в одном наборе 12 фигур. Фигурки можно изготовить из бумаги, картона, пластилина, дерева, глины, или из пластмассы, в общем, из чего угодно. Дальше, берём эти фигурки и начинаем собирать прямоугольную область, размером 6х10 квадратиков. Эта задача достаточно сложна для вычислений вручную, но ЭВМ справляется с ней гораздо быстрее. Основные этапы создания программы, включая процесс разработки алгоритма, выбора языка программирования, анализ сложности алгоритма и программы, приведены ниже.

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

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

-Теоретические сведения, касающиеся метода

При решении задачи, поставленной в курсовой работе, следует применить два основных алгоритмов перебора: алгоритм с возвратами назад(backtracking) и метод проб и ошибок.

- Алгоритм с возвратами назад:

Метод перебора с возвратами позволяет решать практически бесчисленное множество задач, для многих из которых не известны другие алгоритмы. Несмотря на такое большое многообразие переборных задач, в основе их решения есть нечто общее, позволяющее применить данный метод. Таким образом перебор можно считать практически универсальным методом переборных решения задач. Приведём общую схему этого метода:

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

{ поиск одного решения } procedure backtracking(k: integer); { k - номер хода }begin { инициализация выбора варианта } repeat { выбор варинта } if { вариант подходит } then begin { запись варианта } if { решение не найдено } then begin backtracking(k+1); { рекурсивный вызов } if { решение не найдено } then { стирание варианта } end else { вывод решения } end; until { вариантов нет } or { решение найдено }end; begin { запись первого варианта } backtracking(1);end.К достоинствам схемы следует отнести общность, простоту и логичность. Но она имеет и недостатки. Во-первых, надо самому делать запись первого варианта, неплохо бы, чтобы это делала сама процедура. Также в ней использует цикл repeat: можно допустить ошибку в формировании условия выхода из цикла, особенно, если не знаешь законы де Моргана, к тому же иногда проще использовать цикл for, а если вариантов мало, можно обойтись вообще без циклов. Попытаемся устранить выше приведенные недостатки. Для разработки общей схемы перебора с возвратами воспользуемся процедурой из задачи о лабиринте, просто следует ее обобщить: { поиск одного решения } procedure backtracking(k: integer); { k - номер хода }begin { запись варианта } if { решение найдено } then { вывод решения } else { перебор всех вариантов } if { вариант подходит } then backtracking(k+1); { рекурсивны

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать