Оценка асимптотической временной сложности алгоритма поиска с возвращением - Программирование, компьютеры и кибернетика курсовая работа

Главная

Программирование, компьютеры и кибернетика
Оценка асимптотической временной сложности алгоритма поиска с возвращением

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

В курсовой работе требуется формализовать поставленную задачу, разработать эффективные алгоритмы решения, реализовать алгоритм в виде программы, исследовать и оценить теоретически и экспериментально временную и емкостную сложность алгоритмов.
В качестве задачи на курсовую работу была предложена следующая комбинаторная задача:
Задаются арифметические операции, в которых цифры заменены буквами. В данной операции одна и та же буква всегда заменяет одну и ту же цифру, разные буквы представляют разные цифры. Число разрядов исходных чисел (не результат операции) - не более  N . Восстановить все возможные значения букв и операций.
Исследовать асимптотическую временную сложность решения задачи в зависимости от N .
Пример: SEND MORE MONEY соответствует 9567+1085=10652.
При выполнении курсовой работы требуется:
· Формализовать поставленную задачу (перейти от словесной неформальной постановки к математической формулировке);
· Приспособить общие методы и алгоритмы решения к решению конкретной задачи;
· Провести сравнительную оценку различных вариантов с целью выбора наиболее эффективных структур данных и алгоритмов обработки;
· Исследовать и оценить теоретические и экспериментальные методы сокращения перебора в комбинаторных задачах;
· Оценить аналитически и экспериментально эффективность предложенных в работе алгоритмов (временную и емкостную сложности);
· Программно реализовать разработанные алгоритмы на одном из алгоритмических языков программирования.
· Экспериментально исследовать различные способы программной реализации алгоритмов.
Анализ задания. Выводы о методах решения и путях повышения эффективности вычислений
математический алгоритм программирование данные
Рассмотрим индивидуальное задание и проанализируем методы решения. Эта задача имеет логическое ограничение на количество различных букв в строке - количество цифр 10. Поэтому, бесконечно расти, эта задача может только в размерности чисел, но здесь ограничение может быть наложено скорее возможностями программных средств, чем алгоритмом реализации.
Сама идея решения данной задачи заключается в том, что мы последовательно проходим введенную строку и заменяем все вхождения одной буквы на выбранную цифру. После расстановки цифр расставляются знаки операции, и проводится проверка (является решением или нет). Знаков операции всего 4: сложение, вычитание, умножение и деление. Знак `=' ставится вместо последнего не буквенного символа. Так как выбор цифр, которые будут подставлены, выбираются последовательно необходимо запретить выбор тех же цифр. Для этого создадим таблицу размером 10Ч10, и введем следующие обозначения
1- символ выбран в этой строчке в настоящее время;
2- символ был использован в этой строчке раньше (в этой строчке использовать этот символ больше нельзя, но в следующих можно);
3- символ выбран в выше стоящей строчке;
Ввод данной таблицы обусловлен тем, что в данной задаче не возможно определить для данного узла какие значения уже подставлялись, а какие нет. В этом случае возможно повторная проверка уже пройденного пути.
1.1 Структуры данных для представления объектов задачи
Основная работа в алгоритме решения данной задачи происходит с исходной строкой и лишь на конечном этапе производится перевод чисел записанных в строке в числовую форму.
Для алгоритма поиска с возвращением обычно решением является вектор(a 1 , a 2 ,…), но в нашем случае таким решением будет строка с полностью замененными буквами и подставленными знаками, которая и выводится на экран, в том случае если она верна.
Выбор следующего шага выполняется по таблице описанной выше. Так же выполняется подстановка знаков. При продвижении в глубину в строке проставляются 3 в тех столбцах, где в предыдущей строке стоит 3 или 1, и эти цифры уже не могут быть выбраны.
1.2 Анализ ограничений и усовершенствований. Аналитические и/или экспериментальные оценки
Основное ограничение в этой задаче указано в самом задании. Это ограничение связано в однозначном соответствии букв и цифр.
Второе ограничение накладывается на количество знаков, оно влияет на количество пройденных вершин и соответственно на время работы алгоритма. В данной работе это ограничение равно 4. Максимальное число узлов дерева равно 10!. И рассчитывается по формуле:
, где n - число различных букв в строке.
1.3 Разработка алгоритмов решения задачи
В данном пункте описаны алгоритмы для решения поставленной задачи. Сначала приведем сам алгоритм, а потом разберем его.
Алгоритм 1. Итерационный алгоритм поиска с возвращением.
Алгоритм 1 является модификацией общего итерационного алгоритма поиска с возвращением. Суть самого алгоритма описывать не буду, разберу лишь некоторые процедуры.
Этот алгоритм представляет модификацию общего рекурсивного алгоритма поиска с возвращением для решения данной задачи. Процедуры использованный в данном алгоритме аналогичны, использованным в итерационном алгоритме.
Процедура Copy позволяет избежать выбора уже выбранных ранее цифр.
Эта процедура выполняет подстановку знаков и проверку верна ли строка. Она представляет собой поиск с возвращением и похожа на основной алгоритм. Эти две процедуры были разделены по той причине, что они подставляют символы вместо различных символов. Основной алгоритм подставляет вместо буквенных символов цифры, а процедура Podstan подставляет вместо не буквенных символов знаки операций.
Процедура Vozvrat делает обратный шаг, она возвращает последние замененные символы на место и отмечает обратный шаг в таблице.
II. Оценка асимптотической временной сложности алгоритма (Метод Монте-Карло)
Вычисление по методу Монте-Карло можно использовать для оценки эффективности алгоритма поиска с возвращением путём сравнения его с эталоном, полученным для задачи с меньшей размерностью.
В данной работе этот метод используется для исследования асимптотической временной сложности решения задачи в зависимости от количества различных букв в строке и количества знаков операций.
Данная таблица показывает рост времени и пройденных узлов при увеличение количества знаков при одном и том же числе различных букв.
Данная таблица показывает рост времени и пройденных узлов при одновременном увеличение количества знаков и различных букв.
Данная таблица показывает рост времени и пройденных узлов при увеличение количества различных букв, при одном и том же количестве знаков.
III. Программная реализация алгоритма
При реализации данных использовались следующие структуры:
int Byval[11][10] - Таблица хранения уже пройденного пути
char sstr[27] = "abcdefghijklmnopqrstuvwxyz"; - массив элементов распознаваемых как буква
int Znak[4][4] - Таблица хранения пройденного пути для операций
char* isch_str - исходная строка с которой проводятся все операции
Так же для удобства работы был создан стек под эту программу
В которую записываются все символы заменяемые в строке.
Следующая подставляемая цифра выбирается следующим образом:
Берется первый элемент, помеченный 0 в данной строке (зависит от Glub) и помечается 1.
Рассмотрим подробнее программную реализацию алгоритма.
При вводе строки она проверяется на два условия
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 в виде одного модуля
Размеры исполняемого файла: 208 кбайт
Приведу пример работы данной задачи
В данной курсовой работе в соответствие с заданием были разработаны и исследованы алгоритмы решения поставленной комбинаторной задачи. Как основа алгоритма решения были взят общий итерационный алгоритм поиска с возвращением. Отличительной чертой задачи предложенной на курсовой проект является то, что она имеет логические ограничения, и поэтому не способна расти до бесконечности, так же в этой задаче не удалось найти способов сокращения перебора, но нужно заметить, что для данной задачи они не очень важны, так как наибольшее время работы программы 2 минуты (при изменение разрядности это время будет не значительно увеличиваться). Но время работы порядка 1 часа получить не получится.
Результатом данной курсовой работы является пояснительная записка, приложение к пояснительной записке, в котором содержится листинг программы, и сама программа.
char sstr[27] = "abcdefghijklmnopqrstuvwxyz";
int chisla[10]= {1,1,1,1,1,1,1,1,1,1};
int Byval[11][10]= {{0,0,0,0,0,0,0,0,0,0},
for (int i=0, j = 0; i < (int)strlen(str); i++)
if((strchr(sstr,str[i])) && !cfstr[str[i]-97])
for(int a=0; a<(int)strlen(str);a++)
for(int i=0; i<(int)strlen(str)-1;i++)
if ((!((kod>96)&&(kod<123)))&&(Pre)) return(0);
else if (!((kod>96)&&(kod<123)))Pre=1;
for(int j=(int)strlen(str)-2;j>=0;j--)
if(!strchr(sstr,str[j])) {str[j]='=';return(1);}
int Podstan(char* str, char chr,char chrz)
for (int i=0; i<(int)strlen(str); i++)
for(int j=pos; j<=(int)strlen(str);j++)
if (Byval[Glub-1][b]==1) Byval[Glub-1][b]=2;
{ for(int i=0; i<(int)strlen(str);i++ )
if (Glub==0) Byval[Glub][ch1-48]=1;
if ((Byval[Glub-1][i]==1)||(Byval[Glub-1][i]==3)) Byval[Glub][i]=3;}
if (!(Byval[Glub][i])) {Byval[Glub][i]=1;return(i+48);}
for(int i=p+1; i<(int)strlen(str);i++)
if(!(strchr(Chisl,str[i]))) return(i);
case('='):if (dw1==dw2) cout<10) {cout<<”Неправильная строка"<Оценка асимптотической временной сложности алгоритма поиска с возвращением курсовая работа. Программирование, компьютеры и кибернетика.
Курсовая работа по теме Изучение предпочтений потребителей в выборе ночных клубов г. Хабаровска
Пособие по теме Формулы по алгебре
Контрольная Работа 2 9 Класс Алгебра Макарычев
Реферат по теме Жанр «Истории» и ловушки исторического и историко-литературного знания на рубеже тысячелетий
Курсовая работа: Формирование государственной инновационной политики и нормативно-правовой базы, стимулирующей инновационную деятельность
Правовое Регулирование Государственной Социальной Помощи Курсовая
Курсовая работа по теме Анализ обеспеченности предприятия трудовыми ресурсами
Реферат: Функции менеджмента в организации
Контрольная работа по теме Возникновение и расселение основных славянских племен
Курсовая Работа На Тему Соуси
Реферат по теме Правовая защита конкуренции как необходимой предпосылки рыночной экономики
Структура Капитала Курсовая Работа
Дипломная Работа Обеспечение Безопасности
Курсовая работа: Складское хозяйство предприятия. Скачать бесплатно и без регистрации
Реферат: Художественная культура Древней Греции в период архаики и ранней классики
Реферат: Меры электро-пожаробезопасности при сварке рельсовых плетей
Реферат: Тихон Задонский. Скачать бесплатно и без регистрации
Реферат по теме Планування продуктивності праці
Реферат: Разработка оптимальной программы организации инвестирования и финансирования создания малого пре
Курсовая работа по теме Проектування поточної лінії для приготування вологих кормових сумішей при вирощуванні 20000 качок, з розробкою скребкового транспортера
Уголовное законодательство - Государство и право реферат
Формирование творческих способностей детей старшего дошкольного возраста с задержкой психического развития на занятиях изобразительным искусством - Педагогика курсовая работа
Военное лицо России в воспоминаниях современников - История и исторические личности реферат