Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

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

Динамическое програмирование. Подпалендром. [D7, WinXP]

Страницы: < 1 2 ... 5 6 7 8 9 10 11 12 13 14 >
rodion © (2010-05-07 07:30:00)
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины.

есть код задачи, который нужно исправить, для правильной работы:

program Project6;

{$APPTYPE CONSOLE}

uses
SysUtils;
var
Mat:array[1..100,1..100]of integer;
s:string;
s1:string;
i,j,n,d,j1,k,maxj,maxi:integer;

Function F(i, j : Integer) : Integer;
var Ch : Char; R1, R2 : Integer; k : byte;
begin
if Mat[i, j] = -1 then
BEGIN
k := j;
while s[i] <> s[k] do dec(k);
R1 := F(i + 1, j);
if i <> k then R2 := F(i + 1, k - 1) + 2 else R2 := 1;
if R1 > R2 then Mat[i, j] := R1 else Mat[i, j] := R2
END;
F := Mat[i, j]
end;

begin
try
{ TODO -oUser -cConsole Main : Insert code here }
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
readln(s);
for I:=1 to length(s) do
for j := 1 to length(s) do
if i=j then Mat[i,j]:=1
else if i>j then Mat[i,j]:=0
else mat[i,j]:=-1;
maxi:=0;maxj:=0;
for i:=1 to length(s) do
for j:=1 to length(s) do
begin
Mat[i,j]:=f(i,j);
if (j-i+1>maxj-maxi+1)and(j-i+1=Mat[i,j]) then
begin
maxi:=i;
maxj:=j;
end;
end;
writeln(maxj-maxi+1);
writeln(copy(s,maxi,maxj-maxi+1));
readln;
end.

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

xayam (2010-05-10 15:38:00) [221]

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

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

xayam (2010-05-10 15:32:00) [222]

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

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

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

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

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

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

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

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

Sha (2010-05-10 15:26:00) [223]
максимальный, удовлетворяющий [53-54]

Sha (2010-05-10 15:22:00) [224]
значит порядоксимволов

xayam (2010-05-10 15:22:00) [225]
тем более HEOLETELOEH длиннее HELEELEH на один символ. А задача как раз найти максимальный :)

Sha (2010-05-10 15:21:00) [226]
Палиндром образуется вычеркиванием символов из исходной строки,
значит символов в палиндроме должен соответствовать исходному.
Ну, и зеркально расположеные символы относительно центра палиндрома должны быть равны.

xayam (2010-05-10 15:16:00) [227]

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

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

Sha (2010-05-10 15:12:00) [228]
алгоритм [32]
на строке HTEOLFEEOLEH
выдает HEOLETELOEH
вместо HELEELEH

xayam (2010-05-10 14:51:00) [229]

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

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

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

Именно.

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

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

xayam (2010-05-10 14:40:00) [231]

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

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

Sha (2010-05-10 14:26:00) [232]
> 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:11:00) [233]
Или здесь:

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

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

xayam (2010-05-10 14:05:00) [234]

> 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) ?

Sha (2010-05-10 13:55:00) [235]
> xayam
> либо я что-то не понимаю, либо динамическое программирование подразумевает использование рекурсии

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

xayam (2010-05-10 13:46:00) [236]
будут, будут - у препода :)

KilkennyCat (2010-05-10 13:45:00) [237]

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

смешно.

Родион (2010-05-10 13:32:00) [238]
спс xayam , щас буду разбираться в коде. если будут вопросы напишу)

xayam (2010-05-10 13:09:00) [239]
в любом случае у меня короче решение:
M:=copy(P,2,length(P)-2)
:)

KilkennyCat (2010-05-10 13:07:00) [240]
а, я недогнал, мне что-то покеазалось, что исходная строка - палиндром.
Ну ладно, мое решение для частного случая.

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

Наверх

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