Форум «Всё о Паскале» _ Задачи _ сокращение строки
Автор: Bard 9.05.2007 1:40
вчера нам учитель задал такую вот задачку:
вводиться строка из латинских букв требуеться ее сжать...
Цитата
например: если AABCCCCC то надо ее сжать таким образом 2AB5C или AAAAAAAAAABABABCCD то 10A2(BA)B2CD Например, последовательность "ABABCABABC" можно записать как 2(2(AB)C)
помогите с алгоритмом...
Добавлено через 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 9.05.2007 2:30
Если не то же самое - то ОЧЕНЬ похоже: http://forum.pascal.net.ru/index.php?s=&showtopic=3476&view=findpost&p=31133
Автор: Bard 9.05.2007 5:30
большое спасибо но самая главная трудность вот сдесь:
Цитата
AAAAAAAAAABABABCCD = 10A2(BA)B2CD
буду очень благодарен если поможете с реализацией этого алгоритма...
Автор: Malice 10.05.2007 3:39
Приведенная ссылка - очень похожая задача, но не то.. Разница именно в скобках, т.е. в когда повторяется не 1 символ, а несколько. Здесь однозначно пахнет рекурсией..
Автор: volvo 10.05.2007 12:49
Bard, а можно вопрос? Почему, собственно, вариант: AAAAAAAAAABABABCCD преобразуется как 10A2(BA)B2CD, а не как 9A3(AB)2CD?
Автор: samec 10.05.2007 13:06
Цитата(volvo @ 10.05.2007 12:49)
Bard, а можно вопрос? Почему, собственно, вариант: AAAAAAAAAABABABCCD преобразуется как 10A2(BA)B2CD, а не как 9A3(AB)2CD?
судя повсему, потому что сначала перобразовываем одиночные симполы, потом обрабатываем пары, затем триады и т.д.
Автор: volvo 10.05.2007 13:12
Интересно... Максимальное сжатие достигается как раз обратным процессом - сначала все последовательности длины Length(s) div 2, и потом по убывающей до 1...
Кстати, если скомбинировать программу по той ссылке, что я привел выше и вот по этой: http://forum.pascal.net.ru/index.php?s=&showtopic=15899&view=findpost&p=94061
то очень может быть, что получится решить задачу... Надо будет попробовать.
Автор: Malice 10.05.2007 23:52
Набросал решение "в лоб":
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.
На контрольных примерах работает, но по сути есть ошибка, какая - не скажу, чтоб с толку не сбивать
Автор: Bard 12.05.2007 0:36
Цитата
судя повсему, потому что сначала перобразовываем одиночные симполы, потом обрабатываем пары, затем триады и т.д.
ты абсолютно прав ... но есть еще одна загвоздка ...
вот она: если вводиться AAAABBBAAAABBBC то надо выдать 2(4A3B)C потому что AAAABBBAAAABBBC можно записать как 4A3B4A3BC а эту строку - как 2(4A3B)C...
кстати ,Malice, я не понял твой алгоритм для этой задачи ...
Цитата
If не трудно then begin объясни пожалуйста; буду очень благодарен; end;...
Добавлено через 10 мин. Malice, а где же ошибка ... программа проходит через все тесты которые учитель нам дал ...
Автор: Bard 12.05.2007 23:47
Malice, ну не томи ... скажи где же ошибка в твоей программе а то я испробовал почти уже 20-30 тестов но все равно ответ верный ...
Автор: Malice 13.05.2007 1:53
Цитата(Bard @ 12.05.2007 20:47)
Malice, ну не томи ... скажи где же ошибка в твоей программе а то я испробовал почти уже 20-30 тестов но все равно ответ верный ...
Ну если устраивает, тогда ладно.. Просто немного коряво с помощью второй функции повторно сжимать, возможны накладки. С алгоритмом то разобрался ?
Автор: Bard 13.05.2007 15:43
большое тебе спасибо ... я понял где у тебя глюк ... сейчас подправлю ...