Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.90/58: Рейтинг темы: голосов - 58, средняя оценка - 4.90
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 26
1

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

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

Author24 — интернет-сервис помощи студентам
Доброго времени суток! Подскажите как реализовать с помощью рекурсии задачу: описать функцию, которая удаляет из строки все лишние пробелы.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.05.2014, 21:42
Ответы с готовыми решениями:

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

Удаление лишних пробелов
Помогите пожалуйста с задачей: Разработать алгоритм и программу для удаления лишних пробелов в...

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

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

59
daslex
29.04.2015, 23:39     Рекурсия. Удаление лишних пробелов
  #21

Не по теме:

Только учтите, мне решение не надо, если кто будет тут лазать в будущем, очень очевидно непонятные им моменты лучше пояснить в комментариях. И в спойлер. Кому будет интересно пусть сами решают.

0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
30.04.2015, 01:06 22
Не за 5 секунд, но нарисовал кота - все функции с единственным параметром-указателем, никаких стрингов и stl, конечно неоптимально, но зато в рамках условии:
C++
1
2
3
4
5
6
7
8
9
bool bad (char *s) {*(s-1)=*s; return *s ? bad(s+1) : false;}
bool good(char *s) {return *s ? (*s==' '&&*(s+1)==' ' ? bad(s+1) : good(s+1)) : true;}
void task(char *s) {if (!good(s)) task(s);}
 
int _tmain(int argc, _TCHAR* argv[]) {
    char s[] = "            A       string      without      dowble   spaces       ";
    task(s); cout << ">" << s << "<" << endl;
    system("pause"); return 0;
}
Добавлено через 4 минуты
daslex, спасибо за вызванный интерес, не сразу получается придумать некоторые моменты, но имхо эти идеи могут пригодиться в будущем - например, передача управления другой рекурсивной функции при неудаче.
2
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
30.04.2015, 01:14 23
Я когда делал, я использовал только 1 функцию, поэтому вставил в условие, что строка не начинается с пробелов. Так у меня получилось, что это имело значение.
Но ваше решение полностью соответствует условию.
Вот ерунда ли ерунда? Не 5 же секунд понадобилось

Мое решение в разы не оптимальнее. Смысл-то не в практическом применении в бою, а в самом упражнении
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
30.04.2015, 01:21 24
Ну я просто после общения с некоторыми языками воспринимаю функции как объекты первого класса (типа как переменные) и не стесняюсь их накидывать Хотя согласен, упражнение получилось интересное. Спасибо вам еще раз за предоставленную возможность немножко подумать. Некоторые общие идеи моего кота мне даже понравились.

ЗЫ хотя я слабо представляю как может быть решение еще менее оптимально, чем мое последнее. Типа оно на каждый инкремент указателя считает Фибоначчи экспоненциальной рекурсией просто так для большей неоптимальности?
0
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
30.04.2015, 01:45 25
Хотя вру, наверное пооптимальнее все-таки у меня получилось.
на 100000 итерациях с копированием строки для возврата в исходное состояние ваш вариант у меня срабатывает 6 (по time.h clock_t), а мой 1

Вот так вот.

Добавлено через 4 минуты
Ну у меня пробелы вначале не удаляет' и вообще некорректно со строкой с пробелами вначале работает.

Добавлено через 17 минут
Теперь удаляет
Всего 1 рекурсивная функция. Всего 1 аргумент. Если у меня на ПК на 100000 итерациях, с strcpy для возврата испорченной строки в исходное состояние внутри итераций, вариант Ivana работает 6, то мой вариант срабатывает за 2. Так что если будет желание подумать, тут есть над чем еще подумать. Упражнение не исчерпало свой лимит.
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
30.04.2015, 01:46 26
daslex, кстати, в этом разделе так много новых тем появляется, что я не успеваю их все мониторить на предмет интересности. Если что - зовите меня через личку, как очередной раз надо будет написать бесциклового рекурсивного кота, с удовольствием попробую реализовать
0
Iridiscent
30.04.2015, 02:18
  #27

Не по теме:

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

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <conio.h>
#include <ctime>
#include <iomanip>
#include <stdlib.h>
#include <sstream>
#include <cmath>
using namespace std;
int *random(int y,int x);
void cl(char *p,int y,int x);
void vivod(char *p,int y,int x);
int main()
 
{
int y=13,x=80;
srand(time(NULL));
int *ab=random(y,x);
int d=0,j,i;
cout<<*(ab+1);
char *p = new char[y*x];
cl(p,y,x);
*((p+(*(ab+1)))+(y*(*(ab))))='x';
vivod(p,y,x);
}
void vivod(char *p,int y,int x)
{
    for(int i=0;i<y;i++)
    for(int j=0;j<x;j++)
{
    cout<<*((p+j)+(y*i));
if(j==x-1&&x<80)cout<<endl;
 
}
}
void cl(char *p,int y,int x)
{
   for(int i=0;i<y;i++)
    for(int j=0;j<x;j++)
{
    *((p+j)+(y*i))=' ';
if(j==x-1&&x<80)cout<<endl;
}
}
int *random(int y,int x)
{
srand(time(NULL));
int a[6];
int *ab;
ab=&a[0];
int z;
a[0]=rand()%y;a[1]=rand()%x;
a[2]=rand()%y;a[3]=rand()%x;
a[4]=rand()%y;a[5]=rand()%x;
 
return ab;
}

*((p+(ab[1]))+(y*(ab[0])))='x'; тоже вылазит

0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
30.04.2015, 05:04 28
daslex, а попробуйте вот такого кота - имхо он гораздо оптимальнее по скорости и всего 2 функции. (Я знаю что при первой проверке я залезаю за границы массива )
C++
1
2
3
4
5
6
7
8
char *fnd(char *s) {char *p = s-1; return *p==' '||*p==0 ? fnd(p) : s+(*s==' ');}
void task(char *s) {char *d = fnd(s); *d=*s; if (*s) {if (d<s) *s=0; task(s+1);}}
 
int _tmain(int argc, _TCHAR* argv[]) {
    char s[] = "            A       string without      double  spaces       ";
    task(s); cout << ">" << s << "<" << endl;
    system("pause"); return 0;
}
1
378 / 375 / 213
Регистрация: 29.03.2013
Сообщений: 867
30.04.2015, 10:21 29
Интересно и познавательно, спасибо Я бы так не написал конечно.
daslex, а можно всё-таки ваш вариант увидеть под спойлером?
0
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
30.04.2015, 12:47 30
_Ivana, Вот этот последний на 1000000 итерациях (c strcpy внутри)
в моем случае срабатывет за 24 сек
в вашем случае 52 сек

Людвиг Бодмер, Я показывать сейчас не хочу. Боюсь убить интерес в начинании. Может в течении недели если решатели не появятся, я вам в личку скину? Мой вариант читается проще чем предложенные. Ну и работает побыстрее слегка. Одна функция же. Но любым привычным итеративным алгоритмам проигрывает. И скорее всего существуют решения оптимальнее того, что у меня есть.

Надеюсь вы не против.

Я не шучу, когда говорю, что все, что я смог решить по определению просто
1
Людвиг Бодмер
30.04.2015, 14:08
  #31

Не по теме:

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

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

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

Это в gnu gcc. Это к сведению.
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
30.04.2015, 22:47 33
А я кстати хотел вас спросить с какими опциями оптимизации вы компилируете и сравниваете время, но постеснялся. Оптимизатор С++ вроде должен неплохо хвостовую рекурсию в итеративном виде реализовывать, безо всяких коллов и сохранения/восстановления в стек всего контекста, поэтому я и ожидал хорошего результата от своего последнего кота, теперь я доволен.
0
1458 / 795 / 257
Регистрация: 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
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
01.05.2015, 00:15 35

Не по теме:

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



Добавлено через 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
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
01.05.2015, 00:42 36
daslex, запустил, без оптимизации, дождался результата, он правильный. Что я не уловил?

ЗЫ кстати, у меня есть идея алгоритма выполняющего условия и работающего за О(n) Но с ограничениями - строка только из символов начиная с некоторого кода, общее число пробелов меньше этого кода.
0
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
01.05.2015, 00:52 37
Вы у меня спрашиваете, да я же хуже вас соображаю
Кидаю 2 скрина.(на 1 норм, на другом ноунорм). Код это один и тот же.
Слева VS2010, Справа gnu gcc
Миниатюры
Рекурсия. Удаление лишних пробелов   Рекурсия. Удаление лишних пробелов  
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
01.05.2015, 01:00 38
Везде ноунорм - первый пробел нужен А у меня в студии как раз все норм Я же писал, что при первой проверке вылезаю за границы массива и так делать нельзя, я надеюсь что там не 0 и не пробел, иначе ноунорм Возможно у вас напарывается на этот случай, но мне лень было усложнять код чтобы его исключать

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

Добавлено через 1 минуту
В release у меня вообще зависает в студии
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
01.05.2015, 01:08 40
daslex, проверьте на строке не начинающейся с пробелов (прямо как у вас было ), только вызов замените на task(s+1); - посмотрите на результат. Должно быть норм - если проблема в том о чем я говорил.
0
01.05.2015, 01:08
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.05.2015, 01:08
Помогаю со студенческими работами здесь

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

Удаление из текста лишних пробелов
Задание: Удалить из текста повторяющиеся знаки пробела и те пробелы, которые стоят перед абзацем. ...

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

Удаление лишних пробелов в конце строки
На проверочном сайте мое решение не проходит из-за лишнего пробела в выходной строке, как его...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru