Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
Владислав_95
0 / 0 / 0
Регистрация: 30.09.2013
Сообщений: 5
1

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

15.03.2014, 14:55. Просмотров 955. Ответов 2
Метки нет (Все метки)

Задана строка, символы которой могут повторяться. За один ход разрешается вычеркнуть в любом месте строки один или несколько одинаковых символов, идущих в строке подряд. Нужно удалить все символы строки с помощью наименьшего количества вычеркиваний.
Вход. Строка длиной не больше 255.
Выход. Минимальное количество операций, с помощью которых можно удалить все символы строки.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.03.2014, 14:55
Ответы с готовыми решениями:

Дана строка. Удалить из строки все двойные символы. Пример: “asddewwf” → “asdewf”
Дана строка. Удалить из строки все двойные символы. Пример: “asddewwf” →...

Дана строка А и символ s. Удалить из строки символы, размещенные в символа s
Дана строка А и символ s. Удалить из строки символы, размещенные до символа s....

Создать очередь, содержащую любые символы. Удалить из очереди все символы, не являющиеся буквами или цифрами
Используя динамические структуры, реализовать следующие задания....

Удалить из строки все символы ‘+’
Удалить из строки все символы ‘+’. Преобразованную строку вывести на экран.

Удалить из строки все повторяющиеся символы
как удалить со строки все повторяющиеся символы???? заранее благодарен!

2
mymedia
193 / 193 / 120
Регистрация: 27.05.2011
Сообщений: 544
15.03.2014, 16:40 2
Лучший ответ Сообщение было отмечено Владислав_95 как решение

Решение

Так? Я правильно понял?
C++
1
2
3
4
5
6
7
8
9
10
11
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
int main()
{
    using namespace std;
    string str;
    getline(cin,str);
    cout << distance(str.begin(), unique(str.begin(), str.end()));
}
0
Владислав_95
0 / 0 / 0
Регистрация: 30.09.2013
Сообщений: 5
16.03.2014, 08:05  [ТС] 3
Пример. Вход: 1343223; выход: 4.

Анализ задачи. В строке 1343223 из примера можно вычеркнуть 22 (получится

13433), затем 1 и 4, а затем сразу три символа 3, т.е. всего четыре вычеркивания.

Предварительно "сожмем" слово, заменив каждую последовательность одинако-

вых символов, идущих подряд, одним таким символом, например, из 111223114

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

худшем случае. Однако в среднем выигрыш будет существенным за счет уменьшения

числа подзадач (сложность "сжатия" линейна и не влияет на общую оценку — см

задачу 5.4). Кроме того, "сжатие" гарантирует, что все соседние символы различны.

Пусть а [1] …а [т] — строка, т — ее длина. Часть строки a [i] …а [ j ], состоя-

щую из всех символов с i’-го по j-Vi включительно, будем называть i…/-подстрокой

Серия подзадач очевидна: За какое минимально возможное количество вычеркивании

можно удалить u.j-подстроку? Нужная задача будет одной из задач серии, а именно

задачей размером (1, т).

Тривиальные подзадачи, решение которых очевидно — это подзадачи вида (i, i

(одиночный символ удаляется за один ход) и вида (i, i+1) (двухсимвольные подстро-

ки, состоящие из разных символов, удаляются за два хода).

Обозначим минимальное количество действий для удаления {..у-подстроки

через Тц. Оптимальным решением нетривиальной (1,у)-подзадйчи может быть такое:

перебрать все к, удовлетворяющие i
подстроку.

Таким образом, при a\i] *а [ j ] окончательный оптимум (/,./)-подзадачи достаточ-

но искать как ТҐ= Kv (согласно (13.14)), а при a [i] = а [j] следует рассмотреть Ку

и ЛГ* и выбрать из них меньшее.

Но и этого мало. Если одинаковые крайние символы «’…/-подстроки повторяются

внутри нее, то может оказаться, что выгоднее всего сначала удалить все подстроки,

разделяющие эти вхождения, а затем зачеркнуть все эти символы за один ход

(например, слово 1213141 лучше всего обработать, вычеркнув 2, 3, 4, а затем все

единицы за один ход).

Однако "может оказаться" не означает "непременно окажется". Рассмотрим слово

1231413215161. Любое его оптимальное решение (например, сначала вычеркнуть 4,

затем новообразуемые подстроки 11, 33, 22, затем 5, б, и, наконец, оставшиеся 1111)

требует удалять вторую и третью справа единицы (в позициях 9 и 11) вместе с крайними

(в позициях 1 и 13), а единицы в позициях 4 и 6 должны быть вычеркнуты раньше. Таким

образом, на последний ход нужно оставить много единиц, но не все.

Может показаться, что для реализации этой идеи нужен полный перебор под-

множеств вхождений символов, одинаковых с a [i] и а [ j ]. Однако это не так бла-

годаря следующей идее.

Пусть для некоторой /../’-подстроки крайние символы a[i], a[j] совпадают

с некоторым внутренним а [к]. Тогда удаление сначала i+l..fc-1-подстроки, затем

k+\..j-\ – подстроки, затем трех одинаковых символов a[i]a[k]a[j] можно услов-

но свести к тому, что удаляется /..^-подстрока (но символ а [к] при этом загадочным

образом остается), а затем Ј. ../-подстрока. Из суммы количеств ходов по удалению

этих подстрок вычитается 1, поскольку при вычислении Т^+Т^ вычеркивание симво-

ла а [к] считается дважды:

Очевидно, что формула (13.16) позволяет собирать под одно вычеркивание много

одинаковых символов (если оптимальное решение хотя бы одной из (/,&)- и (k,j)-

подзадач получено по этой же формуле), не требуя, чтобы все одинаковые символы

вычеркивались обязательно за один раз.

Как и в задачах об умножении матриц и о максимальном значении выражения,

формулы (13.14)—(13.17) следует реализовать либо с помощью рекурсии с запомина-

нием, либо итеративно заполнить таблицу для 7^, двигаясь от главной диагонали по

линиям, параллельным ей, пока не придем в угловой элемент Т1т.

Вспомогательные величины Ку, K’tj и используются только для вычисления

Ту (при тех же i иу) и в дальнейшем их помнить не обязательно. Однако, реализуя

алгоритм с помощью рекурсии с запоминанием, эти вспомогательные значения все-

таки придется хранить (в массивах или в программном стеке). Так что преимущества

итеративного заполнения таблицы проявляются в данной задаче несколько ярче

чем в предыдущих.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2014, 08:05

Удалить из строки все числовые символы
Здравствуйте, помогите, пожалуйста сделайте задач. Пользователь вводит с...

Удалить из строки все символы, не являющиеся буквами
1. Дана символьная строка. Удалить из нее все символы не являющиеся буквами.

Удалить из строки s1 все символы, встречающиеся в строке s2.
Удалить из строки s1 все символы, встречающиеся в строке s2 А вот здесь как...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru