| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Динамическое програмирование. Подпалендром. [D7, WinXP]
rodion © (2010-05-07 07:30:00)
Страницы: < 1 2 3 4 5 6 7 8 9 10 ... 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.
Заранее спасибо!
Родион (2010-05-11 17:12:00) [121]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
преподу не понравилась матрица.
как я понял:
H 0 0 0 0 0 0 0 0 0 0 0
T 0 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0 0
O 0 0 0 0 0 0 0 0 0 0 0
L 0 0 0 0 0 0 0 0 0 0 0
F 0 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0 0
O 0 0 0 0 0 0 0 0 0 0 0
L 0 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0 0
H 0 0 0 0 0 0 0 0 0 0 0
H T E O L F E O L E H
я не стал заполнять, не удобно. просто я имею в виду что H T E O L F E O L E H я правильно обозначил?
xayam (2010-05-11 16:41:00) [122]
> Sha © (11.05.10 16:26) [156]
> Это он не про заполнение матрицы, а про восстановление по
> ней палиндрома.
> Хотя я тоже не вижу смысла в рекурсии, если цикла достаточно.
ну как бы программа одна и раз без рекурсии, то логично, что все без рекурсии, хотя имхо пропод вообще и не парился: сказал что не сам писал и раз автор не может доказать обратное, при имеющемся коде, то и разговаривать не о чем, хотя [146] не доделано - неправильно работает с некоторыми строками.
> Вот интересно, автору и ты, и я, и препод как восстановить
> палиндром на пальцах рассказали, ты даже матрицу ему показал.
> Он типа все понял и вопросов не имеет. Но вместо того, чтоб
> начать писать, он нам пересказывает, что нам надо сделать
> по словам препода.
ну да, хоть его код посмотреть на какой-нибудь задаче, а скопипастеное явно не катит, хотя я не против копипаста, если можешь разобраться как работает, но тут другой случай :)
Sha (2010-05-11 16:26:00) [123]> xayam © (11.05.10 16:08) [154]
Это он не про заполнение матрицы, а про восстановление по ней палиндрома.
Хотя я тоже не вижу смысла в рекурсии, если цикла достаточно.
Вот интересно, автору и ты, и я, и препод как восстановить палиндром на пальцах рассказали, ты даже матрицу ему показал.
Он типа все понял и вопросов не имеет. Но вместо того, чтоб начать писать, он нам пересказывает, что нам надо сделать по словам препода.
Родион (2010-05-11 16:25:00) [124]вот вот. в позопрошлый раз сказали чтобы была функкция
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;
потом сказала уберай ее или рекурсию убери из функции.
а щас говорит что без рекурсии ни как
xayam (2010-05-11 16:08:00) [125]
> рекурсией фигачишь
в прошлый раз тебе вроде сказали, что без рекурсии. Не?
Palladin (2010-05-11 15:52:00) [126]) я название для фирмы чудо-программистов придумал: Скопируем и Вставим )
Родион (2010-05-11 14:58:00) [127]
> > ребят нужно простое решение задачисапоги заранее начистить?
> :)
я в принципе такого ответа и ожидал)) только вот что тут зделаешь уже..
sniknik (2010-05-11 14:44:00) [128]> ребят нужно простое решение задачи
сапоги заранее начистить? :)
Родион (2010-05-11 14:34:00) [129]не сдал) сидели с преподом, она мне обьясняла как заполняеться матрица, что я и так понял. я ей показал [146] и толком не посмотрев отдала обратно флэху. говорит что не я решал, но так оно и есть я даже спорить не стал.
сказала, что после создания 2х мерн массива идешь проверять вертикаль и диагональ и рекурсией фигачишь. вобщем завтра забиваю на пары, иначе не как, и в 9-30 к ней. ребят нужно простое решение задачи
Sha (2010-05-11 10:12:00) [130]> Leonid Troyanovsky © (11.05.10 09:58) [144]
> если не коллекционировать подобные решения, то, дейс-но,
будет жалко потраченного времени.
Выложу оба решения чуть погодя, там много визуализации лишней, убрать надо.
> Кроме обсуждаемой темы и упомянутых битов можно вспомнить,
например, про точку в регионе.
Про точку есть еще одна совершенно замечательная (или не очень - фиг знает, пробовать надо, а времени нет) идея. Кроме лучевого, есть еще один известный метод - подсчет суммы углов. Но там проблема с точностью и скоростью. Идея в том что количество оборотов вокруг точки можно узнать без подсчета суммы углов, достаточно следить за перемещением вершин по квадрантам.
Sha (2010-05-11 10:06:00) [131]> Родион (11.05.10 10:03) [147]
что код-то делает?
человеским языком объясни.
Родион (2010-05-11 10:03:00) [132]ой блин, не перебор а оббход
xayam (2010-05-11 10:02:00) [133]примерно так, но код не отлажен, может на некоторых строках не работать:
program MaxPalendrom2;
{$APPTYPE CONSOLE}
uses SysUtils;
const max = 100;
type point = record
x, y: integer;
end;
var Mat: array[1..max, 1..max] of integer;
s, r: string;
i, j, n, mini, maxj: integer;
p: point;
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;
function maximum( const a, b, d, f: integer ): point;
begin
if Mat[a, b] > Mat[d, f] then begin
maximum.x:= a;
maximum.y:= b;
end else begin
maximum.x:= d;
maximum.y:= f;
end;
end;
function getNext ( var i, j: integer; var p: point ): string;
var p2: point;
begin
p2.x:= p.x;
p2.y:= p.y;
p:= maximum ( p.x, p.y, i, j );
p:= maximum ( p.x, p.y, i - 1, j + 1 );
p:= maximum ( p.x, p.y, i, j + 1 );
p:= maximum ( p.x, p.y, i - 1, j );
if ( p2.x = p.x ) and ( p2.y = p.y )
then result:= ''
else result:= s[p.x];
i:= i - 1;
j:= j + 1;
end;
begin
readln(s);
//s:= 'HTEOLFEOLEH';
if s = '' then begin
writeln('0');
readln;
exit;
end;
n:= length(s);
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;
i:= n div 2 + 1;
j:= i;
p.x:= i;
p.y:= j;
r:= s[p.x];
if n mod 2 = 1 then mini:= 1 else mini:= 0;
if n mod 2 = 1 then maxj:= n else maxj:= n + 1;
while ( i <> mini ) and ( j <> maxj ) do
r:= r + getNext( i, j, p );
n:= length(r);
writeln( IntToStr( Mat[p.x, p.y] ) );
for i:= n downto 2 do write(r[i]);
write(r);
readln;
end.
Родион (2010-05-11 09:59:00) [134]посмотрел кодировку [84] и посмотрел как там осуществляется пекребор
Leonid Troyanovsky (2010-05-11 09:58:00) [135]
> Sha © (11.05.10 09:25) [140]
> его. И то, и другое требует усилий на понимание и на программирование.
Вот. Т.е., если не коллекционировать подобные решения, то, дейс-но,
будет жалко потраченного времени.
Может ИШ снабдит ссылкой на тот самый задачник, и где-нибудь
найдется местечко для решений, часто с этим АП помогал.
Кроме обсуждаемой темы и упомянутых битов можно вспомнить,
например, про точку в регионе.
--
Regards, LVT.
Sha (2010-05-11 09:54:00) [136]> Родион (11.05.10 09:47) [142]
> Родион (10.05.10 23:11) [129]
> вот я бы посмотрел на код, и разобрался бы,
Вот на код [115] из твоей методички ты смотрел 4 месяца.
Разобрался?
Расскажи, что он делает.
И нафига ты его скопипастил в [142] тоже расскажи.
Родион (2010-05-11 09:47:00) [137]ребят, напишите эти самые 15 строчек плззз! ну оч надо через 40 мин на зачет. от этого много чего зависит
хотиите посмотреть на мою ерунду пожалуйста
begin
readln(s);
n:= length(s);
for i:= 1 to n do
for j:= 1 to n do begin
if i = j then Mat[i, j]:= 1 else
if i > j then Mat[i, j]:= 0 else
Mat[i, j]:= -1;
Matrix( s );
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( 2*length( r ) - 1 ) );
writeln( copy(s, maxi, maxj - maxi + 1) );
readln;
end.
Sha (2010-05-11 09:32:00) [138]или дублируя его =
или дублируя необходиые действия при обработке элемента неглавной диагонали
Sha (2010-05-11 09:25:00) [139]> Leonid Troyanovsky © (11.05.10 08:47) [138]
:)
Тут вообще сюжет интересный.
Сначала мне было интересно решить задачу автора через LCS, т.к. это более общий метод. Там решение оказалость хоть и простым, но не таким гладким, как хотелось бы. Причина в том, что если в длина палиндрома четная, то в нем нет центрального элемента, и раскручивать палиндром приходится, отталкиваясь от ячейки ниже неглавной диагонали, или дублируя его. И то, и другое требует усилий на понимание и на программирование.
Потом я стал разбираться в решении автора. Оказалось, что в матрице запоминаются длины палиндромов-подпоследовательностей, а из нее извлекается решение-подстрока. Такой вот винегрет. В добавок вычисления элементов матрицы сделаны через одно место. А из-за того, что при разборе решения бардак перекочевал в мой код, пришлось наводить в нем порядок. Плюс ко всему захотелось проверить, насколько проще будет решение, если изначально в матрице сидят длины палиндромов, а не общих подпоследовательностей.
Anatoly Podgoretsky (2010-05-11 09:20:00) [140]> Родион (11.05.2010 00:03:13) [133]
Смотря что в них написано, кем написано и сколько это заняло времени, могут очень дорого стоить.
| |
