Динамическое програмирование. Подпалендром.

← →
Sha © (2010-05-11 17:24) [160]

правильно, только нижнюю напись лучше поверху пустить

← →
Родион (2010-05-11 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

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

← →
xayam © (2010-05-11 17:40) [162]

> Родион (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. Все возможные комбинации различных троек и единиц показаны жирным.

← →
xayam © (2010-05-11 17:46) [163]

соответственно в [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

← →
Sha © (2010-05-11 17:47) [164]

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

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

← →
Родион (2010-05-11 18:42) [165]

надо заполнить его же сначала потом делать обход, а то вы сразу убрали все что не надо и норм)))) вобщем чтоб его заполнить я тут кинул пару набросков, посмотрите

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 19:21) [166]

Что ты заполнять собирашься?
Почему ты считаешь, что уже заполненной матрицы Mat недостаточно для вычисления палиндрома?

← →
Родион (2010-05-11 19:34) [167]

где в коде написанно что она уже заполнена. я имею в виду

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 2 2
H 1 1 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:47) [168]

> Родион (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:51) [169]

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

выложи)

← →
Sha © (2010-05-11 19:55) [170]

В настоящее время у меня, как и у тебя похоже, есть дела поважнее и поинтереснее,
удаление отладочного кода из исходников стоит в очереди на 17 месте.

← →
Sha © (2010-05-11 19:56) [171]

На [166] ответь

← →
Родион (2010-05-11 20:03) [172]

я так не считаю, препод требует. чтоб он убедился что я понял как заполнять матрицу.

← →
Sha © (2010-05-11 20:07) [173]

Т.е. алгоритм работы FillPalMatrix тебе непонятен,
а бредовая функция, приведенная в начале ветки, тебе понятна?

← →
Родион (2010-05-11 20:16) [174]

я так не сказал. то есть 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:41) [175]

> 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:57) [176]

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

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

← →
Sha © (2010-05-11 21:00) [177]

Если не затруднит, сформулируй его :)
Я думаю, что даже те теоретики, кто интенсивно работает над строковыми алгоритмами, вряд ли его сходу вспомнят :)

← →
Родион (2010-05-11 21:06) [178]

я бы с радостью!)))) вот только там еще нужно показывать как в матрице это все заполняется. если ты не против я бы тебе передал pdf файлик где тот самый
алгоритм рассматривается =)

← →
Родион (2010-05-11 21:13) [179]

Александр, через файлобменник будет долго, пока загрузит еще.. 420978344 icq, давай кину через аську

← →
Sha © (2010-05-11 21:16) [180]

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

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

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

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

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

← →
Родион (2010-05-11 21:23) [181]

вот именно что надо решить задачу этим самым алгоритмом.. по мне лучше выучить [175] но нужен тот самый алгоритм нудельмана вунша

← →
Родион (2010-05-11 21:34) [182]

Ц 123345567
Т 122345567
Г 122344566
Г 122344555
А 112344444
Т 112334444
А 112333333
Ц 012222222
Г 011111111
АГЦААТГГТ

← →
Sha © (2010-05-11 21:41) [183]

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

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

← →
Sha © (2010-05-11 21:43) [184]

Пропустил
помнят только =
помнят только у нас

← →
Sha © (2010-05-11 21:45) [185]

> Родион (11.05.10 21:34) [182]

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

← →
Родион (2010-05-11 21:51) [186]

алгоритм нудельмана вунша.
пусть есть слова ГЦАТАГГТЦ и АГЦААТГГТ.
схема решения иллюстрируется на [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:56) [187]

> Родион (11.05.10 21:51) [186]
> алгоритм нудельмана вунша.

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

← →
Родион (2010-05-11 21:57) [188]

фрагмент основной логики:

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)] );

← →
Родион (2010-05-11 21:58) [189]

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

Нафиг ты это сюда постишь?

← →
Родион (2010-05-11 22:02) [191]

пока отвечал на [177] не заметил что ты писал, что вспомнил

Хочешь LCS - реализуй на здоровье по своей pdf-методичке.
Какая у тебя будет проблема и как ее побороть, я написал в [140].

← →
Родион (2010-05-11 22:21) [193]

почему бы не помочь реализовать алгоритмом НВ? я все время к этому алгоритму и клонил. а щас...

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

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

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

← →
Родион (2010-05-11 22:46) [195]

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

Я тебе втечение 10-ти постов талдычу, что LCS = два биолога
Биологи подходят, а LCS нет?
Ты здоров?

← →
Родион (2010-05-11 23:09) [197]

знаю что всех уже окончательно достал. но если для тебя это не сложно. можешь все таки выложить реализацию

Родион (11.05.10 22:46) [195]

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

Чем тебя не устраивает реализация LCS из твоего pdf-файла,
которую ты сюда копипастил?

← →
Родион (2010-05-11 23:27) [200]

[188]?? и куда это вставлять?)

Динамическое програмирование. Подпалендром. Найти похожие ветки