2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Сложность одного алгоритма
Сообщение28.06.2021, 20:59 


27/08/16
10195
ТС так и не ответил, откуда эта задача. Можно ли ему помогать?

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

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

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение29.06.2021, 01:20 
Заслуженный участник
Аватара пользователя


16/07/14
9143
Цюрих
realeugene в сообщении #1524694 писал(а):
Мне кажется, сам ТС не очень понимает формулировку заданной ему задачи
Это был пример, на котором предложенный им алгоритм работает неправильно.

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение30.06.2021, 01:04 


21/10/16
91
realeugene в сообщении #1524694 писал(а):
Можно ли ему помогать?
Можно. Помогайте. :D

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

-- 30.06.2021, 01:10 --

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

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

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение30.06.2021, 02:01 


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

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение30.06.2021, 07:29 


12/07/15
3311
г. Чехов
mihaild в сообщении #1524693 писал(а):
Что этот вариант алгоритма выдаст на строке $abcdacbd$?

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

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

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение30.06.2021, 11:17 


27/08/16
10195
В общем, приведу линейный алгоритм без деталей реализации и доказательств.

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

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

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение30.06.2021, 13:23 


27/08/16
10195
Только местоимение "его" лучше выкинуть, получилось неоднозначно.

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение01.07.2021, 07:23 


12/07/15
3311
г. Чехов
Проверяйте свой алгоритм на строках:
abacdeebdfcf
aabcbdefedfc
abcabdcdefef

 Профиль  
                  
 
 Re: Сложность одного алгоритма
Сообщение01.07.2021, 09:55 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group