Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833279 Sat, 27 Jun 2020 07:53:57 +0000 Довести строку до палиндрома https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833279 Расстояние Левенштейна между строкой и её зеркальным отражением.
Символы, "уникальные" для отражения и будут необходимыми символами для вставки.]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833238 Fri, 26 Jun 2020 15:26:37 +0000 Довести строку до палиндрома https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833238 В ячейке A[l, r] хранится количество вставок, необходимых для создания палиндрома из подстроки l..r.

Если S[l] = S[r], то A[l, r] = A[l+1, r-1]

иначе A[l, r] есть минимум из обрезков на один символ справа и слева.

A[l, r] =min(A[l+1, r], A[l, r-1])

При выборе минимума можно запомнить символ, который будет вставлен - он понадобится для " Получить выходную строку"]]> MBo Алгоритмы https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833195 Fri, 26 Jun 2020 08:42:51 +0000 Довести строку до палиндрома https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833195 Если одинаковые, идем дальше.
Если нет, то смотрим следующее, чтоб понять, в каком месте вставлять, если опять разные, то просто принимаем какое-нибудь "правило", например, символ, который со стороны начала фиксируется.

Вообщем цели или первый построенный по личным правилам или все (наверно проще на прологе).]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833193 Fri, 26 Jun 2020 08:22:41 +0000 Довести строку до палиндрома https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833193 - бббаааббб
- ааабббааа

вроде тут их только два (с минимальным кол-вом дополнений, а так бесконечное множество, разумеется)
не знаю, для упрощения, наверное ЛЮБОЙ палиндром сойдет (хотя бы этот вариант сделать)
если не упрощать, а со всеми выкладками, то ВСЕ возможные палиндромы

ЗЫ: да, хорошее замечание, я об этом чет сразу не подумал!]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833190 Fri, 26 Jun 2020 08:04:17 +0000 Довести строку до палиндрома https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833190 Что должно получиться?]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833187 Fri, 26 Jun 2020 07:15:17 +0000 Довести строку до палиндрома https://forum.sources.ru/index.php?showtopic=419069&view=findpost&p=3833187
Задана строка.
Есть требования (я их сам дописал, чтобы недокопывались до постановки):
- входить в строку могут русские (большие и малые) буквы, знаки препинания, цифры, пробел.
- ввод происходит с клавиатуры и заканчивается нажатием ENTER
- предельная длина строки 300 символов (если кому-то важно, можете поставить 3000 или 3млрд символов)

Необходимо:
1. Получить выходную строку, состоящую из МИНИМАЛЬНОГО количества символов. Символы этой выходной строки обладают таким свойством, что если их добавить в нужные позиции стартовой строки, то исходная строка превращается в палиндром (напомню, что палиндром - текст, читающийся одинаково в обоих направлениях, например, "казак"). Символы в выходной строке могут идти в любом порядке. Вывести выходную строку на экран.

2. Получить искомый палиндром и вывести его на экран.
---------------------------------------------------------------------------------
Внимательно, пример:
исходная_строка = "оза УпаланлпУ аора"
выходная строка = "рааза" (прим. не будет ошибкой, если она будет такой ("азара") или такой ("зааар") или ...тут вариантов может быть вроде по формуле перестановок с повторениями, в данном случае = 5! / (1! * 1! * 3!) = 5!/3! = 20, может я прогнал тут чушь )).
искомый_палиндром = "ароза УпаланалапУ азора"
---------------------------------------------------------------------------------

Немного подумав, я осознал, что ни на 1% процент не выкупая эту задачу. Это нужно на рекурсии или дерево строить. а может графы, а может еще что-то. 0 идей, вообще! Была сначала идея двигаться по входной строке с разных концов (от концов к центру), но там куча проблем, что проверять, с чем проверять и пр. пр. Не знаю, короче, как это решается.

Если есть здравые мысли, то поделитесь

ЗЫ: кому важно, это НЕ ПРОМЫШЛЕННАЯ задача, а из категории "Олимпиадная", а это означает, что есть еще автоматом требования эффективности (мин. памяти + макс.быстродействие, т е мин. проверок, циклов и пр.)

Добавлено
ааааа, тут, наверное, на сортировку с подсчетом...]]> FasterHarder Алгоритмы