2014 dxdy logo

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

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




 
 Задача про палиндром
Сообщение28.12.2022, 00:10 
Здравствуйте, не знаю, можно ли такие задачи кидать на этом форуме, но вроде как вполне сходит на дискретную математику. Задача такова: Палиндромом называется строка, которая одинаково читается слева направо и справа налево. Рассмотрим некоторую строку $S$, состоящую из маленьких латинских букв. Какое минимальное количество букв (возможно нуль) нужно в ней удалить, чтобы она не являлась палиндромом? Предложите алгоритм решения задачи, докажите его корректность, оцените трудоемкость. Трудоёмкость состоит в O(n). Просто сравниваем с двух концов и ближе к центру, и ищем не равные символы. Мой вопрос в том, чтобы узнать, в чём сложность этой задачи? Если у кого то есть опыт в таких задачах, то расскажите, может я слишком плохой способ дал?

 
 
 
 Re: Задача про палиндром
Сообщение28.12.2022, 00:47 
Аватара пользователя
Задача нормальная, ваше решение непонятно. Нам же нужно не проверить, является ли строка палиндромом, а удалить из неё что-нибудь, чтобы перестала являться.

 
 
 
 Re: Задача про палиндром
Сообщение28.12.2022, 00:49 
Верно, любой палиндром можно сделать не таковым либо за либо 1 убирание, либо вообще нельзя(где все одинаковые)

-- 28.12.2022, 00:52 --

А вот это одно убирание, если идущие друг за другом символы не равны. И вот за O(n) проверяем эту штуку. Правда для начала так же за O(n) проверим, палиндром ли это вообще, сравнивая с двух концов символы.

 
 
 
 Re: Задача про палиндром
Сообщение28.12.2022, 06:39 
Надо найти минимальное число удалений и доказать корректность алгоритма.

Может надо не с конца, а из середины палиндрома начать?

 
 
 
 Re: Задача про палиндром
Сообщение28.12.2022, 08:21 
Аватара пользователя
Mihaylo в сообщении #1575292 писал(а):
... из середины палиндрома начать?
Из середины как раз максимальное количество имеем, поскольку без центрального знака (на оси симметрии или по соседству) палиндром остается палиндромом: $aba \rightarrow aa;\ \ abba \rightarrow aba.$
Maxim19 в сообщении #1575277 писал(а):
... либо вообще нельзя(где все одинаковые)
В числах — репьюниты. Вот если их исключить, то одного удаленного крайнего знака достаточно. Для доказательства надо разделить палиндромы на четные (по количеству знаков) и нечетные. В центре нечетного п. репьюнит из нечетного кол-ва знаков, как минимум из одного. В центре четного п. репьюнит из четного кол-ва знаков, как минимум из двух. При удалении крайнего знака четность меняется, а репьюнит в центре симметрии остается прежним: $aba \rightarrow ab;\ \ abba \rightarrow abb.$

 
 
 
 Re: Задача про палиндром
Сообщение28.12.2022, 09:26 
Andrey A в сообщении #1575297 писал(а):
Из середины как раз максимальное количество имеем

Вы не поняли. Находим середину палиндрома в строке, двигаясь от середины строки.
Возможно доказательством корректности будет доказательство того, более удаленные от середины строки серединки палиндрома будут менее оптимальными.
(Не путать середину строки с серединой палиндрома. В общем случае это не одно и то же.)

 
 
 
 Re: Задача про палиндром
Сообщение28.12.2022, 12:37 
Аватара пользователя
Maxim19 в сообщении #1575269 писал(а):
Рассмотрим некоторую строку $S$ , состоящую из маленьких латинских букв. Какое минимальное количество букв (возможно нуль) нужно в ней удалить, чтобы она не являлась палиндромом?
Я и теперь не понимаю. Вчитайтесь в свой вопрос, именно на него я и ответил. Если бы было написано "Какое минимальное количество букв (возможно нуль) нужно в ней удалить, чтобы она не содержала ни одного палиндрома?" — это был бы, конечно, другой вопрос.

P.S. Возможно, имелось в виду удалить знаки без предварительного анализа, но тайно или явно анализировать все равно придется, или же надо удалять все знаки. Самое простое — тест на палиндром. При отрицательном результате удалять не нужно ничего, в противном случае — то что я написал.

 
 
 
 Re: Задача про палиндром
Сообщение28.12.2022, 16:37 
Упс. Перепутал два варианта: "чтобы не являлась палиндромом" и "чтобы являлась палиндромом".
Я второй вариант рассматривал, и он более интересный.
Первый вариант банален. Пользуемся определением палиндрома: просто проверяем на палиндромность и в зависимости от этого изменяем 0 или 1 символ.

 
 
 [ Сообщений: 8 ] 


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