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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

математический алгоритм программирование данные Рассмотрим индивидуальное задание и проанализируем методы решения. Эта задача имеет логическое ограничение на количество различных букв в строке — количество цифр 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. Оценка асимптотической временной сложности алгоритма (Метод Монте-Карло)

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

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

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

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

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

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=67 528

514*028=14 392

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

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

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

Приложение

#include

#include

#include

#include

#include

#include

#include

char isch_str[30];

char sstr[27] = «abcdefghijklmnopqrstuvwxyz» ;

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

char Chisl[11] = «1 234 567 890» ;

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;

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

if ((Byval[Glub-1][i]==1)

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

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<

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<<�"Неправильная строка" <

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

getch ();exit (0);}

start=GetTickCount ();

Zna-=2;

Rabota (isch_str);

end=GetTickCount ();

end-=start;

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

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

cout<<" Время «<

cout<<" Вершин «<

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

getch ();

return (0);

}