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

[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

[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