| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Динамическое програмирование. Подпалендром. [D7, WinXP]
rodion © (2010-05-07 07:30:00)
Страницы: < 1 2 ... 5 6 7 8 9 10 11 12 13 14 >
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины.
есть код задачи, который нужно исправить, для правильной работы:
program Project6;
{$APPTYPE CONSOLE}
uses
SysUtils;
var
Mat:array[1..100,1..100]of integer;
s:string;
s1:string;
i,j,n,d,j1,k,maxj,maxi:integer;
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;
begin
try
{ TODO -oUser -cConsole Main : Insert code here }
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
readln(s);
for I:=1 to length(s) do
for j := 1 to length(s) do
if i=j then Mat[i,j]:=1
else if i>j then Mat[i,j]:=0
else mat[i,j]:=-1;
maxi:=0;maxj:=0;
for i:=1 to length(s) do
for j:=1 to length(s) do
begin
Mat[i,j]:=f(i,j);
if (j-i+1>maxj-maxi+1)and(j-i+1=Mat[i,j]) then
begin
maxi:=i;
maxj:=j;
end;
end;
writeln(maxj-maxi+1);
writeln(copy(s,maxi,maxj-maxi+1));
readln;
end.
Заранее спасибо!
xayam (2010-05-10 19:41:00) [181]
> уменьшая номер строки i и столбца j
поправка: увеличивая i и уменьшая j
xayam (2010-05-10 19:39:00) [182]
> Любые последующие действия с матрицей могут привести лишь
> к потере содержащихся в ней решений.
так не теряется же, потому что условие стоит if s[i] <> s[j] then Mat[i, j]:= 0;
в [95] - все возможные решения выделены жирным шрифтом. Чтобы вывести любой результат нужно сделать цикл в направлении от верхнего правого угла к нижнему левому постепенно уменьшая номер строки i и столбца j, тогда значение матрицы будет уменьшаться на два от начальных семи до единицы, все просто :) еще нужно учесть, что размер матрицы может быть четным числом.
Sha (2010-05-10 19:32:00) [183]Для того, чтобы найти и вывести все решения обоих задач
(для подстрок-палиндромов и подпоследовательностей-палиндромов)
достаточно иметь матрицу, сформированную FillPalMatrix.
Любые последующие действия с матрицей могут привести лишь к потере
содержащихся в ней решений.
xayam (2010-05-10 19:29:00) [184]о, блин я тормоз, там же три решения на каждую тройку:
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
так что все работает, нужно обнулять и вычленять любой результат
xayam (2010-05-10 19:24:00) [185]Вот сравни эти матрицы:
обнуленная необнуленная
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:17:00) [186]в матрицеесть решения, я про вывод не говорю
xayam (2010-05-10 19:15:00) [187]
> потому что пример автора ищет не подпоследовательности-палиндромы,
> а подстроки-палиндромы
как раз и те и другие, два решения-подпоследовательности есть в матрице
xayam (2010-05-10 19:13:00) [188]
> 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
очевидно, что большинство решений для получения максимального палендрома не имеют смысла, как и нули ниже главной диагонали. Не?
Sha (2010-05-10 19:08:00) [189]И это правильно,
потому что пример автора ищет не подпоследовательности-палиндромы,
а подстроки-палиндромы,
т.е. в примере автора символы палиндрома-результата должны стоять рядом в исходной строке.
Подстрок-палиндромов длины больше 1 нет во введенной строке.
xayam (2010-05-10 19:01:00) [190]выводит:
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 18:53:00) [191]> так обнулить же тоже надо
не надо
Sha (2010-05-10 18:52:00) [192]Например, процедура автора с ипользованием 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;
xayam (2010-05-10 18:51:00) [193]
> Sha © (10.05.10 18:46) [85]
> Просто 1 раз в самом начале вызови FillPalMatrix(s) и все.
> Больше не меняй элементы матрицы.
так обнулить же тоже надо, иначе там неправильно получается - не палендром, а какой-то мусор в матрице
Sha (2010-05-10 18:46:00) [194]Просто 1 раз в самом начале вызови FillPalMatrix(s) и все.
Больше не меняй элементы матрицы.
Не читай элементы ниже главной диагонали,
они не имеют смысла, т.к. не существует строк с отрицательной длиной.
xayam (2010-05-10 18:34:00) [195]Вот тест для твоего кода, по матрице видно, что только два решения.
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:27:00) [196]> xayam © (10.05.10 17:28) [76]
> Мы и первоисточники читаем.
> http://.../lesson2.htm
Кошмар. Непричесанный полуфабрикат.
xayam (2010-05-10 18:19:00) [197]
> Заполнение той же матрицы, что у автора, без рекурсии приведено
> в [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:03:00) [198]>> но там гораздо уникальнее решения
> полного решения там нет, только часть.
Полное решение для подстроки привел автор.
> тем более в данном случае надо без рекурсии решить
Заполнение той же матрицы, что у автора, без рекурсии приведено в [47].
> Матрица, конечно, это не совсем обычно, но по-моему тоже не обязательно так делать.
Для подстрок или подпоследовательностей, когда нужна только длина подпоследовательности, достаточно вектора.
Если нужна сама подпоследовательность, то, по-видимому, без матрицы не обойтись.
Точнее, мне решения без матрицы не попадались.
KilkennyCat (2010-05-10 17:57:00) [199]
> И вообще ничего уникального в рекурсии не вижу
я имел ввиду не алгоритм, а полученные результаты. когда я начну считать рекурсию уникальной - застрелюсь :)
xayam (2010-05-10 17:54:00) [200]хотя нет, матрица конечно лучше, если вычеркивание
| |
