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

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