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

← →
rodion (2010-05-07 07:30) [0]

Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, 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.

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

← →
MBo © (2010-05-07 07:56) [1]

мпожно перевернуть строку и искать общую подпоследовательность максимальной длины с перехлестом не более, чем на один символ

← →
xayam © (2010-05-07 08:21) [2]

не обязательно идущих подряд? это больше анаграмма, чем полиндром. И это... код можно прокомментировать

← →
12 © (2010-05-07 08:26) [3]

> try
> { TODO -oUser -cConsole Main : Insert code here }
> except
> on E:Exception do
> Writeln(E.Classname, ": ", E.Message);
> end;

сильно

← →
Игорь Шевченко © (2010-05-07 10:25) [4]

> try
> { TODO -oUser -cConsole Main : Insert code here }
> except
> on E:Exception do
> Writeln(E.Classname, ": ", E.Message);
> end;

ты откуда код списал, дубинушко ? Я бы только за это выгнал бы с треском

← →
rodion (2010-05-07 11:01) [5]

это можно удалить, это автоматом написалось...

вобщем люди, щас только с зачета, завалил..
препод сказал, что функцию ваще как бэ не нужна ибо там есть рекурсия
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
надо ее засунуть когда уже будет сформирован массив, вобщем что то в этом духе...а потом я, как сказал Игорь Шевченко, вылетел с треском..
народ помогите кто чем может, 17 мая меня отчисляют если не сдам(
такие дела..

← →
Плохиш © (2010-05-07 11:09) [6]

> народ помогите кто чем может, 17 мая меня отчисляют если
> не сдам

в 17 мая переместить?

← →
12 © (2010-05-07 11:12) [7]

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

Вообщем, ща Ега придет и скажет чего делать :)

← →
Плохиш © (2010-05-07 11:15) [8]

> Вообщем, ща Ега придет и скажет чего делать

А, вот кто по пятницам подаёт :-))

PS. Что-то давно не видно всяких защитников немощных и обездоленных...

← →
12 © (2010-05-07 11:26) [9]

не, Ега сайт призывник ру знает как точно пишется :)

← →
12 © (2010-05-07 11:29) [10]

автору. Пока примерно так не будет - вряд ли чего дождешься.

// назначение: выбить из матрицы элементы по принципу левой ноги в кастрюле 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; // Function

← →
Rouse_ © (2010-05-07 11:40) [11]

Если придет Ега до 18 нуль-нуль, то будем карать... Не отвлекайте человека - ему код писать нужно :)

← →
Rouse_ © (2010-05-07 11:43) [12]

зы: резюме местного it отдела - "код уныл" :)

← →
rodion (2010-05-07 13:13) [13]

> народ помогите кто чем может, 17 мая меня отчисляют если
> не сдам

в 17 мая переместить?

17 отчислят если не сдам во вторник крайний срок..

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

← →
Palladin © (2010-05-07 13:17) [14]

ну не нужны стране такие космонавты

← →
Sha © (2010-05-07 13:19) [15]

> с января парюсь надо этой задачой

Значит наибольшую общую подпоследоватьность двух последоватьностей
без всякой палиндромности находить уже умеешь?

Имеешь отформатированный отлаженный код для стандартной задачи?

← →
Anatoly Podgoretsky © (2010-05-07 13:33) [16]

> rodion (07.05.2010 11:01:05) [5]

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

← →
Б (2010-05-07 13:42) [17]

За деньгу в сети всегда решат.

← →
rodion (2010-05-07 16:50) [18]

-
> Имеешь отформатированный отлаженный код для стандартной
> задачи?

я в задаче разобрался, проблема в том что реализовать не могу, вот и прошу помощи у вас. поможете или нет?(

← →
antonn © (2010-05-07 16:51) [19]

> Palladin © (07.05.10 13:17) [14]
>
> ну не нужны стране такие космонавты

а солдаты такие нужны?

← →
Leonid Troyanovsky © (2010-05-07 17:28) [20]

> antonn © (07.05.10 16:51) [19]

> а солдаты такие нужны?

Солдаты всякие Родине пригодятся.
Кто программу сварганит, кто борщ сварит, кто споет -
главное чтоб для общей цели.

offtop
А чего, оный Подпалендром - это, дейс-но, динамческое
программирование, бо мы, как-то, учили, что это Беллман и др.?

Или я опять от жизни отстал :( ?
end offtop

--
Regards, LVT.

← →
Smile (2010-05-07 17:38) [21]

По поводу Бэллмана ...
А у меня (я больше прикладник) это Дженкинс и Бокс
:)

← →
Leonid Troyanovsky © (2010-05-07 17:55) [22]

> Smile (07.05.10 17:38) [21]

> А у меня (я больше прикладник) это Дженкинс и Бокс

Не запутывай нас, оные из планирования эксперимента, IMHO,
вроде крутового восхождения.

--
Regards, LVT.

← →
Smile (2010-05-07 18:02) [23]

> Leonid Troyanovsky © (07.05.10 17:55) [22]

Это было так давно, что возможно и ошибся:(
"Беллман Р., Энджел Э. Динамическое программирование и уравнения в частных производных", гораздо ближе ...
:)

← →
Sha © (2010-05-07 18:52) [24]

> rodion (07.05.10 16:50) [18]
> я в задаче разобрался,

Ну, если в задаче разобрался, то должен понимать, что она родственна задаче
поиска максимальной подпоследовательности (LCS) двух последовательностей.

Раз мучаешься с января, то наверняка гуглил неоднократно и ссылка
http://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность
тебе знакома.

> проблема в том что реализовать не могу,

Наверняка там или еще где скачал, понял и отладил готовую реализацию

> вот и прошу помощи у вас. поможете или нет?(

Конечно, поможем. Советом.
Заметь, что твоя задача решается с помощью того же алгоритма.
Пусть длина твоей строки равна L. Тебе надо найти максимальную LCS
для L всевозможных пар строк, образованных началом длины Y=1..L
и хвостом длины X=L+1-N. Все такиe LCS лежат на неглавной диагонали матрицы.
Т.е. тебе даже не надо строить всю мартицу для исходной и перевернутой строки.
А дальше, как обычно, из найденного максимального элемента
восстанавливаешь общую подпоследовательность. Это начало палиндрома.
Хвост попробуй найти сам.
Рассмотри случаи четной и нечетной длины палиндрома.

← →
Sha © (2010-05-07 18:59) [25]

Опечатка, надо так
и хвостом длины X=L+1-Y.

← →
Германн © (2010-05-08 02:38) [26]

> ты откуда код списал, дубинушко

Причем даже не выучил/заметил как пишется термин Палиндром
В стройбат однозначно!

← →
rodion (2010-05-08 11:56) [27]

Sha, спс что помогаешь, но блин это с++(я про ссылку). надо разбираться сидеть, а времени разбираться нету(((

> Германн © (08.05.10 02:38) [26]
> > ты откуда код списал, дубинушкоПричем даже не выучил/заметил
> как пишется термин ПалиндромВ стройбат однозначно!

может хватит критики не по делу? и так не по себе

← →
Sha © (2010-05-08 12:26) [28]

тут на псевдокоде, почти паскаль

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

← →
Плохиш © (2010-05-08 15:53) [29]

> Sha © (08.05.10 12:26) [28]

Ты не умничай, ты код для копи-пасте давай, а то

> надо разбираться сидеть, а времени разбираться нету(((

> и так не по себе

← →
Игорь Шевченко © (2010-05-09 01:15) [30]

> надо разбираться сидеть, а времени разбираться нету(((

это разве наши проблемы ?

← →
Германн © (2010-05-09 01:21) [31]

> это разве наши проблемы ?

Отчасти это твоя проблема, Игорь. И также других модераторов. Сколько ещё веток на одну и ту же тему заведёт автор за оставшиеся 8 дней?
:)

← →
xayam © (2010-05-10 11:13) [32]

> Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH.
> Напишите программу, находящую в данной строке подпалиндром
> максимальной длины.

может я не прав, но это же не максимальный подпалендром, еще две буквы "О" есть. Не? Я по-своему решил, вроде работает, но нужно на разных строках потестировать:
program MaxPolendrom; {$APPTYPE CONSOLE} uses SysUtils; var s: string; i, j, k, n, b, c: integer; rs: set of 1..100; l, r: array[1..100] of integer; flag: boolean; begin readln(s); for i:= 1 to 100 do begin l[i]:= 0; r[i]:= 0; end; n:= length(s); i:= 1; j:= 2; k:= 0; rs:= []; flag:= false; while true do begin if s[i] = s[j] then begin k:= k + 1; l[k]:= i; r[k]:= j; rs:= rs + [j] {+ [i]}; end; if flag or ( s[i] = s[j] ) then begin i:= i + 1; b:= i; while i in rs do i:= i + 1; if ( i >= n ) or ( ( i = b ) and ( i in rs ) ) then break; flag:= false; j:= i; end; j:= j + 1; b:= j; while j in rs do j:= j + 1; if ( j >= n + 1 ) or ( ( j = b ) and ( j in rs ) ) then flag:= true; end; for i:= 1 to k do write( " left [k]: " + IntToStr( l[i] ) + " " ); writeln; for i:= 1 to k do write( " right[k]: " + IntToStr( r[i] ) + " " ); writeln; c:= 0; for i:= 1 to n do begin flag:= true; for j:= 1 to k do if ( l[j] = i ) or ( r[j] = i ) then flag:= false; if flag then begin c:= i; break; end; end; if c > 0 then writeln( IntToStr( 2*k + 1 ) ) else writeln( IntToStr( 2*k ) ); for i:= 1 to k do write(s[l[i]]); if c > 0 then write(s[c]); //центральный символ обязателен? for i:= k downto 1 do write(s[r[i]]); readln; end.

← →
xayam © (2010-05-10 11:47) [33]

после readln(s); еще можно вставить проверку на пустую строку, иначе ошибка вылетает:
if s = "" then begin write("0"); readln; exit; end;

← →
xayam © (2010-05-10 12:17) [34]

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

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

← →
KilkennyCat © (2010-05-10 12:31) [35]

> rs: set of 1..100;
> l, r: array[1..100] of integer

в свою очередь вызывает

> for i:= 1 to 100 do begin
> l[i]:= 0;
> r[i]:= 0;
> end;

что некрасиво.

← →
KilkennyCat © (2010-05-10 12:38) [36]

А вообще, решение простое:
MaxPodPalindrom := copy(Palindrom, 2, length(Palindrom)-2);

← →
xayam © (2010-05-10 12:46) [37]

> KilkennyCat © (10.05.10 12:31) [35]
> > rs: set of 1..100;
> > l, r: array[1..100] of integer
> в свою очередь вызывает
> что некрасиво.

ну да это я по привычке обнуляю :)

> MaxPodPalindrom := copy(Palindrom, 2, length(Palindrom)-
> 2);

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

← →
KilkennyCat © (2010-05-10 13:05) [38]

мое решение полностью удовлетворяет поставленному условию.

← →
KilkennyCat © (2010-05-10 13:07) [39]

а, я недогнал, мне что-то покеазалось, что исходная строка - палиндром.
Ну ладно, мое решение для частного случая.

← →
xayam © (2010-05-10 13:09) [40]

в любом случае у меня короче решение:
M:=copy(P,2,length(P)-2)
:)

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

спс xayam , щас буду разбираться в коде. если будут вопросы напишу)

← →
KilkennyCat © (2010-05-10 13:45) [42]

> если будут вопросы

смешно.

← →
xayam © (2010-05-10 13:46) [43]

будут, будут - у препода :)

← →
Sha © (2010-05-10 13:55) [44]

> xayam
> либо я что-то не понимаю, либо динамическое программирование подразумевает использование рекурсии

Динамическое программирование подразумевает сведение большой задачи к нескольким более мелким и вычисление результата большой задачи с использованием результатов более мелких.
Принципиальное отличие от рекурсии в том, что ни одна задача не решается более одного раза, т.к. все результаты решения подзадач, которые могут потребоваться в будущем, запоминаются. Это резко повышает скорость вычислений по сравнению с рекурсией.
Напоминает индукцию в математике.

← →
xayam © (2010-05-10 14:05) [45]

> Sha © (10.05.10 13:55) [44]
> Динамическое программирование подразумевает сведение большой
> задачи к нескольким более мелким и вычисление результата
> большой задачи с использованием результатов более мелких.

Вот же черным по белому написано:
http://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность
Метод динамического программирования Вначале найдём длину наибольшей подпоследовательности. Допустим мы ищем решение для случая (n1, n2), где n1, n2 — длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m1, m2) меньших заданной. Тогда задача (n1, n2) сводится к меньшим подзадачам следующим образом: [ 0, если n1=0 и n2=0 f(n1,n2) = [ f(n1-1, n2-1) +1, если s[n1] = s[n2] [ max( f(n1-1, n2), f(n1, n2-1) ), если s[n1] <> s[n2]
Ты хочешь сказать, что это не рекурсия - f(n1-1, n2-1) ?

← →
xayam © (2010-05-10 14:11) [46]

Или здесь:

http://ru.wikipedia.org/wiki/Динамическое_программирование

Идея динамического программирования ... В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага. 1) Разбиение задачи на подзадачи меньшего размера. 2) Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм. 3) Использование полученного решения подзадач для конструирования решения исходной задачи.

← →
Sha © (2010-05-10 14:26) [47]

> xayam © (10.05.10 14:05) [45]
> Ты хочешь сказать, что это не рекурсия - f(n1-1, n2-1) ?

Я хочу сказать другое.
Здесь функция вызывает себя, значит, имеет место рекурсивный вызов.
Но эта запись приведена всего лишь для облегчения понимания логики работы.
В действительности можно организовать вычисления так, что никакой рекурсии не будет. Например, вычисления факториала.
Метод динамического программирования предназначен для ограничения рекурсии в глубину одним уровнем. Он особенно хорошо работает, когда есть рекурсивная зависимость по нескольким переменным, когда при помощи обычной рекурсии вычислить что-либо просто невозможно, т.к. все время уходит на бесконечные повторы одних и техже вычислений.

Обычно результаты предыдущих вычислений запоминаются в массиве и, например, полубредовая функция, списанная автором из методички
и использующая начальное заполнение
Function F(i, j : Integer) : Integer;
всего лишь вычисляет длину палиндрома в подстроке s[i..j]
и может быть записана без всякой рекурсии, например, так:
procedure FillPalMatrix(const s: string); var i, j, t, count, found: integer; begin; for j:=1 to length(s) do begin; Mat[j,j]:=1; for i:=j-1 downto 1 do begin; count:=Mat[i+1,j]; t:=j; while s[t]<>s[i] do dec(t); found:=t-i+1; if t>=i+2 then found:=Mat[i+1, t-1]+2; if count<found then count:=found; Mat[i,j]:=count; end; end; end;

← →
xayam © (2010-05-10 14:40) [48]

> ...Метод динамического программирования предназначен для ограничения
> рекурсии в глубину одним уровнем...
> ...Но эта запись приведена всего лишь для облегчения понимания
> логики работы...

нет ты уж определись ДЛЯ чего это. А то тут по ходу каша: записываю в виде рекурсии, а решаю как хочу. Что тогда является критерием для определения принадлежности алгоритма к динамическому?

← →
Sha © (2010-05-10 14:45) [49]

> xayam © (10.05.10 14:40) [48]
> А то тут по ходу каша: записываю в виде рекурсии, а решаю как хочу.

Именно.

> Что тогда является критерием для определения принадлежности алгоритма к динамическому?

Принципиальное отличие от рекурсии в том, что ни одна подзадача не решается более одного раза

← →
xayam © (2010-05-10 14:51) [50]

> Sha © (10.05.10 14:45) [49]
> Принципиальное отличие от рекурсии в том, что ни одна подзадача
> не решается более одного раза

[32] соответствует этому требованию? Я бы назвал этот способ не динамическим и не полным перебором, а например перебор с фильтрацией, поскольку за счет использования множества rs отсекаются значения i и j, которые повторяются т.е. как раз "ни одна подзадача не решается более одного раза" Не?

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

алгоритм [32]
на строке HTEOLFEEOLEH
выдает HEOLETELOEH
вместо HELEELEH

← →
xayam © (2010-05-10 15:16) [52]

> Sha © (10.05.10 15:12) [51]
> на строке HTEOLFEEOLEH
> выдает HEOLETELOEH
> вместо HELEELEH

так вроде и задумывалось. Ищется первое нечетное количество определенного символа и этот символ вставляется в центр, в данном случае количество символов T равно 1. Неправильно?

← →
Sha © (2010-05-10 15:21) [53]

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

← →
Sha © (2010-05-10 15:22) [54]

значит порядок символов

← →
xayam © (2010-05-10 15:22) [55]

тем более HEOLETELOEH длиннее HELEELEH на один символ. А задача как раз найти максимальный :)

← →
Sha © (2010-05-10 15:26) [56]

максимальный, удовлетворяющий [53-54]

← →
xayam © (2010-05-10 15:32) [57]

> Sha © (10.05.10 15:21) [53]
> Палиндром образуется вычеркиванием символов из исходной строки

никакого вычеркивания у меня нет, формируются два массива l[k] и r[k], которые соответствуют найденной одинаковой паре символов, отличаются только значения (смещение в строке s)

> значит символов в палиндроме должен соответствовать исходному.

исходной строке? с какого перепугу?

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

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

> значит порядок символов

в условии задачи написано: не обязательно идущих подряд. Т.е. порядок не учитывается.

← →
xayam © (2010-05-10 15:38) [58]

> xayam © (10.05.10 15:22) [55]
> тем более HEOLETELOEH длиннее HELEELEH на один символ
> Sha © (10.05.10 15:12) [51]

опс, даже не на один, а на три. Буквы "О" забыл?

← →
Sha © (2010-05-10 15:48) [59]

> xayam © (10.05.10 15:32) [57]

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

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

От автора требуется найти способ восстановить
подпоследовательность по той же матрице,
если он до сих по не догадался.

← →
xayam © (2010-05-10 15:56) [60]

слушай мы щас вроде не про автора говорим и его заморочки с скопипастенной функцией, у меня ее вообще в алгоритме нет. Даже нет двумерного массива 100х100 и он вроде бы тоже не обязателен в использовании, а только два массива в сумме 2х100 + несколько вспомогательных переменных, так что в памяти явно выигрывается [32], и в скорости по-моему претензий не должно быть со стороны препода, только [32] вряд ли является динамическим алгоритмом, хотя можно попытаться доказать обратное преподу, если он упрется, все таки полного перебора тоже нет, к тому же на строке до 100 символов летает.

← →
Sha © (2010-05-10 16:04) [61]

> xayam © (10.05.10 15:56) [60]
> слушай мы щас вроде не про автора говорим

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

Ключевое слово здесь подпоследовательность.
Конечно, ответ может получаться любым способом,
но результат должен быть подпоследовательностью и палиндромом.

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

← →
xayam © (2010-05-10 16:11) [62]

> Ключевое слово здесь подпоследовательность.

такого слова в условии вообще нет. К тому же, если ты не заметил, нахождение подпоследовательности - частный случай алгоритма [32], поскольку при этом важен порядок символов, [32] же не зависит от порядка символов, поскольку ищутся только пары одинаковых символов, поэтому как бы ты не упорядочил символы - алгоритм будет работать. Если не согласен, то пиши входные данные, что выводит алгоритм и что должно быть на самом деле по-твоему. [51] правильно выводит, ошибки нет.

← →
Sha © (2010-05-10 16:17) [63]

>> Ключевое слово здесь подпоследовательность.

> xayam © (10.05.10 16:11) [62]
> такого слова в условии вообще нет

Подпоследовательность = последовательность символов из данной строки, не обязательно идущих подряд

> Если не согласен, то пиши входные данные, что выводит алгоритм и что должно быть на самом деле по-твоему

Уже написал в [51].

Если бы можно было пересталять символы,
задача элементарно решалась бы при помощи массива 256 счетчиков.

← →
xayam © (2010-05-10 16:19) [64]

> нахождение подпоследовательности - частный случай алгоритма [32]

конечно имеется ввиду подпоследовательности, являющейся палендромом

← →
xayam © (2010-05-10 16:22) [65]

> Sha © (10.05.10 16:17) [63]
> > xayam ©
> > Если не согласен, то пиши входные данные, что выводит
> алгоритм и что должно быть на самом деле по-твоему
> Уже написал в [51].

ну так правильно выдает же, внимательно прочитай свое [51], буква "О" в исходной строке встречается два раза + центр T (без пары). Так и должно быть.

← →
Sha © (2010-05-10 16:29) [66]

Вот смотри берем HTEOLFEEOLEH вычеркиваем X X X X остается H E L EE LEH а как из HTEOLFEEOLEH получить H EOLETELOEH вычеркиванием?

← →
Родион (2010-05-10 16:40) [67]

ребят, завтра пойду пробовать сдавать. возьму код [32].

зы: что делает IntToStr?
зыы: не закрывайте тему плз

← →
Sha © (2010-05-10 16:42) [68]

> Родион (10.05.10 16:40) [67]
> возьму код [32]

очень не советую

← →
xayam © (2010-05-10 16:54) [69]

> Sha © (10.05.10 16:29) [66]

а где в условии это вычеркивание упоминается? Написано - порядок не имеет значения. Конечно, если методом вычеркивания, то алгоритм другой будет. Тут кажется неоднозначно условие задачи, поэтому я бы два алгоритма преподу отнес, а он сам пусть выбирает. Иначе может придраться.

> Родион (10.05.10 16:40) [67]
> что делает IntToStr?

ну как бы это... переводит целый тип в строковый :)

← →
Родион (2010-05-10 16:54) [70]

кк.. ну что то же надо показать

← →
xayam © (2010-05-10 17:00) [71]

> Родион (10.05.10 16:54) [70]
> кк.. ну что то же надо показать

как бы это... второй вариант алгоритма сам... Не?

← →
xayam © (2010-05-10 17:02) [72]

или Sha проси, наверно и код набросает, раз столько знает :)

← →
Sha © (2010-05-10 17:06) [73]

> xayam © (10.05.10 16:54) [69]
> а где в условии это вычеркивание упоминается?

В слове последовательность.
Последовательность подразумевает важность сохранения порядка.
Из вычеркивания следует сохранение порядка и наоборот.

> я бы два алгоритма преподу отнес

И продемонстрировал, что не понимаешь условия задачи, которую решаешь 4 месяца?
Выгонит сразу.

> Родион (10.05.10 16:54) [70]
> что делает IntToStr?

О существовании справки, которая вызывается по клавише F1 тебе известно?
читать пробовал?
что из прочитанного неясно?

ты хоть понял для чего матрица нужна?
чему равны ее элементы?
как по ним подстрока восстанавливается в списанном примере?
расскажи.

← →
xayam © (2010-05-10 17:13) [74]

> Sha © (10.05.10 17:06) [73]
> > я бы два алгоритма преподу отнес
> И продемонстрировал, что не понимаешь условия задачи, которую
> решаешь 4 месяца?

4 месяца это конечно круто, справился примерно за 2 часа вместе с составлением алгоритма.

> В слове последовательность.
> Последовательность подразумевает важность сохранения порядка.
> Из вычеркивания следует сохранение порядка и наоборот.

ну да последовательность, при не подряд идущих символах - это крутая формулировка, по-моему неточность в задании.

← →
KilkennyCat © (2010-05-10 17:22) [75]

> xayam © (10.05.10 16:54) [69]
> а где в условии это вычеркивание упоминается? Написано -
> порядок не имеет значения.

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

← →
xayam © (2010-05-10 17:28) [76]

> KilkennyCat © (10.05.10 17:22) [75]
> не идущие подряд и порядок - это разные вещи.

ну может быть, но я могу и так и так трактовать

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

Мы и первоисточники читаем.
http://comp-science.narod.ru/WebPage/lesson2.htm
Подпалиндром Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины. Формат входных данных Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита. Формат выходных данных В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них.
А Вы нет? Тогда мы идем к Вам :)

← →
KilkennyCat © (2010-05-10 17:36) [77]

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

← →
xayam © (2010-05-10 17:47) [78]

> KilkennyCat © (10.05.10 17:36) [77]
> но там гораздо уникальнее решения

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

> а в твоем случае достаточно сосчитать сколько каких букв

я подумаю, может быть можно приспособить [32] под вычеркивание, скорей всего это возможно.

← →
xayam © (2010-05-10 17:54) [79]

хотя нет, матрица конечно лучше, если вычеркивание

← →
KilkennyCat © (2010-05-10 17:57) [80]

> И вообще ничего уникального в рекурсии не вижу

я имел ввиду не алгоритм, а полученные результаты. когда я начну считать рекурсию уникальной - застрелюсь :)

← →
Sha © (2010-05-10 18:03) [81]

>> но там гораздо уникальнее решения
> полного решения там нет, только часть.

Полное решение для подстроки привел автор.

> тем более в данном случае надо без рекурсии решить

Заполнение той же матрицы, что у автора, без рекурсии приведено в [47].

> Матрица, конечно, это не совсем обычно, но по-моему тоже не обязательно так делать.

Для подстрок или подпоследовательностей, когда нужна только длина подпоследовательности, достаточно вектора.

Если нужна сама подпоследовательность, то, по-видимому, без матрицы не обойтись.
Точнее, мне решения без матрицы не попадались.

← →
xayam © (2010-05-10 18:19) [82]

> Заполнение той же матрицы, что у автора, без рекурсии приведено
> в [47].
> Sha © (10.05.10 14:26) [47]
> procedure FillPalMatrix( const s: string );
> var
> i, j, t, count, found: integer;
> begin;
> for j:=1 to length(s) do begin;
> Mat[j,j]:=1;
> for i:=j-1 downto 1 do begin;
> count:=Mat[i+1,j];
> t:=j;
> while s[t]<>s[i] do dec(t);
> found:=t-i+1;
> if t>=i+2 then found:=Mat[i+1, t-1]+2;
> if count<found then count:=found;
> Mat[i,j]:=count;
> end;
> end;
> end;

ну я потестировал этот код без рекурсии. Для исходное строки HTEOLFEOLEH есть два решения по матрице HEOFOEH и HELFLEH, а того что в примере HELOLEH нет. Ошибся где-то в процедуре?

← →
Sha © (2010-05-10 18:27) [83]

> xayam © (10.05.10 17:28) [76]
> Мы и первоисточники читаем.
> http://.../lesson2.htm

Кошмар. Непричесанный полуфабрикат.

← →
xayam © (2010-05-10 18:34) [84]

Вот тест для твоего кода, по матрице видно, что только два решения.
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

program MaxPalendrom2; {$APPTYPE CONSOLE} uses SysUtils; const max = 100; var Mat: array[1..max, 1..max] of integer; s: string; i, j, n: integer; procedure FillPalMatrix(const s: string); var i, j, t, count, found: integer; begin; for j:= 1 to n do begin Mat[j, j]:= 1; for i:= j - 1 downto 1 do begin count:= Mat[i + 1, j]; t:=j; while s[t] <> s[i] do dec(t); found:= t - i + 1; if t >= i + 2 then found:= Mat[i + 1, t - 1] + 2; if count < found then count:= found; Mat[i, j]:= count; end; end; end; begin //readln(s); s:= "HTEOLFEOLEH"; n:= length(s); for i:= 1 to n do for j:= 1 to n do if i = j then Mat[i, j]:= 1 else if i > j then Mat[i, j]:= 0 else Mat[i, j]:= -1; FillPalMatrix( s ); for i:= 1 to n do for j:= 1 to n do if s[i] <> s[j] then Mat[i, j]:= 0; for i:= 1 to n do begin for j:= 1 to n do write( inttostr( Mat[i, j] ) + " " ); writeln; end; readln; end.

← →
Sha © (2010-05-10 18:46) [85]

Просто 1 раз в самом начале вызови FillPalMatrix(s) и все.
Больше не меняй элементы матрицы.

Не читай элементы ниже главной диагонали,
они не имеют смысла, т.к. не существует строк с отрицательной длиной.

← →
xayam © (2010-05-10 18:51) [86]

> Sha © (10.05.10 18:46) [85]
> Просто 1 раз в самом начале вызови FillPalMatrix(s) и все.
> Больше не меняй элементы матрицы.

так обнулить же тоже надо, иначе там неправильно получается - не палендром, а какой-то мусор в матрице

← →
Sha © (2010-05-10 18:52) [87]

Например, процедура автора с ипользованием FillPalMatrix(s) перепишется так:
begin; s:=Edit1.Text; FillPalMatrix(s); maxi:=0; maxj:=0; for j:=1 to length(s) do for i:=j downto 1 do if (j-i+1>maxj-maxi+1) and (j-i+1=Mat[i,j]) then begin; maxi:=i; maxj:=j; end; Memo1.Lines.Add(IntTostr(maxj-maxi+1)); Memo1.Lines.Add(copy(s,maxi,maxj-maxi+1)); //палиндром без пропусков end;

← →
Sha © (2010-05-10 18:53) [88]

> так обнулить же тоже надо

не надо

← →
xayam © (2010-05-10 19:01) [89]

выводит:
1 H
program MaxPalendrom2; {$APPTYPE CONSOLE} uses SysUtils; const max = 100; var Mat: array[1..max, 1..max] of integer; s: string; i, j, n, maxi, maxj: integer; //f: TEXT; procedure FillPalMatrix(const s: string); var i, j, t, count, found: integer; begin; for j:= 1 to n do begin Mat[j, j]:= 1; for i:= j - 1 downto 1 do begin count:= Mat[i + 1, j]; t:=j; while s[t] <> s[i] do dec(t); found:= t - i + 1; if t >= i + 2 then found:= Mat[i + 1, t - 1] + 2; if count < found then count:= found; Mat[i, j]:= count; end; end; end; begin //readln(s); s:= "HTEOLFEOLEH"; n:= length(s); //assign(f, "C:\text.txt"); //rewrite(f); for i:= 1 to n do for j:= 1 to n do if i = j then Mat[i, j]:= 1 else if i > j then Mat[i, j]:= 0 else Mat[i, j]:= -1; FillPalMatrix( s ); {for i:= 1 to n do for j:= 1 to n do if s[i] <> s[j] then Mat[i, j]:= 0;} maxi:= 0; maxj:= 0; for j:= 1 to n do for i:= j downto 1 do if ( j - i + 1 > maxj - maxi + 1 ) and ( j - i + 1 = Mat[i, j] ) then begin maxi:= i; maxj:= j; end; writeln( IntTostr( maxj - maxi + 1) ); writeln( copy(s, maxi, maxj - maxi + 1) ); //rewrite(f); readln; end.

← →
Sha © (2010-05-10 19:08) [90]

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

← →
xayam © (2010-05-10 19:13) [91]

> Sha © (10.05.10 18:53) [88]
> > так обнулить же тоже надо
> не надо

это почему? Вот без обнуления к строке
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 1 1 1 1 1 3 3 3 5 7 2) 0 1 1 1 1 1 3 3 3 5 5 3) 0 0 1 1 1 1 3 3 3 5 5 4) 0 0 0 1 1 1 1 3 3 3 3 5) 0 0 0 0 1 1 1 1 3 3 3 6) 0 0 0 0 0 1 1 1 1 3 3 7) 0 0 0 0 0 0 1 1 1 3 3 8) 0 0 0 0 0 0 0 1 1 1 1 9) 0 0 0 0 0 0 0 0 1 1 1 10) 0 0 0 0 0 0 0 0 0 1 1 11) 0 0 0 0 0 0 0 0 0 0 1
очевидно, что большинство решений для получения максимального палендрома не имеют смысла, как и нули ниже главной диагонали. Не?

← →
xayam © (2010-05-10 19:15) [92]

> потому что пример автора ищет не подпоследовательности-палиндромы,
> а подстроки-палиндромы

как раз и те и другие, два решения-подпоследовательности есть в матрице

← →
xayam © (2010-05-10 19:17) [93]

в матрице есть решения, я про вывод не говорю

← →
xayam © (2010-05-10 19:24) [94]

Вот сравни эти матрицы:
обнуленная необнуленная 1 0 0 0 0 0 0 0 0 0 7 1 1 1 1 1 1 3 3 3 5 7 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 3 3 3 5 5 0 0 1 0 0 0 3 0 0 5 0 0 0 1 1 1 1 3 3 3 5 5 0 0 0 1 0 0 0 3 0 0 0 0 0 0 1 1 1 1 3 3 3 3 0 0 0 0 1 0 0 0 3 0 0 0 0 0 0 1 1 1 1 3 3 3 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 3 3 0 0 0 0 0 0 1 0 0 3 0 0 0 0 0 0 0 1 1 1 3 3 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1

В обнуленной сразу решения видно.

← →
xayam © (2010-05-10 19:29) [95]

о, блин я тормоз, там же три решения на каждую тройку:
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-10 19:32) [96]

Для того, чтобы найти и вывести все решения обоих задач
(для подстрок-палиндромов и подпоследовательностей-палиндромов)
достаточно иметь матрицу, сформированную FillPalMatrix.

Любые последующие действия с матрицей могут привести лишь к потере
содержащихся в ней решений.

← →
xayam © (2010-05-10 19:39) [97]

> Любые последующие действия с матрицей могут привести лишь
> к потере содержащихся в ней решений.

так не теряется же, потому что условие стоит if s[i] <> s[j] then Mat[i, j]:= 0;
в [95] - все возможные решения выделены жирным шрифтом. Чтобы вывести любой результат нужно сделать цикл в направлении от верхнего правого угла к нижнему левому постепенно уменьшая номер строки i и столбца j, тогда значение матрицы будет уменьшаться на два от начальных семи до единицы, все просто :) еще нужно учесть, что размер матрицы может быть четным числом.

← →
xayam © (2010-05-10 19:41) [98]

> уменьшая номер строки i и столбца j

поправка: увеличивая i и уменьшая j

← →
Sha © (2010-05-10 19:43) [99]

> xayam © (10.05.10 19:39) [97]

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

← →
Sha © (2010-05-10 20:08) [100]

Для полной ясности. Мы заполняли матрицу не решениями.

Mat[i,j] содержит длину максимального палиндрома, образованного некоторыми символами подстроки s[i..j], идущими в том же порядке.
А среди них совершенно случайно оказались нужные нам в обоих задачах длины :)

← →
Родион (2010-05-10 20:35) [101]

ув. Sha и xayam что я могу показать завтра на зачете из всего, что вы перерешали? =)

← →
Плохиш © (2010-05-10 20:47) [102]

> что я могу показать завтра на зачете из всего, что вы перерешали?

Что понял, то и показывай.

← →
KilkennyCat © (2010-05-10 20:48) [103]

> Родион (10.05.10 20:35) [101]

ничего. если бы понял, не спросил бы, а раз не понял, то как покажешь-то? Проще сразу коньяк.

← →
Родион (2010-05-10 21:01) [104]

ребят, мне не чего собственно объяснять не нужно.. мне просто надо принести задачу, чтоб как она сказала в данной функции

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;

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

← →
Плохиш © (2010-05-10 21:04) [105]

> за несколько дней проведенных в этом форуме я понял

А должен был понять, что проблемы индейцев шерифа не волнуют.

← →
Родион (2010-05-10 21:08) [106]

> А должен был понять, что проблемы индейцев шерифа не волнуют.

спасибо

← →
Sha © (2010-05-10 21:15) [107]

> Родион (10.05.10 21:01) [104]
> чтоб как она сказала в данной функции не было рекурсии

Перечитай ветку, текст заполнения матрицы приводился уже.
А функкция, если она тебе все еще зачем-то нужна, будет из одного оператора:
Result:=Mat[i,j];

← →
Родион (2010-05-10 21:18) [108]

> А функкция, если она тебе все еще зачем-то нужна

препод сказал ваще убирай ее или рекурсию из функции в конец программы, что то в этом роде

← →
Sha © (2010-05-10 21:23) [109]

> ваще убирай ее

Молодец какая :)
Полностью солидарен.

> или рекурсию из функции в конец программы, что то в этом роде

Скорее всего, что-то в этом роде :)
Иначе телега впереди лошади.

← →
xayam © (2010-05-10 21:26) [110]

> Родион (10.05.10 21:18) [108]
> > А функкция, если она тебе все еще зачем-то нужна
> препод сказал ваще убирай ее или рекурсию из функции в конец
> программы, что то в этом роде

[84] как раз без рекурсии и все правильно заполняет, осталось только матрицу обойти и вывести результат. Хоть что-то ты должен сделать :)

← →
Sha © (2010-05-10 21:38) [111]

> [84] как раз без рекурсии и все правильно заполняет
там много лишнего, можно обрезать
program MaxPalendrom2; {$APPTYPE CONSOLE} uses SysUtils; const max = 100; var Mat: array[1..max, 1..max] of integer; procedure FillPalMatrix(const s: string); var i, j, t, count, found: integer; begin for j:= 1 to n do begin Mat[j, j]:= 1; for i:= j - 1 downto 1 do begin count:= Mat[i + 1, j]; t:=j; while s[t] <> s[i] do dec(t); found:= t - i + 1; if t >= i + 2 then found:= Mat[i + 1, t - 1] + 2; if count < found then count:= found; Mat[i, j]:= count; end; end; end; var s: string; begin readln(s); FillPalMatrix(s); //тут твои 15 строчек end.
Всего 15 строчек написать надо.
И что характерно, за все это время ни единой попытки написать первую строчку

← →
Родион (2010-05-10 21:39) [112]

"обойти матрицу" можно тут поподробнее чуть, xayam :)

← →
Родион (2010-05-10 21:41) [113]

for j:= 1 to n do begin \ мб не n а max. или я о5 туплю(

← →
xayam © (2010-05-10 21:49) [114]

Чтобы вывести любой результат нужно сделать цикл в направлении от верхнего правого угла к нижнему левому постепенно уменьшая номер строки i и столбца j, тогда значение матрицы будет уменьшаться на два от начальных семи до единицы

← →
Sha © (2010-05-10 21:53) [115]

> Родион (10.05.10 21:39) [112]
> "обойти матрицу" можно тут поподробнее чуть, xayam :)

Так он уже матрицы выводил, показывал
Нам хочется, чтоб эти 15 сточек ты сам написал.

Вот, например, если вместо них написать
maxi:=0; maxj:=0; for j:=1 to length(s) do for i:=j downto 1 do if (j-i+1>maxj-maxi+1) and (j-i+1=Mat[i,j]) then begin; maxi:=i; maxj:=j; end;
то мы найдем, положение максимального палиндрома-строки.
Можешь это использовать в качестве примера обхода матрицы.

← →
xayam © (2010-05-10 21:54) [116]

> Родион (10.05.10 21:39) [112]
> "обойти матрицу" можно тут поподробнее чуть, xayam :)

[114] + [95] (жирным выделено то что тебе нужно получить в общем виде пройдя один из путей 7-3-1)

← →
xayam © (2010-05-10 21:57) [117]

7-5-33-1111

← →
xayam © (2010-05-10 22:10) [118]

если коротко, то примерно так осуществляется обход:
r:= ""; // результирующая половина подпалендрома вместе с центром i:= 1; // первая строка j:= n; // правый столбец while i <> j do r:= r + getNext( i, j );
ну и прототип функции getNext:
function getNext ( var i, j: integer ): string; begin //здесь твой анализ матрицы Mat[i, j] //точнее нужно рассмотреть четыре ячейки: // Mat[i+1, j] // Mat[i, j-1] // Mat[i+1, j-1] // Mat[i, j] //и в зависимости от их нулевого/ненулевого значения изменить //соответственно i и/или j для следующей итерации end;
и вывод результата:
writeln( IntToStr( 2*length( r ) - 1 ) ); write(r); for i:= length(r) - 1 downto 1 do write(r[i]);

← →
Родион (2010-05-10 22:18) [119]

> function getNext ( var i, j: integer ): string;begin
> //здесь твой анализ матрицы Mat[i, j] //точнее
> нужно рассмотреть четыре ячейки: // Mat[i+1,
> j] // Mat[i, j-1] //
> Mat[i+1, j-1] // Mat[i, j] //и в
> зависимости от их нулевого/ненулевого значения изменить
> //соответственно i и/или j для следующей итерацииend;
>

и все их надо рассматривать, их же много

← →
xayam © (2010-05-10 22:20) [120]

четыре всего

← →
Родион (2010-05-10 22:27) [121]

блин... я даже не знаю, xayam(

← →
Sha © (2010-05-10 22:28) [122]

> xayam © (10.05.10 22:10) [118]

Можно немного схитрить.
Достаточно отслеживать изменение длины палиндрома при движении
только одного конца строки. Например, будем смотреть, как меняется
длина при движении начала строки вправо. Засекли уменьшение - найден очередной символ. Теперь ищем его справа в самой строке, а не в матрице.
Тем самым определяем новый правый конец. А найденные символы заносим
в палиндром-результат. И т.д. Прелесть в том, что алгоритм сойдется в
середине палиндрома и особых случаев не будет.

> Родион (10.05.10 22:18) [119]
> и все их надо рассматривать, их же много

Компьютер железный, не устанет.

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

> FillPalMatrix(s); //тут твои 15 строчекend.Всего 15 строчек
> написать надо.

ребят я не знаю(

← →
Sha © (2010-05-10 22:48) [124]

> Родион (10.05.10 22:46) [123]
> ребят я не знаю

Вот в [122] что тебе не понятно?

← →
Родион (2010-05-10 22:51) [125]

да мне бы эти 15 строчек и было бы мне счастье)

← →
Sha © (2010-05-10 22:57) [126]

Герман иногда бывает прав.

← →
Родион (2010-05-10 23:03) [127]

> Герман иногда бывает прав.

это значит нет? :(

← →
Sha © (2010-05-10 23:06) [128]

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

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

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

← →
xayam © (2010-05-10 23:34) [130]

> бы посмотрел на код, и разобрался бы, так ведь проще когда
> программа перед глазами

ну я так не играю :) захотел прогу - бац текст перед глазами и все работает! Какой интерес? Творчество хоть какое-то должно быть или нет? Люди вообще должны удовольствие получать от процесса, а не от результата, каким бы он ни был Иначе нафиг учиться/сдавать программированию(е) ?

← →
Родион (2010-05-10 23:55) [131]

> ну я так не играю :) захотел прогу - бац текст перед глазами
> и все работает! Какой интерес? Творчество хоть какое-то
> должно быть или нет? Люди вообще должны удовольствие получать
> от процесса, а не от результата, каким бы он ни был Иначе
> нафиг учиться/сдавать программированию(е) ?

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

← →
Игорь Шевченко © (2010-05-10 23:57) [132]

> вот только времени у меня в обрез

а денег ?

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

и сколько же будет стоить эти самые 15 строчек?

← →
Servy © (2010-05-11 00:09) [134]

Вставлю-ка и я 5 копеек в это бурное обсуждение. Во-первых, код из [0] судя по всему скопипащен отсюда (задача подпалиндром с тем же условием, код в подсказке):

http://comp-science.narod.ru/WebPage/lesson2.htm

Там, помимо него было описано еще и назначение функции F, как она была получена, в общем-то почти все, что нужно для решения. Чтобы заполнять матрицу итеративно, достаточно внимательно прочитать, что:

F(I, J) = Max(F(I + 1, J), 2 + F(I + 1, K – 1));

Где K <= J (что опять же разжевано по ссылке).

Таким образом, значение элементов строк матрицы зависит от значений элементов следующей строки. Получаем цикл вроде:

for I := Length(S) downto 1 do for J := 1 to Length(S) do begin // TODO: добавить проверку граничных условий, рассмаотренных по приведенной ссылке // TODO: добавить поиск K Matrix[I, J] := Max(Matrix(I + 1, J), 2 + Matrix(I + 1, K – 1)); end;

После того, как матрица длин подпалиндромов найдена, остается лишь получить сам подпалиндром. Сделать это довольно просто, вот псевдокод:

var Finish: Integer; Result: String; // ... Result := ""; Finish := Length(S); for I := 1 to Length(S) do if (Matrix[I, Finish)] < Matrix[I+1, Finish]) then begin // символ I участвует в подпалиндроме [I..Finish] Result := Result + S[I]; // TODO: ищем в S начиная с позиции Finish в направлении начала строки позицию символа, совпадающуго с S[I] (обозначим ее за K). Finish := K-1; if Finish <= I then Break; end;

Матрица Matrix в этом псевдокоде должна иметь Length(S)+1 строк как минимум и в Length(S)+1й строке иметь нули (что согласуется с начальными условиями). Можно избавиться от этого ограничения, усложнив условие в цикле.

После этого в строке Result будет половина подпалиндрома (или больше половины на один символ, если длина подпалиндрома нечетна). Так как длину подпалиндрома мы уже выяснили ранее, то составить вторую половину - peace of cake.

P.S. Весь код и псевдокод написан тут, и ничего из написанного я не проверял, так что возможны ошибки. Отладчик поможет :).

← →
Родион (2010-05-11 01:08) [135]

> и вывод результата: writeln( IntToStr( 2*length( r ) -
> 1 ) ); write(r); for i:= length(r) - 1 downto 1 do
> write(r[i]);

2*length( r ) это чтоб слово выдало зеркально, но 2*length( r ) -1 зачем тут
"-1"???

← →
Германн © (2010-05-11 03:42) [136]

> Sha © (10.05.10 22:57) [126]
>
> Герман иногда бывает прав.
>

Иногда - это мягко сказано!

← →
Германн © (2010-05-11 03:56) [137]

Я не против помощи новичкам.
Но против шпаргалок, если они написаны не самим автором вопроса, а переданы автору другими лицами.
Хотя это вообще не имеет смысла. Любой преподаватель легко поймает шпаргальщика!

← →
Leonid Troyanovsky © (2010-05-11 08:47) [138]

> Sha © (10.05.10 23:06) [128]

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

Мне казалось, что ты готовишь ответы для упомянутого ИШ
виртуального сборника (наиболее часто задаваемых перед
сессией/призывом) вопросов.

Один твой ответ - сравнение способов вычисления количества
бит в целом числе:
http://www.delphimaster.net/view/2-1214996937/40-48
хранится и на моих магнитных скрижалях.

--
Regards, LVT.

← →
Anatoly Podgoretsky © (2010-05-11 09:20) [139]

> Родион (11.05.2010 00:03:13) [133]

Смотря что в них написано, кем написано и сколько это заняло времени, могут очень дорого стоить.

← →
Sha © (2010-05-11 09:25) [140]

> Leonid Troyanovsky © (11.05.10 08:47) [138]

:)

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

Потом я стал разбираться в решении автора. Оказалось, что в матрице запоминаются длины палиндромов-подпоследовательностей, а из нее извлекается решение-подстрока. Такой вот винегрет. В добавок вычисления элементов матрицы сделаны через одно место. А из-за того, что при разборе решения бардак перекочевал в мой код, пришлось наводить в нем порядок. Плюс ко всему захотелось проверить, насколько проще будет решение, если изначально в матрице сидят длины палиндромов, а не общих подпоследовательностей.

← →
Sha © (2010-05-11 09:32) [141]

или дублируя его =
или дублируя необходиые действия при обработке элемента неглавной диагонали

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

ребят, напишите эти самые 15 строчек плззз! ну оч надо через 40 мин на зачет. от этого много чего зависит

хотиите посмотреть на мою ерунду пожалуйста

begin
readln(s);
n:= length(s);
for i:= 1 to n do
for j:= 1 to n do begin
if i = j then Mat[i, j]:= 1 else
if i > j then Mat[i, j]:= 0 else
Mat[i, j]:= -1;
Matrix( s );
maxi:= 0;
maxj:= 0;
for j:= 1 to n do
for i:= j downto 1 do
if ( j - i + 1 > maxj - maxi + 1 ) and ( j - i + 1 = Mat[i, j] ) then begin
maxi:= i;
maxj:= j;
end;
writeln( IntToStr( 2*length( r ) - 1 ) );
writeln( copy(s, maxi, maxj - maxi + 1) );
readln;
end.

← →
Sha © (2010-05-11 09:54) [143]

> Родион (11.05.10 09:47) [142]
> Родион (10.05.10 23:11) [129]
> вот я бы посмотрел на код, и разобрался бы,

Вот на код [115] из твоей методички ты смотрел 4 месяца.
Разобрался?
Расскажи, что он делает.
И нафига ты его скопипастил в [142] тоже расскажи.

← →
Leonid Troyanovsky © (2010-05-11 09:58) [144]

> Sha © (11.05.10 09:25) [140]

> его. И то, и другое требует усилий на понимание и на программирование.

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

Может ИШ снабдит ссылкой на тот самый задачник, и где-нибудь
найдется местечко для решений, часто с этим АП помогал.

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

--
Regards, LVT.

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

посмотрел кодировку [84] и посмотрел как там осуществляется пекребор

← →
xayam © (2010-05-11 10:02) [146]

примерно так, но код не отлажен, может на некоторых строках не работать:
program MaxPalendrom2; {$APPTYPE CONSOLE} uses SysUtils; const max = 100; type point = record x, y: integer; end; var Mat: array[1..max, 1..max] of integer; s, r: string; i, j, n, mini, maxj: integer; p: point; procedure FillPalMatrix(const s: string); var i, j, t, count, found: integer; begin; for j:= 1 to n do begin Mat[j, j]:= 1; for i:= j - 1 downto 1 do begin count:= Mat[i + 1, j]; t:= j; while s[t] <> s[i] do dec(t); found:= t - i + 1; if t >= i + 2 then found:= Mat[i + 1, t - 1] + 2; if count < found then count:= found; Mat[i, j]:= count; end; end; end; function maximum( const a, b, d, f: integer ): point; begin if Mat[a, b] > Mat[d, f] then begin maximum.x:= a; maximum.y:= b; end else begin maximum.x:= d; maximum.y:= f; end; end; function getNext ( var i, j: integer; var p: point ): string; var p2: point; begin p2.x:= p.x; p2.y:= p.y; p:= maximum ( p.x, p.y, i, j ); p:= maximum ( p.x, p.y, i - 1, j + 1 ); p:= maximum ( p.x, p.y, i, j + 1 ); p:= maximum ( p.x, p.y, i - 1, j ); if ( p2.x = p.x ) and ( p2.y = p.y ) then result:= "" else result:= s[p.x]; i:= i - 1; j:= j + 1; end; begin readln(s); //s:= "HTEOLFEOLEH"; if s = "" then begin writeln("0"); readln; exit; end; n:= length(s); FillPalMatrix( s ); for i:= 1 to n do for j:= 1 to n do if s[i] <> s[j] then Mat[i, j]:= 0; for i:= 1 to n do begin for j:= 1 to n do write( IntToStr( Mat[i, j] ) + " " ); writeln; end; i:= n div 2 + 1; j:= i; p.x:= i; p.y:= j; r:= s[p.x]; if n mod 2 = 1 then mini:= 1 else mini:= 0; if n mod 2 = 1 then maxj:= n else maxj:= n + 1; while ( i <> mini ) and ( j <> maxj ) do r:= r + getNext( i, j, p ); n:= length(r); writeln( IntToStr( Mat[p.x, p.y] ) ); for i:= n downto 2 do write(r[i]); write(r); readln; end.

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

ой блин, не перебор а оббход

← →
Sha © (2010-05-11 10:06) [148]

> Родион (11.05.10 10:03) [147]

что код-то делает?
человеским языком объясни.

← →
Sha © (2010-05-11 10:12) [149]

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

Выложу оба решения чуть погодя, там много визуализации лишней, убрать надо.

> Кроме обсуждаемой темы и упомянутых битов можно вспомнить,
например, про точку в регионе.
Про точку есть еще одна совершенно замечательная (или не очень - фиг знает, пробовать надо, а времени нет) идея. Кроме лучевого, есть еще один известный метод - подсчет суммы углов. Но там проблема с точностью и скоростью. Идея в том что количество оборотов вокруг точки можно узнать без подсчета суммы углов, достаточно следить за перемещением вершин по квадрантам.

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

не сдал) сидели с преподом, она мне обьясняла как заполняеться матрица, что я и так понял. я ей показал [146] и толком не посмотрев отдала обратно флэху. говорит что не я решал, но так оно и есть я даже спорить не стал.
сказала, что после создания 2х мерн массива идешь проверять вертикаль и диагональ и рекурсией фигачишь. вобщем завтра забиваю на пары, иначе не как, и в 9-30 к ней. ребят нужно простое решение задачи

← →
sniknik © (2010-05-11 14:44) [151]

> ребят нужно простое решение задачи
сапоги заранее начистить? :)

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

> > ребят нужно простое решение задачисапоги заранее начистить?
> :)

я в принципе такого ответа и ожидал)) только вот что тут зделаешь уже..

← →
Palladin © (2010-05-11 15:52) [153]

) я название для фирмы чудо-программистов придумал: Скопируем и Вставим )

← →
xayam © (2010-05-11 16:08) [154]

> рекурсией фигачишь

в прошлый раз тебе вроде сказали, что без рекурсии. Не?

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

вот вот. в позопрошлый раз сказали чтобы была функкция
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;
потом сказала уберай ее или рекурсию убери из функции.
а щас говорит что без рекурсии ни как

← →
Sha © (2010-05-11 16:26) [156]

> xayam © (11.05.10 16:08) [154]

Это он не про заполнение матрицы, а про восстановление по ней палиндрома.
Хотя я тоже не вижу смысла в рекурсии, если цикла достаточно.

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

← →
xayam © (2010-05-11 16:41) [157]

> Sha © (11.05.10 16:26) [156]
> Это он не про заполнение матрицы, а про восстановление по
> ней палиндрома.
> Хотя я тоже не вижу смысла в рекурсии, если цикла достаточно.

ну как бы программа одна и раз без рекурсии, то логично, что все без рекурсии, хотя имхо пропод вообще и не парился: сказал что не сам писал и раз автор не может доказать обратное, при имеющемся коде, то и разговаривать не о чем, хотя [146] не доделано - неправильно работает с некоторыми строками.

> Вот интересно, автору и ты, и я, и препод как восстановить
> палиндром на пальцах рассказали, ты даже матрицу ему показал.
> Он типа все понял и вопросов не имеет. Но вместо того, чтоб
> начать писать, он нам пересказывает, что нам надо сделать
> по словам препода.

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

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

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

преподу не понравилась матрица.
как я понял:

H 0 0 0 0 0 0 0 0 0 0 0
T 0 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0 0
O 0 0 0 0 0 0 0 0 0 0 0
L 0 0 0 0 0 0 0 0 0 0 0
F 0 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0 0
O 0 0 0 0 0 0 0 0 0 0 0
L 0 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0 0
H 0 0 0 0 0 0 0 0 0 0 0
H T E O L F E O L E H

я не стал заполнять, не удобно. просто я имею в виду что H T E O L F E O L E H я правильно обозначил?

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

в смысле слева направо а не нпоборот

← →
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

← →
Sha © (2010-05-11 22:00) [190]

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

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

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

← →
Sha © (2010-05-11 22:09) [192]

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

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

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

← →
Sha © (2010-05-11 22:30) [194]

> Родион (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]?? и куда это вставлять?)

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

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

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

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

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

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

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

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

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

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

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

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

Вторая построена стандартным алгоритмом 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] ))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

> Родион (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]

что дальше?

На втором этапе работы алгоритма LCS происходит восстановление НОП по матрице, построенной на первом этапе.
Все достаточно просто.
Понятно, что длина НОП для двух полных строк сидит в угловой ячейке.
Мы начинаем прыгать в соседние ячейки и смотреть как меняется длина.
Причем прыгаем всегда в ту соседнюю ячейку, которая использовалась при вычислении длины, помещенной в текущую ячейку.
Если при таком прыжке длина уменьшилась, значит мы прыгнули из ячейки, которая содержала общий символ. Запоминаем его. Так мы восстановим всю НОП.

которая содержала общий символ =
которая соответсвует общему символу обеих подстрок

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

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

Не беги впереди паровоза.
Пока нигде не видно палиндромов.
С чего ты взял, что подпоследовательность будет палиндромом?
У строк АБВ и АБВГД НОП=АБВ - это что палиндром?
ЗАБУДЬ ПРО ПАЛИНДРОМЫ

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

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

да блин, я вобще понять не могу зачем нужен НОП? вот смотри я заполню матрицу по алогоритму нудельмана вунша а потом [243] мне и препод так сказал

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

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

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

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

← →
Родион (2010-05-12 16:26) [248]

ладно, но ты же понял что я имел в виду, можно же так ее решить? мы МОП даже не проходили.. надо решить как она хочет(

Нельзя ее так решить. Могу пример привести.
Только время оба потратим. Ты этого хочешь?

← →
Родион (2010-05-12 16:38) [250]

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

> Sha

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

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

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

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

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

:)

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

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

НОП=БА

АБАБА

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

я по анологии делал
| 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

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

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

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

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

Ты сам его выбрал, если ты помнишь 2 биолога = LCS

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

если это так и есть то почему у биологов заполнение матрицы:

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 17:51) [260]

и надо после этого просто спустится от 7 по жирным цифрам. я скопировал, их тут не видно

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

вывести результат и здача решена. вот все что мне сказал препод

Биологи рисуют первую строку последней, вторую - предпоследней, и т.д.

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

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 18:07) [264]

разве FillPalMatrix так ее заполняет?

← →
Родион (2010-05-12 20:21) [265]

> Sha

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

> Родион (12.05.10 18:02) [263]

Перестань рисовать матрицу вверх ногами.

> как заполнить то я его знаю, как это реализовать в коде

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

> Родион (12.05.10 18:07) [264]
> разве FillPalMatrix так ее заполняет?

Конечно не так.
Она заполняет по первому (самописному алгоритму из [206]
Но ты сказалЮ что тебе нужен другой алгоритм (2х биологов)

> вобщем я так понял, сам я наверно врядли что напишу..

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

> готов заплатить, за реализацию программы

Я за такую фигню денег не беру,
но если считаешь, что сайт тебе был чем-то полезен можешь оказать помошь сайту.

Вот пример, про который я говорил, показывающий что твоя училка не права или, точнее, не совсем права.

Возьмем, например, строку s1=12312,
для нее перевернутая строка s2=21321
Существует 5 LCS длины 3: 121, 131, 132, 231, 232,
из которых только 3 являются палиндромами.

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

//Палиндромом называется последовательность символов, которая одинаково //читается слева направо и справа налево. Требуется найти в данной строке //подпоследовательность-палиндром макcимальной длины, используя алгоритм LCS const MaxStrLen= 256; type TMatrixLCS= array[0..MaxStrLen, 0..MaxStrLen] of integer; var MatrixLCS: TMatrixLCS; //Первая фаза алгоритма LCS. Заполняем матрицу длинами подпоследовательностей. //Пусть у нас есть строки s1[1..n1] и s2[1..n2]. //Тогда после работы первой стадии алгоритма LCS элемент M[i,j] матрицы будет //содержать длину наибольшей общей подпоследовательности строк s1[1..i] и s2[1..j]. procedure FillMatrixLCS(const s1, s2: string); var Col, Row, Val: integer; begin; for Col:=0 to Length(s1) do MatrixLCS[0,Col]:=0; for Row:=0 to Length(s2) do MatrixLCS[Row,0]:=0; for Col:=1 to Length(s1) do for Row:=1 to Length(s2) do if s2[Row]=s1[Col] then MatrixLCS[Row,Col]:=MatrixLCS[Row-1,Col-1] + 1 else begin; Val:=MatrixLCS[Row,Col-1]; if Val<MatrixLCS[Row-1,Col] then Val:=MatrixLCS[Row-1,Col]; MatrixLCS[Row,Col]:=Val; end; end; //Вторая фаза алгоритма LCS. //Строим наибольшую общую подпоследовательность строк s1[1..Col] и s2[1..Row]. function GetCellLCS(Col, Row: integer; const s1, s2: string): string; begin; Result:=""; while (Col>0) and (Row>0) do if s1[Col]=s2[Row] then begin; Result:=s1[Col] + Result; dec(Col); dec(Row); end else if MatrixLCS[Row,Col-1]>MatrixLCS[Row-1,Col] then dec(Col) else dec(Row); end; procedure TForm1.Button1Click(Sender: TObject); var s1, s2, s3: string; Col, Row, MaxCol, MaxRow, Val, MaxVal: integer; IsEvenLength, MaxIsOddLength: boolean; begin; //Вводим исходную строку и строим матрицу длин наибольших общих подпоследовательностей //для исходной и перевернутой строки при помощи первой фазы алгоритма LCS s1:=Edit1.Text; if Length(s1)>MaxStrLen then exit; s2:=ReverseString(s1); FillMatrixLCS(s1, s2); //Было бы ошибкой сейчас просто вызвать вторую фазу алгоритма //и завершить работу, например, так: //Edit2.Text:=GetCellLCS(Length(s1), Length(s2), s1, s2); //Вторая фаза вернет наибольшую общую подпоследовательность, которая может //оказаться не палиндромом, например, для s1=12312 и s2=21321 может вернуться //132 или 231 вместо 121, 131, 212, 232. //Пусть длина исходной строки равна L. Мы найдем максимальный палиндром, если //будем искать максимальную общую подпоследовательность для L всевозможных //пар строк, образованных ее началом длины Y=1..L первернутым хвостом длины //X=L+1-Y. Все длины всех таких подпоследовательностей лежат на неглавной //диагонали матрицы. Поэтому ищем максимальный элемент на диагонали. MaxCol:=0; MaxRow:=0; MaxVal:=0; MaxIsOddLength:=false; for Col:=1 to Length(s1) do begin; Row:=Length(s1) + 1 - Col; Val:=MatrixLCS[Row,Col]; if MaxVal<=Val then begin; //Символ, соответствующий элементу главной диагонали, лежит в центре //палиндрома четной длины, если выполняются следующие условия: IsEvenLength:=(Col>1) //символ не первый and (s1[Col]=s2[Row+1]) //предыдущий символ ему равен and (Val=MatrixLCS[Row+1,Col-1]); //длины LCS для них совпадают //четный палиндром предпочтительнее при одинаковых значениях элементов if (MaxVal<Val) or IsEvenLength then begin; MaxVal:=Val; MaxIsOddLength:=not IsEvenLength; MaxRow:=Row; MaxCol:=Col; end; end; end; //Вызываем вторую фазу алгоритма LCS, чтобы найти половину палиндрома s3:=GetCellLCS(MaxCol, MaxRow, s1, s2); //Зеркально отражаем начало в хвост и выводим результат SetLength(s3, 2 * Length(s3) - ord(MaxIsOddLength)); for Col:=1 to Length(s3) div 2 do s3[Length(s3)+1-Col]:=s3[Col]; Edit2.Text:=s3; end;

> Я за такую фигню денег не беру,
> но если считаешь, что сайт тебе был чем-то полезен можешь
> оказать помошь сайту.

+1
http://www.delphimaster.ru/donate.html

Пожалуй сей топик - это первый пример на ДМ, когда новичку (я бы высказался ещё более грубо, но не хочу пока) дали не только пример, но практически полный урок от Мастера по конкретному вопросу.

Хотя "реализация программы" это только первый этап.

//Палиндромом называется последовательность символов, которая одинаково //читается слева направо и справа налево. Требуется найти в данной строке //подпоследовательность-палиндром макcимальной длины, используя алгоритм //динамического программирования. //Решим эту задачу для палиндромов двух типов: //палиндромов-подпоследовательностей, когда пропуск символов исходной строки разрешается, //и палиндромов-подстрок, когда пропуск запрещен. const MaxStrLen= 256; type TMatrixDP= array[1..MaxStrLen,1..MaxStrLen] of integer; var MatrixDP: TMatrixDP; //FillMatrixDP заполняет матрицу длинами палиндромов, так что //элемент MatrixDP[i,j] содержит длину наибольшего палиндрома, образованного некоторыми //символами подстроки s[i..j], идущими в том же порядке, что и в строке s. //Очевидно, MatrixDP[i,i]=1. Другие значения вычисляются рекурсивно. //Подстроку s[i..j] (i<j) можно получить приписыванием символа s[i] //к подстроке s[i+1..j]. Если при этом не образуется максимального палиндрома, то //полагаем MatrixDP[i,j]=MatrixDP[i+1,j]. Если образуется, то в подстроке s[i..j], //перебирая символы, начиная с позиции j, находим ему пару. //Если пара находится в позиции i, то MatrixDP[i,j]=1, //если в позиции i+1, то MatrixDP[i,j]=2, //если в позиции t (i+2<=t<=j), то MatrixDP[i,j]=MatrixDP[i+1,t-1] + 2. procedure FillMatrixDP(const s: string); var i, j, t, count, found: integer; begin; for j:=1 to length(s) do begin; MatrixDP[j,j]:=1; for i:=j-1 downto 1 do begin; count:=MatrixDP[i+1,j]; t:=j; while s[t]<>s[i] do dec(t); found:=t-i+1; if t>=i+2 then found:=MatrixDP[i+1, t-1]+2; if count<found then count:=found; MatrixDP[i,j]:=count; end; end; end; procedure TForm1.Button2Click(Sender: TObject); var i, j, maxi, maxj, k, w: integer; s, t: string; begin; //Вводим исходную строку и строим матрицу длин палиндромов s:=Edit1.Text; if Length(s)>MaxStrLen then exit; FillMatrixDP(s); //Найдем палиндром-подпоследовательность (пропуски символов исходной строки допустимы) w:=MatrixDP[1,Length(s)]; SetLength(t,w); i:=1; j:=Length(s); k:=1; while w>0 do begin; while (i<j) and (MatrixDP[i+1,j]=w) do inc(i); t[k]:=s[i]; t[Length(t)+1-k]:=s[i]; inc(k); while s[i]<>s[j] do dec(j); dec(j); w:=w-2; end; Memo1.Lines.Add(t); //Найдем палиндром-подстроку (пропуски символов исходной строки запрещены) maxi:=0; maxj:=0; for j:=1 to length(s) do for i:=j downto 1 do //Если длина палиндрома равна количеству символов подстроки, //то палиндром является подстрокой if (j-i+1>maxj-maxi+1) and (j-i+1=MatrixDP[i,j]) then begin; maxi:=i; maxj:=j; end; Memo1.Lines.Add(copy(s,maxi,maxj-maxi+1)); end;

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

> procedure TForm1.Button2Click(Sender: TObject);

что за кнопка? выдает ошибку в процедуре на TForm1, если {$APPTYPE CONSOLE}.

> > Я за такую фигню денег не беру,> но если считаешь, что
> сайт тебе был чем-то полезен можешь > оказать помошь сайту.
> +1http://www.delphimaster.ru/donate.html

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

Наверно, 99% приложений для Windows - оконные, да и отлаживаться обычно удобнее в оконном приложении, поэтому в исходниках ты видишь формы, едиты, мемы и разные кнопки :)

В твоем случае просто удали
procedure TForm1.Button2Click(Sender: TObject);
а для ввода/вывода используй ReadLn/WriteLn

← →
Родион (2010-05-13 15:03) [274]

удалить всю процедуру или только строчку?

> Родион (13.05.10 15:03) [274]
>
> удалить всю процедуру или только строчку?
>

строчку

← →
Родион (2010-05-13 16:00) [276]

> Но ты сказалЮ что тебе нужен другой алгоритм (2х биологов)

нельзя ли по этому алгоритму решить задачу?

кодировки [268] и [271] слишком сложные, хоть может и правильно работают. но у меня вылазят слишком много ошибок.

а как на сччет

program MaxPalendrom2;
{$APPTYPE CONSOLE}
uses SysUtils;

const max = 100;
var Mat: array[1..max, 1..max] of integer;

procedure FillPalMatrix(const s: string);
var
i, j, t, count, found: integer;
begin
for j:= 1 to n do begin
Mat[j, j]:= 1;
for i:= j - 1 downto 1 do begin
count:= Mat[i + 1, j];
t:=j;
while s[t] <> s[i] do dec(t);
found:= t - i + 1;
if t >= i + 2 then found:= Mat[i + 1, t - 1] + 2;
if count < found then count:= found;
Mat[i, j]:= count;
end;
end;
end;

var
s: string;
begin
readln(s);
FillPalMatrix(s);
//тут твои 15 строчек
end.

> Родион (13.05.10 16:00) [276]
> а как на сччет
> //тут твои 15 строчек

Ну, выкуси код из [271]
w:=Mat[1,Length(s)]; SetLength(t,w); i:=1; j:=Length(s); k:=1; while w>0 do begin; while (i<j) and (MatrixDP[i+1,j]=w) do inc(i); t[k]:=s[i]; t[Length(t)+1-k]:=s[i]; inc(k); while s[i]<>s[j] do dec(j); dec(j); w:=w-2; end;

добавь вывод результата
WriteLn(t);

и объявления
var i, j, k, w: integer; s, t: string;

только это не "два биолога", а обычное ДП

В выкушенном коде MatrixDP на Mat забыл заменить во втором случае

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