Динамическое програмирование. Подпалендром.

← →
xayam © (2010-05-10 13:09) [40]

в любом случае у меня короче решение:
M:=copy(P,2,length(P)-2)
:)

← →
Родион (2010-05-10 13:32) [41]

спс xayam , щас буду разбираться в коде. если будут вопросы напишу)

← →
KilkennyCat © (2010-05-10 13:45) [42]

> если будут вопросы

смешно.

← →
xayam © (2010-05-10 13:46) [43]

будут, будут - у препода :)

← →
Sha © (2010-05-10 13:55) [44]

> xayam
> либо я что-то не понимаю, либо динамическое программирование подразумевает использование рекурсии

Динамическое программирование подразумевает сведение большой задачи к нескольким более мелким и вычисление результата большой задачи с использованием результатов более мелких.
Принципиальное отличие от рекурсии в том, что ни одна задача не решается более одного раза, т.к. все результаты решения подзадач, которые могут потребоваться в будущем, запоминаются. Это резко повышает скорость вычислений по сравнению с рекурсией.
Напоминает индукцию в математике.

← →
xayam © (2010-05-10 14:05) [45]

> Sha © (10.05.10 13:55) [44]
> Динамическое программирование подразумевает сведение большой
> задачи к нескольким более мелким и вычисление результата
> большой задачи с использованием результатов более мелких.

Вот же черным по белому написано:
http://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность
Метод динамического программирования Вначале найдём длину наибольшей подпоследовательности. Допустим мы ищем решение для случая (n1, n2), где n1, n2 — длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m1, m2) меньших заданной. Тогда задача (n1, n2) сводится к меньшим подзадачам следующим образом: [ 0, если n1=0 и n2=0 f(n1,n2) = [ f(n1-1, n2-1) +1, если s[n1] = s[n2] [ max( f(n1-1, n2), f(n1, n2-1) ), если s[n1] <> s[n2]
Ты хочешь сказать, что это не рекурсия - f(n1-1, n2-1) ?

← →
xayam © (2010-05-10 14:11) [46]

Или здесь:

http://ru.wikipedia.org/wiki/Динамическое_программирование

Идея динамического программирования ... В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага. 1) Разбиение задачи на подзадачи меньшего размера. 2) Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм. 3) Использование полученного решения подзадач для конструирования решения исходной задачи.

← →
Sha © (2010-05-10 14:26) [47]

> xayam © (10.05.10 14:05) [45]
> Ты хочешь сказать, что это не рекурсия - f(n1-1, n2-1) ?

Я хочу сказать другое.
Здесь функция вызывает себя, значит, имеет место рекурсивный вызов.
Но эта запись приведена всего лишь для облегчения понимания логики работы.
В действительности можно организовать вычисления так, что никакой рекурсии не будет. Например, вычисления факториала.
Метод динамического программирования предназначен для ограничения рекурсии в глубину одним уровнем. Он особенно хорошо работает, когда есть рекурсивная зависимость по нескольким переменным, когда при помощи обычной рекурсии вычислить что-либо просто невозможно, т.к. все время уходит на бесконечные повторы одних и техже вычислений.

Обычно результаты предыдущих вычислений запоминаются в массиве и, например, полубредовая функция, списанная автором из методички
и использующая начальное заполнение
Function F(i, j : Integer) : Integer;
всего лишь вычисляет длину палиндрома в подстроке s[i..j]
и может быть записана без всякой рекурсии, например, так:
procedure FillPalMatrix(const s: string); var i, j, t, count, found: integer; begin; for j:=1 to length(s) do begin; Mat[j,j]:=1; for i:=j-1 downto 1 do begin; count:=Mat[i+1,j]; t:=j; while s[t]<>s[i] do dec(t); found:=t-i+1; if t>=i+2 then found:=Mat[i+1, t-1]+2; if count<found then count:=found; Mat[i,j]:=count; end; end; end;

← →
xayam © (2010-05-10 14:40) [48]

> ...Метод динамического программирования предназначен для ограничения
> рекурсии в глубину одним уровнем...
> ...Но эта запись приведена всего лишь для облегчения понимания
> логики работы...

нет ты уж определись ДЛЯ чего это. А то тут по ходу каша: записываю в виде рекурсии, а решаю как хочу. Что тогда является критерием для определения принадлежности алгоритма к динамическому?

← →
Sha © (2010-05-10 14:45) [49]

> xayam © (10.05.10 14:40) [48]
> А то тут по ходу каша: записываю в виде рекурсии, а решаю как хочу.

Именно.

> Что тогда является критерием для определения принадлежности алгоритма к динамическому?

Принципиальное отличие от рекурсии в том, что ни одна подзадача не решается более одного раза

← →
xayam © (2010-05-10 14:51) [50]

> Sha © (10.05.10 14:45) [49]
> Принципиальное отличие от рекурсии в том, что ни одна подзадача
> не решается более одного раза

[32] соответствует этому требованию? Я бы назвал этот способ не динамическим и не полным перебором, а например перебор с фильтрацией, поскольку за счет использования множества rs отсекаются значения i и j, которые повторяются т.е. как раз "ни одна подзадача не решается более одного раза" Не?

← →
Sha © (2010-05-10 15:12) [51]

алгоритм [32]
на строке HTEOLFEEOLEH
выдает HEOLETELOEH
вместо HELEELEH

← →
xayam © (2010-05-10 15:16) [52]

> Sha © (10.05.10 15:12) [51]
> на строке HTEOLFEEOLEH
> выдает HEOLETELOEH
> вместо HELEELEH

так вроде и задумывалось. Ищется первое нечетное количество определенного символа и этот символ вставляется в центр, в данном случае количество символов T равно 1. Неправильно?

← →
Sha © (2010-05-10 15:21) [53]

Палиндром образуется вычеркиванием символов из исходной строки,
значит символов в палиндроме должен соответствовать исходному.
Ну, и зеркально расположеные символы относительно центра палиндрома должны быть равны.

← →
Sha © (2010-05-10 15:22) [54]

значит порядок символов

← →
xayam © (2010-05-10 15:22) [55]

тем более HEOLETELOEH длиннее HELEELEH на один символ. А задача как раз найти максимальный :)

← →
Sha © (2010-05-10 15:26) [56]

максимальный, удовлетворяющий [53-54]

← →
xayam © (2010-05-10 15:32) [57]

> Sha © (10.05.10 15:21) [53]
> Палиндром образуется вычеркиванием символов из исходной строки

никакого вычеркивания у меня нет, формируются два массива l[k] и r[k], которые соответствуют найденной одинаковой паре символов, отличаются только значения (смещение в строке s)

> значит символов в палиндроме должен соответствовать исходному.

исходной строке? с какого перепугу?

> Ну, и зеркально расположеные символы относительно центра
> палиндрома должны быть равны.

так и есть, нов условии задачи помимо максимального кол-ва символов указано, что строка должна одинаково читаться, как слева направа, так и справа налева. Есть ли центральный символ или нет его - это условие соблюдается, но при наличии центра получается длинее выходная строка, поэтому центр и добавляется.

> значит порядок символов

в условии задачи написано: не обязательно идущих подряд. Т.е. порядок не учитывается.

← →
xayam © (2010-05-10 15:38) [58]

> xayam © (10.05.10 15:22) [55]
> тем более HEOLETELOEH длиннее HELEELEH на один символ
> Sha © (10.05.10 15:12) [51]

опс, даже не на один, а на три. Буквы "О" забыл?

← →
Sha © (2010-05-10 15:48) [59]

> xayam © (10.05.10 15:32) [57]

Автор списал с методички решение задачи,
в которой требуется найти в исходной строке
подстроку максимальной длины,
которая является палиндромом.

Препод проверяет насколько чувак понял решение
и просит его решить ту же задачу,
при условии что ищется не подстрока,
а подпоследовательность.
Т.е. между символами подпоследовательности
могут быть другие символы.

От автора требуется найти способ восстановить
подпоследовательность по той же матрице,
если он до сих по не догадался.

← →
xayam © (2010-05-10 15:56) [60]

слушай мы щас вроде не про автора говорим и его заморочки с скопипастенной функцией, у меня ее вообще в алгоритме нет. Даже нет двумерного массива 100х100 и он вроде бы тоже не обязателен в использовании, а только два массива в сумме 2х100 + несколько вспомогательных переменных, так что в памяти явно выигрывается [32], и в скорости по-моему претензий не должно быть со стороны препода, только [32] вряд ли является динамическим алгоритмом, хотя можно попытаться доказать обратное преподу, если он упрется, все таки полного перебора тоже нет, к тому же на строке до 100 символов летает.

← →
Sha © (2010-05-10 16:04) [61]

> xayam © (10.05.10 15:56) [60]
> слушай мы щас вроде не про автора говорим

Ну это я сказал, что б было понятно, откуда ноги растут, ну и немного подсказать автору :)

Ключевое слово здесь подпоследовательность.
Конечно, ответ может получаться любым способом,
но результат должен быть подпоследовательностью и палиндромом.

Твое решение не годится, т.к. не может быть получено вычеркиванием
символов из исходной строки, т.е. не является подпоследовательностью.

← →
xayam © (2010-05-10 16:11) [62]

> Ключевое слово здесь подпоследовательность.

такого слова в условии вообще нет. К тому же, если ты не заметил, нахождение подпоследовательности - частный случай алгоритма [32], поскольку при этом важен порядок символов, [32] же не зависит от порядка символов, поскольку ищутся только пары одинаковых символов, поэтому как бы ты не упорядочил символы - алгоритм будет работать. Если не согласен, то пиши входные данные, что выводит алгоритм и что должно быть на самом деле по-твоему. [51] правильно выводит, ошибки нет.

← →
Sha © (2010-05-10 16:17) [63]

>> Ключевое слово здесь подпоследовательность.

> xayam © (10.05.10 16:11) [62]
> такого слова в условии вообще нет

Подпоследовательность = последовательность символов из данной строки, не обязательно идущих подряд

> Если не согласен, то пиши входные данные, что выводит алгоритм и что должно быть на самом деле по-твоему

Уже написал в [51].

Если бы можно было пересталять символы,
задача элементарно решалась бы при помощи массива 256 счетчиков.

← →
xayam © (2010-05-10 16:19) [64]

> нахождение подпоследовательности - частный случай алгоритма [32]

конечно имеется ввиду подпоследовательности, являющейся палендромом

← →
xayam © (2010-05-10 16:22) [65]

> Sha © (10.05.10 16:17) [63]
> > xayam ©
> > Если не согласен, то пиши входные данные, что выводит
> алгоритм и что должно быть на самом деле по-твоему
> Уже написал в [51].

ну так правильно выдает же, внимательно прочитай свое [51], буква "О" в исходной строке встречается два раза + центр T (без пары). Так и должно быть.

← →
Sha © (2010-05-10 16:29) [66]

Вот смотри берем HTEOLFEEOLEH вычеркиваем X X X X остается H E L EE LEH а как из HTEOLFEEOLEH получить H EOLETELOEH вычеркиванием?

← →
Родион (2010-05-10 16:40) [67]

ребят, завтра пойду пробовать сдавать. возьму код [32].

зы: что делает IntToStr?
зыы: не закрывайте тему плз

← →
Sha © (2010-05-10 16:42) [68]

> Родион (10.05.10 16:40) [67]
> возьму код [32]

очень не советую

> Sha © (10.05.10 16:29) [66]

а где в условии это вычеркивание упоминается? Написано - порядок не имеет значения. Конечно, если методом вычеркивания, то алгоритм другой будет. Тут кажется неоднозначно условие задачи, поэтому я бы два алгоритма преподу отнес, а он сам пусть выбирает. Иначе может придраться.

> Родион (10.05.10 16:40) [67]
> что делает IntToStr?

ну как бы это... переводит целый тип в строковый :)

← →
Родион (2010-05-10 16:54) [70]

кк.. ну что то же надо показать

> Родион (10.05.10 16:54) [70]
> кк.. ну что то же надо показать

как бы это... второй вариант алгоритма сам... Не?

или Sha проси, наверно и код набросает, раз столько знает :)

> xayam © (10.05.10 16:54) [69]
> а где в условии это вычеркивание упоминается?

В слове последовательность.
Последовательность подразумевает важность сохранения порядка.
Из вычеркивания следует сохранение порядка и наоборот.

> я бы два алгоритма преподу отнес

И продемонстрировал, что не понимаешь условия задачи, которую решаешь 4 месяца?
Выгонит сразу.

> Родион (10.05.10 16:54) [70]
> что делает IntToStr?

О существовании справки, которая вызывается по клавише F1 тебе известно?
читать пробовал?
что из прочитанного неясно?

ты хоть понял для чего матрица нужна?
чему равны ее элементы?
как по ним подстрока восстанавливается в списанном примере?
расскажи.

> Sha © (10.05.10 17:06) [73]
> > я бы два алгоритма преподу отнес
> И продемонстрировал, что не понимаешь условия задачи, которую
> решаешь 4 месяца?

4 месяца это конечно круто, справился примерно за 2 часа вместе с составлением алгоритма.

> В слове последовательность.
> Последовательность подразумевает важность сохранения порядка.
> Из вычеркивания следует сохранение порядка и наоборот.

ну да последовательность, при не подряд идущих символах - это крутая формулировка, по-моему неточность в задании.

> xayam © (10.05.10 16:54) [69]
> а где в условии это вычеркивание упоминается? Написано -
> порядок не имеет значения.

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

> KilkennyCat © (10.05.10 17:22) [75]
> не идущие подряд и порядок - это разные вещи.

ну может быть, но я могу и так и так трактовать

> во-вторых появляется множество решений, раз можно переставлять
> буквы.

Мы и первоисточники читаем.
http://comp-science.narod.ru/WebPage/lesson2.htm
Подпалиндром Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины. Формат входных данных Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита. Формат выходных данных В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них.
А Вы нет? Тогда мы идем к Вам :)

но там гораздо уникальнее решения, а в твоем случае достаточно сосчитать сколько каких букв.

> KilkennyCat © (10.05.10 17:36) [77]
> но там гораздо уникальнее решения

полного решения там нет, только часть. И вообще ничего уникального в рекурсии не вижу, тем более в данном случае надо без рекурсии решить. Матрица, конечно, это не совсем обычно, но по-моему тоже не обязательно так делать.

> а в твоем случае достаточно сосчитать сколько каких букв

я подумаю, может быть можно приспособить [32] под вычеркивание, скорей всего это возможно.

хотя нет, матрица конечно лучше, если вычеркивание

> И вообще ничего уникального в рекурсии не вижу

я имел ввиду не алгоритм, а полученные результаты. когда я начну считать рекурсию уникальной - застрелюсь :)

Динамическое програмирование. Подпалендром. Найти похожие ветки