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

← →
KilkennyCat © (2010-05-10 17:57) [80]

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

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

← →
Sha © (2010-05-10 18:03) [81]

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

Полное решение для подстроки привел автор.

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

Заполнение той же матрицы, что у автора, без рекурсии приведено в [47].

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

Для подстрок или подпоследовательностей, когда нужна только длина подпоследовательности, достаточно вектора.

Если нужна сама подпоследовательность, то, по-видимому, без матрицы не обойтись.
Точнее, мне решения без матрицы не попадались.

← →
xayam © (2010-05-10 18:19) [82]

> Заполнение той же матрицы, что у автора, без рекурсии приведено
> в [47].
> Sha © (10.05.10 14:26) [47]
> 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;

ну я потестировал этот код без рекурсии. Для исходное строки HTEOLFEOLEH есть два решения по матрице HEOFOEH и HELFLEH, а того что в примере HELOLEH нет. Ошибся где-то в процедуре?

← →
Sha © (2010-05-10 18:27) [83]

> xayam © (10.05.10 17:28) [76]
> Мы и первоисточники читаем.
> http://.../lesson2.htm

Кошмар. Непричесанный полуфабрикат.

← →
xayam © (2010-05-10 18:34) [84]

Вот тест для твоего кода, по матрице видно, что только два решения.
1 0 0 0 0 0 0 0 0 0 7 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 0 0 5 0 0 0 0 1 0 0 0 3 0 0 0 0 0 0 0 1 0 0 0 3 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1

program MaxPalendrom2; {$APPTYPE CONSOLE} uses SysUtils; const max = 100; var Mat: array[1..max, 1..max] of integer; s: string; i, j, n: integer; procedure FillPalMatrix(const s: string); var i, j, t, count, found: integer; begin; for j:= 1 to n 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; begin //readln(s); s:= "HTEOLFEOLEH"; n:= length(s); for i:= 1 to n do for j:= 1 to n do if i = j then Mat[i, j]:= 1 else if i > j then Mat[i, j]:= 0 else Mat[i, j]:= -1; FillPalMatrix( s ); for i:= 1 to n do for j:= 1 to n do if s[i] <> s[j] then Mat[i, j]:= 0; for i:= 1 to n do begin for j:= 1 to n do write( inttostr( Mat[i, j] ) + " " ); writeln; end; readln; end.

← →
Sha © (2010-05-10 18:46) [85]

Просто 1 раз в самом начале вызови FillPalMatrix(s) и все.
Больше не меняй элементы матрицы.

Не читай элементы ниже главной диагонали,
они не имеют смысла, т.к. не существует строк с отрицательной длиной.

← →
xayam © (2010-05-10 18:51) [86]

> Sha © (10.05.10 18:46) [85]
> Просто 1 раз в самом начале вызови FillPalMatrix(s) и все.
> Больше не меняй элементы матрицы.

так обнулить же тоже надо, иначе там неправильно получается - не палендром, а какой-то мусор в матрице

← →
Sha © (2010-05-10 18:52) [87]

Например, процедура автора с ипользованием FillPalMatrix(s) перепишется так:
begin; s:=Edit1.Text; FillPalMatrix(s); maxi:=0; maxj:=0; for j:=1 to length(s) do for i:=j downto 1 do if (j-i+1>maxj-maxi+1) and (j-i+1=Mat[i,j]) then begin; maxi:=i; maxj:=j; end; Memo1.Lines.Add(IntTostr(maxj-maxi+1)); Memo1.Lines.Add(copy(s,maxi,maxj-maxi+1)); //палиндром без пропусков end;

← →
Sha © (2010-05-10 18:53) [88]

> так обнулить же тоже надо

не надо

← →
xayam © (2010-05-10 19:01) [89]

выводит:
1 H
program MaxPalendrom2; {$APPTYPE CONSOLE} uses SysUtils; const max = 100; var Mat: array[1..max, 1..max] of integer; s: string; i, j, n, maxi, maxj: integer; //f: TEXT; procedure FillPalMatrix(const s: string); var i, j, t, count, found: integer; begin; for j:= 1 to n 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; begin //readln(s); s:= "HTEOLFEOLEH"; n:= length(s); //assign(f, "C:\text.txt"); //rewrite(f); for i:= 1 to n do for j:= 1 to n do if i = j then Mat[i, j]:= 1 else if i > j then Mat[i, j]:= 0 else Mat[i, j]:= -1; FillPalMatrix( s ); {for i:= 1 to n do for j:= 1 to n do if s[i] <> s[j] then Mat[i, j]:= 0;} maxi:= 0; maxj:= 0; for j:= 1 to n do for i:= j downto 1 do if ( j - i + 1 > maxj - maxi + 1 ) and ( j - i + 1 = Mat[i, j] ) then begin maxi:= i; maxj:= j; end; writeln( IntTostr( maxj - maxi + 1) ); writeln( copy(s, maxi, maxj - maxi + 1) ); //rewrite(f); readln; end.

← →
Sha © (2010-05-10 19:08) [90]

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

← →
xayam © (2010-05-10 19:13) [91]

> Sha © (10.05.10 18:53) [88]
> > так обнулить же тоже надо
> не надо

это почему? Вот без обнуления к строке
1) H
2) T
3) E
4) O
5) L
6) F
7) E
8) O
9) L
10) E
11) H
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 1) 1 1 1 1 1 1 3 3 3 5 7 2) 0 1 1 1 1 1 3 3 3 5 5 3) 0 0 1 1 1 1 3 3 3 5 5 4) 0 0 0 1 1 1 1 3 3 3 3 5) 0 0 0 0 1 1 1 1 3 3 3 6) 0 0 0 0 0 1 1 1 1 3 3 7) 0 0 0 0 0 0 1 1 1 3 3 8) 0 0 0 0 0 0 0 1 1 1 1 9) 0 0 0 0 0 0 0 0 1 1 1 10) 0 0 0 0 0 0 0 0 0 1 1 11) 0 0 0 0 0 0 0 0 0 0 1
очевидно, что большинство решений для получения максимального палендрома не имеют смысла, как и нули ниже главной диагонали. Не?

← →
xayam © (2010-05-10 19:15) [92]

> потому что пример автора ищет не подпоследовательности-палиндромы,
> а подстроки-палиндромы

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

← →
xayam © (2010-05-10 19:17) [93]

в матрице есть решения, я про вывод не говорю

← →
xayam © (2010-05-10 19:24) [94]

Вот сравни эти матрицы:
обнуленная необнуленная 1 0 0 0 0 0 0 0 0 0 7 1 1 1 1 1 1 3 3 3 5 7 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 3 3 3 5 5 0 0 1 0 0 0 3 0 0 5 0 0 0 1 1 1 1 3 3 3 5 5 0 0 0 1 0 0 0 3 0 0 0 0 0 0 1 1 1 1 3 3 3 3 0 0 0 0 1 0 0 0 3 0 0 0 0 0 0 1 1 1 1 3 3 3 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 3 3 0 0 0 0 0 0 1 0 0 3 0 0 0 0 0 0 0 1 1 1 3 3 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1

В обнуленной сразу решения видно.

← →
xayam © (2010-05-10 19:29) [95]

о, блин я тормоз, там же три решения на каждую тройку:
1 0 0 0 0 0 0 0 0 0 7 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 0 0 5 0 0 0 0 1 0 0 0 3 0 0 0 0 0 0 0 1 0 0 0 3 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
так что все работает, нужно обнулять и вычленять любой результат

← →
Sha © (2010-05-10 19:32) [96]

Для того, чтобы найти и вывести все решения обоих задач
(для подстрок-палиндромов и подпоследовательностей-палиндромов)
достаточно иметь матрицу, сформированную FillPalMatrix.

Любые последующие действия с матрицей могут привести лишь к потере
содержащихся в ней решений.

← →
xayam © (2010-05-10 19:39) [97]

> Любые последующие действия с матрицей могут привести лишь
> к потере содержащихся в ней решений.

так не теряется же, потому что условие стоит if s[i] <> s[j] then Mat[i, j]:= 0;
в [95] - все возможные решения выделены жирным шрифтом. Чтобы вывести любой результат нужно сделать цикл в направлении от верхнего правого угла к нижнему левому постепенно уменьшая номер строки i и столбца j, тогда значение матрицы будет уменьшаться на два от начальных семи до единицы, все просто :) еще нужно учесть, что размер матрицы может быть четным числом.

← →
xayam © (2010-05-10 19:41) [98]

> уменьшая номер строки i и столбца j

поправка: увеличивая i и уменьшая j

← →
Sha © (2010-05-10 19:43) [99]

> xayam © (10.05.10 19:39) [97]

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

← →
Sha © (2010-05-10 20:08) [100]

Для полной ясности. Мы заполняли матрицу не решениями.

Mat[i,j] содержит длину максимального палиндрома, образованного некоторыми символами подстроки s[i..j], идущими в том же порядке.
А среди них совершенно случайно оказались нужные нам в обоих задачах длины :)

← →
Родион (2010-05-10 20:35) [101]

ув. Sha и xayam что я могу показать завтра на зачете из всего, что вы перерешали? =)

← →
Плохиш © (2010-05-10 20:47) [102]

> что я могу показать завтра на зачете из всего, что вы перерешали?

Что понял, то и показывай.

← →
KilkennyCat © (2010-05-10 20:48) [103]

> Родион (10.05.10 20:35) [101]

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

← →
Родион (2010-05-10 21:01) [104]

ребят, мне не чего собственно объяснять не нужно.. мне просто надо принести задачу, чтоб как она сказала в данной функции

Function F(i, j : Integer) : Integer;
var Ch : Char; R1, R2 : Integer; k : byte;
begin
if Mat[i, j] = -1 then
BEGIN
k := j;
while s[i] <> s[k] do dec(k);
R1 := F(i + 1, j);
if i <> k then R2 := F(i + 1, k - 1) + 2 else R2 := 1;
if R1 > R2 then Mat[i, j] := R1 else Mat[i, j] := R2
END;
F := Mat[i, j]
end;

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

← →
Плохиш © (2010-05-10 21:04) [105]

> за несколько дней проведенных в этом форуме я понял

А должен был понять, что проблемы индейцев шерифа не волнуют.

← →
Родион (2010-05-10 21:08) [106]

> А должен был понять, что проблемы индейцев шерифа не волнуют.

спасибо

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

> Родион (10.05.10 21:01) [104]
> чтоб как она сказала в данной функции не было рекурсии

Перечитай ветку, текст заполнения матрицы приводился уже.
А функкция, если она тебе все еще зачем-то нужна, будет из одного оператора:
Result:=Mat[i,j];

← →
Родион (2010-05-10 21:18) [108]

> А функкция, если она тебе все еще зачем-то нужна

препод сказал ваще убирай ее или рекурсию из функции в конец программы, что то в этом роде

> ваще убирай ее

Молодец какая :)
Полностью солидарен.

> или рекурсию из функции в конец программы, что то в этом роде

Скорее всего, что-то в этом роде :)
Иначе телега впереди лошади.

> Родион (10.05.10 21:18) [108]
> > А функкция, если она тебе все еще зачем-то нужна
> препод сказал ваще убирай ее или рекурсию из функции в конец
> программы, что то в этом роде

[84] как раз без рекурсии и все правильно заполняет, осталось только матрицу обойти и вывести результат. Хоть что-то ты должен сделать :)

> [84] как раз без рекурсии и все правильно заполняет
там много лишнего, можно обрезать
program MaxPalendrom2; {$APPTYPE CONSOLE} uses SysUtils; const max = 100; var Mat: array[1..max, 1..max] of integer; procedure FillPalMatrix(const s: string); var i, j, t, count, found: integer; begin for j:= 1 to n 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; var s: string; begin readln(s); FillPalMatrix(s); //тут твои 15 строчек end.
Всего 15 строчек написать надо.
И что характерно, за все это время ни единой попытки написать первую строчку

← →
Родион (2010-05-10 21:39) [112]

"обойти матрицу" можно тут поподробнее чуть, xayam :)

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

for j:= 1 to n do begin \ мб не n а max. или я о5 туплю(

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

> Родион (10.05.10 21:39) [112]
> "обойти матрицу" можно тут поподробнее чуть, xayam :)

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

Вот, например, если вместо них написать
maxi:=0; maxj:=0; for j:=1 to length(s) do for i:=j downto 1 do if (j-i+1>maxj-maxi+1) and (j-i+1=Mat[i,j]) then begin; maxi:=i; maxj:=j; end;
то мы найдем, положение максимального палиндрома-строки.
Можешь это использовать в качестве примера обхода матрицы.

> Родион (10.05.10 21:39) [112]
> "обойти матрицу" можно тут поподробнее чуть, xayam :)

[114] + [95] (жирным выделено то что тебе нужно получить в общем виде пройдя один из путей 7-3-1)

7-5-33-1111

если коротко, то примерно так осуществляется обход:
r:= ""; // результирующая половина подпалендрома вместе с центром i:= 1; // первая строка j:= n; // правый столбец while i <> j do r:= r + getNext( i, j );
ну и прототип функции getNext:
function getNext ( var i, j: integer ): string; begin //здесь твой анализ матрицы Mat[i, j] //точнее нужно рассмотреть четыре ячейки: // Mat[i+1, j] // Mat[i, j-1] // Mat[i+1, j-1] // Mat[i, j] //и в зависимости от их нулевого/ненулевого значения изменить //соответственно i и/или j для следующей итерации end;
и вывод результата:
writeln( IntToStr( 2*length( r ) - 1 ) ); write(r); for i:= length(r) - 1 downto 1 do write(r[i]);

← →
Родион (2010-05-10 22:18) [119]

> function getNext ( var i, j: integer ): string;begin
> //здесь твой анализ матрицы Mat[i, j] //точнее
> нужно рассмотреть четыре ячейки: // Mat[i+1,
> j] // Mat[i, j-1] //
> Mat[i+1, j-1] // Mat[i, j] //и в
> зависимости от их нулевого/ненулевого значения изменить
> //соответственно i и/или j для следующей итерацииend;
>

и все их надо рассматривать, их же много

четыре всего

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