Оценка асимптотической временной сложности алгоритма поиска с возвращением

Размещено на http://www.allbest.ru/

Задание на курсовую работу

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

В качестве задачи на курсовую работу была предложена следующая комбинаторная задача:

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

Исследовать асимптотическую временную сложность решения задачи в зависимости от N.

Пример: SEND MORE MONEY соответствует 9567+1085=10652.

При выполнении курсовой работы требуется:

· Формализовать поставленную задачу (перейти от словесной неформальной постановки к математической формулировке);

· Приспособить общие методы и алгоритмы решения к решению конкретной задачи;

· Провести сравнительную оценку различных вариантов с целью выбора наиболее эффективных структур данных и алгоритмов обработки;

· Исследовать и оценить теоретические и экспериментальные методы сокращения перебора в комбинаторных задачах;

· Оценить аналитически и экспериментально эффективность предложенных в работе алгоритмов (временную и емкостную сложности);

· Программно реализовать разработанные алгоритмы на одном из алгоритмических языков программирования.

· Экспериментально исследовать различные способы программной реализации алгоритмов.

Анализ задания. Выводы о методах решения и путях повышения эффективности вычислений

математический алгоритм программирование данные

Рассмотрим индивидуальное задание и проанализируем методы решения. Эта задача имеет логическое ограничение на количество различных букв в строке - количество цифр 10. Поэтому, бесконечно расти, эта задача может только в размерности чисел, но здесь ограничение может быть наложено скорее возможностями программных средств, чем алгоритмом реализации.

Сама идея решения данной задачи заключается в том, что мы последовательно проходим введенную строку и заменяем все вхождения одной буквы на выбранную цифру. После расстановки цифр расставляются знаки операции, и проводится проверка (является решением или нет). Знаков операции всего 4: сложение, вычитание, умножение и деление. Знак `=' ставится вместо последнего не буквенного символа. Так как выбор цифр, которые будут подставлены, выбираются последовательно необходимо запретить выбор тех же цифр. Для этого создадим таблицу размером 10Ч10, и введем следующие обозначения

0- символ можно выбрать:

1- символ выбран в этой строчке в настоящее время;

2- символ был использован в этой строчке раньше (в этой строчке использовать этот символ больше нельзя, но в следующих можно);

3- символ выбран в выше стоящей строчке;

Ввод данной таблицы обусловлен тем, что в данной задаче не возможно определить для данного узла какие значения уже подставлялись, а какие нет. В этом случае возможно повторная проверка уже пройденного пути.

I. Формализация задачи

1.1 Структуры данных для представления объектов задачи

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

Для алгоритма поиска с возвращением обычно решением является вектор(a₁, a₂,…), но в нашем случае таким решением будет строка с полностью замененными буквами и подставленными знаками, которая и выводится на экран, в том случае если она верна.

Выбор следующего шага выполняется по таблице описанной выше. Так же выполняется подстановка знаков. При продвижении в глубину в строке проставляются 3 в тех столбцах, где в предыдущей строке стоит 3 или 1, и эти цифры уже не могут быть выбраны.

1.2 Анализ ограничений и усовершенствований. Аналитические и/или экспериментальные оценки

Основное ограничение в этой задаче указано в самом задании. Это ограничение связано в однозначном соответствии букв и цифр.

Второе ограничение накладывается на количество знаков, оно влияет на количество пройденных вершин и соответственно на время работы алгоритма. В данной работе это ограничение равно 4. Максимальное число узлов дерева равно 10!. И рассчитывается по формуле:

, где n - число различных букв в строке.

1.3 Разработка алгоритмов решения задачи

В данном пункте описаны алгоритмы для решения поставленной задачи. Сначала приведем сам алгоритм, а потом разберем его.

Алгоритм 1. Итерационный алгоритм поиска с возвращением.

Алгоритм 1 является модификацией общего итерационного алгоритма поиска с возвращением. Суть самого алгоритма описывать не буду, разберу лишь некоторые процедуры.

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



Процедура Copy позволяет избежать выбора уже выбранных ранее цифр.

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



Процедура Vozvrat делает обратный шаг, она возвращает последние замененные символы на место и отмечает обратный шаг в таблице.

II. Оценка асимптотической временной сложности алгоритма (Метод Монте-Карло)

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

В данной работе этот метод используется для исследования асимптотической временной сложности решения задачи в зависимости от количества различных букв в строке и количества знаков операций.

Размер задачи	Метод Монте-Карло	Фактичкески
Число Букв	Число символов	Число узлов	Порядок роста	Число узлов	Время (мс)	Порядок роста
6	1	8231241		7921100	2140
6	2	8763254	1,06	8543802	2391	1,11
6	3	9245687	1,05	9234561	2641	1,10
6	4	10632540	1,15	10045678	2857	1,08

Данная таблица показывает рост времени и пройденных узлов при увеличение количества знаков при одном и том же числе различных букв.

Размер задачи	Метод Монте-Карло	Фактичкески
Число Букв	Число символов	Число узлов	Порядок роста	Число узлов	Время (мс)	Порядок роста
7	1	3546211		3211300	9406
8	2	10542136	2,9	9864100	35328	3,7
9	3	25874961	2,4	24660250	83218	2,5
10	4	36844794	1,4	36990375	125512	1,5

Данная таблица показывает рост времени и пройденных узлов при одновременном увеличение количества знаков и различных букв.

Размер задачи	Метод Монте-Карло	Фактичкески
Число Букв	Число символов	Число узлов	Порядок роста	Число узлов	Время (мс)	Порядок роста
1	1	51		50	0
2	1	472	9	460	0
3	1	3751	8	3700	15
4	1	26135	7	26020	63	4
5	1	157564	6	157060	453	7
6	1	793451	5	792100	2106	4,7
7	1	3324578	4,1	3211300	9844	4,4
8	1	10065487	3	9864100	33047	3,5
9	1	21789546	2	20750500	74078	2,4
10	1	34589744	1,5	33492900	108203	1,4

Данная таблица показывает рост времени и пройденных узлов при увеличение количества различных букв, при одном и том же количестве знаков.

III. Программная реализация алгоритма

3.1 Реализация данных

При реализации данных использовались следующие структуры:

int Byval[11][10] - Таблица хранения уже пройденного пути

char sstr[27] = "abcdefghijklmnopqrstuvwxyz"; - массив элементов распознаваемых как буква

int Znak[4][4] - Таблица хранения пройденного пути для операций

char* isch_str - исходная строка с которой проводятся все операции

Так же для удобства работы был создан стек под эту программу

struct stac

{

int nom;

char sym;

};

В которую записываются все символы заменяемые в строке.

Следующая подставляемая цифра выбирается следующим образом:

Берется первый элемент, помеченный 0 в данной строке (зависит от Glub) и помечается 1.

3.2 Реализация алгоритмов

Рассмотрим подробнее программную реализацию алгоритма.

При вводе строки она проверяется на два условия

1 - различных буквенных символов должно быть не более 10

2 - не должно быть два подряд идущих не буквенных символов, и всего не буквенных символов не должно быть не более 4.(procedure Proverka и Prover)

Procedure Rabota - основная процедура в которой и происходит основная работа.

Procedure Pystot - процедура просматривающая таблицу Byval и определяющая есть ли еще цифру доступные к вставке.

Procedure Sled - процедура выбирающая еще не использованную цифру.

Procedure NextPo - выбор следующей не заменненой буквы. Проходя по строке и сравнивая каждый символ со строкой sstr первый символ который есть в sstr выбирается на замену.

Procedure Podstano - процедура подставляет знаки и выполняет окончательную проверку строки. Если строка верна то она выводится на экран.

Все процедуры разработаны для итерационного варианта реализации алгоритм поиска с возвращением. Хотя итерационный и рекурсивный вариант похожи и переход от одного варианта реализации к другому не займет много времени и не потребует больших изменений в тексте программы. Автор выбрал для программной реализации итерационный вариант в силу того, что рекурсивный вариант требует больше памяти, несколько сложнее для реализации и в силу личных предпочтений автора.

3.3 Исследование способов программирования

Программа была реализована на языке высокого уровня Microsoft Visual C++ 6.0 d в виде одного модуля

Размеры исходного файла: 6кбайт

Размеры исполняемого файла: 208 кбайт

Приведу пример работы данной задачи

asd fgh sderg

367*184=67528

514*028=14392

Выводы по работе

В данной курсовой работе в соответствие с заданием были разработаны и исследованы алгоритмы решения поставленной комбинаторной задачи. Как основа алгоритма решения были взят общий итерационный алгоритм поиска с возвращением. Отличительной чертой задачи предложенной на курсовой проект является то, что она имеет логические ограничения, и поэтому не способна расти до бесконечности, так же в этой задаче не удалось найти способов сокращения перебора, но нужно заметить, что для данной задачи они не очень важны, так как наибольшее время работы программы 2 минуты (при изменение разрядности это время будет не значительно увеличиваться). Но время работы порядка 1 часа получить не получится.

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

Приложение

#include <iostream.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#include <Windows.h>

#include <conio.h>

char isch_str[30];

char sstr[27] = "abcdefghijklmnopqrstuvwxyz";

int chisla[10]= {1,1,1,1,1,1,1,1,1,1};

char Chisl[11] = "1234567890";

char cfstr[27];

char Znaki[5]="+-*/";

int Byval[11][10]= {{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0}};

int Znak[4][4]={{0,0,0,0},

{0,0,0,0},

{0,0,0,0},

{0,0,0,0}

};

int Ukaz;

int Zna;

int Chis;

int Pustota=0;

int Prisn=1;

long okr;

int Ver=0;

double start,end;

struct stac

{

int nom;

char sym;

};

stac STAC[15];

stac POPS()

{

Ukaz--;

return(STAC[Ukaz]);

}

int PUSHS(stac Elm)

{

STAC[Ukaz]=Elm;

Ukaz++;

return(0);

}

int Proverka(char* str)

{

memset(cfstr,0,27);

for (int i=0, j = 0; i < (int)strlen(str); i++)

if((strchr(sstr,str[i])) && !cfstr[str[i]-97])

{

j++;

cfstr[str[i]-97] = 1;

};

for(int a=0; a<(int)strlen(str);a++)

if (!(strchr(sstr,str[a]))) Zna++;

return j;

}

int Prover(char* str)

{

int Pre=0,kod;

for(int i=0; i<(int)strlen(str)-1;i++)

{

kod=str[i];

if ((!((kod>96)&&(kod<123)))&&(Pre)) return(0);

else if (!((kod>96)&&(kod<123)))Pre=1;

else Pre=0;

}

for(int j=(int)strlen(str)-2;j>=0;j--)

if(!strchr(sstr,str[j])) {str[j]='=';return(1);}

return(0);

}

int Podstan(char* str, char chr,char chrz)

{

for (int i=0; i<(int)strlen(str); i++)

if (str[i]==chr) str[i]=chrz;

return(0);

}

int Vozvrat(char* str,int Glub)

{

stac Pr;

char ch,cho;

int pos;

Pr=POPS();

ch=Pr.sym;

pos=Pr.nom;

cho=str[pos];

for(int j=pos; j<=(int)strlen(str);j++)

{if(str[j]==cho) str[j]=ch;}

for(int i=0; i<10; i++)

Byval[Glub][i]=0;

{for (int b=0; b<10; b++)

if (Byval[Glub-1][b]==1) Byval[Glub-1][b]=2;

}

return(0);

}

int Proverca(char* str,int Glub)

{

return(1);

}

int NextPo(char* str, int po)

{ for(int i=0; i<(int)strlen(str);i++ )

if(strchr(sstr,str[i])) return(i);

return(-1);

}

int Pystot(char* str, int Glub)

{

for(int j=10,a=0; a<10; a++)

if(Byval[Glub][a]) j--;

return(j);

}

int Copy(int Glub, char ch1)

{

if (Glub==0) Byval[Glub][ch1-48]=1;

else{for(int i=0;i<=10;i++)

if ((Byval[Glub-1][i]==1)||(Byval[Glub-1][i]==3)) Byval[Glub][i]=3;}

return(0);

}

char Sled(int Glub)

{

for (int i=0; i<10; i++)

if (!(Byval[Glub][i])) {Byval[Glub][i]=1;return(i+48);}

return(0);

}

int Pys(int zn)

{

for(int j=4,i=0; i<=4;i++)

j-=Znak[zn][i];

return(j);

}

int Vyb(char* str, int p)

{

for(int i=p+1; i<(int)strlen(str);i++)

if(!(strchr(Chisl,str[i]))) return(i);

return(-1);

}

char V(int zn)

{

for (int i=0; i<4; i++)

if (!Znak[zn][i])

{Znak[zn][i]=1;

switch(i){

case(0):return('+'); break;

case(1):return('-'); break;

case(2):return('*'); break;

case(3):return('/'); break;

}

}

return(0);

}

int Voz(char* str)

{ stac pred;

pred=POPS();

str[pred.nom]=pred.sym;

return(0);

}

int PROVERKA(char* str,int zn)

{ int pos=0;

char ch;

double dw1=atof(str),dw2;

int i=0;

if (zn<Zna) return(0);

while (pos<(int)strlen(str))

{

while (isdigit(str[pos])) pos++;

ch=str[pos];

pos+=1;

dw2=atoi(str+pos);

switch(ch)

{

case('='):if (dw1==dw2) cout<<str<<endl; Pustota=1;return(1);

case('+'):dw1+=dw2; break;

case('-'):dw1-=dw2; break;

case('*'):dw1*=dw2; break;

case('/'):if (!(dw2==0))dw1/=dw2; break;

}

}

return(0);

}

int Podstano(char* str, int Glub)

{

int zn=0,p=0,Pri=1;

stac Per;

char ch;

Ver++;

if (Chis>Glub)return(0);

while (zn>=0)

{

while((Pri)&&(Pys(zn)))

{p=Vyb(str,p);

Per.nom=p;

Per.sym=str[p];

PUSHS(Per);

ch=V(zn);

Ver++;

if(str[p]!='=')

{str[p]=ch;

zn++;

if(zn==1)

{ for(int a=3;a>=0;a--)

if (Znak[0][a]==1){ Znak[1][a]=1;

break;}}

if (!(zn==1)) {for(int i=0;i<4;i++)

Znak[zn][i]=Znak[zn-1][i];}

}

if (PROVERKA(str,zn)) Pri=0;

}

if (zn!=0) Voz(str);

for(int b=0; b<4;b++)

Znak[zn][b]=0;

zn--;

Pri=1;

p=0;

}

Prisn=0;

return(0);

}

int Rabota(char* str)

{ int Nomerchis=0; //Номер последнего заменненого символа

memset(chisla,1,10);

char* isch=str;

char ch,ch1;

int po=0,k=1,Nu=0,Glub=0; //Ex-признак выхода

stac Per;

while (Glub>=0)

{

while ((Prisn)&&(Pystot(str,Glub)))

{

if (po!=-1)

{

ch=str[po];

Per.nom=po;

Per.sym=ch;

PUSHS(Per);

ch1=Sled(Glub);

if(ch1!=0)Podstan(str,ch,ch1);

Glub++;

Copy(Glub,ch1);

Podstano(str,Glub);}

po=NextPo(str,po);

}

Vozvrat(str,Glub);

Glub--;

Prisn=1;

}

return(0);

}

int main()

{

cout<<”Введите строку”<< endl;

fgets(isch_str,30,stdin);

Chis=Proverka(isch_str);

if (Chis>10) {cout<<”Неправильная строка"<<endl; getch();exit(0);}

if (!(Prover(isch_str))) {cout<<"Неправильная строка"<<endl;

getch();exit(0);}

start=GetTickCount();

Zna-=2;

Rabota(isch_str);

end=GetTickCount();

end-=start;

if (!Pustota) cout<<"Нет вариантов";

cout<<"Перебор закончен"<<endl;

cout<<"Время "<<end<<endl;

cout<<"Вершин "<<Ver<<endl;

cout<<"Press any key"<< endl;

getch();

return(0);

}

Размещено на Allbest.ru