М4. НАМ

Написать исполнитель нормальных алгоритмов Маркова для заданного алфавита.

Ввод Вывод Комментарий
abbbcaa
aa->a
bb->b
cc->c
abca Пройдено
x
*x->xx*
*=>
->*
xx Пройдено
cbabca
ba->ab
cb->bc
ca->ac
aabbcc Пройдено

Прочитав строку и команды нам нужно разделить каждую команду на три элемента: ключ, значение, boolean-переменная (отвечает на вопрос: «Конечная ли команда?»). Последняя переменная нужна для того чтобы определить производится ли окончание операций после данной команды.
После этого я использовал небольшой аналог рекурсии. Дело в том, что я использовал бесконечный вызов функции до того момента, когда сама функция не передаст циклу команду остановиться.
В самой же функции идет поиск каждой команды в заданной строке, вначале по первому символу, а потом, если символ совпал, проверяется идентична ли найденная часть строки одной из наших команд.
Если никакая команда не нашла соответствие, функция возвращает 0 и программа выходит из цикла.
Если же совпадение было найдено, то мы заменяем найденный в строке ключ на соответствующее ему значение и возвращаем boolean-переменную (опять же соответствующую заданному ключу), таким образом если это конечная операция, то будет произведен выход из функции, иначе — будет произведен повторный вызов функции.
Так же следует учитывать и то что пустой ключ указывает на то что значение должно добавиться к началу строки, учтем это при написании кода.

Опробовать код можно здесь: http://ideone.com/QobpUI

Куленюк Денис Віталійович
Куленюк Денис Віталійович

Latest posts by Куленюк Денис Віталійович (see all)

One thought on “М4. НАМ

  1. Честно говоря, сложно проверить эту программу.
    У Вас есть глобальные переменные:
    string s;
    string *h, *t;
    int *b;
    int n;
    vector p;
    int step=0;
    int op;

    Наша вина — не научили правильно называть переменные. Из имен понять ничего нельзя, комментариев нет.
    Одна функция int f() — что делает, что возращает? Вроде как из кода можно догадаться, что выполняет одну команду

    «Последняя переменная » — последняя в каком списке?

    В общем может программа и правильная, но не буду даже ее проверять, пока не напишете объяснение не только каких-то интересных, нетривиальных с Вашей точки зрения моментов, но и самого базиса. Начать нужно с того, что такое вообще нормальный алгоритм Маркова, как он работает (все это очень кратко) и какой у Вас формат ввода, в частности какой формат представления команды. «нужно разделить каждую команду на три элемента: ключ, значение, boolean-переменная» — отсюда понятно, что в команде есть 3 элемента, но в каком порядке записаны, как обозначается признак, того, что команда конечная (в Вашей терминологии, возможно лучше слово заключительная), в чем различие «->» и «=>» и т.д.

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