Мастера 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-11 21:06:00) [101]
я бы с радостью!)))) вот только там еще нужно показывать как в матрице это все заполняется. если ты не против я бы тебе передал pdf файлик где тот самый
алгоритм рассматривается =)

Sha (2010-05-11 21:00:00) [102]
Если не затруднит, сформулируй его :)
Я думаю, что даже те теоретики, кто интенсивно работает над строковыми алгоритмами, вряд ли его сходу вспомнят :)

Родион (2010-05-11 20:57:00) [103]

> > FillPalMatrix формирует матрицу по принцепу алгоритма
> нудельмана-вунша?Нет, если, конечно, ты знаешь что это за
> принцип :)

вот он то мне и нужен. вот от куда все непонимание пошло.ффф =)

Sha (2010-05-11 20:41:00) [104]
> FillPalMatrix формирует матрицу по принцепу алгоритма нудельмана-вунша?

Нет, если, конечно, ты знаешь что это за принцип :)

FillPalMatrix заполняет матрицу длинами палиндромов.
Mat[i,j] содержит длину наибольшего палиндрома, образованного некоторыми
символами подстроки s[i..j], идущими в том же порядке, что и в строке s.
Очевидно, Mat[i,i]=1. Другие значения вычисляются рекурсивно.
Подстроку s[i..j] (i<j) можно получить приписыванием символа s[i]
к подстроке s[i+1..j]. Если при этом не образуется максимального палиндрома, то
полагаем Mat[i,j]=Mat[i+1,j]. Если образуется, то в подстроке s[i..j],
перебирая символы, начиная с позиции j, находим ему пару.
Если пара находится в позиции i, то Mat[i,j]=1,
если в позиции i+1, то Mat[i,j]=2,
если в позиции t (i+2<=t<=j), то Mat[i,j]=Mat[i+1,t-1] + 2.

> не подойдет(хоть и правильно)

т.е. чтоб подошло надо сделать неправильно?

> ибо преподу надо чтоб все было заполненно.

для всех возможных подстрок s[i..j] все элементы Mat[i,j] заполнены
чего не хватает? конкретно?

> что в FillPalMatrix исправить или добавить, чтоб удв условиям?

не трогай ее руками, а то сломаешь

Родион (2010-05-11 20:16:00) [105]
я так не сказал. то есть FillPalMatrix формирует матрицу по принцепу алгоритма нудельмана-вунша? а то что я писал for i:=1 n do
for j:=1 n do begin
A[i,j]:=Max(A[i-1,j],A[i,j-1]);
if S[i]=S[j] then A[i,j]:=Max(A[i,j],A[i-1,j-1]+1); - не покатит.

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

Sha (2010-05-11 20:07:00) [106]
Т.е. алгоритм работы FillPalMatrix тебе непонятен,
а бредовая функция, приведенная в начале ветки, тебе понятна?

Родион (2010-05-11 20:03:00) [107]
я так не считаю, препод требует. чтоб он убедился что я понял как заполнять матрицу.

Sha (2010-05-11 19:56:00) [108]
На [166] ответь

Sha (2010-05-11 19:55:00) [109]
В настоящее время у меня, как и у тебя похоже, есть дела поважнее и поинтереснее,
удаление отладочного кода из исходников стоит в очереди на 17 месте.

Родион (2010-05-11 19:51:00) [110]

> Sha © (11.05.10 10:12) [149]
> > Leonid Troyanovsky © (11.05.10 09:58) [144]> если не
> коллекционировать подобные решения, то, дейс-но, будет жалко
> потраченного времени. Выложу оба решения чуть погодя, там
> много визуализации лишней, убрать надо.

выложи)

Sha (2010-05-11 19:47:00) [111]
> Родион (11.05.10 19:34) [167]
> где в коде написанно что она уже заполнена

100 раз говорили, что она заполняется вызовом FillPalMatrix

> я имею в виду

Может, конечно, тебе удобно иначе, но в математике и программировании принято располагать матрицу так, чтобы первая строка содержала элементы M[1,1], M[1,2]...M[1,x], а последняя M[у,1], M[y,2]...M[y,x].

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

Родион (2010-05-11 19:34:00) [112]
где в коде написанно что она уже заполнена. я имею в виду

H 1
T 1
E 1
O 1
L 1
F 1
E 1
O 1
L 1
E 1 1 2 2 2 2 2 2 2 22
H 11 1 1 1 1 1 1 1 1 1
H T E O L F E O L E H

ну и т. д.

Sha (2010-05-11 19:21:00) [113]
Что ты заполнять собирашься?
Почему ты считаешь, что уже заполненной матрицы Mat недостаточно для вычисления палиндрома?

Родион (2010-05-11 18:42:00) [114]
надо заполнить его же сначала потом делать обход, а то вы сразу убрали все что не надо и норм)))) вобщем чтоб его заполнить я тут кинул пару набросков, посмотрите

for i:=1 n do
for j:=1 n do begin
A[i,j]:=Max(A[i-1,j],A[i,j-1]);
if S[i]=S[j] then A[i,j]:=Max(A[i,j],A[i-1,j-1]+1);

Sha (2010-05-11 17:47:00) [115]
> там ведь другое будет

Да, там будут еще дины других палиндромов.
xayam специально для тебя обнулил ненужные элементы матрицы, которые ты пропустить должен.
Можно было и не обнулять, ты их и так пропустишь, когда палиндром будешь воостанавливать.

xayam (2010-05-11 17:46:00) [116]
соответственно в [146] организован цикл от центра матрицы до верхнего правого угла при этом в каждой очередной четверке примыкающих ячейках ищется максимум и проходятся по цепочке, выделенной жирной здесь:
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

xayam (2010-05-11 17:40:00) [117]

> Родион (11.05.10 17:30) [161]
> я вот это заполнение понять не могу.

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
Блин объясняли же, 7 - семисимвольный палендром, 5 - пятисимвольный вложенный в семь, 3 - вложен в пять, 1 - вложен в 3.
Итого палендром: 7531357. Все возможные комбинации различных троек и единиц показаны жирным.

Родион (2010-05-11 17:30:00) [118]
а разница? ну для кого как привычнее))

я вот это заполнение понять не могу.
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

там ведь другое будет

Sha (2010-05-11 17:24:00) [119]
правильно, только нижнюю напись лучше поверху пустить

Родион (2010-05-11 17:13:00) [120]
в смысле слева направо а не нпоборот

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

Наверх

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