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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При реализации данных использовались следующие структуры: Byval[11][10] - Таблица хранения уже пройденного путиsstr[27] = "abcdefghijklmnopqrstuvwxyz"; - массив элементов распознаваемых как букваZnak[4][4] - Таблица хранения пройденного пути для операций

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

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

struct stac

{nom;sym;

};

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

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

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

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

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

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

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

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

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

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

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

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

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

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