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

← →
rodion (2010-05-07 07:30) [0]

Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, 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.

Заранее спасибо!

← →
MBo © (2010-05-07 07:56) [1]

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

← →
xayam © (2010-05-07 08:21) [2]

не обязательно идущих подряд? это больше анаграмма, чем полиндром. И это... код можно прокомментировать

← →
12 © (2010-05-07 08:26) [3]

> try
> { TODO -oUser -cConsole Main : Insert code here }
> except
> on E:Exception do
> Writeln(E.Classname, ": ", E.Message);
> end;

сильно

← →
Игорь Шевченко © (2010-05-07 10:25) [4]

> try
> { TODO -oUser -cConsole Main : Insert code here }
> except
> on E:Exception do
> Writeln(E.Classname, ": ", E.Message);
> end;

ты откуда код списал, дубинушко ? Я бы только за это выгнал бы с треском

← →
rodion (2010-05-07 11:01) [5]

это можно удалить, это автоматом написалось...

вобщем люди, щас только с зачета, завалил..
препод сказал, что функцию ваще как бэ не нужна ибо там есть рекурсия
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
надо ее засунуть когда уже будет сформирован массив, вобщем что то в этом духе...а потом я, как сказал Игорь Шевченко, вылетел с треском..
народ помогите кто чем может, 17 мая меня отчисляют если не сдам(
такие дела..

← →
Плохиш © (2010-05-07 11:09) [6]

> народ помогите кто чем может, 17 мая меня отчисляют если
> не сдам

в 17 мая переместить?

← →
12 © (2010-05-07 11:12) [7]

код - каша
прямое не уважение к людям
ты думаешь кто-то будет тратить время на разбор, если тебе лень было потратить минутку на форматирование и комментарии?

Вообщем, ща Ега придет и скажет чего делать :)

← →
Плохиш © (2010-05-07 11:15) [8]

> Вообщем, ща Ега придет и скажет чего делать

А, вот кто по пятницам подаёт :-))

PS. Что-то давно не видно всяких защитников немощных и обездоленных...

← →
12 © (2010-05-07 11:26) [9]

не, Ега сайт призывник ру знает как точно пишется :)

← →
12 © (2010-05-07 11:29) [10]

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

// назначение: выбить из матрицы элементы по принципу левой ноги в кастрюле 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; // Function

← →
Rouse_ © (2010-05-07 11:40) [11]

Если придет Ега до 18 нуль-нуль, то будем карать... Не отвлекайте человека - ему код писать нужно :)

← →
Rouse_ © (2010-05-07 11:43) [12]

зы: резюме местного it отдела - "код уныл" :)

← →
rodion (2010-05-07 13:13) [13]

> народ помогите кто чем может, 17 мая меня отчисляют если
> не сдам

в 17 мая переместить?

17 отчислят если не сдам во вторник крайний срок..

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

← →
Palladin © (2010-05-07 13:17) [14]

ну не нужны стране такие космонавты

← →
Sha © (2010-05-07 13:19) [15]

> с января парюсь надо этой задачой

Значит наибольшую общую подпоследоватьность двух последоватьностей
без всякой палиндромности находить уже умеешь?

Имеешь отформатированный отлаженный код для стандартной задачи?

← →
Anatoly Podgoretsky © (2010-05-07 13:33) [16]

> rodion (07.05.2010 11:01:05) [5]

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

← →
Б (2010-05-07 13:42) [17]

За деньгу в сети всегда решат.

← →
rodion (2010-05-07 16:50) [18]

-
> Имеешь отформатированный отлаженный код для стандартной
> задачи?

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

← →
antonn © (2010-05-07 16:51) [19]

> Palladin © (07.05.10 13:17) [14]
>
> ну не нужны стране такие космонавты

а солдаты такие нужны?

← →
Leonid Troyanovsky © (2010-05-07 17:28) [20]

> antonn © (07.05.10 16:51) [19]

> а солдаты такие нужны?

Солдаты всякие Родине пригодятся.
Кто программу сварганит, кто борщ сварит, кто споет -
главное чтоб для общей цели.

offtop
А чего, оный Подпалендром - это, дейс-но, динамческое
программирование, бо мы, как-то, учили, что это Беллман и др.?

Или я опять от жизни отстал :( ?
end offtop

--
Regards, LVT.

← →
Smile (2010-05-07 17:38) [21]

По поводу Бэллмана ...
А у меня (я больше прикладник) это Дженкинс и Бокс
:)

← →
Leonid Troyanovsky © (2010-05-07 17:55) [22]

> Smile (07.05.10 17:38) [21]

> А у меня (я больше прикладник) это Дженкинс и Бокс

Не запутывай нас, оные из планирования эксперимента, IMHO,
вроде крутового восхождения.

--
Regards, LVT.

← →
Smile (2010-05-07 18:02) [23]

> Leonid Troyanovsky © (07.05.10 17:55) [22]

Это было так давно, что возможно и ошибся:(
"Беллман Р., Энджел Э. Динамическое программирование и уравнения в частных производных", гораздо ближе ...
:)

← →
Sha © (2010-05-07 18:52) [24]

> rodion (07.05.10 16:50) [18]
> я в задаче разобрался,

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

Раз мучаешься с января, то наверняка гуглил неоднократно и ссылка
http://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность
тебе знакома.

> проблема в том что реализовать не могу,

Наверняка там или еще где скачал, понял и отладил готовую реализацию

> вот и прошу помощи у вас. поможете или нет?(

Конечно, поможем. Советом.
Заметь, что твоя задача решается с помощью того же алгоритма.
Пусть длина твоей строки равна L. Тебе надо найти максимальную LCS
для L всевозможных пар строк, образованных началом длины Y=1..L
и хвостом длины X=L+1-N. Все такиe LCS лежат на неглавной диагонали матрицы.
Т.е. тебе даже не надо строить всю мартицу для исходной и перевернутой строки.
А дальше, как обычно, из найденного максимального элемента
восстанавливаешь общую подпоследовательность. Это начало палиндрома.
Хвост попробуй найти сам.
Рассмотри случаи четной и нечетной длины палиндрома.

← →
Sha © (2010-05-07 18:59) [25]

Опечатка, надо так
и хвостом длины X=L+1-Y.

← →
Германн © (2010-05-08 02:38) [26]

> ты откуда код списал, дубинушко

Причем даже не выучил/заметил как пишется термин Палиндром
В стройбат однозначно!

← →
rodion (2010-05-08 11:56) [27]

Sha, спс что помогаешь, но блин это с++(я про ссылку). надо разбираться сидеть, а времени разбираться нету(((

> Германн © (08.05.10 02:38) [26]
> > ты откуда код списал, дубинушкоПричем даже не выучил/заметил
> как пишется термин ПалиндромВ стройбат однозначно!

может хватит критики не по делу? и так не по себе

← →
Sha © (2010-05-08 12:26) [28]

тут на псевдокоде, почти паскаль

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

> Sha © (08.05.10 12:26) [28]

Ты не умничай, ты код для копи-пасте давай, а то

> надо разбираться сидеть, а времени разбираться нету(((

> и так не по себе

> надо разбираться сидеть, а времени разбираться нету(((

это разве наши проблемы ?

> это разве наши проблемы ?

Отчасти это твоя проблема, Игорь. И также других модераторов. Сколько ещё веток на одну и ту же тему заведёт автор за оставшиеся 8 дней?
:)

> Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH.
> Напишите программу, находящую в данной строке подпалиндром
> максимальной длины.

может я не прав, но это же не максимальный подпалендром, еще две буквы "О" есть. Не? Я по-своему решил, вроде работает, но нужно на разных строках потестировать:
program MaxPolendrom; {$APPTYPE CONSOLE} uses SysUtils; var s: string; i, j, k, n, b, c: integer; rs: set of 1..100; l, r: array[1..100] of integer; flag: boolean; begin readln(s); for i:= 1 to 100 do begin l[i]:= 0; r[i]:= 0; end; n:= length(s); i:= 1; j:= 2; k:= 0; rs:= []; flag:= false; while true do begin if s[i] = s[j] then begin k:= k + 1; l[k]:= i; r[k]:= j; rs:= rs + [j] {+ [i]}; end; if flag or ( s[i] = s[j] ) then begin i:= i + 1; b:= i; while i in rs do i:= i + 1; if ( i >= n ) or ( ( i = b ) and ( i in rs ) ) then break; flag:= false; j:= i; end; j:= j + 1; b:= j; while j in rs do j:= j + 1; if ( j >= n + 1 ) or ( ( j = b ) and ( j in rs ) ) then flag:= true; end; for i:= 1 to k do write( " left [k]: " + IntToStr( l[i] ) + " " ); writeln; for i:= 1 to k do write( " right[k]: " + IntToStr( r[i] ) + " " ); writeln; c:= 0; for i:= 1 to n do begin flag:= true; for j:= 1 to k do if ( l[j] = i ) or ( r[j] = i ) then flag:= false; if flag then begin c:= i; break; end; end; if c > 0 then writeln( IntToStr( 2*k + 1 ) ) else writeln( IntToStr( 2*k ) ); for i:= 1 to k do write(s[l[i]]); if c > 0 then write(s[c]); //центральный символ обязателен? for i:= k downto 1 do write(s[r[i]]); readln; end.

после readln(s); еще можно вставить проверку на пустую строку, иначе ошибка вылетает:
if s = "" then begin write("0"); readln; exit; end;

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

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

> rs: set of 1..100;
> l, r: array[1..100] of integer

в свою очередь вызывает

> for i:= 1 to 100 do begin
> l[i]:= 0;
> r[i]:= 0;
> end;

что некрасиво.

А вообще, решение простое:
MaxPodPalindrom := copy(Palindrom, 2, length(Palindrom)-2);

> KilkennyCat © (10.05.10 12:31) [35]
> > rs: set of 1..100;
> > l, r: array[1..100] of integer
> в свою очередь вызывает
> что некрасиво.

ну да это я по привычке обнуляю :)

> MaxPodPalindrom := copy(Palindrom, 2, length(Palindrom)-
> 2);

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

мое решение полностью удовлетворяет поставленному условию.

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

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

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