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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.94
akik
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 26
15.05.2014, 21:42     Рекурсия. Удаление лишних пробелов #1
Доброго времени суток! Подскажите как реализовать с помощью рекурсии задачу: описать функцию, которая удаляет из строки все лишние пробелы.
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
daslex
29.04.2015, 23:39     Рекурсия. Удаление лишних пробелов
  #21

Не по теме:

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
_Ivana
2185 / 1390 / 124
Регистрация: 01.03.2013
Сообщений: 4,137
Записей в блоге: 2
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, спасибо за вызванный интерес, не сразу получается придумать некоторые моменты, но имхо эти идеи могут пригодиться в будущем - например, передача управления другой рекурсивной функции при неудаче.
daslex
1084 / 494 / 101
Регистрация: 02.08.2011
Сообщений: 2,408
30.04.2015, 01:14     Рекурсия. Удаление лишних пробелов #23
Я когда делал, я использовал только 1 функцию, поэтому вставил в условие, что строка не начинается с пробелов. Так у меня получилось, что это имело значение.
Но ваше решение полностью соответствует условию.
Вот ерунда ли ерунда? Не 5 же секунд понадобилось

Мое решение в разы не оптимальнее. Смысл-то не в практическом применении в бою, а в самом упражнении
_Ivana
2185 / 1390 / 124
Регистрация: 01.03.2013
Сообщений: 4,137
Записей в блоге: 2
30.04.2015, 01:21     Рекурсия. Удаление лишних пробелов #24
Ну я просто после общения с некоторыми языками воспринимаю функции как объекты первого класса (типа как переменные) и не стесняюсь их накидывать Хотя согласен, упражнение получилось интересное. Спасибо вам еще раз за предоставленную возможность немножко подумать. Некоторые общие идеи моего кота мне даже понравились.

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

Вот так вот.

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

Добавлено через 17 минут
Теперь удаляет
Всего 1 рекурсивная функция. Всего 1 аргумент. Если у меня на ПК на 100000 итерациях, с strcpy для возврата испорченной строки в исходное состояние внутри итераций, вариант Ivana работает 6, то мой вариант срабатывает за 2. Так что если будет желание подумать, тут есть над чем еще подумать. Упражнение не исчерпало свой лимит.
_Ivana
2185 / 1390 / 124
Регистрация: 01.03.2013
Сообщений: 4,137
Записей в блоге: 2
30.04.2015, 01:46     Рекурсия. Удаление лишних пробелов #26
daslex, кстати, в этом разделе так много новых тем появляется, что я не успеваю их все мониторить на предмет интересности. Если что - зовите меня через личку, как очередной раз надо будет написать бесциклового рекурсивного кота, с удовольствием попробую реализовать
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'; тоже вылазит

_Ivana
2185 / 1390 / 124
Регистрация: 01.03.2013
Сообщений: 4,137
Записей в блоге: 2
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;
}
Людвиг Бодмер
 Аватар для Людвиг Бодмер
212 / 209 / 70
Регистрация: 29.03.2013
Сообщений: 555
Завершенные тесты: 2
30.04.2015, 10:21     Рекурсия. Удаление лишних пробелов #29
Интересно и познавательно, спасибо Я бы так не написал конечно.
daslex, а можно всё-таки ваш вариант увидеть под спойлером?
daslex
1084 / 494 / 101
Регистрация: 02.08.2011
Сообщений: 2,408
30.04.2015, 12:47     Рекурсия. Удаление лишних пробелов #30
_Ivana, Вот этот последний на 1000000 итерациях (c strcpy внутри)
в моем случае срабатывет за 24 сек
в вашем случае 52 сек

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

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

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

Не по теме:

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

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

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

Это в gnu gcc. Это к сведению.
_Ivana
2185 / 1390 / 124
Регистрация: 01.03.2013
Сообщений: 4,137
Записей в блоге: 2
30.04.2015, 22:47     Рекурсия. Удаление лишних пробелов #33
А я кстати хотел вас спросить с какими опциями оптимизации вы компилируете и сравниваете время, но постеснялся. Оптимизатор С++ вроде должен неплохо хвостовую рекурсию в итеративном виде реализовывать, безо всяких коллов и сохранения/восстановления в стек всего контекста, поэтому я и ожидал хорошего результата от своего последнего кота, теперь я доволен.
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 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
1084 / 494 / 101
Регистрация: 02.08.2011
Сообщений: 2,408
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
2185 / 1390 / 124
Регистрация: 01.03.2013
Сообщений: 4,137
Записей в блоге: 2
01.05.2015, 00:42     Рекурсия. Удаление лишних пробелов #36
daslex, запустил, без оптимизации, дождался результата, он правильный. Что я не уловил?

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

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

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

Удаление лишних пробелов C++
C++ Создание программы со своей библиотекой ( удаление элементов с N по M в строке и удаление лишних пробелов(если 2 и более оставить один))
Удаление лишних символов C++

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

Или воспользуйтесь поиском по форуму:
_Ivana
2185 / 1390 / 124
Регистрация: 01.03.2013
Сообщений: 4,137
Записей в блоге: 2
01.05.2015, 01:08     Рекурсия. Удаление лишних пробелов #40
daslex, проверьте на строке не начинающейся с пробелов (прямо как у вас было ), только вызов замените на task(s+1); - посмотрите на результат. Должно быть норм - если проблема в том о чем я говорил.
Yandex
Объявления
01.05.2015, 01:08     Рекурсия. Удаление лишних пробелов
Ответ Создать тему
Опции темы

Текущее время: 21:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru