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

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

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

 
 Ответить  Открыть новую тему 
> сокращение строки, помогите решить задачку...
сообщение
Сообщение #1


Учиться, учиться еще раз учиться
***

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

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


вчера нам учитель задал такую вот задачку: 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


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Если не то же самое - то ОЧЕНЬ похоже:
Задача про строки и повторяющиеся символы.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Учиться, учиться еще раз учиться
***

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

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


большое спасибо good.gif но самая главная трудность вот сдесь:
Цитата
AAAAAAAAAABABABCCD = 10A2(BA)B2CD
wacko.gif
буду очень благодарен если поможете с реализацией этого алгоритма... rolleyes.gif


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Профи
****

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

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


Приведенная ссылка - очень похожая задача, но не то.. Разница именно в скобках, т.е. в когда повторяется не 1 символ, а несколько. Здесь однозначно пахнет рекурсией..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






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

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Бывалый
***

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

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


Цитата(volvo @ 10.05.2007 12:49) *

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

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


Гость






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

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

то очень может быть, что получится решить задачу... Надо будет попробовать.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Профи
****

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

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


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


Учиться, учиться еще раз учиться
***

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

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


Цитата

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


ты абсолютно прав 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 -


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Учиться, учиться еще раз учиться
***

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

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


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


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Профи
****

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

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


Цитата(Bard @ 12.05.2007 20:47) *

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

Ну если устраивает, тогда ладно.. Просто немного коряво с помощью второй функции повторно сжимать, возможны накладки. С алгоритмом то разобрался ?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Учиться, учиться еще раз учиться
***

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

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


большое тебе спасибо good.gif ... я понял где у тебя глюк yes2.gif ... сейчас подправлю smile.gif ...

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

Thanks


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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