Помощь - Поиск - Пользователи - Календарь
Полная версия: сокращение строки
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Bard
вчера нам учитель задал такую вот задачку: smile.gif

вводиться строка из латинских букв требуеться ее сжать...

Цитата

например:
если AABCCCCC то надо ее сжать таким образом 2AB5C
или
AAAAAAAAAABABABCCD то 10A2(BA)B2CD
Например, последовательность "ABABCABABC" можно записать как 2(2(AB)C)


помогите с алгоритмом... blum.gif

Добавлено через 5 мин.
а вот и оригинал задачи:
Цитата
Сжатие

Рассмотрим последовательность строк, состоящую только из больших латинских букв. Например, последовательность "AAAABBBAAAABBBC" - одна из таких последовательностей. Ее длина 15 символов. Поскольку в последовательности могут быть только буквы, можно заменить несколько подряд идущих одинаковых букв одной такой буквой, поставив перед ней натуральное число - количество повторений буквы.
Например, вышеупомянутую последовательность можно записать как "4A3B4A3BC" и длина такой записи будет только 9 символов. Легко видеть, что группа 4A3B повторяется в этой записи два раза подряд. Запишем это повторение, применяя скобки для выделения повторяющейся группы, а перед группой напишем количество ее повторений: 2(4A3B)C . Длина этой последовательности уже только 8 символов. Разумеется, могут случиться повторяющиеся группы на нескольких уровнях. Например, последовательность "ABABCABABC" можно записать как 2(2(AB)C)

Задача
Напишите программу OLI5B, которая по данной исходной последовательности находит и выводит сжатую последовательность.

Формат входных данных (файл B.IN )
В единственной строке текстового файла B.in дана исходная последовательность. Ее длина не превосходит 250 символов

Формат выходных данных (файл B.OUT )
В единственной строке текстового файла B.out следует вывести сжатую последовательность.

Например:
Тесты Входные данные - B.IN Выходные данные - B.OUT
1 AABCCCCC 2AB5C
2 EEEEEEEEEEEEEEEEEEEEEU 21EU
3 AAAAAAAAAABABABCCD 10A2(BA)B2CD
volvo
Если не то же самое - то ОЧЕНЬ похоже:
Задача про строки и повторяющиеся символы.
Bard
большое спасибо good.gif но самая главная трудность вот сдесь:
Цитата
AAAAAAAAAABABABCCD = 10A2(BA)B2CD
wacko.gif
буду очень благодарен если поможете с реализацией этого алгоритма... rolleyes.gif
Malice
Приведенная ссылка - очень похожая задача, но не то.. Разница именно в скобках, т.е. в когда повторяется не 1 символ, а несколько. Здесь однозначно пахнет рекурсией..
volvo
Bard, а можно вопрос? Почему, собственно, вариант:
AAAAAAAAAABABABCCD преобразуется как 10A2(BA)B2CD, а не как 9A3(AB)2CD?
samec
Цитата(volvo @ 10.05.2007 12:49) *

Bard, а можно вопрос? Почему, собственно, вариант:
AAAAAAAAAABABABCCD преобразуется как 10A2(BA)B2CD, а не как 9A3(AB)2CD?

судя повсему, потому что сначала перобразовываем одиночные симполы, потом обрабатываем пары, затем триады и т.д.
volvo
Интересно... Максимальное сжатие достигается как раз обратным процессом - сначала все последовательности длины Length(s) div 2, и потом по убывающей до 1...

Кстати, если скомбинировать программу по той ссылке, что я привел выше и вот по этой:
Интересная задача на рекурсию

то очень может быть, что получится решить задачу... Надо будет попробовать.
Malice
Набросал решение "в лоб":
uses crt;
function pack2 (s:string):string;
var n,i:integer;
rs,q:string;
begin
for i:=1 to length (s) div 2 do begin
q:=copy (s,1,i); n:=1;
while copy (s,length(q)*n+1,length(q))=q do inc (n);
if n>1 then begin
str (n,rs); if length (q)=1 then
pack2:=rs+pack2(q)+pack2 (copy (s,length(q)*n+1,255)) else
pack2:=rs+'('+pack2(q)+')'+pack2 (copy (s,length(q)*n+1,255));
exit;
end;
end;
if length (s)<2 then pack2:=s else
pack2:=s[1]+pack2(copy (s,2,255));
end;

function pack (s:string):string;
begin
s:=pack2(s);
while (s<>pack2(s)) and (length(pack2(s))<length (s)) do s:=pack2(s);
pack:=s;
end;

var s:string;
begin
clrscr;
s:='AAAAAAAAAABABABCCD'; writeln (s,' = ',pack(s));
s:='ABABCABABC'; writeln (s,' = ',pack(s));
end.


На контрольных примерах работает, но по сути есть ошибка, какая - не скажу, чтоб с толку не сбивать rolleyes.gif
Bard
Цитата

судя повсему, потому что сначала перобразовываем одиночные симполы, потом обрабатываем пары, затем триады и т.д.


ты абсолютно прав good.gif ... но есть еще одна загвоздка wink.gif ...

вот она: mega_chok.gif
если вводиться AAAABBBAAAABBBC то надо выдать 2(4A3B)C
потому что AAAABBBAAAABBBC можно записать как 4A3B4A3BC а эту строку - как 2(4A3B)C...

кстати ,Malice, я не понял твой алгоритм для этой задачи nea.gif ...
Цитата
If не трудно then begin объясни пожалуйста; буду очень благодарен; end;...


Добавлено через 10 мин.
Malice, а где же ошибка blink.gif ... программа проходит через все тесты которые учитель нам дал good.gif ...
Bard
Malice, ну не томи mega_chok.gif ... скажи где же ошибка в твоей программе а то я испробовал почти уже 20-30 тестов но все равно ответ верный wacko.gif ...
Malice
Цитата(Bard @ 12.05.2007 20:47) *

Malice, ну не томи mega_chok.gif ... скажи где же ошибка в твоей программе а то я испробовал почти уже 20-30 тестов но все равно ответ верный wacko.gif ...

Ну если устраивает, тогда ладно.. Просто немного коряво с помощью второй функции повторно сжимать, возможны накладки. С алгоритмом то разобрался ?
Bard
большое тебе спасибо good.gif ... я понял где у тебя глюк yes2.gif ... сейчас подправлю smile.gif ...

P.S. да с алгоритмом разобрался lol.gif

Thanks
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.