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

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

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

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

Страницы: < 1 2 3 4 5 6 7 8 9 10 ... 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.

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

Родион (2010-05-12 14:48:00) [41]
поправочка s1[1..6]=aomtag

Родион (2010-05-12 14:46:00) [42]
то есть если я возьму s1[1..6] amotag и s2[1..6] atmojr то НОП=tmo ? я правильно понял?)

Sha (2010-05-12 14:27:00) [43]
В примере по ссылке
s1[1..4]=ABCB
s2[1..4]=DCBA

M[34]=2, т.к. s1[1..4]=ABCB, s2[1..3]=DCB, НОП=CB

Родион (2010-05-12 14:17:00) [44]
можно на примере в матрице?

Sha (2010-05-12 14:13:00) [45]
> 2 идущих рядом строки?

Не обязательно. Одна может быть у тебя, другая у меня :)

Родион (2010-05-12 14:10:00) [46]

> Пусть у нас есть строки s1[1..n1] и s2[1..n2].

2 идущих рядом строки?

Sha (2010-05-12 14:05:00) [47]
И нафига юлил столько времени? Еще раз так сделаешь, разговор будет окончен.

Пусть у нас есть строки s1[1..n1] и s2[1..n2].
Тогда после работы первой стадии алгоритма LCS элемент M[i,j] матрицы будет содержать длинунаибольшей общей подпоследовательности строк s1[1..i] и s2[1..j].
Выучить наизусть.

Родион (2010-05-12 14:02:00) [48]
я запутался.. мы формируем матрицу потом заполняем ее 1..7, потом идет НОП (если она обязательна, то что она делает?) почему нельзя после заполнения матрицы сразу приступить к нахождению палиндрома?

Родион (2010-05-12 13:54:00) [49]
не знаю. может ты мне скажешь? ((

Sha (2010-05-12 13:43:00) [50]
А не надо врубаться раньше времени.

На вопросы отвечать будем?
Каков физический смысл элементов матрицы, сформированной алгоритмом LCS?

Родион (2010-05-12 13:40:00) [51]
дык, я врубится не могу полносью еще, для чего нужен НОП.. вот и прошу обьяснить примерно

Sha (2010-05-12 13:36:00) [52]
> Родион (12.05.10 13:32) [226]
> надо найти наиб подпоследовательности

я знаю.

На вопросы отвечать будем?
Каков физический смысл элементов матрицы, сформированной алгоритмом LCS?

Родион (2010-05-12 13:32:00) [53]
надо найти наиб подпоследовательности

Sha (2010-05-12 13:16:00) [54]
НЕТ У НАС НИКАКИХ ПАЛИНДРОМОВ.
Мы разбираем работу алгоритма LCS, который ты должен был выучить за семестр.

На вопросы отвечать будем?
Каков физический смысл элементов матрицы, сформированной алгоритмом LCS?

Родион (2010-05-12 13:10:00) [55]
самое большое число в матрице - это максимальное количество букв в палиндроме максимальной длинны. в данном случае 7

Sha (2010-05-12 13:02:00) [56]
Надо же, а я думал она содержит числа которые появились после заполнения матрицы

Каков их физический смысл? Что это такое?
Количество колес у твоего мерседеса или яиц у Билла Гейтса?

Родион (2010-05-12 12:59:00) [57]
числа которые появились после заполнения матрицы

Sha (2010-05-12 12:55:00) [58]
Не перейдем ко 2му этапу пока не будет полной ясности с первым.
Ответь на [219]

Родион (2010-05-12 12:51:00) [59]
какой 2ой этап?

Sha (2010-05-12 12:51:00) [60]
А что она содержит понял?

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

Наверх

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