| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / 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.
Заранее спасибо!
KilkennyCat (2010-05-10 13:05:00) [241]мое решение полностью удовлетворяет поставленному условию.
xayam (2010-05-10 12:46:00) [242]
> 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);
это что такое? тут же не только максимальный подпалендром, но и анаграмма одновременно :) к тому же в входной строке может быть уже задан палендром, тогда эту входную строку нужно вывести в том же виде. Не?
KilkennyCat (2010-05-10 12:38:00) [243]А вообще, решение простое:
MaxPodPalindrom := copy(Palindrom, 2, length(Palindrom)-2);
KilkennyCat (2010-05-10 12:31:00) [244]
> 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;
что некрасиво.
xayam (2010-05-10 12:17:00) [245]
> ...препод сказал, что функцию ваще как бэ не нужна ибо там
> есть рекурсия...
> ...я б перебором бы сделал, а нельзя. а как динамическим прогромированием
> ее решать я ваще не понимаю...
либо я что-то не понимаю, либо динамическое программирование подразумевает использование рекурсии поскольку общее решение задачи сводится к решению более мелких рекурсивно, но если препод сказал, что рекурсия не нужна, то мой вариант должен подойти, т.к. перебор не полный и быстрый даже на длинных строках :) хотя и динамическим его не назовешь по-моему.
xayam (2010-05-10 11:47:00) [246]после readln(s); еще можно вставить проверку на пустую строку, иначе ошибка вылетает:
if s = '' then begin
write('0');
readln;
exit;
end;
xayam (2010-05-10 11:13:00) [247]
> Например, 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.
Германн (2010-05-09 01:21:00) [248]
> это разве наши проблемы ?
Отчасти это твоя проблема, Игорь. И также других модераторов. Сколько ещё веток на одну и ту же тему заведёт автор за оставшиеся 8 дней?
:)
Игорь Шевченко (2010-05-09 01:15:00) [249]
> надо разбираться сидеть, а времени разбираться нету(((
это разве наши проблемы ?
Плохиш (2010-05-08 15:53:00) [250]
> Sha © (08.05.10 12:26) [28]
Ты не умничай, ты код для копи-пасте давай, а то
> надо разбираться сидеть, а времени разбираться нету(((
> и так не по себе
Sha (2010-05-08 12:26:00) [251]тут на псевдокоде, почти паскаль
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
rodion (2010-05-08 11:56:00) [252]Sha, спс что помогаешь, но блин это с++(я про ссылку). надо разбираться сидеть, а времени разбираться нету(((
> Германн © (08.05.10 02:38) [26]
> > ты откуда код списал, дубинушкоПричем даже не выучил/заметил
> как пишется термин ПалиндромВ стройбат однозначно!
может хватит критики не по делу? и так не по себе
Германн (2010-05-08 02:38:00) [253]
> ты откуда код списал, дубинушко
Причем даже не выучил/заметил как пишется термин Палиндром
В стройбат однозначно!
Sha (2010-05-07 18:59:00) [254]Опечатка, надо так
и хвостом длины X=L+1-Y.
Sha (2010-05-07 18:52:00) [255]> 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 лежат на неглавной диагонали матрицы.
Т.е. тебе даже не надо строить всю мартицу для исходной и перевернутой строки.
А дальше, как обычно, из найденного максимального элемента
восстанавливаешь общую подпоследовательность. Это начало палиндрома.
Хвост попробуй найти сам.
Рассмотри случаи четной и нечетной длины палиндрома.
Smile (2010-05-07 18:02:00) [256]> Leonid Troyanovsky © (07.05.10 17:55) [22]
Это было так давно, что возможно и ошибся:(
"Беллман Р., Энджел Э. Динамическое программирование и уравнения в частных производных", гораздо ближе ...
:)
Leonid Troyanovsky (2010-05-07 17:55:00) [257]
> Smile (07.05.10 17:38) [21]
> А у меня (я больше прикладник) это Дженкинс и Бокс
Не запутывай нас, оные из планирования эксперимента, IMHO,
вроде крутового восхождения.
--
Regards, LVT.
Smile (2010-05-07 17:38:00) [258]По поводу Бэллмана ...
А у меня (я больше прикладник) это Дженкинс и Бокс
:)
Leonid Troyanovsky (2010-05-07 17:28:00) [259]
> antonn © (07.05.10 16:51) [19]
> а солдаты такие нужны?
Солдаты всякие Родине пригодятся.
Кто программу сварганит, кто борщ сварит, кто споет -
главное чтоб для общей цели.
offtop
А чего, оный Подпалендром - это, дейс-но, динамческое
программирование, бо мы, как-то, учили, что это Беллман и др.?
Или я опять от жизни отстал :( ?
end offtop
--
Regards, LVT.
antonn (2010-05-07 16:51:00) [260]
> Palladin © (07.05.10 13:17) [14]
>
> ну не нужны стране такие космонавты
а солдаты такие нужны?
| |
