Форум программистов, компьютерный форум CyberForum.ru

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

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

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

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

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

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

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Людвиг Бодмер
30.04.2015, 14:08     Рекурсия. Удаление лишних пробелов
  #31

Не по теме:

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
daslex
1271 / 516 / 106
Регистрация: 02.08.2011
Сообщений: 2,665
30.04.2015, 21:33     Рекурсия. Удаление лишних пробелов #32
Вот заметил, что с включенной оптимизацией вариант Ivana обгоняет мой. O2 на 1000000 итерациях
Мой (не показанный тут вариант решения) у меня работает 14сек
Ivana у меня работает 8 сек (такая вот заметная оптимизация)

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

Это в gnu gcc. Это к сведению.
_Ivana
3042 / 1729 / 150
Регистрация: 01.03.2013
Сообщений: 4,908
Записей в блоге: 2
30.04.2015, 22:47     Рекурсия. Удаление лишних пробелов #33
А я кстати хотел вас спросить с какими опциями оптимизации вы компилируете и сравниваете время, но постеснялся. Оптимизатор С++ вроде должен неплохо хвостовую рекурсию в итеративном виде реализовывать, безо всяких коллов и сохранения/восстановления в стек всего контекста, поэтому я и ожидал хорошего результата от своего последнего кота, теперь я доволен.
DiffEreD
1429 / 766 / 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";
}
daslex
1271 / 516 / 106
Регистрация: 02.08.2011
Сообщений: 2,665
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;
_Ivana
3042 / 1729 / 150
Регистрация: 01.03.2013
Сообщений: 4,908
Записей в блоге: 2
01.05.2015, 00:42     Рекурсия. Удаление лишних пробелов #36
daslex, запустил, без оптимизации, дождался результата, он правильный. Что я не уловил?

ЗЫ кстати, у меня есть идея алгоритма выполняющего условия и работающего за О(n) Но с ограничениями - строка только из символов начиная с некоторого кода, общее число пробелов меньше этого кода.
daslex
1271 / 516 / 106
Регистрация: 02.08.2011
Сообщений: 2,665
01.05.2015, 00:52     Рекурсия. Удаление лишних пробелов #37
Вы у меня спрашиваете, да я же хуже вас соображаю
Кидаю 2 скрина.(на 1 норм, на другом ноунорм). Код это один и тот же.
Слева VS2010, Справа gnu gcc
Миниатюры
Рекурсия. Удаление лишних пробелов   Рекурсия. Удаление лишних пробелов  
_Ivana
3042 / 1729 / 150
Регистрация: 01.03.2013
Сообщений: 4,908
Записей в блоге: 2
01.05.2015, 01:00     Рекурсия. Удаление лишних пробелов #38
Везде ноунорм - первый пробел нужен А у меня в студии как раз все норм Я же писал, что при первой проверке вылезаю за границы массива и так делать нельзя, я надеюсь что там не 0 и не пробел, иначе ноунорм Возможно у вас напарывается на этот случай, но мне лень было усложнять код чтобы его исключать

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

Добавлено через 1 минуту
В release у меня вообще зависает в студии
_Ivana
3042 / 1729 / 150
Регистрация: 01.03.2013
Сообщений: 4,908
Записей в блоге: 2
01.05.2015, 01:08     Рекурсия. Удаление лишних пробелов #40
daslex, проверьте на строке не начинающейся с пробелов (прямо как у вас было ), только вызов замените на task(s+1); - посмотрите на результат. Должно быть норм - если проблема в том о чем я говорил.
daslex
1271 / 516 / 106
Регистрация: 02.08.2011
Сообщений: 2,665
01.05.2015, 01:14     Рекурсия. Удаление лишних пробелов #41
Так и есть. С такой строкой работает. Но
Цитата Сообщение от _Ivana Посмотреть сообщение
Тоько зачем же ограничение, что строка не начинается с пробелов
Да, а зачем оно, мы уже его дружно убрали

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

Добавлено через 1 минуту
без UB
_Ivana
3042 / 1729 / 150
Регистрация: 01.03.2013
Сообщений: 4,908
Записей в блоге: 2
01.05.2015, 01:15     Рекурсия. Удаление лишних пробелов #42
Индийский метод решения проблем - пишем обертку, в которой склеиваем нужную строку к другой из одного символа, запускаем таск со второго и с него же возвращаем результат - фсё работает

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

Добавлено через 53 секунды
Хотя у меня нету ограничений. Вроде. Может и не тот.
_Ivana
3042 / 1729 / 150
Регистрация: 01.03.2013
Сообщений: 4,908
Записей в блоге: 2
01.05.2015, 01:20     Рекурсия. Удаление лишних пробелов #44
У меня за один пробег указателем по строке. Быстрее в принципе нельзя, теоретически. Но вот такие ограничения.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.05.2015, 01:21     Рекурсия. Удаление лишних пробелов
Еще ссылки по теме:

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

Фиксированная точка в printf() и удаление лишних нулей - C++
Есть число 0.000000000001 и мне его нужно вывести на экран, но если написать printf(&quot;%.37f&quot;, 0.000000000001); выводится...

Удаление лишних (подряд идущих) разделителей при разделении строки - C++
Здравствуйте! Задача такая: вводятся в массив razd N разделителей(ну там что то на подобии &quot;!&quot; , &quot;.&quot; , &quot;?&quot; , &quot;пробел&quot; и тд... только этот...

Удаление пробелов - C++
Доброго времени суток ув. форумчане! Дали задание до 6.11, вчера вроде понял как делать, а сегодня что-то голова не варит. В общем сама...

Удаление пробелов - C++
Доброго времени суток ув. форумчане! Дали задание до 6.11, вчера вроде понял как делать, а сегодня что-то голова не варит. В общем сама...


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

Или воспользуйтесь поиском по форуму:
daslex
1271 / 516 / 106
Регистрация: 02.08.2011
Сообщений: 2,665
01.05.2015, 01:21     Рекурсия. Удаление лишних пробелов #45
Я обошел вниманием потому что не очень понял зачем вообще ограничения.

Добавлено через 1 минуту
Прямо с одним пробегом по строке и строка будет доступна вне функции в видоизмененной форме? Если так, то интересно.
Yandex
Объявления
01.05.2015, 01:21     Рекурсия. Удаление лишних пробелов
Ответ Создать тему
Опции темы

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