Комментарии:
15
сначала
по количеству реакций
Ваш комментарий
Типа того и получится.
Без нефалемки здесь не обойтись.
up
Типа того и получится.[2].
Когда работать будешь, тоже на форуме будешь спрашивать?
Гринааа
Что такое нафалемка?
Нефалемы древние.
miha64
Ты на программиста учишься?
Torum.
Да.
Muny
Типа того.
Дежа вю какое-то..
PS. Типа того и получится.
Извиняюсь если в чем-то не прав или путаю, но Вам ведь ни к чему знать облагаемые дополнительным налогом товары, ввозимые судовым транспортом в Египет при размере партии свыше 400кг, однако если контуженного преподавателя по таможенному праву переклинит - отвертеться от этой темы будет сложно. Так и в этой ситуации - извращенское применение не самого приятного алгоритма для методических(!) целей.
ЗАГРУЗИТЬ ВСЕ КОММЕНТАРИИ
Задача:
Палиндромом называется строка, которая читается одинаково слева направо и справа налево. Например, 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]? Мб статейку посоветуйте. Заранее спасибо.