Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2010.08.27;
Скачать: CL | DM;

Вниз

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

 
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)

:)



Страницы: 1 2 3 4 5 6 7 вся ветка

Текущий архив: 2010.08.27;
Скачать: CL | DM;

Наверх




Память: 0.58 MB
Время: 0.19 c
15-1270007391
Дмитрий С
2010-03-31 07:49
2010.08.27
Какой гугл умный:


15-1264530887
Rouse_
2010-01-26 21:34
2010.08.27
Вопрос по поводу Дельфи 2009 (и выше)


15-1269360123
TUser
2010-03-23 19:02
2010.08.27
Генетика и геномика человека


15-1273125258
oxothuk
2010-05-06 09:54
2010.08.27
Точки останова


15-1268650699
Омлет
2010-03-15 13:58
2010.08.27
Проверка на выпуклость четырехугольника