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

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

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

← →
Sha © (2010-05-11 23:32) [201]

Училку спроси.

← →
Sha © (2010-05-11 23:40) [202]

До сих пор ты не задал ни одного вопроса по существу якобы интересующего тебя алгоритма LCS и деталям его реализации в твоем случае. Более того, не ответил на вопрос [194], когда тебя спросили, что в описании деталей тебе не ясно. Более того, не написал сам ни строчки кода. Все это заставляет меня думать, что тебе это не надо. Ну, а мне тем более.

← →
Родион (2010-05-12 08:27) [203]

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

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

← →
Sha © (2010-05-12 09:30) [204]

Скажи, что не получается, задай вопрос - и тебе ответят.

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

← →
Родион (2010-05-12 09:46) [205]

ладно, мне надо реализовать алгоритм который вы уже сто тыщ раз мне писали про заполнение
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 10:22) [206]

Давай сначала определимся с алгоритмом.
Ты привел разные матрицы, построенные по разным алгоритмам.

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

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

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

← →
Sha © (2010-05-12 10:29) [207]

Вторая построена стандартным алгоритмом LCS

← →
Родион (2010-05-12 11:00) [208]

построил для 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

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

и вот как я понял щас с цифры 7 надо спускаться по закрашенным клеткам и тем самым записывать их. вот только как спускаться я фиг знает.

← →
Родион (2010-05-12 11:04) [210]

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

с [208] ))

← →
Sha © (2010-05-12 11:13) [211]

Отлично. Идем дальше.
Используем алгоритм LCS для поиска палиндромов в строке HTEOLFEOLEH.
Данный алгоритм предназначен для поиска общих подпоследовательностей в 2 произвольных строках.
С какими двумя строками ты предполагаешь работать?

← →
Родион (2010-05-12 11:24) [212]

постой постой, не торопись) алгоритм LCS это и есть тот самый спуск с "7"?

← →
Sha © (2010-05-12 11:30) [213]

Мы до спуска еще не дошли.

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

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

← →
Родион (2010-05-12 11:54) [214]

перечетал раз 10 и завис.. разве после формирования матрицы нельзя ли сразу начать спуск.. если без наиб большей последовательности ни как, то буду читать пока не пойму :)

← →
Sha © (2010-05-12 12:01) [215]

Забудь про спуск. Он тебе пока не нужен.

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

← →
Родион (2010-05-12 12:31) [216]

я вот тут немножно запутался. сначала надо найти НОП а потом обходить матрицу.

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

← →
Sha © (2010-05-12 12:43) [217]

НЕТ пока ни о каком обходе. ЗАБУДЬ.

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

← →
Родион (2010-05-12 12:45) [218]

как она строится понял, ибо не написал бы [208])

← →
Sha © (2010-05-12 12:51) [219]

А что она содержит понял?

← →
Родион (2010-05-12 12:51) [220]

какой 2ой этап?

← →
Sha © (2010-05-12 12:55) [221]

Не перейдем ко 2му этапу пока не будет полной ясности с первым.
Ответь на [219]

← →
Родион (2010-05-12 12:59) [222]

числа которые появились после заполнения матрицы

← →
Sha © (2010-05-12 13:02) [223]

Надо же, а я думал она содержит числа которые появились после заполнения матрицы

Каков их физический смысл? Что это такое?
Количество колес у твоего мерседеса или яиц у Билла Гейтса?

← →
Родион (2010-05-12 13:10) [224]

самое большое число в матрице - это максимальное количество букв в палиндроме максимальной длинны. в данном случае 7

← →
Sha © (2010-05-12 13:16) [225]

НЕТ У НАС НИКАКИХ ПАЛИНДРОМОВ.
Мы разбираем работу алгоритма LCS, который ты должен был выучить за семестр.

На вопросы отвечать будем?
Каков физический смысл элементов матрицы, сформированной алгоритмом LCS?

← →
Родион (2010-05-12 13:32) [226]

надо найти наиб подпоследовательности

← →
Sha © (2010-05-12 13:36) [227]

> Родион (12.05.10 13:32) [226]
> надо найти наиб подпоследовательности

я знаю.

На вопросы отвечать будем?
Каков физический смысл элементов матрицы, сформированной алгоритмом LCS?

← →
Родион (2010-05-12 13:40) [228]

дык, я врубится не могу полносью еще, для чего нужен НОП.. вот и прошу обьяснить примерно

А не надо врубаться раньше времени.

На вопросы отвечать будем?
Каков физический смысл элементов матрицы, сформированной алгоритмом LCS?

← →
Родион (2010-05-12 13:54) [230]

не знаю. может ты мне скажешь? ((

← →
Родион (2010-05-12 14:02) [231]

я запутался.. мы формируем матрицу потом заполняем ее 1..7, потом идет НОП (если она обязательна, то что она делает?) почему нельзя после заполнения матрицы сразу приступить к нахождению палиндрома?

И нафига юлил столько времени? Еще раз так сделаешь, разговор будет окончен.

Пусть у нас есть строки s1[1..n1] и s2[1..n2].
Тогда после работы первой стадии алгоритма LCS элемент M[i,j] матрицы будет содержать длину наибольшей общей подпоследовательности строк s1[1..i] и s2[1..j].
Выучить наизусть.

← →
Родион (2010-05-12 14:10) [233]

> Пусть у нас есть строки s1[1..n1] и s2[1..n2].

2 идущих рядом строки?

> 2 идущих рядом строки?

Не обязательно. Одна может быть у тебя, другая у меня :)

← →
Родион (2010-05-12 14:17) [235]

можно на примере в матрице?

В примере по ссылке
s1[1..4]=ABCB
s2[1..4]=DCBA

M[34]=2, т.к. s1[1..4]=ABCB, s2[1..3]=DCB, НОП=CB

← →
Родион (2010-05-12 14:46) [237]

то есть если я возьму s1[1..6] amotag и s2[1..6] atmojr то НОП=tmo ? я правильно понял?)

← →
Родион (2010-05-12 14:48) [238]

поправочка s1[1..6]=aomtag

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

← →
Родион (2010-05-12 15:14) [240]

что дальше?

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