Мастера 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 23:11:00) [81]
Родион (11.05.10 22:46) [195]

А ты ссылку на форум преподавателю дай - вот забавно будет

Родион (2010-05-11 23:09:00) [82]
знаю что всех уже окончательно достал. но если для тебя это не сложно. можешь все таки выложить реализацию

Sha (2010-05-11 22:51:00) [83]
Я тебе втечение 10-ти постов талдычу, что LCS = два биолога
Биологи подходят, а LCS нет?
Ты здоров?

Родион (2010-05-11 22:46:00) [84]
дык в этом то и проблема, что LCS она не принемает, сегодня она мне сказала что этим методом нельзя. решай этим алгоритмом и показала мне. мож кинуть хоть начала кода хоть что нить из него

Sha (2010-05-11 22:30:00) [85]
> Родион (11.05.10 22:21) [193]
> почему бы не помочь реализовать алгоритмом НВ?

Во-первых, ты сам попросил исправить другой алгоритм.

Во-вторых, тебе уже разжевали решение при помощи LCS, только ты этого не заметил.
И не вспоминай этих биологов.
Прочти [24] [25] [140] [141]
Что непонятно?

Родион (2010-05-11 22:21:00) [86]
почему бы не помочь реализовать алгоритмом НВ? я все время к этому алгоритму и клонил. а щас...

Sha (2010-05-11 22:09:00) [87]
Хочешь LCS - реализуй на здоровье по своей pdf-методичке.
Какая у тебя будет проблема и как ее побороть, я написал в [140].

Родион (2010-05-11 22:02:00) [88]
пока отвечал на [177] не заметил что ты писал, что вспомнил

Sha (2010-05-11 22:00:00) [89]
Нафиг ты это сюда постишь?

Родион (2010-05-11 21:58:00) [90]

> Да знаю я его :)Только весь мир называет его LCS.А эти два
> биолога вроде первыми среди биологов додумались применить
> его в биологии.А если я первым применю его в сантехнике,
> этот будет мой алгоритм?
ахаххахахаха :DDDDDDDD

Родион (2010-05-11 21:57:00) [91]
фрагмент основной логики:

for i:=1 to leghth(S1) do
for j:=1 to leghth(S2) do begin
A[i,j]:= Max(A[i-1,j], A[i,j-1]);
if S1[i]=S2[j] then A[i,j]:=max (A[i,j], A[i-1,j-1]+1);
end;
writeln('ответ: ',A[leghth(S1),leghth(S2)] );

Sha (2010-05-11 21:56:00) [92]
> Родион (11.05.10 21:51) [186]
> алгоритм нудельмана вунша.

Да знаю я его :)
Только весь мир называет его LCS.
А эти два биолога вроде первыми среди биологов додумались применить его в биологии.
А если я первым применю его в сантехнике, этот будет мой алгоритм?

Родион (2010-05-11 21:51:00) [93]
алгоритм нудельмана вунша.
пусть есть слова ГЦАТАГГТЦ и АГЦААТГГТ.
схема решения иллюстрируется на [182]. там закрашены клетки, находящиеся
на пересечении строки и столбца с одинаковыми буквами. принцип заполнения таблицы W следущий: элемент W[i,j] равен наибольшему из чисел W[i-1,j], W[i,j-1], а если клетка <i,j> закрашена, то и W[i-1,j-1]+1. Формирование первой строки и первого столбца выполняется до заполнения таблицы и осуществляется так: единицей отмечается первое совпадение, затем эта единица автоматически заностся во все оставшиеся клетки. например, W[3,l]-первое совпадение в столбце , затем эта единица идет по первому столбцу. Подпоследовательность формируется при обратном просмотре заполненной таблицы от клетки, помеченной максимальный значением. Путь - это клетки с метками, отличающимися на единицу, буквы выписываются из закрашенных клеток. последовательность этих букв - ответ задачи. для примера 2 последовательности: ГЦААГТ и ГЦАТГГТ

Sha (2010-05-11 21:45:00) [94]
> Родион (11.05.10 21:34) [182]

я же сказал: переворачивать свои мозги не собираюсь

Sha (2010-05-11 21:43:00) [95]
Пропустил
помнят только =
помнят только у нас

Sha (2010-05-11 21:41:00) [96]
Этих двух товарищей почему-то помнят только, как будто им принадлежит авторство алгоритма LCS. Если не ошибаюсь, то ли они занимались каким-то частным случаем, то ли сейчас есть лучшие результаты, в общем в англоязычной литературе упоминание о них ты вряд ли отыщешь.
Использовать этот алгоритм LCS тебе еще MBo предложил в [1].
Реализация будет сложнее. Ответ тот же. Нафиг надо.

Оба решения используют динамическое программирование.
Ограничений на выбор алгоритма в условии нет.

Родион (2010-05-11 21:34:00) [97]
Ц 12 3345567
Т 12234 556 7
Г 1 22344 5 66
Г 1 22344 555
А 112 344444
Т 11233 444 4
А 112 333333
Ц 01 2222222
Г 0 11111 111
АГЦААТГГТ

Родион (2010-05-11 21:23:00) [98]
вот именно что надо решить задачу этим самым алгоритмом.. по мне лучше выучить [175] но нужен тот самый алгоритм нудельмана вунша

Sha (2010-05-11 21:16:00) [99]
Не морочь голову. Не нужен тебе этот принцип, и училке твоей не нужен.
Ты тратишь время на фигню, вместо того чтоб решать задачу.

> вот только там еще нужно показывать как в матрице это все заполняется

Ну, словами расскажешь. Выучи [175] наизусть. Серьезно.
Но имей ввиду, что рекурсивные по сути вычисления FillPalMatrix выполняет в цикле.
Не дай себя сбить с толку.

> если ты не против я бы тебе передал pdf файлик

я сам кому хошь могу передать pdf-файлик

Родион (2010-05-11 21:13:00) [100]
Александр, через файлобменник будет долго, пока загрузит еще.. 420978344 icq, давай кину через аську

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

Наверх

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