Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Динамическое програмирование. Подпалендром. [D7, WinXP]

Страницы: < 1 2 ... 5 6 7 8 9 10 11 12 13 14 >
rodion © (2010-05-07 07:30:00)
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, 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 22:10:00) [161]
если коротко, то примерно так осуществляется обход:
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]);

xayam (2010-05-10 21:57:00) [162]
7-5-33-1111

xayam (2010-05-10 21:54:00) [163]

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

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

Sha (2010-05-10 21:53:00) [164]
> Родион (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;
то мы найдем, положение максимального палиндрома-строки.
Можешь это использовать в качестве примера обхода матрицы.

xayam (2010-05-10 21:49:00) [165]
Чтобы вывести любой результат нужно сделать цикл в направлении от верхнего правого угла к нижнему левому постепенно уменьшая номер строки i и столбца j, тогда значение матрицы будет уменьшаться на два от начальных семи до единицы

Родион (2010-05-10 21:41:00) [166]
for j:= 1 to n do begin \ мб не n а max. или я о5 туплю(

Родион (2010-05-10 21:39:00) [167]
'обойти матрицу' можно тут поподробнее чуть, xayam :)

Sha (2010-05-10 21:38:00) [168]
> [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 строчек написать надо.
И что характерно, за все это время ни единой попытки написать первую строчку

xayam (2010-05-10 21:26:00) [169]

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

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

Sha (2010-05-10 21:23:00) [170]
> ваще убирай ее

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

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

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

Родион (2010-05-10 21:18:00) [171]

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

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

Sha (2010-05-10 21:15:00) [172]
> Родион (10.05.10 21:01) [104]
> чтоб как она сказала в данной функции не было рекурсии

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

Родион (2010-05-10 21:08:00) [173]

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

спасибо

Плохиш (2010-05-10 21:04:00) [174]

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

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

Родион (2010-05-10 21:01:00) [175]
ребят, мне не чего собственно объяснять не нужно.. мне просто надо принести задачу, чтоб как она сказала в данной функции

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х масивов, но реализовать все же не могу ибо я наверно нуп, собственно и по этому обратился к вам

KilkennyCat (2010-05-10 20:48:00) [176]

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

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

Плохиш (2010-05-10 20:47:00) [177]

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

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

Родион (2010-05-10 20:35:00) [178]
ув. Sha и xayam что я могу показать завтра на зачете из всего, что вы перерешали? =)

Sha (2010-05-10 20:08:00) [179]
Для полной ясности. Мы заполняли матрицу не решениями.

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

Sha (2010-05-10 19:43:00) [180]
> xayam © (10.05.10 19:39) [97]

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

Страницы: < 1 2 ... 5 6 7 8 9 10 11 12 13 14 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »