Мастера 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.

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

Sha (2010-05-12 17:42:00) [21]
Ты сам его выбрал, если ты помнишь 2 биолога = LCS

Родион (2010-05-12 17:39:00) [22]

> то теперь давай подумаем, какое отношение имеет агоритм
> LCS к твоей задаче.

вот именно что?)) я это и пытаюсь спросить уже фиг знает скколько) по мне дак это просто другой способо решить задачу, не?

Родион (2010-05-12 17:37:00) [23]
я по анологии делал
| 0 1 2 3 4 5 6 7
| M Z J A W X U
-----|-----------------
0 | 0 0 0 0 0 0 0 0
1 X | 0 0 0 0 0 0 1 1
2 M | 0 1 1 1 1 1 1 1
3 J | 0 1 1 2 2 2 2 2
4 Y | 0 1 1 2 2 2 2 2
5 A | 0 1 1 2 3 3 3 3
6 U | 0 1 1 2 3 3 3 4
7 Z | 0 1 2 2 3 3 3 4

тут повотрных букв нету поэтому сбился чуть

Sha (2010-05-12 17:30:00) [24]
АБАБА

Родион (2010-05-12 17:23:00) [25]
НОП=БА

Sha (2010-05-12 16:56:00) [26]
> Плохиш © (12.05.10 16:43) [251]
> Почему ты такой злой, что тебе егойная училка сделала?

:)

Не научила чувака слушать и думать.

Sha (2010-05-12 16:53:00) [27]
Ну если ты понял, как восстановить НОП для двух произвольных строк, то теперь давай подумаем, какое отношение имеет агоритм LCS к твоей задаче.

Возьмем, например, в качестве
s1[1..7]=АБВАБАГ, а в качестве s2 - перевернутую строку s1:
s2[1..7]=ГАБАВБА

Есть какие-нибудь соображения?

Плохиш (2010-05-12 16:43:00) [28]

> Sha

Почему ты такой злой, что тебе егойная училка сделала?

Родион (2010-05-12 16:38:00) [29]
я бы рад чтоб ты обьяснил мне, потому что я не понимаю почему ее нельзя так решить. Но времени у меня нету вобще!!! одна надежда на тебя, так что давай дальше...

Sha (2010-05-12 16:28:00) [30]
Нельзя ее так решить. Могу пример привести.
Только время оба потратим. Ты этого хочешь?

Родион (2010-05-12 16:26:00) [31]
ладно, но ты же понял что я имел в виду, можно же так ее решить? мы МОП даже не проходили.. надо решить как она хочет(

Sha (2010-05-12 16:21:00) [32]
> Родион (12.05.10 16:13) [245]
> да блин, я вобще понять не могу зачем нужен НОП?

Это пока не требуется.
Твоя задача понять как восстанавливается НОП по матрице на втором этапе алгоритма.

> вот смотри я заполню матрицу...

Если можешь написать алгоритм сам - пиши.
Если хочешь, чтоб научили, как написать, слушай, что говорят, иначе не получится.

Омлет (2010-05-12 16:15:00) [33]
> Sha ©

Мне бы столько терпения ))

Родион (2010-05-12 16:13:00) [34]
да блин, я вобще понять не могу зачем нужен НОП? вот смотри я заполню матрицу по алогоритму нудельмана вунша а потом [243] мне и препод так сказал

Sha (2010-05-12 16:09:00) [35]
Не беги впереди паровоза.
Пока нигде не видно палиндромов.
С чего ты взял, что подпоследовательность будет палиндромом?
У строк АБВ и АБВГД НОП=АБВ - это что палиндром?
ЗАБУДЬ ПРО ПАЛИНДРОМЫ

Твоя задача понять как восстанавливается НОП по матрице на втором этапе алгоритма.
Если что неясно, сходи еще раз по ссылке, пока не наступит просветление.
Когда наступит, сообщи.

Родион (2010-05-12 16:00:00) [36]
подпоследовательность формируется при обратном просмотре заполненной таблицы от клетки, помеченной максимальным значением. путь с 7-ерки это клетки с метками, отличающимися на единицу, буквы записываются из закрашенных клеток. последовательность этих букв ответ задачи так?

Sha (2010-05-12 15:39:00) [37]
которая содержала общий символ =
которая соответсвует общему символу обеих подстрок

Sha (2010-05-12 15:35:00) [38]
На втором этапе работы алгоритма LCS происходит восстановление НОП по матрице, построенной на первом этапе.
Все достаточно просто.
Понятно, что длина НОП для двух полных строк сидит в угловой ячейке.
Мы начинаем прыгать в соседние ячейки и смотреть как меняется длина.
Причем прыгаем всегда в ту соседнюю ячейку, которая использовалась при вычислении длины, помещенной в текущую ячейку.
Если при таком прыжке длина уменьшилась, значит мы прыгнули из ячейки, которая содержала общий символ. Запоминаем его. Так мы восстановим всю НОП.

Родион (2010-05-12 15:14:00) [39]
что дальше?

Sha (2010-05-12 14:54:00) [40]
s1[1..6]=aomtag
s2[1..6]=atmojr
НОП=at или ao или am, что больше нравится
tmo нельзя получить вычеркиванием (обсуждалось раньше), значит это не НОП

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

Наверх

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