Мастера 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 12:45:00) [61]
как она строится понял, ибо не написал бы [208])

Sha (2010-05-12 12:43:00) [62]
НЕТ пока ни о каком обходе. ЗАБУДЬ.

Процесс нахождения НОП двухэтапный.
На первом этапе мы строим вспомогательную матрицу.
Как она строится и каков физический смысл ее элементов ты понял?

Родион (2010-05-12 12:31:00) [63]
я вот тут немножно запутался. сначала надо найти НОП а потом обходить матрицу.

обойти матрицу это и значит этот самый спуск?

Sha (2010-05-12 12:01:00) [64]
Забудь про спуск. Он тебе пока не нужен.

Просто пойми, что вычисляет LCS

Родион (2010-05-12 11:54:00) [65]
перечетал раз 10 и завис.. разве после формирования матрицы нельзя ли сразу начать спуск.. если без наиб большей последовательности ни как, то буду читать пока не пойму :)

Sha (2010-05-12 11:30:00) [66]
Мы до спуска еще не дошли.

ссылку давал уже
http://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность

Как поймешь для чего нужен LCS, пойдем дальше

Родион (2010-05-12 11:24:00) [67]
постой постой, не торопись) алгоритм LCS это и есть тот самый спуск с "7"?

Sha (2010-05-12 11:13:00) [68]
Отлично. Идем дальше.
Используем алгоритм LCS для поиска палиндромов в строке HTEOLFEOLEH.
Данный алгоритм предназначен для поиска общих подпоследовательностей в 2 произвольных строках.
С какими двумя строками ты предполагаешь работать?

Родион (2010-05-12 11:04:00) [69]

> С какой матрицей ты собираешься работать?

с [208] ))

Родион (2010-05-12 11:02:00) [70]
и вот как я понял щас с цифры 7 надо спускаться по закрашенным клеткам и тем самым записывать их. вот только как спускаться я фиг знает.

Родион (2010-05-12 11:00:00) [71]
построил для HTEOLFEOLEH

1) H
2) T
3) E
4) O
5) L
6) F
7) E
8) O
9) L
10) E
11) H

1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11)
1) 1 2 2 3 4 4 5 5 5 6 7
2) 1 2 2 3 4 4 5 5 5 6 6
3) 1 1 2 3 4 4 5 5 5 6 6
4) 1 1 2 3 4 4 4 5 5 5 5
5) 1 1 2 3 4 4 4 4 5 5 5
6) 1 1 2 3 3 4 4 4 4 5 5
7) 1 1 2 3 3 3 4 4 4 5 5
8) 1 1 2 3 3 3 3 4 3 3 3
9) 1 1 2 2 3 3 3 3 3 3 3
10) 1 1 2 2 2 2 2 2 2 2 2
11) 1 1 1 1 1 1 1 1 1 1 1

Sha (2010-05-12 10:29:00) [72]
Вторая построена стандартным алгоритмом LCS

Sha (2010-05-12 10:22:00) [73]
Давай сначала определимся с алгоритмом.
Ты привел разные матрицы, построенные по разнымалгоритмам.

Первая построена самописным (но от этого он не становится плохим) алгоритмом, который заполняет матрицу длинами всевозможных палиндромов-подпоследовательностейдля строк s[i..j] При этом заполнена только верхняя часть матрицы, т.к. i<=j

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

С какой матрицей ты собираешься работать?

Родион (2010-05-12 09:46:00) [74]
ладно, мне надо реализовать алгоритм который вы уже сто тыщ раз мне писали про заполнение
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

я все понимаю что по диагонали буквы совподут по любому, и нет смысла полностю заполнять ее, просто после этого всего бахнуть writeln( IntToStr( 2*length( r ) - 1 ) ) и будет норм. но к как бы мне этого не хотелось, от меня требуется заполнить его как обьясняют в своей книжке эти 2 биолога
Ц 123345567
Т 122345567
Г 122344566
Г 122344555
А 112344444
Т 112334444
А 112333333
Ц 012222222
Г 011111111
АГЦААТГГТ
пример не очень хороший, ибо слова разные. но смысл тот же. щас если получиться попробую написать на HTEOLFEOLEH

Sha (2010-05-12 09:30:00) [75]
Скажи, что не получается, задай вопрос - и тебе ответят.

"Напишите за меня все, так чтобы препод был доволен" - сам понимаешь, это не вопрос, это задание. Неудивительно, что желающих исполнять твои задания не так много.

Родион (2010-05-12 08:27:00) [76]

> Все это заставляет меня думать, что тебе это не надо. Ну,
> а мне тем более.

было бы не надо не сидел бы целыми днями в делфи и на форумах. не ужели так сложно написать эти 15 не дописанных строчек, а я потом бы с кодом и поработал, вместо этого критика на тематику какой же я @@@. ну если б я смог бы сам регшить задачу, я бы не писал на форум за помощью в реализации кода

Sha (2010-05-11 23:40:00) [77]
До сих пор ты не задал ни одного вопроса по существу якобы интересующего тебя алгоритма LCS и деталям его реализации в твоем случае. Более того, не ответил на вопрос [194], когда тебя спросили, что в описании деталей тебе не ясно. Более того, не написал сам ни строчки кода. Все это заставляет меня думать, что тебе это не надо. Ну, а мне тем более.

Sha (2010-05-11 23:32:00) [78]
Училку спроси.

Родион (2010-05-11 23:27:00) [79]
[188]?? и куда это вставлять?)

Sha (2010-05-11 23:16:00) [80]
Чем тебя не устраивает реализация LCS из твоего pdf-файла,
которую ты сюда копипастил?

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

Наверх

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