Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Reska
0 / 0 / 0
Регистрация: 13.12.2015
Сообщений: 249
#1

Конечный автомат - C++

25.02.2017, 19:58. Просмотров 315. Ответов 4
Метки нет (Все метки)

Задание типа нахождения кратчайшей последовательности вставок и удалений одного символа превращающий данную цепочку x в такую же данную y, что такое автомат знаю, но вот все не получается написать это
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.02.2017, 19:58
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Конечный автомат (C++):

Конечный автомат - C++
Доброго времени суток! Помогите, пожалуйста, разобрать задачу. Дано условие: C*C(aa)b(a)*(aa|ab) Для этого нужно написать задачу на...

Конечный автомат - C++
Всем доброго времени суток! Я в программировании кое-что понимаю, но именно что "кое-что". По болезни пропустил недели две, препод по проге...

Конечный автомат - C++
Нужно написать программу работы данного автомата.

Конечный автомат - C++
Здравствуйте! Возникли проблемы с задачей: дан набор правил q0 -> aq1, q1 -> bq2, q1 -> q2, q1 -> cq2, q2 -> aq3 и др. Нужно написать...

Детерминированный конечный автомат - C++
Всем привет,у меня такая проблема: Написал в билдере код,но не получается запустить в VS 10,никак не могу понять в чем же проблема. И кому...

Конечный автомат для строк - C++
Конечный автомат для строк используя switch. Помогите пожалуйста...

4
Reska
0 / 0 / 0
Регистрация: 13.12.2015
Сообщений: 249
26.02.2017, 20:25  [ТС] #2
поступает на вход строка x=accddcd и y=abcd, есть состояния удалить и вставить, непонятен триггер, по какому принципу вообще определять краткость вставки/удаления
0
OlafNestandart
54 / 54 / 21
Регистрация: 24.10.2016
Сообщений: 186
26.02.2017, 20:49 #3
Цитата Сообщение от Reska Посмотреть сообщение
непонятен триггер
Вам нужно смотреть на шаг вперед (можно и на несколько), удалять когда следующие символы совпадают, вставлять когда не совпадают.
0
Reska
0 / 0 / 0
Регистрация: 13.12.2015
Сообщений: 249
28.02.2017, 10:14  [ТС] #4
это расстояние Левенштейна и тут работа со строковыми переменными, а нужны автоматы, в общем на помощь
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <vector>
#include <algorithm>
 
template <typename T>
typename T::size_type levenshtein_distance(const T & src, const T & dst) {
  const typename T::size_type m = src.size();
  const typename T::size_type n = dst.size();
  if (m == 0) {
    return n;
  }
  if (n == 0) {
    return m;
  }
 
  std::vector< std::vector<typename T::size_type> > matrix(m + 1);
 
  for (typename T::size_type i = 0; i <= m; ++i) {
    matrix[i].resize(n + 1);
    matrix[i][0] = i;
  }
  for (typename T::size_type i = 0; i <= n; ++i) {
    matrix[0][i] = i;
  }
 
  typename T::size_type above_cell, left_cell, diagonal_cell, cost;
 
  for (typename T::size_type i = 1; i <= m; ++i) {
    for(typename T::size_type j = 1; j <= n; ++j) {
      cost = src[i - 1] == dst[j - 1] ? 0 : 1;
      above_cell = matrix[i - 1][j];
      left_cell = matrix[i][j - 1];
      diagonal_cell = matrix[i - 1][j - 1];
      matrix[i][j] = std::min(std::min(above_cell + 1, left_cell + 1), diagonal_cell + cost);
    }
  }
 
  return matrix[m][n];
}
Пример использования:
 
// Может быть использован любой подходящий контейнер (напр. std::vector).
// В нашем примере использованы строки:
...
const std::string src = "125";
const std::string dst = "521";
const std::string::size_type distance = levenshtein_distance(src, dst);
...
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6968 / 3259 / 327
Регистрация: 04.12.2011
Сообщений: 9,024
Записей в блоге: 5
28.02.2017, 11:26 #5
Цитата Сообщение от Reska Посмотреть сообщение
это расстояние Левенштейна и тут работа со строковыми переменными, а нужны автоматы, в общем на помощь
Reska, вы задаёте вопрос так, будто все знают задачу лучше вас. Результат вы видите. Я всё же рискну порассуждать. Это потому наверное, что я понятия не имею о чём тут речь.
Допустим имеем последовательность:
Цитата Сообщение от Reska Посмотреть сообщение
x=accddcd и y=abcd
Ясно что сумма длин это количество операций соответствующее полному удалению х и вставке y целиком. Не вдаваясь в логические подробности я предлагаю искать в x последовательность не обязательно строго подряд идущих символов соответствующую таковой в y. То есть начиная с символа y[0] ='a' ищем в х. В данном случае находим сразу. Затем ищем y[1]='b' и не находим до конца x, то то есть пора искать y[2]='c' и т.д.
Поскольку с мы находим как x[1] то нужно увеличить счетчик найденных и сравнить его с предыдущим максимальным значением (если больше не найдём совпадений из y в х).
Что касается автоматов, то тут их есть. Представьте, что вместо 'с' нам попался опять 'a' - это значит, что продолжить нужно с его позиции. Это можно сделать рекурсивно или используя стек...
В общем не принимайте близко к сердцу, если я не о том. Даже в этом случае, надеюсь, что вы расскажете подробнее, а люди подтянутся.
0
28.02.2017, 11:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.02.2017, 11:26
Привет! Вот еще темы с ответами:

Конечный автомат. Построить транслитератор - C++
Построить транслитеротор: кириллица-&gt;латиница, а также конечный автомат, осуществляющий обратную транслитерацию: латиница-&gt;кириллица в...

Конечный автомат. Лабиринт (поиск в глубину) - C++
Пусть лабиринт задан двумерным массивом bool, индексы ячеек соответствуют их координатам. Ячейка содержит true, если она проходима, и...

Как организовать на си++ недетерминированый конечный автомат? - C++
Доброго времени суток. Подскажите пожалуйста как организовать на си++ не детерминированый конечный автомат, с теорией знаком, на практике...

Конечный автомат по поиску числовых констант в строке - C++
Построить автомат, осуществляющий чтение вектор строки, содержащей числовые константы. Например, такой: (+27, -3, 2.1, 15, 0.7Е+12). На...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Закрытая тема Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru