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

Начало

1. Выполнить пункты 2-8; (v1)

2. Если не достигли пределов доски, то выполняем пункт 3,иначе пункт 9; (z1)

3. Если сумма каждого элемента i-ой фигуры пентамино и каждого поля доски, начиная с исходной позиции j, не больше единицы, то пункт 4, иначе пункт 2; (z2)

4. Присваиваем соответствующим элементам доски значение i (т.е. устанавливаем фигуру пентамино на доску); (v2)

5. Если i<12, то пункт 6, иначе 7; (z3)

6. Увеличиваем i на единицу и переход к пункту 2; (v3)

7. Вывод на экран одного решения; (v4)

8. Обнуляем значения i-ой фигуры на доске; (v5)

9. Если j<n, то пункт 1; (z4)

Конец

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

-Обоснование выбора структур данных

Прежде чем приступить к разработке алгоритма и созданию программы, нам необходимо иметь представление о способе представления данных в ЭВМ. Поэтому первым вопросом, при разработке программ, является выбор структур данных. В своей программе мне пришлось применить последовательно две структуры для представления в памяти фигур пентамино. Изначально каждая фигура была описана как строка массива geometry. Количество столбцов в этом массиве-25. Именно столько необходимо для представления двумерного массива 5х5. А количество строк соответственно равно 12, так как мы знаем, что всего фигурок двенадцать.

Возможно, возникнет вопрос: «Почему для представления каждой фигуры нужно 25 чисел?» Действительно, это довольно много, но если для каждой фигуры создать отдельный массив со своей “собственной” размерностью, то в памяти необходимо хранить этот массив размерностей для каждой фигуры пентамино и обращаться к ним исключительно по индексам массива. А это помимо того, что неудобно в процессе отладки, к тому же достаточно громоздко и ничуть не экономит память. Вследствие этого, я предпочла иметь константный массив geometry[12][25].

Однако, как уже было сказано, такое представление данных имеется только на начальном этапе работы программы. Если при выполнении рекурсии, в обращение к подпрограмме, в качестве фактических параметров выступает массив, размерностью 12х25, то это чрезвычайно снижает эффективность программы, экономию памяти, а также быстродействие. Несмотря на то, что современная вычислительная система справится даже с наихудшим программным вариантом алгоритма, этот факт стоит учитывать. По этой причине, мне пришлось перевести массив geometry в структуры типа массив записей. Каждая запись массива имеет два поля: массив shape(5x5), в котором представлена форма каждой фигуры и переменная located. Она служит чем-то вроде метки на каждую фигуру, предоставляющей информацию о том стоит ли фигура на доске или нет. С такой структурой данных работать гораздо удобнее так как при рекурсивном вызове процедуры, мы передаём всего лишь текущий элемент массива записей, то есть одну запись.

Опять-таки, вновь возникает вопрос: «Почему нельзя было представить фигуры пентамино в таком виде, не затрачивая лишней памяти на массив geometry?» Это возможно лишь в том случае, если данные вводят с устройства ввода, но это слишком утомительно, так как их объём достаточно велик. Также можно было считывать с файла, но эти способы идентичны по объёму занимаемой памяти. Описывать же каждое поле каждой записи в виде константы не позволяют средства языков программирования, как TurboPascal, так и VisualC++.

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

1. Подпрограмма из массива geometry формирует структуру типа массив записей, используемую далее в главной подпрограмме placing:

void forming();

2. Подпрограмма непосредственно реализует метод проб и ошибок с использованием метода backtracking. Осуществляет рекурсивное покрытие прямоугольной области nxm фигурами пентамино и при нахождении каждого решения обращается к функции print:

void placing(int i);

3. Подпрограмма осуществляет вывод на экран различных данных, используемых и полученных в программе:

void print();

Вызов функций forming() осуществляется непосредственно из основной функции main(), функция placing(inti) изначально вызывается в функции main, а затем происходит рекурсивный вызов подпрограммы.

-Программа

Далее приводится непосредственно сам текст исходного кода программы, реализующей алгоритм решения задачи Y-пентамино.

#include<iostream.h>

#include<cmath>

#include"pent.h"

void forming(int geo[12][25]);