PlayGround.ru
Ropnet
, купить игру Need for Speed: Shift, Dark Souls: Prepare to Die Edition скриншоты, мод для Endless Space


[Оффтоп] Опять программистам.

miha64   18 февраля 2013 в 20:16

Задача:
Палиндромом называется строка, которая читается одинаково слева направо и справа налево. Например, 1001 – палиндром, 1010 – нет. Напишите программу, которая превращает любую строку из 0 и 1 в палиндром, добавляя в нее минимальное количество новых символов. Добавлять новые символы можно слева, справа и внутрь строки.
Вводится строка длиной не более 100 символов, состоящая только из 0 и 1.
Вывести в первой строке количество добавленных символов, во второй строке – получившийся палиндром. Если существует несколько вариантов, вывести вариант, который идет раньше в лексикографическом порядке.
Решение:
Задача на динамическое программирование. Сначала необходимо построить таблицу T, в которой в ячейке T[i,j] хранится минимальное количество добавляемых символов к строке s[i…j] для получения палиндрома. T[i,j] = T[i+1,j-1], если s=s[j], T[i,j]=min(T[i,j-1],T[i+1,j])+1 если s=s[j]. Выполняя обратную трассировку по таблице T легко найти палиндром-результат.

Вот... Вопрос: какие действия включает в себя фраза "построить таблицу"? Как надо ее заполнять, чтобы потом T[i,j] присваивать T[i+1,j-1]? Мб статейку посоветуйте. Заранее спасибо.

Гринааа Морнингстар   18 февраля 2013 в 20:36

Без нефалемки здесь не обойтись.

miha64   18 февраля 2013 в 21:03

Гринааа
Что такое нафалемка?

Torum.   18 февраля 2013 в 21:11

Нефалемы древние.

malloc   18 февраля 2013 в 21:21

miha64
Ты на программиста учишься?

miha64   18 февраля 2013 в 21:33

Muny
Типа того.

Torum.   18 февраля 2013 в 21:38

Типа того и получится.

shtyle   18 февраля 2013 в 23:17

Дежа вю какое-то..

PS. Типа того и получится.

Извиняюсь если в чем-то не прав или путаю, но Вам ведь ни к чему знать облагаемые дополнительным налогом товары, ввозимые судовым транспортом в Египет при размере партии свыше 400кг, однако если контуженного преподавателя по таможенному праву переклинит - отвертеться от этой темы будет сложно. Так и в этой ситуации - извращенское применение не самого приятного алгоритма для методических(!) целей.

shtyle   19 февраля 2013 в 00:12

miha64 - Забыл ответить:

Таблица строится немного непонятно как, точнее куда именно добавлять символы. Еще сдается мне вот здесь T[i,j]=min(T[i,j-1],T[i+1,j])+1 если s=s[j] вот так s=s[ i ]

А дальше - надо найти место для которого можно начать строить. T[0,0] какой-нибудь.

Но мне все равно не нравится, может подойдет такой вариант решения?:

Переберем все варианты положения центра палиндрома-результата - то есть исходные цифры и места между цифрами. Затем для каждого положения центра:
1. если в центре цифра - кушаем её, теперь центр между цифрами
2. если цифры слева и справа совпали - едим их, если нет - с той стороны где цифр меньше добавляем в центр подходящую цифру и едим их.
3. слово не кончилось - снова 2.

из перебранных вариантов выбираем с наименьшими добавленными.

Чтобы выдавать лексикографически минимальные результаты - на шаге 2 если цифр слева и справа поровну - добавляй 0 а не 1.

malloc   19 февраля 2013 в 00:15

Типа того и получится.[2].

Когда работать будешь, тоже на форуме будешь спрашивать?

miha64   19 февраля 2013 в 00:30

shtyle
Спасибо большое. Завтра попробую все это осмыслить и написать.
Muny
Конечно, только вопросы будут другого уровня. Это плохо?

qwerty1999   19 февраля 2013 в 01:45

Так и в этой ситуации - извращенское применение не самого приятного алгоритма для методических(!) целей.
Что за бред? Тебе дали проблему - реши её.

Walamaz   19 февраля 2013 в 06:06

Давным давно в турбо-паскале что-то подобное решал :D

jk241   19 февраля 2013 в 06:06

В таблице T[j,j] = 0, так что по твоим формулам все остальное можно заполнить, тогда T[0,n] будет как раз то число что ты ищешь.