|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
21.03.2011, 18:04 | #1 |
Регистрация: 21.03.2011
Сообщений: 7
|
Динамическое программирование.Удаление строки
Дана строка S, состоящая из n маленьких латинских букв. За один ход Вам разрешается удалить один или несколько подряд идущих одинаковых символов. Необходимо удалить все символы из строки S за минимальное количество ходов.
Буду признателен за разъяснение алгоритма для данной задачи,учитывая,что её нужно решать методами динамического программирования. Я в нём абсолютный ноль, так что надеюсь тема не будет удалена из-за отсутствия кода.Я сам его напишу,мне нужны советы по поводу алгоритма решения. Заранее спасибо. |
21.03.2011, 20:54 | #2 |
Регистрация: 21.03.2011
Сообщений: 7
|
Я так понял,что нужно в матрицу NxN (N -размерность строки) начиная с главной диагонали,вписывать количество минимальных удалений для подстрок длины 1,2 и т.д
Подскажите формулу перехода для таких состояний. Я надеюсь на форуме кто-нибудь в состоянии мне помочь? |
22.03.2011, 04:10 | #3 |
Регистрация: 21.03.2011
Сообщений: 7
|
КТО-НИБУДЬ В СОСТОЯНИИ ДОПОЛНИТЬ КОД ИЛИ ОБЬЯСНИТЬ ЧТО НЕ ТАК?
Код:
___________ Код нужно оформлять по правилам: тегом [CODE]..[/СODE] (это кнопочка с решёточкой #) Не забывайте об этом! Модератор. Последний раз редактировалось Serge_Bliznykov; 22.03.2011 в 09:05. |
22.03.2011, 08:32 | #4 |
кривокодер ;)
Форумчанин
Регистрация: 20.06.2008
Сообщений: 707
|
в Си не силен, могу помочь только с логикой...
читаем символ Х пока Х+1 равен по значению Х то удаляем Х+1, и входим в новую интерацию ЭТОГО цикла. когда Х и Х+1 не равны - инкрементим Х, и начинаем заново, если не достигнут конец строки. Если нужно могу написать пример на паскале...
"А как написать праграму?, "ришыти задачьку очинь нада" ©с форума. Жить становится интереснее, жить становится веселее...
{Быть или не быть} {Неуспешный суицид} |
22.03.2011, 23:40 | #5 |
Регистрация: 21.03.2011
Сообщений: 7
|
Напиши,если не трудно. Хотя мне кажется,идея не верна - на строке
авсрра - у тебя будет 4 хода? |
23.03.2011, 10:46 | #6 |
personality
Старожил
Регистрация: 28.04.2009
Сообщений: 2,882
|
Вообще, задача тут довольно не тривиальная... как объяснить железной башке, что человек специально может задавать такие аццкие строки...
Думаю, сперва надо произвести посчет количества каждой буквы и удаление одиночных символов(т.е. совем одиночный а не одиночно стоящих), ну тут многие догадаются )) потом, думаю, можно подсчитать группы одинаковых символов, т.е. подряд идущих. ну и по идее организовать цикл по всем этим группам, где рекурсивно вызывать такой же цикл (но уже с удаленной на предыдущем шаге группой) и счетом величины стека рекурсии... в итоге каждая рекурсия долна вернуть величину шагов по вызову самой себя, если мы начнем с некоей группы. Запутанно, конечно.. и не четко условие выбора группы на каждом шаге рекурсии. Ещё есть идея, но даже не знаю как она будет работать... сделать процедуру которая считает за сколько шагов можно сделать самую большую группу символов, ну и проверяем если удаление мвалых подгрупп этих символов выгоднее чем составление большой группы, то переходим к рассмотрению задачи для следующей максимально-символьной группе, но с уже удаленными символами предыдущей группы. Минус сего метода, наверное, в том что промежуточное составленние группы (т.е. не максимально возможной) мб выгоднее, чем удаление малых групп... |
23.03.2011, 12:59 | #7 | |
кривокодер ;)
Форумчанин
Регистрация: 20.06.2008
Сообщений: 707
|
Цитата:
Код:
Этот алгоритм уберет только первый повторяющийся символ... В каждом проходе.
"А как написать праграму?, "ришыти задачьку очинь нада" ©с форума. Жить становится интереснее, жить становится веселее...
{Быть или не быть} {Неуспешный суицид} Последний раз редактировалось Johnson; 23.03.2011 в 13:04. |
|
30.03.2011, 00:03 | #8 | |
Регистрация: 21.03.2011
Сообщений: 7
|
Цитата:
Народ,помогите довести до ума код,защитил алгоритм у преподавателя,а нормальная реализация не выходит. Алгоритм - пусть в строке S содержится N символов. Создаём матрицу NxN,на главной диагонали расставляем единицы-кол-во удалений для подстроки длины 1,на диагонали над главной - 2,или 1 в зависимости от того,состоит ли подстрока длинны 2 из одинаковых или разных символов. Далее, увеличивая длины подстрок, пользуемся следующими формулами: А(i,j)-подстрока,внутри неё бегаем по К Если S(i)!=S(k),то в матрицу => A(i,j)=1+A(i+1,j) Иначе - S(i)==S(k) -в матрицу => A(i,j)=MIN(A(i+1,k-1)+A(k,j) Таким образом,в правом верхнем углу матрицы будет ответ. |
|
30.03.2011, 00:08 | #9 |
Регистрация: 21.03.2011
Сообщений: 7
|
Код:
|
14.10.2014, 15:52 | #10 |
Новичок
Джуниор
Регистрация: 14.10.2014
Сообщений: 1
|
zartos91, мне кажется, у Вас что-то не так. Например:
abcba - очевидно, что 3 удаления, но Ваш код выдал 4. acdcbbc - 4 удаления - у Вас 6. и т.д. Последний раз редактировалось Summer_Time; 14.10.2014 в 16:03. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
динамическое программирование | stefan0202 | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 07.02.2011 22:05 |
Динамическое программирование | Daniya.ru | Общие вопросы .NET | 2 | 19.12.2010 11:40 |
Программирование на shell. Удаление строки. | 66promises | Помощь студентам | 0 | 23.05.2010 15:08 |
Динамическое программирование | joey_ramone | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 23.04.2010 13:51 |
Динамическое программирование. | MAKEDON | Помощь студентам | 6 | 26.08.2009 14:10 |