Оценка асимптотической временной сложности алгоритма поиска с возвращением
Задание на курсовую работу
В курсовой работе требуется формализовать поставленную задачу, разработать эффективные алгоритмы решения, реализовать алгоритм в виде программы, исследовать и оценить теоретически и экспериментально временную и емкостную сложность алгоритмов.
В качестве задачи на курсовую работу была предложена следующая комбинаторная задача:
Задаются арифметические операции, в которых цифры заменены буквами. В данной операции одна и та же буква всегда заменяет одну и ту же цифру, разные буквы представляют разные цифры. Число разрядов исходных чисел (не результат операции) - не более N. Восстановить все возможные значения букв и операций.
Исследовать асимптотическую временную сложность решения задачи в зависимости от N.
Пример: SEND MORE MONEY соответствует 9567+1085=10652.
При выполнении курсовой работы требуется:
·Формализовать поставленную задачу (перейти от словесной неформальной постановки к математической формулировке);
·Приспособить общие методы и алгоритмы решения к решению конкретной задачи;
·Провести сравнительную оценку различных вариантов с целью выбора наиболее эффективных структур данных и алгоритмов обработки;
·Исследовать и оценить теоретические и экспериментальные методы сокращения перебора в комбинаторных задачах;
·Оценить аналитически и экспериментально эффективность предложенных в работе алгоритмов (временную и емкостную сложности);
·Программно реализовать разработанные алгоритмы на одном из алгоритмических языков программирования.
·Экспериментально исследовать различные способы программной реализации алгоритмов.
Анализ задания. Выводы о методах решения и путях повышения эффективности вычислений
математический алгоритм программирование данные
Рассмотрим индивидуальное задание и проанализируем методы решения. Эта задача имеет логическое ограничение на количество различных букв в строке - количество цифр 10. Поэтому, бесконечно расти, эта задача может только в размерности чисел, но здесь ограничение может быть наложено скорее возможностями программных средств, чем алгоритмом реализации.
Сама идея решения данной задачи заключается в том, что мы последовательно проходим введенную строку и заменяем все вхождения одной буквы на выбранную цифру. После расстановки цифр расставляются знаки операции, и проводится проверка (является решением или нет). Знаков операции всего 4: сложение, вычитание, умножение и деление. Знак = ставится вместо последнего не буквенного символа. Так как выбор цифр, которые будут подставлены, выбираются последовательно необходимо запретить выбор тех же цифр. Для этого создадим таблицу размером 10×10, и введем следующие обозначения
0-символ можно выбрать:
1-символ выбран в этой строчке в настоящее время;
-символ был использован в этой строчке раньше (в этой строчке использовать этот символ больше нельзя, но в следующих можно);
-символ выбран в выше стоящей строчке;
Ввод данной таблицы обусловлен тем, что в данной задаче не возможно определить для данного узла какие значения уже подставлялись, а какие нет. В этом случае возможно повторная проверка уже пройденного пути.
I.Формализация задачи
.1 Структуры данных для представления объектов задачи
Основная работа в алгоритме решения данной задачи происходит с исходной строкой и лишь на конечном этапе производится перевод чисел записанных в строке в числовую форму.
Для алгоритма поиска с возвращением обычно решением является вектор(a1, a2,…), но в нашем случае таким решением будет строка с полностью замененными буквами и подставленными знаками, которая и выводится на экран, в том случае если она верна.
Выбор следующего шага выполняется по таблице описанной выше. Так же выполняется подстановка знаков. При продвижении в глубину в строке проставляются 3 в тех столбцах, где в предыдущей строке стоит 3 или 1, и эти цифры уже не могут быть выбраны.
1.2 Анализ ограничений и усовершенствований. Аналитические и/или экспериментальные оценки
Основное ограничение в этой задаче указано в самом задании. Это ограничение связано в однозначном соответствии букв и цифр.
Второе ограничение накладывается на количество знаков, оно влияет на количество пройденных вершин и соответственно на время работы алгоритма. В данной работе это ограничение равно 4. Максимальное число узлов дерева равно 10!. И рассчитывается по формуле:
, где n - число различных букв в строке.
1.3 Разработка алгоритмов решения задачи
В данном пункте описаны алгоритмы для решения поставленной задачи. Сначала приведем сам алгоритм, а потом разберем его.
Алгоритм 1. Итерационный алгоритм поиска с возвращением.
Алгоритм 1 является модификацией общего итерационного алгоритма поиска с возвращением. Суть самого алгоритма описывать не буду, разберу лишь некоторые процедуры.
Этот алгоритм представляет модификацию общего рекурсивного алгоритма поиска с возвращением для решения данной задачи. Процедуры использованный в данном алгоритме аналогичны, использованным в итерационном алгоритме.
Процедура Copy позволяет избежать выбора уже выбранных ранее цифр.
Эта процедура выполняет подстановку знаков и проверку верна ли строка. Она представляет собой поиск с возвращением и похожа на основной алгоритм. Эти две процедуры были разделены по той причине, что они подставляют символы вместо различных символов. Основной алгоритм подставляет вместо буквенных символов цифры, а процедура Podstan подставляет вместо не буквенных символов знаки операций.
Процедура Vozvrat делает обратный шаг, она возвращает последние замененные символы на место и отмечает обратный шаг в таблице.
II.Оценка асимптотической временной сложности алгоритма (Метод Монте-Карло)
Вычисление по методу Монте-Карло можно использовать для оценки эффективности алгоритма поиска с возвращением путём сравнения его с эталоном, полученным для задачи с меньшей размерностью.
В данной работе этот метод используется для исследования асимптотической временной сложности решения задачи в зависимости от количества различных букв в строке и количества знаков операций.
Размер задачиМетод Монте-КарлоФактичкескиЧисло БуквЧисло символовЧисло узловПорядок ростаЧисло узловВремя (мс)Порядок роста618231241792110021406287632541,06854380223911,116392456871,05923456126411,1064106325401,151004567828571,08
Данная таблица показывает рост времени и пройденных узлов при увеличение количества знаков при одном и том же числе различных букв.
Размер задачиМетод Монте-КарлоФактичкескиЧисло БуквЧисло символовЧисло узловПорядок ростаЧисло узловВремя (мс)Порядок роста7135462113211300940682105421362,99864100353283,793258749612,424660250832182,5104368447941,4369903751255121,5
Данная таблица показывает рост времени и пройденных узлов при одновременном увеличение количества знаков и различных букв.
Размер задачиМетод Монте-КарлоФактичкескиЧисло БуквЧисло символовЧисло узловПорядок ростаЧисло узловВремя (мс)Порядок роста1151500214729460031375183700154126135726020634511575646157060453761793451579210021064,77133245784,1321130098444,4811006548739864100330473,59121789546220750500740782,4101345897441,5334929001082031,4
Данная таблица показывает рост времени и пройденных узлов при увеличение количества различных букв, при одном и том же количестве знаков.
III.Программная реализация алгоритма
3.1 Реализация данных
При реализации данных использовались следующие структуры:Byval[11][10] - Таблица хранения уже пройденного путиsstr[27] = "abcdefghijklmnopqrstuvwxyz"; - массив элементов распознаваемых как букваZnak[4][4] - Таблица хранения пройденного пути для операций
char* isch_str - исходная строка с которой проводятся все операции
Так же для удобства работы был создан стек под эту программу
struct stac
{nom;sym;
};
В которую записываются все символы заменяемые в строке.
Следующая подставляемая цифра выбирается следующим образом:
Берется первый элемент, помеченный 0 в данной строке (зависит от Glub) и помечается 1.
3.2 Реализация алгоритмов
Рассмотрим подробнее программную реализацию алгоритма.
При вводе строки она проверяется на два условия
- различных буквенных символов должно быть не более 10
- не должно быть два подряд идущих не буквенных символов, и всего не буквенных символов не должно быть не более 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
*184=67528
*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>isch_str[30];sstr[27] = "abcdefghijklmnopqrstuvwxyz";chisla[10]= {1,1,1,1,1,1,1,1,1,1};Chisl[11] = "1234567890";cfstr[27];Znaki[5]="+-*/";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}};Znak[4][4]={{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0}
};Ukaz;Zna;Chis;Pustota=0;Prisn=1;okr;Ver=0;start,end;stac
{nom;sym;
};STAC[15];POPS()
{-;(STAC[Ukaz]);
}PUSHS(stac Elm)
{[Ukaz]=Elm;++;(0);
}Proverka(char* str)
{(cfstr,0,27);(int i=0, j = 0; i < (int)strlen(str); i++) ((strchr(sstr,str[i])) && !cfstr[str[i]-97])
{++;[str[i]-97] = 1;
};(int a=0; a<(int)strlen(str);a++)(!(strchr(sstr,str[a]))) Zna++;j;
}Prover(char* str)
{Pre=0,kod;(int i=0; i<(int)strlen(str)-1;i++)
{=str[i];((!((kod>96)&&(kod<123)))&&(Pre)) return(0);if (!((kod>96)&&(kod<123)))Pre=1;Pre=0;
}(int j=(int)strlen(str)-2;j>=0;j--)(!strchr(sstr,str[j])) {str[j]='=';return(1);}(0);
}Podstan(char* str, char chr,char chrz)
{(int i=0; i<(int)strlen(str); i++)(str[i]==chr) str[i]=chrz;(0);
}Vozvrat(char* str,int Glub)
{Pr;ch,cho;pos;=POPS();=Pr.sym;=Pr.nom;=str[pos];(int j=pos; j<=(int)strlen(str);j++)
{if(str[j]==cho) str[j]=ch;}(int i=0; i<10; i++)[Glub][i]=0;
{for (int b=0; b<10; b++)(Byval[Glub-1][b]==1) Byval[Glub-1][b]=2;
}(0);
}Proverca(char* str,int Glub)
{(1);
}NextPo(char* str, int po)
{for(int i=0; i<(int)strlen(str);i++ )(strchr(sstr,str[i])) return(i);(-1);
}Pystot(char* str, int Glub)
{(int j=10,a=0; a<10; a++)(Byval[Glub][a]) j--;(j);
}Copy(int Glub, char ch1)
{(Glub==0) Byval[Glub][ch1-48]=1;{for(int i=0;i<=10;i++)((Byval[Glub-1][i]==1)||(Byval[Glub-1][i]==3)) Byval[Glub][i]=3;}(0);
}Sled(int Glub)
{(int i=0; i<10; i++)(!(Byval[Glub][i])) {Byval[Glub][i]=1;return(i+48);}(0);
}Pys(int zn)
{(int j=4,i=0; i<=4;i++)=Znak[zn][i];(j);
}Vyb(char* str, int p)
{(int i=p+1; i<(int)strlen(str);i++)(!(strchr(Chisl,str[i]))) return(i);(-1);
}V(int zn)
{(int i=0; i<4; i++)(!Znak[zn][i])
{Znak[zn][i]=1;(i){(0):return('+'); break;(1):return('-'); break;(2):return('*'); break;(3):return('/'); break;
}
}(0);
}Voz(char* str)
{stac pred;=POPS();[pred.nom]=pred.sym;(0);
}PROVERKA(char* str,int zn)
{int pos=0;ch;dw1=atof(str),dw2;i=0;(zn<Zna) return(0);(pos<(int)strlen(str))
{(isdigit(str[pos])) pos++;=str[pos];+=1;=atoi(str+pos);(ch)
{('='):if (dw1==dw2) cout<<str<<endl; Pustota=1;return(1);('+'):dw1+=dw2; break;('-'):dw1-=dw2; break;('*'):dw1*=dw2; break;('/'):if (!(dw2==0))dw1/=dw2; break;
}
}(0);
}Podstano(char* str, int Glub)
{zn=0,p=0,Pri=1;Per;ch;++;(Chis>Glub)return(0);(zn>=0)
{((Pri)&&(Pys(zn)))
{p=Vyb(str,p);.nom=p;.sym=str[p];(Per);=V(zn);++;(str[p]!='=')
{str[p]=ch;++;(zn==1)
{ for(int a=3;a>=0;a--)(Znak[0][a]==1){ Znak[1][a]=1; ;}}(!(zn==1)) {for(int i=0;i<4;i++)[zn][i]=Znak[zn-1][i];}
}(PROVERKA(str,zn)) Pri=0;
}(zn!=0) Voz(str);(int b=0; b<4;b++)[zn][b]=0;-;=1;=0;
}=0;(0);
}Rabota(char* str)
{int Nomerchis=0; //Íîìåð ïîñëåäíåãî çàìåííåíîãî ñèìâîëà
memset(chisla,1,10);* isch=str;ch,ch1;
int po=0,k=1,Nu=0,Glub=0; //Ex-ïðèçíàê âûõîäà
stac Per;(Glub>=0)
{((Prisn)&&(Pystot(str,Glub)))
{(po!=-1)
{=str[po];.nom=po;.sym=ch;(Per);=Sled(Glub);(ch1!=0)Podstan(str,ch,ch1);++;(Glub,ch1);(str,Glub);}=NextPo(str,po);
}(str,Glub);-;=1;
}(0);
}main()
{<<Введите строку<< endl;(isch_str,30,stdin);=Proverka(isch_str);(Chis>10) {cout<<Неправильная строка"<<endl; getch();exit(0);}(!(Prover(isch_str))) {cout<<"Неправильная строка"<<endl; ();exit(0);}=GetTickCount();=2;(isch_str);=GetTickCount();=start;(!Pustota) cout<<"Нет вариантов";<<"Перебор закончен"<<endl;<<"Время "<<end<<endl;<<"Вершин "<<Ver<<endl;<<"Press any key"<< endl;();(0);
}
Больше работ по теме:
Предмет: Информационное обеспечение, программирование
Тип работы: Курсовая работа (т)
Новости образования
КОНТАКТНЫЙ EMAIL: [email protected]
Скачать реферат © 2017 | Пользовательское соглашение
ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ