2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Сложность одного алгоритма
Сообщение28.06.2021, 20:59 
ТС так и не ответил, откуда эта задача. Можно ли ему помогать?

Мне кажется, сам ТС не очень понимает формулировку заданной ему задачи:

gogoshik в сообщении #1524514 писал(а):
Выдаст $zz$, то есть что "сокращения не существует".
Что мешает сократить строку до пустой?

 
 
 
 Re: Сложность одного алгоритма
Сообщение29.06.2021, 01:20 
Аватара пользователя
realeugene в сообщении #1524694 писал(а):
Мне кажется, сам ТС не очень понимает формулировку заданной ему задачи
Это был пример, на котором предложенный им алгоритм работает неправильно.

 
 
 
 Re: Сложность одного алгоритма
Сообщение30.06.2021, 01:04 
realeugene в сообщении #1524694 писал(а):
Можно ли ему помогать?
Можно. Помогайте. :D

Тут нужно искусство решить задачу, а в чем хитрость не понять эту задачу?

-- 30.06.2021, 01:10 --

realeugene в сообщении #1524559 писал(а):
Алфавитом обычно называют фиксированное в задаче константное множество. А у вас нечто иное.
Алфавитом называется конечное непустое множество. Его элементы называются символами или буквами.

У ТС:
gogoshik в сообщении #1524505 писал(а):
Пусть $s$ -- конечная строка символов произвольного алфавита
Где противоречие?

 
 
 
 Re: Сложность одного алгоритма
Сообщение30.06.2021, 02:01 
matemat в сообщении #1524767 писал(а):
Можно. Помогайте.
Вы ТС? Нет? Он так и не ответил, откуда задача. Задача уровня тестовой.

 
 
 
 Re: Сложность одного алгоритма
Сообщение30.06.2021, 07:29 
mihaild в сообщении #1524693 писал(а):
Что этот вариант алгоритма выдаст на строке $abcdacbd$?

Алгоритм подсчитает число спутанных пар символов:
ab - спутана
ac - спутана
ad - спутана
bc - не спутана
bd - спутана
cd - спутана

Да, действительно... Надо строить некоторое дерево спутанности, в котором в корне лежит исходная строка, в которой потенциально могут спутанные символы. По мере нахождения спутанных символов выстраивать ветви дерева. При этом, если высота дерева превышает 4 (?), то алгоритм завершается...

 
 
 
 Re: Сложность одного алгоритма
Сообщение30.06.2021, 11:17 
В общем, приведу линейный алгоритм без деталей реализации и доказательств.

Рассматриваем символы строки по одному. Если рассматриваемый символ второй в паре, и предыдущий оставшийся в строке символ совпадает со следующим оставшимся символом для первого символа его пары, удаляем из строки эту пару символов.

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

 
 
 
 Re: Сложность одного алгоритма
Сообщение30.06.2021, 13:23 
Только местоимение "его" лучше выкинуть, получилось неоднозначно.

 
 
 
 Re: Сложность одного алгоритма
Сообщение01.07.2021, 07:23 
Проверяйте свой алгоритм на строках:
abacdeebdfcf
aabcbdefedfc
abcabdcdefef

 
 
 
 Re: Сложность одного алгоритма
Сообщение01.07.2021, 09:55 
Mihaylo в сообщении #1524867 писал(а):
Проверяйте свой алгоритм на строках:
Спасибо. Действительно, чрезмерная оптимизация привела к багу. Нужно добавить условие, что равные друг другу соседи - это разные символы, а не один и тот же символ строки.

 
 
 [ Сообщений: 24 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group