int j1,h1,b;
//цикл нахождения всевозможных вариантов для i-ой фигуры
for(int j=1;j<=n;j++)
{ j1=j;
//просматриваем каждый столбец j-ой строки
for(int h=1;h<=m;h++)
{ h1=h;b=1;
//циклы доступа к элементам массива формата каждой фигуры
for(int k=1;k<=5;k++)
{ for(int l=1;l<=5;l++)
//если сумма элементов массива формы i-ой фигуры
//и элементов массива поля расстановки больше 1
//т.е. происходит наложение фигур друг на друга, то b присвоить значение 0
{ if (image[i].shape[k][l]+field[j1][h1]>1) b=0;
h1++;
}
j1++;h1=h;
}
//если не разу не произошло наложение фигур, т.е. фигура подходит,
//то выход из цикла поиска
//т.е. из цикла возможных исходных позиции фигуры по столбцам
if (b==1) break;
j1=j;
}
if (b==1)
//присваиваем полю расстановки подошедшую нам фигуру
{ for(int k=1;k<=5;k++)
for(int l=1;l<=5;l++)
if (image[i].shape[k][l]==1) field[-j+k][-l+h]=i;
//поменяли признак находится на доске/не находится
image[i].located='Y';
//если это не случай с последней фигурой,
//то рекурсией осуществляем установку след.фигуры
if (i<12) placing(++i);
// else //иначе, т.е. если дошли до посл.фигуры(нашли 1 вариант), вывод на экран
// print();
//обнуляем значения последней поставленной фигуры
//на поле расстановеи и ищем след.подходящий вариант
for(k=j;k<=6;k++)
for(int l=h;l<=10;l++) field[k][l]=0;
//поменяли признак находится на доске/не находится
image[i].located='N';
}
} //выполняем всё вышесказанное для каждой фигуры,
//устонавливая её,находя подходящий вариант и
//удаления для последущего поиска других вариантов
}
//вывод данных(поле расстановки) на экран
void print(int geo[12][25])
{
for(int i=1;i<12;i++){
for(int j=1;j<25;j++) //координаты поля расстановки
cout<<geo[i][j];
cout<<endl;} //непосредственный вывод
//сохранение формата вывода
}
Несмотря на гибкость встроенных средств языка С++ и его неоспоримое удобство при создании программ, он имеет ряд особенностей, часто ведущих к путанице и ошибкам. Добавленные комментарии позволяют избежать этого. По этой причине текст программы богато ими снабжён.
-Тестирование программы
В процессе тестирования программы необходимо следует провести анализ сложности алгоритма и оценку эффективности её работы.
Проведём этот анализ с помощью алгоритмической меры Колмогорова. Для оценки логической сложности алгоритмов предлагается использовать количественную меру в виде полной энтропии (алгоритмической меры количества информации по Колмогорову) двоичной последовательности
Ia(k, s)=n*H(k,s),
где H(k,s) = -((k/n)log(k/n)+(s1/n)log(s1/n)+(s0/n)log(s0/n))
илиН(к,s)= -( (k/n)log(k/n)+2(s/n)log(s/n));
n - общее число выходов безусловных и условных операторов содержательного алгоритма (граф-схемы),
к - число выходов безусловных операторов,
s1, - число «единичных» выходов условных операторов,
S0 - число «нулевых» выходов условных операторов,
s — число условных операторов (s=s1= s0).
Ia(k, s)=-n((k/n)log(k/n)) бит — доля логической сложности1 алгоритма по безусловным операторам;
Ij(k,s) = -n(2(s/n)log(s/n))бит-доля логической сложности алгоритма по условным операторам.
Эта формула представляет собой абсолютную логическую сложность алгоритма, измеренную в двоичных единицах (битах).
Вычислим эти значения для нашего алгоритма:
n=13; k=5; s=s1=s0=4;
k/n=0.39; s/n=0.31;
(k/n)log(k/n)=-0.53; (s/n)log(s/n)=-0.52;
Н(к,s)= -(-0.53+2(-0.52))=1.57; I(k, s)=13*1.57=20.41 бит.
Учитывая тот факт, что количество информации, затрачиваемое при реализации алгоритма решения по методу полного перебора, составляет около 28.6, мы можем смело утверждать, что данный алгоритм достаточно эффективен. Несомненно, это не означает, что реализованная по этому алгоритму программа идеальна. Например, её можно было оптимизировать, сократив количество столбцов в массиве geometry на 8, так как последние восемь элементов нигде не используются. Однако, это алгоритмическая мера и многое ещё зависит от реализации алгоритма в программном продукте.
В моей задаче требуется вывести все возможные решения, но несмотря на то, что их не так много, как ожидалось(видимо из-за того, что в условии задачи повороты фигур не предусмотрены), всё-таки это займёт много места. Так как тест программы заключается в выводе меньшего количества результатов, то я приведу несколько примеров вывода для области 6х10 и5х12.
6х10:
1)
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-пентамино». Подводя итоги, можем сделать несколько важных выводов.
1. Применение метода проб и ошибок, вместо обычного полного перебора, позволяет существенно сократить время выполнения программы, а также объём затрачиваемой памяти. Это было выяснено при анализе сложности алгоритма по алгоритмической мере А.Колмогорова. Вычисления показали, что количество информации алгоритма по методу проб и ошибок, значительно меньше, чем у алгоритма прямого перебора.
2. Важной характеристической особенностью разработки программы для решения головоломок является то, что практически невозможно сократить число переборов за счёт рассмотрения отдельных случаев, не имеющих места быть в том или ином случае. В задаче пентамино была только возможность предотвратить рассмотрение замкнутых областей доски, площадь которых меньше или больше пяти(в такие области фигуру уже ставить нельзя, поэтому просматривать её в программе нет смысла - нужно искать другое решение). Однако даже в этом случае существуют такие варианты, при которых ограничение процесса расстановки этим условием ведёт к появлению ошибок. В остальных же случаях, это сделать крайне сложно, так как далеко не все могут не только выявлять закономерности при решении головоломок, но и даже просто решить их.
3. Основная сложность в программе принадлежит представлению данных и непосредственной работе с ними. Все остальные вопросы возникают именно вследствие специфичности исходных данных и результата. Действительно, каждая фигура пентамино есть двумерный массив, а массив фигур представляет собой уже трёхмерный. Это довольно громоздко. И особенно это видно при проверке возможности вставки фигуры в прямоугольную область, когда приходится оперировать с большим числом циклов, чтобы проверить каждый элемент пентамино. В остальном же, а именно в алгоритме нахождения покрытия доски с фигурками пентамино, эта задача мало, чем отличается от той же известной задаче о расстановке восьми ферзей на шахматной доске.
-Список литературы
1. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003.
2. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си: Учеб. пособие. – Финансы и статистика, 2004.
3. Х.М. Дейтел, П. Дж. Дейтел. Как программировать на С++: Четвёртое издание. Пер. с англ.— М.: ООО «Бином—Пресс», 2005г.
4. Дж. Макконнелл. Основы современных алгоритмов. 2-е дополненное издание. Москва: Техносфера, 2004.
5. Морозов М. Большая книга загадок и головоломок № 5.Эгмонт Россия Лтд, 2004.