|
Почетный модератор
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
|
|
Построение минимального палиндрома01.10.2009, 16:10. Показов 8819. Ответов 39
Метки нет (Все метки)
Никак не могу придумать алгоритма:
есть входная строка в n символов, необходимо добавить такое кол-во символов, чтобы вышел минимально возможный палиндром... палиндром
Палиндро́м (от греч. πάλιν — «назад, снова» и греч. δρóμος — «бег») — число (например, 404), буквосочетание, слово (например, топот, финск. saippuakauppias = продавец мыла — самое длинное употребительное слово-палиндром в мире) или текст, одинаково (или почти одинаково) читающиеся в обоих направлениях.
т.е. вход: abcb выход: abcba вход: aaabbba выход: aaabbbaaa
0
|
|
| 01.10.2009, 16:10 | |
|
Ответы с готовыми решениями:
39
Построение минимального остовного дерева. Использовать алгоритм Борувки
|
|
Почетный модератор
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
|
|
| 02.10.2009, 11:06 [ТС] | |
|
odip, ну я же про его алгоритм говорил, он его поправил, а я еще не дописал его (в разработке, если на работе покой будет - допишу)... а аналог твоего алгоритма я тоже реализовал, но не так витиевато, как у тебя... хотя сейчас потестируем, что уж там)))
вопросов нет... работает... но просто вместо витиеватого кода, хотелось витиеватого алгоритма, слишком просто все выходит... хоть и простота рулит, но вот такая взяла меня блажь...
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
||||||
| 02.10.2009, 11:47 | ||||||
|
Не знаю что ты подразумеваешь под словом "витиеватый алгоритм", IMHO алгоритм очень прост.
Можно еще ускорить. Во-первых нужно не использовать функцию is_pal(), вставить проверку сразу в тело функции. Во-вторых у меня сначала копируется хвост из начало в конец, а потом проверяется - не палиндров ли это. Так вот - можно не копировать хвост, так как ясно, что скопированный хвост и так является копией. Нужно просто проверять пропустив копирование хвоста. Добавлено через 20 минут Программа, версия 2
0
|
||||||
|
Почетный модератор
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
|
|
| 02.10.2009, 11:51 [ТС] | |
|
odip, ну вот видишь, пошла оптимизация алгоритма))) а на счет витиеватого алгоритма, если у меня все же получится реализовать - покажу и расскажу...
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
||
| 02.10.2009, 11:53 | ||
![]() Просто для простоты сделал более тупой метод.
0
|
||
|
Почетный модератор
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
|
|
| 02.10.2009, 11:57 [ТС] | |
|
odip, у меня возникли неприятные смутные подозрения по поводу тупого метода, но промолчу дабы не оффтопить
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
| 02.10.2009, 11:58 | |
|
Не знаю какие у тебя там подозрения, но метод работает.
0
|
|
|
Почетный модератор
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
|
|
| 02.10.2009, 12:03 [ТС] | |
|
odip, я не про метод... ну да ладно... будет желание еще что-нить придумать, выкладывай
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
| 02.10.2009, 12:04 | |
|
Вот тут задача про палиндром: https://www.cyberforum.ru/pascal/thread53635.html
0
|
|
|
Почетный модератор
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
|
|
| 02.10.2009, 12:06 [ТС] | |
|
odip, думаю это его сюда надо направлять, а не наоборот
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
| 02.10.2009, 12:08 | |
|
Там несколько другая задача.
Алгоритм для той задачи я уже написал
0
|
|
| 02.10.2009, 12:19 | |
|
еще один возможной алгоритм (хотя в принципе все возможные - варианты одного и того же):
в цикле проверяем, не палиндром ли строка(без нуля), затем строка без первого символа, строка без второго и т.д. количество "непалиндромов" - это количество символов, которые нужно потом переписать "зеркально" из начала в конец. например: c = 0; abcded - не палиндром c++ bcded - не палиндром c++ cded - не палиндром c++ ded - палиндром. с = 3, значит переписать нужно три символа.
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
| 02.10.2009, 12:20 | |
|
Угу, один в один как в Построение минимального палиндрома
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
| 02.10.2009, 12:32 | |
|
2novi4ok: Пургу несешь. Код нормально написан.
Если у тебя все в одну строку - проверь свой броузер или еще чего.
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
||
| 02.10.2009, 13:34 | ||
|
То есть ты предлагаешь мне изменить мой код под такой вариант отступов, который нравится именно тебе ?
Извини, но не собираюсь.
0
|
||
|
Почетный модератор
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
|
|
| 02.10.2009, 14:19 [ТС] | |
|
novi4ok, odip, за форматирования программного кода - создайте тему и спорьте, а здесь это флуд...
0
|
|
|
562 / 373 / 55
Регистрация: 05.04.2009
Сообщений: 767
|
|||||||
| 02.10.2009, 23:49 | |||||||
|
можно приписывать сразу.
1
|
|||||||
|
Почетный модератор
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
|
|
| 03.10.2009, 09:59 [ТС] | |
|
mirso, этот алгоритм я тоже уже реализовал... по простоте думаю ему первое место...
0
|
|
| 03.10.2009, 09:59 | |
|
Определение палиндрома Нахождение палиндрома
Нахождение палиндрома Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Про "Windows must die!"
kumehtar 04.11.2026
Знаете, чет накатило. . . .
Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .
|
Красочные поля с номером страницы svg+background-image
russiannick 04.11.2026
Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг.
Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует.
В процессе разработки. . .
|
Вступаем в новую фазу генерации favicons, векторную.
russiannick 02.11.2026
Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .
|
Генератор паролей (вариант №4)
Maks 01.11.2026
После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации:
1. Вернуть возможность использования знаков | 1 l I;. . .
|
|
Генератор паролей (вариант №3)
Maks 30.10.2026
Финальная версия генератора паролей 1С.
Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .
|
Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени)
zorxor 30.10.2026
Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию?
Фраза «Любая достаточно развитая технология неотличима от магии». . .
|
За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ)
zorxor 30.10.2026
Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль?
Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .
|
Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени)
zorxor 30.10.2026
Как убивали Suno. Хронология.
«Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .
|