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

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

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

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

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

Доброго времени суток! Подскажите как реализовать с помощью рекурсии задачу: описать функцию, которая удаляет из строки все лишние пробелы.
Лучшие ответы (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++
Здравствуйте, нужна помощь в написании конечного автомата. Удаление лишних пробелов из текста нужна написать в конечном автомате. Помогите...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
_Ivana
3059 / 1746 / 151
Регистрация: 01.03.2013
Сообщений: 4,927
Записей в блоге: 2
29.04.2015, 23:08 #16
Пожалуйста. Еще проще. Правда в первый раз запрашивает за границей массива, но это ерунда
C++
1
2
3
4
5
6
7
void task(char *s, char *d) {*d = *s; if (*s) { task(s+1, d+1-(*s==' '&&*(s-1)==' ') );} }
 
int _tmain(int argc, _TCHAR* argv[]) {
    char s[] = "            A       string      without      spaces              ", d[500];
    task(s, d); cout << ">" << d << "<" << endl;
    system("pause"); return 0;
}
daslex
1271 / 516 / 106
Регистрация: 02.08.2011
Сообщений: 2,668
29.04.2015, 23:17 #17
ну и какой новичок это осилит?
(s+1, d+1-(*s==' '&&*(s-1)==' ') )

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

И 1 условие не соблюдено. Похоже моя вина, что не договорил, что только один аргумент
foo(S) ; //Только так А не foo(S1,S2)
_Ivana
3059 / 1746 / 151
Регистрация: 01.03.2013
Сообщений: 4,927
Записей в блоге: 2
29.04.2015, 23:20 #18
Кстати, функция почти нормальная, можно даже вызывать без нарезания строки дестинейшна -
C++
1
task(s, s);
если не жалко испортить исходную строку и она не константная. Рекурсия без циклов на указателях рулит

Добавлено через 2 минуты
Цитата Сообщение от daslex Посмотреть сообщение
И 1 условие не соблюдено. Похоже моя вина, что не договорил, что только один аргумент
foo(S) ; //Только так А не foo(S1,S2)
Ну уж совсем к ерунде то не цепляйтесь -
C++
1
void finalres (char *s) {task(s, s);}
daslex
1271 / 516 / 106
Регистрация: 02.08.2011
Сообщений: 2,668
29.04.2015, 23:32 #19
Цитата Сообщение от _Ivana Посмотреть сообщение
task(s, s);
Ерунда не ерунда. 1 аргумент нужен. С 2 легче.

Добавлено через 2 минуты

Не по теме:

Да и с 1 легко. Но с 2 легче.



Добавлено через 5 минут
строку портить можно. Она не константная.
_Ivana
3059 / 1746 / 151
Регистрация: 01.03.2013
Сообщений: 4,927
Записей в блоге: 2
29.04.2015, 23:35 #20
daslex, щас попробую сделать.
daslex
29.04.2015, 23:39
  #21

Не по теме:

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

_Ivana
3059 / 1746 / 151
Регистрация: 01.03.2013
Сообщений: 4,927
Записей в блоге: 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
1271 / 516 / 106
Регистрация: 02.08.2011
Сообщений: 2,668
30.04.2015, 01:14 #23
Я когда делал, я использовал только 1 функцию, поэтому вставил в условие, что строка не начинается с пробелов. Так у меня получилось, что это имело значение.
Но ваше решение полностью соответствует условию.
Вот ерунда ли ерунда? Не 5 же секунд понадобилось

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

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

Вот так вот.

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

Добавлено через 17 минут
Теперь удаляет
Всего 1 рекурсивная функция. Всего 1 аргумент. Если у меня на ПК на 100000 итерациях, с strcpy для возврата испорченной строки в исходное состояние внутри итераций, вариант Ivana работает 6, то мой вариант срабатывает за 2. Так что если будет желание подумать, тут есть над чем еще подумать. Упражнение не исчерпало свой лимит.
_Ivana
3059 / 1746 / 151
Регистрация: 01.03.2013
Сообщений: 4,927
Записей в блоге: 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
3059 / 1746 / 151
Регистрация: 01.03.2013
Сообщений: 4,927
Записей в блоге: 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;
}
Людвиг Бодмер
343 / 340 / 131
Регистрация: 29.03.2013
Сообщений: 846
Завершенные тесты: 4
30.04.2015, 10:21 #29
Интересно и познавательно, спасибо Я бы так не написал конечно.
daslex, а можно всё-таки ваш вариант увидеть под спойлером?
daslex
1271 / 516 / 106
Регистрация: 02.08.2011
Сообщений: 2,668
30.04.2015, 12:47 #30
_Ivana, Вот этот последний на 1000000 итерациях (c strcpy внутри)
в моем случае срабатывет за 24 сек
в вашем случае 52 сек

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

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

Я не шучу, когда говорю, что все, что я смог решить по определению просто
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.04.2015, 12:47
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
30.04.2015, 12:47
Ответ Создать тему
Опции темы

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