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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.94
akik
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 26
15.05.2014, 21:42     Рекурсия. Удаление лишних пробелов #1
Доброго времени суток! Подскажите как реализовать с помощью рекурсии задачу: описать функцию, которая удаляет из строки все лишние пробелы.
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
daslex
1084 / 494 / 101
Регистрация: 02.08.2011
Сообщений: 2,408
01.05.2015, 01:14     Рекурсия. Удаление лишних пробелов #41
Так и есть. С такой строкой работает. Но
Цитата Сообщение от _Ivana Посмотреть сообщение
Тоько зачем же ограничение, что строка не начинается с пробелов
Да, а зачем оно, мы уже его дружно убрали

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

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

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

Добавлено через 53 секунды
Хотя у меня нету ограничений. Вроде. Может и не тот.
_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,123
Записей в блоге: 2
01.05.2015, 01:20     Рекурсия. Удаление лишних пробелов #44
У меня за один пробег указателем по строке. Быстрее в принципе нельзя, теоретически. Но вот такие ограничения.
daslex
1084 / 494 / 101
Регистрация: 02.08.2011
Сообщений: 2,408
01.05.2015, 01:21     Рекурсия. Удаление лишних пробелов #45
Я обошел вниманием потому что не очень понял зачем вообще ограничения.

Добавлено через 1 минуту
Прямо с одним пробегом по строке и строка будет доступна вне функции в видоизмененной форме? Если так, то интересно.
_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,123
Записей в блоге: 2
01.05.2015, 01:26     Рекурсия. Удаление лишних пробелов #46
Но надо знать минимальный код символа в строке. Попробую нарисовать, если параллельные дела не отвлекут.
daslex
1084 / 494 / 101
Регистрация: 02.08.2011
Сообщений: 2,408
01.05.2015, 01:32     Рекурсия. Удаление лишних пробелов #47
Да можно не торопиться.

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

Не по теме:

мне оно скорее всего непонятно будет. я не такой умный, чтоб сходу все улавливать, если что.

_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,123
Записей в блоге: 2
01.05.2015, 02:47     Рекурсия. Удаление лишних пробелов #48
Ну собственно вот, один пробег инкрементирующимся указателем по строке, одна хвосторекурсивная функция:
C++
1
2
3
4
5
6
7
8
9
10
void task(char *s) {
    char p = *(s-1);
    int r = p<' ' ? p + (*s==' ' && *(s-1-p)==' ') : (p==' ' && *s==' ' ? 1 : 0);
    char *d = s-r; *d=*s; if (*s) {if (r) *s=r; task(s+1);}
}
int _tmain(int argc, _TCHAR* argv[]) {
    char s[] = "       A       string without      double     spaces  ";
    task(s+1); cout << ">" << s << "<" << endl;
    system("pause"); return 0;
}
Код пробела 32, строка может содержать символы от него и выше по коду, и иметь не более 31 дублирующихся пробелов (не дублирующиеся пробелы не считаются). Ограничение конечно серьезное, но зато сложность как у лучшего итеративного алгоритма - O(n).
daslex
1084 / 494 / 101
Регистрация: 02.08.2011
Сообщений: 2,408
01.05.2015, 07:56     Рекурсия. Удаление лишних пробелов #49
_Ivana, интересно не столько увидеть код, сколько понять этот код. В этой теме сейчас ведут активность не те люди, которым лишь бы Лабу на халяву сдать. Я не совсем безнадежен, но мне тяжело понимать без пояснений. А понять-то желание есть. Небольшой такой экскурс тур в алгоритм был бы совсем не лишним.
И лучше избежать тернарных операций. Выглядит неплохо, но читается для ознакомления тяжеловато, приходится разбивать на ифы. И если я могу с горем пополам разбить, могут найтись заинтересованные новички, которые не смогут.
_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,123
Записей в блоге: 2
01.05.2015, 15:31     Рекурсия. Удаление лишних пробелов #50
daslex, а предыдущих моих котов вы поняли? В этом идея такова - чтобы за одну пробежку по строке мы могли решить задачу, нам при каждом входе в функцию необходимо знать накопленное к этому моменту количество дублирующихся пробелов, чтобы указатель записи сместить на это число влево от текущего указателя чтения. В моем коде это переменная r, и собственно, основная суть кота в его расчете. Но помнить это число негде - нет статиков, глобальных и лишних входящих переменных. Но ведь у нас есть халявное доступное внешнее мутабельное состояние - сама входящая строка Поэтому я запоминаю его в предыдущем символе строки - и если у меня значение в предыдущем символе строки до 32 (кода пробела), то это мое смещение, которое я инкрементирую если надо и кладу в текущий символ (после его спасения по указателю записи конечно) - для того чтобы на следующей итерации взять как значение предыдущего указателя Если же смещения нет, то ноль по-умолчанию.

Добавлено через 3 минуты
ЗЫ если чуть поработать, то можно снять ограничение на количество дублей пробелов, и читать смещение не из одной а из нескольких предыдущих ячеек строки - их более чем хватит, но это сделает кота более громоздким, и честно говоря, мне немного лениво это реализовывать Можете попробовать вы, если есть желание.
daslex
1084 / 494 / 101
Регистрация: 02.08.2011
Сообщений: 2,408
02.05.2015, 05:58     Рекурсия. Удаление лишних пробелов #51
Неа, прошлых не понял. Я же писал вам, что вы пишете тяжелочитаемо, писал еще со времен рекурсии со склейкой цифр, но вы, наверное, не поняли, что я и себя имел ввиду тоже.
Даже просто примитивные примеры рекурсии еще суметь понять надо, а тут хитрые приемы всякие в бой идут с усложнением удобочитаемости ради эффективности и экономии строчек, без комментариев и без пояснений. Я принял как это как должное, и каждый раз спрашивать пояснений мне не очень-то и удобно. Да и желания особого не было разбираться в таких котах. Плюс, они UB. (Можно, конечно строчку корректировать и делать не UB, но так задача не в зачет (сами ведь понимаете про не в зачет))

Добавлено через 1 минуту
Но спасибо за пояснение. Разобраться с последним будет попроще
_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,123
Записей в блоге: 2
02.05.2015, 14:36     Рекурсия. Удаление лишних пробелов #52
UB вроде только второй, последний по алгоритму не должен (если только я не ошибся нигде), и первый скорее всего тоже не должен, не помню уже.

ЗЫ я согласен, что словесное описание дает больше понимания, чем сам код. Поэтому например на кодефорсес при разборе задач с прошедших раундов дается описание идеи алгоритма, а не пример кода. Но если мы в темах будем вместо работающих котов кидаться описаниями типа "да тут тривиально, брутфорсный набор потом сортировки и бинарный поиск", то это будет напоминать анекдот про рыбака, у которого кончилась наживка, он насадил на крючок бумажку с надписью "жирный червяк" и вытащил бумажку "лещ на 3 кг"
daslex
1084 / 494 / 101
Регистрация: 02.08.2011
Сообщений: 2,408
02.05.2015, 17:26     Рекурсия. Удаление лишних пробелов #53

Не по теме:

Если бы код попроще был написан, его не нужно полностью описывать.
Код должен говорить сам за себя. (Хороший стиль)
Я об UB имел ввиду тот код, который с одним S, когда уходит за начало строки с надеждой. Но не будем более оффтопить.



Добавлено через 35 минут
И едва ли мой алгоритм кому-нибудь может быть интересен. Проще чем решения в лоб сложно придумать.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string.h>
 
using std::cout;
 
void foo(char *S){
    if ((S[0]==' ') && (S[1]==' ')) {
            strncpy(&(S[0]),&(S[1]),strlen(S)-1);
            S[strlen(S)-1]='\0';
            foo(S);
    }
 
    if (S[0]) foo(&(S[1]));
}
 
int main(){
    char s[] = "      A                 string              without               dowble   spaces       ";
 
                foo(s);
 
    cout<<">"<<s<<"<\n";
}
_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,123
Записей в блоге: 2
02.05.2015, 18:37     Рекурсия. Удаление лишних пробелов #54
К вопросу об условиях задачи и одной функции: вы говорили, что у вас одна функция - это так и есть, говорили что нельзя циклы - тоже вроде так и есть. Однако, за красивым инклюдом <string.h> и вызовом strncpy и strlen как раз и скрываются и другие функции, и явные циклы - ставлю 100 денег на то, что там с вайлом реализация внутри, а не рекурсией. Просто к тому, что в следующий раз хорошо бы так формулировать ограничения, чтобы исключить подобные неоднозначности. У меня то все коты не вызывают никаких библиотечных функций.
daslex
1084 / 494 / 101
Регистрация: 02.08.2011
Сообщений: 2,408
02.05.2015, 18:59     Рекурсия. Удаление лишних пробелов #55
бесспорно.
В посте №10 тоже такие циклы (в неявном образе) присутствуют. Я об этом знал, но не сказал, что так нельзя .

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

Добавлено через 3 минуты
Ну strncpy можно и заменить на memmove. Тогда только длина строки цикл и имеет.
_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,123
Записей в блоге: 2
02.05.2015, 19:13     Рекурсия. Удаление лишних пробелов #56
Длину строки можно написать и свою рекурсивную с одним аргументом - это тривиально. Вот вызов внутренней функции у вас есть не с одним а с тремя аргументами. Тоже не нарушение - внешняя то вызывается с одним. Но в моих котах и этой вольности нет - все функции, сколько бы их не было, вызываются с одним аргументом. Я наверное слишком жестко понял ограничение на один аргумент.

Добавлено через 3 минуты
ЗЫ кстати, возлагаю за это вину на вас - в посте 17 вы мне явно указали на 2 аргумента, я в посте 18 показал как сделать внешнюю функцию-обертку с 1 аргументом, вы не подтвердили что это допустимо, а потом выкладываете своего кота, где внешняя функция вызывает другую с 3 аргументами - имхо нестыковочка
daslex
1084 / 494 / 101
Регистрация: 02.08.2011
Сообщений: 2,408
02.05.2015, 19:39     Рекурсия. Удаление лишних пробелов #57
Ну, что ж поделать. Я не отрицаю, что моя вина есть. Только было явное указание на 1 функцию foo(S), а не foo(S,S) и больше указаний не было. В этом я свою вину не признаю. О внутренних функциях речи не шло.
Это форс-мажорные обстоятельства, что вы так интерпретировали

Если я напишу свою рекурсивную, то я сам нарушу условие одной функции).

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

Добавлено через 2 минуты
В посте 35 я даже условия не ставил на 1 функцию.

Добавлено через 1 минуту
Как и в первоначальной постановке вопроса. Не было у меня такого условия.
_Ivana
2177 / 1382 / 124
Регистрация: 01.03.2013
Сообщений: 4,123
Записей в блоге: 2
02.05.2015, 19:41     Рекурсия. Удаление лишних пробелов #58
По пунктам:
1) UB недопустимо, разумеется
2) условий на количество функций не было, и правильно. Это была ваша личная инициатива, но решения с несколькими функциями также засчитываются, даже у вас пара библиотечных юзается
3) насчет количества аргументов остальных функций, вызываемых из основной - тут конечно надо было явно оговорить. Ибо я возьму во внешнюю функцию только указатель на начало строки, и в ней вызову внутреннюю с 2 аргументами - текущий указатель и накопительное количество дублирующихся пробелов - будет быстро - О(n), надежно и просто. И внешняя функция будет с одним аргументом.
daslex
02.05.2015, 19:47
  #59

Не по теме:

Иногда имеет смысл уточнять у задавшего вопрос (задачку). Просто неаккуратно выкинутое условие способно стать не хилой подсказкой.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.05.2015, 19:51     Рекурсия. Удаление лишних пробелов
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
_Ivana
02.05.2015, 19:51     Рекурсия. Удаление лишних пробелов
  #60

Не по теме:

daslex, засим предлагаю выбрать другую жертву тему, где требуется помощь очередному халя ТС, и решить ее в рамках уже традиционных ограничений

Yandex
Объявления
02.05.2015, 19:51     Рекурсия. Удаление лишних пробелов
Ответ Создать тему
Опции темы

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