Палиндромы 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

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

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

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

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

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

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

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

Рекурсия?

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

//главная функция счтиющая палендромы
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 18:31

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

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

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

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

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% времени.

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

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

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

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 9:56

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

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

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