IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Задачи на палиндромы, палиндромы!Помогите пожалуста срочно!
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 2
Пол: Мужской
Реальное имя: Николай

Репутация: -  0  +


Палиндромы 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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Знаток
****

Группа: Пользователи
Сообщений: 396
Пол: Мужской

Репутация: -  9  +


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


--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






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

МЕНЬШЕ чем на 3 палиндрома приведенную строку разбить нельзя.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4





Группа: Пользователи
Сообщений: 2
Пол: Мужской
Реальное имя: Николай

Репутация: -  0  +


Я в паскале ноль можете мне написать в паскале! Пожалуста я буду очень благодарен!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Знаток
****

Группа: Пользователи
Сообщений: 396
Пол: Мужской

Репутация: -  9  +


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



--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Знаток
****

Группа: Пользователи
Сообщений: 396
Пол: Мужской

Репутация: -  9  +


Цитата(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 не знаю

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


--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






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

Кстати, если принимать строки в качестве параметра по константной ссылке (как Const st: string), то можно значительно уменьшить использование стека.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Знаток
****

Группа: Пользователи
Сообщений: 396
Пол: Мужской

Репутация: -  9  +


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


--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Знаток
****

Группа: Пользователи
Сообщений: 396
Пол: Мужской

Репутация: -  9  +


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

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


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

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

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


--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






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 -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Знаток
****

Группа: Пользователи
Сообщений: 396
Пол: Мужской

Репутация: -  9  +


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

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


--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Гость






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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 17:06
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name