Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Задачи на палиндромы

Автор: Snake08 6.11.2008 21:01

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

Автор: feniks25 7.11.2008 1:19

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

Автор: volvo 7.11.2008 1:26

Цитата
и ещё почему надо определить МИНИМАЛЬНОЕ количество, это сколько 1,2,3...
не понятно
Потому что любую строку можно разбить на палиндромы, если они будут минимальной длины (по одной букве)... В задании же требуется разбить строку на минимальное количество палиндромов, соответственно, их длины должны быть максимально возможными... Вот, в примере строка разбита на 3 палиндрома, а можно было бить на
5: abbacbb = a + bb + a + c + bb
6: abbacbb = a + b + b + a + c + bb
и даже на 7...

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

Автор: Snake08 7.11.2008 1:47

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

Автор: Lapp 7.11.2008 6:20

Цитата(Snake08 @ 6.11.2008 21:47) *
Я в паскале ноль можете мне написать в паскале!

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

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

Автор: feniks25 7.11.2008 12:19

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


Автор: Lapp 7.11.2008 12:52

Цитата(feniks25 @ 7.11.2008 8:19) *
но как хранить данные об исключениях (сначала думал просто удалять, но нельзя)
создать динамический массив? для всех отрывков строк?

Рекурсия? smile.gif

Автор: feniks25 7.11.2008 22:18

Цитата(Lapp @ 7.11.2008 8:52) *

Рекурсия? smile.gif

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


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

Автор: volvo 7.11.2008 22:44

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

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

Автор: feniks25 7.11.2008 23:29

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

Автор: Lapp 8.11.2008 11:50

Цитата(feniks25 @ 7.11.2008 19:29) *
хм... ну тогда можно не использовать рекурсию, а сделать проще.
Дык. Тогда можно и до Питера не использовать поезд - пешком проще! smile.gif
Перемудрил, ты, однако.. Реально именно рекурсия всегда проще (алгоритмически) и короче. Если, конечно, подумать сначала smile.gif
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% времени.

Автор: feniks25 8.11.2008 13:29

Цитата(Lapp @ 8.11.2008 6:50) *

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


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

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

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

Автор: volvo 8.11.2008 13:55

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.

Автор: feniks25 8.11.2008 21:26

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

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

Автор: volvo 8.11.2008 21:45

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