Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.94
akik
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 26
#1

Рекурсия. Удаление лишних пробелов - C++

15.05.2014, 21:42. Просмотров 2705. Ответов 59
Метки нет (Все метки)

Доброго времени суток! Подскажите как реализовать с помощью рекурсии задачу: описать функцию, которая удаляет из строки все лишние пробелы.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.05.2014, 21:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия. Удаление лишних пробелов (C++):

Создание программы со своей библиотекой ( удаление элементов с N по M в строке и удаление лишних пробелов(если 2 и более оставить один)) - C++
добрый день. помогите, пожалуйста понять мои ошибки в работе. Мне нужно написать программу со своей библиотекой, которая включает в себя...

Удаление лишних пробелов - C++
Помогите пожалуйста с задачей: Разработать алгоритм и программу для удаления лишних пробелов в тексте (лишними считать> 1 пропуска).

Удаление лишних пробелов - C++
Доброго времени суток уважаемые профики С++. Хотелось бы узнать как сделать функцию удаление лишних пробелов? То есть что бы по 1...

Удаление лишних пробелов - C++
Знаю, тема изъёрзана) но вот код, и своих функций он не выполняет( #include <iostream> using namespace std; int main() {...

Удаление лишних пробелов - C++
И снова здравствуйте, Господа эксперты. Помогите пожалуйста Удалить в тексте лишние пробелы. Данные считать из файла и вывести в файл. Вот...

Удаление лишних пробелов из текста - C++
Здравствуйте, нужна помощь в написании конечного автомата. Удаление лишних пробелов из текста нужна написать в конечном автомате. Помогите...

59
Людвиг Бодмер
30.04.2015, 14:08     Рекурсия. Удаление лишних пробелов
  #31

Не по теме:

daslex, Хорошо. Нужно конечно поддерживать интригу Если в личку скинете через недельку, то буду благодарен вам.

0
daslex
1285 / 529 / 109
Регистрация: 02.08.2011
Сообщений: 2,750
30.04.2015, 21:33 #32
Вот заметил, что с включенной оптимизацией вариант Ivana обгоняет мой. O2 на 1000000 итерациях
Мой (не показанный тут вариант решения) у меня работает 14сек
Ivana у меня работает 8 сек (такая вот заметная оптимизация)

А без оптимизации как я выше писал
Мой у меня работает 24сек
Ivana 52 сек

Это в gnu gcc. Это к сведению.
0
_Ivana
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
30.04.2015, 22:47 #33
А я кстати хотел вас спросить с какими опциями оптимизации вы компилируете и сравниваете время, но постеснялся. Оптимизатор С++ вроде должен неплохо хвостовую рекурсию в итеративном виде реализовывать, безо всяких коллов и сохранения/восстановления в стек всего контекста, поэтому я и ожидал хорошего результата от своего последнего кота, теперь я доволен.
0
DiffEreD
1431 / 768 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
30.04.2015, 22:59 #34
Может не в тему, но:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <string>
#include <boost/algorithm/string/regex.hpp>
#include <boost/algorithm/string/trim.hpp>
 
int main() {
    std::string s = "   A   string    without      dowble   spaces       ";
    boost::erase_all_regex(s, boost::regex("(?<=\\w\\s)\\s+(?=\\w)"));
    boost::trim(s);
    std::cout << s << "\n";
}
0
daslex
1285 / 529 / 109
Регистрация: 02.08.2011
Сообщений: 2,750
01.05.2015, 00:15 #35

Не по теме:

Может и в тему, но рекурсия тут причем



Добавлено через 4 минуты
Мы тут решаем задачку.на Рекурсию. (на номера строк не смотреть. это все одна задача)
PHP
1
2
3
4
5
6
7
8
Циклы вообще не используем.
static нельзя.
глобальные нельзя
в функцию подается только строка и ничего больше
в функцию подается только 1 аргумент (исходная строка) и ничего более
после обработки внутри функции, строка должна быть очищенной вне функции.
Любое множество подряд идущих пробелов должно стать одним пробелом
без STL
Добавлено через 49 минут
_Ivana, А попробуйте ваш последний вариант вот в таком виде запустить. У меня получилось не то, что я ожидал.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
char s[255]; 
 
    for (size_t i=0;i<1000000;i++){
    strcpy(s,"            A       string without      double  spaces       "); //Возвращаю на исходную
    task(s); 
    }
    cout<<">"<<s<<"<"<<endl;
0
_Ivana
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
01.05.2015, 00:42 #36
daslex, запустил, без оптимизации, дождался результата, он правильный. Что я не уловил?

ЗЫ кстати, у меня есть идея алгоритма выполняющего условия и работающего за О(n) Но с ограничениями - строка только из символов начиная с некоторого кода, общее число пробелов меньше этого кода.
0
daslex
1285 / 529 / 109
Регистрация: 02.08.2011
Сообщений: 2,750
01.05.2015, 00:52 #37
Вы у меня спрашиваете, да я же хуже вас соображаю
Кидаю 2 скрина.(на 1 норм, на другом ноунорм). Код это один и тот же.
Слева VS2010, Справа gnu gcc
0
Миниатюры
Рекурсия. Удаление лишних пробелов   Рекурсия. Удаление лишних пробелов  
_Ivana
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
01.05.2015, 01:00 #38
Везде ноунорм - первый пробел нужен А у меня в студии как раз все норм Я же писал, что при первой проверке вылезаю за границы массива и так делать нельзя, я надеюсь что там не 0 и не пробел, иначе ноунорм Возможно у вас напарывается на этот случай, но мне лень было усложнять код чтобы его исключать

Добавлено через 1 минуту
ЗЫ у меня кстати тоже 10-я студия Не гонюсь за новинками.
0
daslex
1285 / 529 / 109
Регистрация: 02.08.2011
Сообщений: 2,750
01.05.2015, 01:06 #39
Но это решение получается не решением. Ну когда пол строки обрезает, это же наглость А вдруг найдется человек который возьмет пример на вооружение. И по закону подлости в самый не подходящий момент самую нужную строчку обрежет

Добавлено через 1 минуту
В release у меня вообще зависает в студии
0
_Ivana
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
01.05.2015, 01:08 #40
daslex, проверьте на строке не начинающейся с пробелов (прямо как у вас было ), только вызов замените на task(s+1); - посмотрите на результат. Должно быть норм - если проблема в том о чем я говорил.
0
daslex
1285 / 529 / 109
Регистрация: 02.08.2011
Сообщений: 2,750
01.05.2015, 01:14 #41
Так и есть. С такой строкой работает. Но
Цитата Сообщение от _Ivana Посмотреть сообщение
Тоько зачем же ограничение, что строка не начинается с пробелов
Да, а зачем оно, мы уже его дружно убрали

Добавлено через 1 минуту
Решение полностью соответствует первоначально поставленной задаче.
Но можно ведь и не цепляться к начальным пробелам и решить с ними.

Добавлено через 1 минуту
без UB
0
_Ivana
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
01.05.2015, 01:15 #42
Индийский метод решения проблем - пишем обертку, в которой склеиваем нужную строку к другой из одного символа, запускаем таск со второго и с него же возвращаем результат - фсё работает

Вы обошли вниманием мой алгоритм с ограничениями за О(n). Не интересна реализация, сильные ограничения?
0
daslex
1285 / 529 / 109
Регистрация: 02.08.2011
Сообщений: 2,750
01.05.2015, 01:18 #43
Что-то мне подсказывает, что это тот алгоритм, который я использовал. Он просто до ужаса прост.

Добавлено через 53 секунды
Хотя у меня нету ограничений. Вроде. Может и не тот.
0
_Ivana
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
01.05.2015, 01:20 #44
У меня за один пробег указателем по строке. Быстрее в принципе нельзя, теоретически. Но вот такие ограничения.
0
daslex
1285 / 529 / 109
Регистрация: 02.08.2011
Сообщений: 2,750
01.05.2015, 01:21 #45
Я обошел вниманием потому что не очень понял зачем вообще ограничения.

Добавлено через 1 минуту
Прямо с одним пробегом по строке и строка будет доступна вне функции в видоизмененной форме? Если так, то интересно.
0
01.05.2015, 01:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.05.2015, 01:21
Привет! Вот еще темы с ответами:

Удаление лишних пробелов с помощью вспомогательного массива - C++
имеется массив. пробелов между словами в первом случае 2 во втором 3. требуется сократить кол-во пробелов до 1 между каждым словом. ...

Удаление лишних пробелов в начале и конце строки. - C++
Нужно написать функцию char*alltrim(char*string) для удаления пробелов в начале и конце строки с помощью указателей. Помогите завершить...

Реализовать функцию UnSpace(s), возвращающую строку, полученную удалением из исходной всех лишних пробелов - C++
Реализовать функцию UnSpace(s), возвращающую строку, полученную удалением из исходной всех лишних пробелов (т.е. последовательность из N...

Удаление лишних символов - C++
Имеется файл txt.txt в котором 50 000 строк, просто физически это обработать тяжело. Нужно удалить все эти знаки ( ) | и 0. (Левая...


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

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

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