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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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