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

@akik · Регистрация: 14.12.2013

Студворк — интернет-сервис помощи студентам

Доброго времени суток! Подскажите как реализовать с помощью рекурсии задачу: описать функцию, которая удаляет из строки все лишние пробелы.

@daslex · 29.04.2015, 23:39

Не по теме:

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

@_Ivana · 30.04.2015, 01:06

Не за 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 · 30.04.2015, 01:14

Я когда делал, я использовал только 1 функцию, поэтому вставил в условие, что строка не начинается с пробелов. Так у меня получилось, что это имело значение.
Но ваше решение полностью соответствует условию.
Вот ерунда ли ерунда? Не 5 же секунд понадобилось

Мое решение в разы не оптимальнее. Смысл-то не в практическом применении в бою, а в самом упражнении

@_Ivana · 30.04.2015, 01:21

Ну я просто после общения с некоторыми языками воспринимаю функции как объекты первого класса (типа как переменные) и не стесняюсь их накидывать

Хотя согласен, упражнение получилось интересное. Спасибо вам еще раз за предоставленную возможность немножко подумать. Некоторые общие идеи моего кота мне даже понравились.

ЗЫ хотя я слабо представляю как может быть решение еще менее оптимально, чем мое последнее. Типа оно на каждый инкремент указателя считает Фибоначчи экспоненциальной рекурсией просто так для большей неоптимальности?

@daslex · 30.04.2015, 01:45

Хотя вру, наверное пооптимальнее все-таки у меня получилось.
на 100000 итерациях с копированием строки для возврата в исходное состояние ваш вариант у меня срабатывает 6 (по time.h clock_t), а мой 1

Вот так вот.

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

Добавлено через 17 минут
Теперь удаляет

Всего 1 рекурсивная функция. Всего 1 аргумент.

Если у меня на ПК на 100000 итерациях, с strcpy для возврата испорченной строки в исходное состояние внутри итераций, вариант Ivana работает 6, то мой вариант срабатывает за 2. Так что если будет желание подумать, тут есть над чем еще подумать. Упражнение не исчерпало свой лимит.

@_Ivana · 30.04.2015, 01:46

daslex, кстати, в этом разделе так много новых тем появляется, что я не успеваю их все мониторить на предмет интересности. Если что - зовите меня через личку, как очередной раз надо будет написать бесциклового рекурсивного кота, с удовольствием попробую реализовать

@Iridiscent · 30.04.2015, 02:18

Не по теме:

подскажите почему вылазит за пределы памяти присвоение в 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 · 30.04.2015, 05:04

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;
}

@Людвиг Бодмер · 30.04.2015, 10:21

Интересно и познавательно, спасибо

Я бы так не написал конечно.
daslex, а можно всё-таки ваш вариант увидеть под спойлером?

@daslex · 30.04.2015, 12:47

_Ivana, Вот этот последний на 1000000 итерациях (c strcpy внутри)
в моем случае срабатывет за 24 сек
в вашем случае 52 сек

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

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

Я не шучу, когда говорю, что все, что я смог решить по определению просто

@Людвиг Бодмер · 30.04.2015, 14:08

Не по теме:

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

@daslex · 30.04.2015, 21:33

Вот заметил, что с включенной оптимизацией вариант Ivana обгоняет мой. O2 на 1000000 итерациях
Мой (не показанный тут вариант решения) у меня работает 14сек
Ivana у меня работает 8 сек (такая вот заметная оптимизация)

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

Это в gnu gcc. Это к сведению.

@_Ivana · 30.04.2015, 22:47

А я кстати хотел вас спросить с какими опциями оптимизации вы компилируете и сравниваете время, но постеснялся. Оптимизатор С++ вроде должен неплохо хвостовую рекурсию в итеративном виде реализовывать, безо всяких коллов и сохранения/восстановления в стек всего контекста, поэтому я и ожидал хорошего результата от своего последнего кота, теперь я доволен.

DiffEreD · 30.04.2015, 22:59

Может не в тему, но:

Кликните здесь для просмотра всего текста

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 · 01.05.2015, 00:15

Не по теме:

Может и в тему, но рекурсия тут причем :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;

@_Ivana · 01.05.2015, 00:42

daslex, запустил, без оптимизации, дождался результата, он правильный. Что я не уловил?

ЗЫ кстати, у меня есть идея алгоритма выполняющего условия и работающего за О(n)

Но с ограничениями - строка только из символов начиная с некоторого кода, общее число пробелов меньше этого кода.

@daslex · 01.05.2015, 00:52

Вы у меня спрашиваете, да я же хуже вас соображаю

Кидаю 2 скрина.(на 1 норм, на другом ноунорм). Код это один и тот же.
Слева VS2010, Справа gnu gcc

@_Ivana · 01.05.2015, 01:00

Везде ноунорм - первый пробел нужен

А у меня в студии как раз все норм

Я же писал, что при первой проверке вылезаю за границы массива и так делать нельзя, я надеюсь что там не 0 и не пробел, иначе ноунорм

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

Добавлено через 1 минуту
ЗЫ у меня кстати тоже 10-я студия

Не гонюсь за новинками.

@daslex · 01.05.2015, 01:06

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

А вдруг найдется человек который возьмет пример на вооружение. И по закону подлости в самый не подходящий момент самую нужную строчку обрежет

Добавлено через 1 минуту
В release у меня вообще зависает в студии

@_Ivana · 01.05.2015, 01:08

daslex, проверьте на строке не начинающейся с пробелов (прямо как у вас было

), только вызов замените на task(s+1); - посмотрите на результат. Должно быть норм - если проблема в том о чем я говорил.

Новые блоги и статьи Все статьи Все блоги /
Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .	Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений
сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .	сукцессия 13. Питон модель трехзонного мицелия, пока что в основном арбускулярного anaschu 28.06.2026 ## Разработка агентной модели микоризной сукцессии: от выявления артефактов к созданию комплексной системы ### Аннотация Представлено исследование по разработке агентной модели микоризной. . .	сукцессия 12. краткий список проверок модели перед запуском. anaschu 27.06.2026 Скрытые отказы в моделях систем динамики (SD-models) экологических систем: два случая из практики Контекст Разбирался прототип модели систем динамики (SD-модели) микоризной сукцессии: пять. . .	Сукцессия 11. Проверка орудий перед войной: разработка через тестирование anaschu 27.06.2026 Как не дать модели соврать самой себе: проверки для симуляции микоризной сукцессии Введение Когда вы строите математическую модель живой системы — грибов, растений, почвы — главная опасность. . .

@akik 0 / 0 / 0 Регистрация: 14.12.2013 Сообщений: 26

	Рекурсия. Удаление лишних пробелов 15.05.2014, 21:42. Показов 12860. Ответов 59 Метки нет (Все метки) Доброго времени суток! Подскажите как реализовать с помощью рекурсии задачу: описать функцию, которая удаляет из строки все лишние пробелы. 0

@daslex
	29.04.2015, 23:39
	Не по теме: Только учтите, мне решение не надо, если кто будет тут лазать в будущем, очень очевидно непонятные им моменты лучше пояснить в комментариях. И в спойлер. Кому будет интересно пусть сами решают. 0

@daslex 1373 / 596 / 199 Регистрация: 02.08.2011 Сообщений: 2,886
	30.04.2015, 01:14
	Я когда делал, я использовал только 1 функцию, поэтому вставил в условие, что строка не начинается с пробелов. Так у меня получилось, что это имело значение. Но ваше решение полностью соответствует условию. Вот ерунда ли ерунда? Не 5 же секунд понадобилось Мое решение в разы не оптимальнее. Смысл-то не в практическом применении в бою, а в самом упражнении 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	30.04.2015, 01:21
	Ну я просто после общения с некоторыми языками воспринимаю функции как объекты первого класса (типа как переменные) и не стесняюсь их накидывать Хотя согласен, упражнение получилось интересное. Спасибо вам еще раз за предоставленную возможность немножко подумать. Некоторые общие идеи моего кота мне даже понравились. ЗЫ хотя я слабо представляю как может быть решение еще менее оптимально, чем мое последнее. Типа оно на каждый инкремент указателя считает Фибоначчи экспоненциальной рекурсией просто так для большей неоптимальности? 0

@daslex 1373 / 596 / 199 Регистрация: 02.08.2011 Сообщений: 2,886
	30.04.2015, 01:45
	Хотя вру, наверное пооптимальнее все-таки у меня получилось. на 100000 итерациях с копированием строки для возврата в исходное состояние ваш вариант у меня срабатывает 6 (по time.h clock_t), а мой 1 Вот так вот. Добавлено через 4 минуты Ну у меня пробелы вначале не удаляет' и вообще некорректно со строкой с пробелами вначале работает. Добавлено через 17 минут Теперь удаляет Всего 1 рекурсивная функция. Всего 1 аргумент. Если у меня на ПК на 100000 итерациях, с strcpy для возврата испорченной строки в исходное состояние внутри итераций, вариант Ivana работает 6, то мой вариант срабатывает за 2. Так что если будет желание подумать, тут есть над чем еще подумать. Упражнение не исчерпало свой лимит. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	30.04.2015, 01:46
	daslex, кстати, в этом разделе так много новых тем появляется, что я не успеваю их все мониторить на предмет интересности. Если что - зовите меня через личку, как очередной раз надо будет написать бесциклового рекурсивного кота, с удовольствием попробую реализовать 0

@Людвиг Бодмер 378 / 375 / 213 Регистрация: 29.03.2013 Сообщений: 867
	30.04.2015, 10:21
	Интересно и познавательно, спасибо Я бы так не написал конечно. daslex, а можно всё-таки ваш вариант увидеть под спойлером? 0

@daslex 1373 / 596 / 199 Регистрация: 02.08.2011 Сообщений: 2,886
	30.04.2015, 12:47
	_Ivana, Вот этот последний на 1000000 итерациях (c strcpy внутри) в моем случае срабатывет за 24 сек в вашем случае 52 сек Людвиг Бодмер, Я показывать сейчас не хочу. Боюсь убить интерес в начинании. Может в течении недели если решатели не появятся, я вам в личку скину? Мой вариант читается проще чем предложенные. Ну и работает побыстрее слегка. Одна функция же. Но любым привычным итеративным алгоритмам проигрывает. И скорее всего существуют решения оптимальнее того, что у меня есть. Надеюсь вы не против. Я не шучу, когда говорю, что все, что я смог решить по определению просто 1

@Людвиг Бодмер
	30.04.2015, 14:08
	Не по теме: daslex, Хорошо. Нужно конечно поддерживать интригу :) Если в личку скинете через недельку, то буду благодарен вам. 0

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

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	30.04.2015, 22:47
	А я кстати хотел вас спросить с какими опциями оптимизации вы компилируете и сравниваете время, но постеснялся. Оптимизатор С++ вроде должен неплохо хвостовую рекурсию в итеративном виде реализовывать, безо всяких коллов и сохранения/восстановления в стек всего контекста, поэтому я и ожидал хорошего результата от своего последнего кота, теперь я доволен. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	01.05.2015, 00:42
	daslex, запустил, без оптимизации, дождался результата, он правильный. Что я не уловил? ЗЫ кстати, у меня есть идея алгоритма выполняющего условия и работающего за О(n) Но с ограничениями - строка только из символов начиная с некоторого кода, общее число пробелов меньше этого кода. 0

@daslex 1373 / 596 / 199 Регистрация: 02.08.2011 Сообщений: 2,886
	01.05.2015, 00:52
	Вы у меня спрашиваете, да я же хуже вас соображаю Кидаю 2 скрина.(на 1 норм, на другом ноунорм). Код это один и тот же. Слева VS2010, Справа gnu gcc Миниатюры 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	01.05.2015, 01:00
	Везде ноунорм - первый пробел нужен А у меня в студии как раз все норм Я же писал, что при первой проверке вылезаю за границы массива и так делать нельзя, я надеюсь что там не 0 и не пробел, иначе ноунорм Возможно у вас напарывается на этот случай, но мне лень было усложнять код чтобы его исключать Добавлено через 1 минуту ЗЫ у меня кстати тоже 10-я студия Не гонюсь за новинками. 0

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

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	01.05.2015, 01:08
	daslex, проверьте на строке не начинающейся с пробелов (прямо как у вас было ), только вызов замените на task(s+1); - посмотрите на результат. Должно быть норм - если проблема в том о чем я говорил. 0