Палиндромы 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...
не понятно
Я в паскале ноль можете мне написать в паскале! Пожалуста я буду очень благодарен!
слушайте, задумался, чтобы найти минимальное количество надо найти максимально длинную строку, исключить её из анализа и в оставшейся части дробить её на более мелкие, мелкие...
но как хранить данные об исключениях (сначала думал просто удалять, но нельзя)
создать динамический массив? для всех отрывков строк?
//главная функция счтиющая палендромы
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;
хм... ну тогда можно не использовать рекурсию, а сделать проще.
создадим массив [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.
feniks25, как говорил один из героев Ж.Верна "не следует смешивать статику с динамикой, это может привести к серьёзным промахам."
{ Ну, это не обязательно, это моя старая привычка имитации 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.
а зачем ещё три массива, если все нужные операции можно сделать в пределах одного
и зачем хранить позиции палендромов