Задачи на палиндромы, палиндромы!Помогите пожалуста срочно! Опции

[Snake08]

Палиндромы 1!
Задана строка, которая составляется из малых латинских букв. Разрешается удалять из строки определенные буквы. Сколькими разными образами можно при этом получить палиндром?
Входные данные: заданная строка находится в файле palindrome1.dat, длина его не превышает 30 символов
Исходные данные: в первую строку файла palindrome1.sol надо вывести искомое количество образов получения палиндрому
Пример входных и исходных данных:
palindrome1.dat
aab
palindrome1.sol
4
Объяснение: палиндром можно получить, удалив символы 1) 1 і 2; 2) 1 і 3; 3) 2 і 3; 4) 3!
Палиндромы 2!
Задана строка, которая составляется из малых латинских букв. Нужно разбить его на минимальное возможное количество палиндромов.
Входные данные: заданная строка находится в файле palindrome2.dat, длина не превышает 2000 символов
Исходные данные: в первую строку файла palindrome2.sol надо вывести минимальное количество палиндромов, на которые можно разбить строку
Пример входных и исходных данных:
palindrome2.dat
abbacbb
palindrome2.sol
3
Объяснение: abbacbb = abba + c + bb

[Rian]

ну не знаю задача может мудрёная но не сложная
что не знаешь?
можешь определить являетя ли отрывок строки палиндромом?
можешь перебрать все возможные отрывки строк?
и ещё почему надо определить МИНИМАЛЬНОЕ количество, это сколько 1,2,3...
не понятно

[volvo]

и ещё почему надо определить МИНИМАЛЬНОЕ количество, это сколько 1,2,3...
не понятно

Потому что любую строку можно разбить на палиндромы, если они будут минимальной длины (по одной букве)... В задании же требуется разбить строку на минимальное количество палиндромов, соответственно, их длины должны быть максимально возможными... Вот, в примере строка разбита на 3 палиндрома, а можно было бить на
5: abbacbb = a + bb + a + c + bb
6: abbacbb = a + b + b + a + c + bb
и даже на 7...

МЕНЬШЕ чем на 3 палиндрома приведенную строку разбить нельзя.

[Snake08]

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

[Lapp]

Я в паскале ноль можете мне написать в паскале!

Значит ли это, что ты просишь готовую программу целиком? С начала и до конца? Боюсь, здесь ты это не получишь (разве что в "Задачах на заказ").

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

[Rian]

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

[Lapp]

но как хранить данные об исключениях (сначала думал просто удалять, но нельзя)
создать динамический массив? для всех отрывков строк?

Рекурсия?

[Rian]

Рекурсия?

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

//главная функция счтиющая палендромы
function calc(st:string):integer;
var
count:integer;

//определение является ли строка палендромом
  function palendrom(s:string):boolean;
  var
  i:integer;

  begin
  result:=true;
    for i:=1 to length(s)div 2 do
    if s[i]<>s[length(s)-i+1] then begin
    result:=false;
    break
    end;
  end;

//сама рекурсия
  procedure PalCount(st:string;x1,x2:integer);
  var
  st1,st2,tPal:string;
  y1,y2:integer;
  begin
  tpal:='';
  y1:=0;
  y2:=0;
//переносим для обработки часть строки
    st1:=Copy(st,x1,x2-x1+1);

//проверяем все отрывки строки и находим отрезок максимальной длины
  for x1:=1 to length(st1) do
  for x2:=length(st1) downto x1 do begin
    st2:=Copy(st1,x1,x2-x1+1);

      if (palendrom(st2)) then
        if length(st2)>length(tPal) then begin
        tPal:=st2;
        y1:=x1;
        y2:=x2;
        end;
  end;

//если tpal не пуста то значит
//мы нашли палендром в строке
//вызываем такую же процедуру для левой и правой части строки
  if length(tpal)>0 then begin
      count:=count+1;
      PalCount(st1,1,y1-1);
      PalCount(st1,y2+1,length(st1));
  end;
  end;

begin
count:=0;
PalCount(st,1,length(st));
result:=count;
end;

кажется ещё можно не проверять длины строк, а сами строки
if tpal<>'' then begin

ну а подойдёт ли решение Snake08 не знаю

Сообщение отредактировано: feniks25 - 7.11.2008 22:31

[volvo]

кажется решил

Возможно, что это даже отработает на 32-битном компиляторе. В случае с Турбо-Паскалем (все-таки раздел-то для него, а не для 32-бит) вылезают как минимум 2 проблемы:
1) может не хватить стека при большой длине входной последовательности (в условии указано до 2000 символов);
2) String хранит до 256 символов, но никак не 2000.

Кстати, если принимать строки в качестве параметра по константной ссылке (как Const st: string), то можно значительно уменьшить использование стека.

[Rian]

хм... ну тогда можно не использовать рекурсию, а сделать проще.
создадим массив [1..2000]
заполним его нужными символами
найдём в этой строке наибольший палендром
перепишем этот отрезок нолями
найдём новый непрерывный отрезок между нолями, проверим его на палендром...
ну и будем заодно считать сколько штук нашли

[Lapp]

хм... ну тогда можно не использовать рекурсию, а сделать проще.

Дык. Тогда можно и до Питера не использовать поезд - пешком проще!
Перемудрил, ты, однако.. Реально именно рекурсия всегда проще (алгоритмически) и короче. Если, конечно, подумать сначала

var
  w:string;

function MinPal(s:string):integer;
var
  i,m,n:integer;
  Pal:boolean;
begin
  Pal:=true;
  for i:=1 to Length(s) div 2 do Pal:=Pal and(s[i]=s[Length(s)-i+1]);
  if Pal then MinPal:=1
  else begin
    n:=Length(s);
    for i:=1 to Length(s)-1 do begin
      m:=MinPal(Copy(s,1,i))+MinPal(Copy(s,i+1,Length(s)-i));
      if m<n then n:=m
    end;
    MinPal:=n
  end
end;

begin
  ReadLn(w);
  WriteLn(MinPal(w))
end.

Ну, что может быть проще?
Если заменить первый цикл на while или хотя бы вставить в него break, то можно сэкономить 50% времени.

[Rian]

Если заменить первый цикл на while или хотя бы вставить в него break, то можно сэкономить 50% времени.

?
странно, слушай ты тестировал свою прогу?
короче вот что я намерял
test='ghjaaabbbjjjioklk';
количество 9
мой вариант:память-12кб время при 1000 повторах 62 мс
твой :память-12кб время при 1 повторе 8609мс

тестировал Delphi7.
учёл совет volvo про константы

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

[volvo]

feniks25, как говорил один из героев Ж.Верна "не следует смешивать статику с динамикой, это может привести к серьёзным промахам."

надо создавать массив, а это ещё больше памяти...

Да, надо... Но только учти, что массив (длиной 2000 символов) описывается глобально 1 раз, плюс добавляется еще 3 целочисленных массива (третий - для сохранения позиций этих самых палиндромов, так что можно в принципе обойтись и двумя) тоже по 2000 Integer-ов, итого в худшем случае все это удовольствие стоит тебе 14000 байт. А уж 2000 уровней рекурсии Паскаль как-нибудь осилит с (учётом того, что на каждом витке в стек кладётся не огромная строка, и не ещё бОльший массив, а всего несколько целочисленных переменных):

{ Ну, это не обязательно, это моя старая привычка имитации X++ и X-- }
function incr(var X: integer): integer;
begin incr := X; inc(X); end;
function decr(var X: integer): integer;
begin decr := X; dec(X); end;

const
  maxLen = 2000;
var
  A : array[1 .. maxLen] of char; 
  Yl, Res, positions: array [1 .. maxLen] of integer;

function is_palindrom(start, finish: integer): boolean;
begin
  is_palindrom := false;
  while start <= finish do
    if A[incr(start)] <> A[decr(finish)] then exit;
  is_palindrom := true;
end;

var n, Rmin, Rv: Integer;

procedure check(start: integer);
var i, j: integer;
begin
  if Rv < Rmin - 1 then
    for i := n downto start do
      if Rv < Yl[i] then if is_palindrom(start, i) then begin

        Yl[i] := incr(Rv);
        Res[Rv] := i;
        if i < n then check(i + 1)
        else
          if Rv < Rmin then begin
            Rmin := Rv;
            for j := 1 to Rv do positions[j] := Res[j];
          end;
        dec(Rv);

      end;
end;

var i: integer;
begin
  Rmin := maxLen;
  Rv := 0;
  for i:=1 to maxLen do Yl[i] := maxLen;

  n := 0;

  { Немного необычное заполнение массива, все-же не строка, чтоб ReadLn использовать }
  while not eoln do begin
    inc(n); read(a[n]);
  end;

  check(1);
  writeln(Rmin);

  { При желании печатаем и сами палиндромы, составляющие строку }
  (*
  j:=0;
  for i:=1 to Rmin do begin
    writeLn(Copy(A,j+1,positions[i] - j)); j := positions[i]
  end;
  *)
end.

Сообщение отредактировано: volvo - 8.11.2008 13:56

[Rian]

а зачем ещё три массива, если все нужные операции можно сделать в пределах одного

и зачем хранить позиции палендромов

[volvo]

а зачем ещё три массива, если все нужные операции можно сделать в пределах одного

Если ты на 100% уверен, что следующим же вопросом не последует "А как мне вывести сами палиндромы, составляющие исходную строку?", то можно обойтись и одним.