Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Reska
0 / 0 / 2
Регистрация: 13.12.2015
Сообщений: 249
#1

Конечный автомат

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

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

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

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

Конечный автомат
Здравствуйте! Возникли проблемы с задачей: дан набор правил q0 -> aq1, q1 ->...

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

Детерминированный конечный автомат
Всем привет,у меня такая проблема: Написал в билдере код,но не получается...

4
Reska
0 / 0 / 2
Регистрация: 13.12.2015
Сообщений: 249
26.02.2017, 20:25  [ТС] #2
поступает на вход строка x=accddcd и y=abcd, есть состояния удалить и вставить, непонятен триггер, по какому принципу вообще определять краткость вставки/удаления
0
OlafNestandart
54 / 54 / 31
Регистрация: 24.10.2016
Сообщений: 186
26.02.2017, 20:49 #3
Цитата Сообщение от Reska Посмотреть сообщение
непонятен триггер
Вам нужно смотреть на шаг вперед (можно и на несколько), удалять когда следующие символы совпадают, вставлять когда не совпадают.
0
Reska
0 / 0 / 2
Регистрация: 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
Комп_Оратор)
Эксперт по математике/физике
7045 / 3346 / 452
Регистрация: 04.12.2011
Сообщений: 9,306
Записей в блоге: 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

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

Конечный автомат. Построить транслитератор
Построить транслитеротор: кириллица-&gt;латиница, а также конечный автомат,...

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


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

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

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