Мастера 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.

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

Leonid Troyanovsky (2010-05-11 08:47:00) [141]

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

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

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

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

--
Regards, LVT.

Германн (2010-05-11 03:56:00) [142]
Я не против помощи новичкам.
Но против шпаргалок, если они написаны не самим автором вопроса, а переданы автору другими лицами.
Хотя это вообще не имеет смысла. Любой преподаватель легко поймает шпаргальщика!

Германн (2010-05-11 03:42:00) [143]

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

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

Родион (2010-05-11 01:08:00) [144]

> и вывод результата: 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"???

Servy (2010-05-11 00:09:00) [145]
Вставлю-ка и я 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 00:03:00) [146]
и сколько же будет стоить эти самые 15 строчек?

Игорь Шевченко (2010-05-10 23:57:00) [147]

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

а денег ?

Родион (2010-05-10 23:55:00) [148]

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

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

xayam (2010-05-10 23:34:00) [149]

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

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

Родион (2010-05-10 23:11:00) [150]
вот я бы посмотрел на код, и разобрался бы, так ведь проще когда программа перед глазами, ну а если бы не понял что то не понял в обходе то скопировал бы строчку и спросил бы сразу

Sha (2010-05-10 23:06:00) [151]
Это значит нет смысла тратить свое время на написание кода для того,
кто не хочет потратить на это даже секунды своего времени.

Родион (2010-05-10 23:03:00) [152]

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

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

Sha (2010-05-10 22:57:00) [153]
Герман иногда бывает прав.

Родион (2010-05-10 22:51:00) [154]
да мне бы эти 15 строчек и было бы мне счастье)

Sha (2010-05-10 22:48:00) [155]
> Родион (10.05.10 22:46) [123]
> ребят я не знаю

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

Родион (2010-05-10 22:46:00) [156]

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

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

Sha (2010-05-10 22:28:00) [157]
> xayam © (10.05.10 22:10) [118]

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

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

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

Родион (2010-05-10 22:27:00) [158]
блин... я даже не знаю, xayam(

xayam (2010-05-10 22:20:00) [159]
четыре всего

Родион (2010-05-10 22:18:00) [160]

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

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

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

Наверх

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