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

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

15.05.2014, 21:42. Показов 11587. Ответов 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
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
01.05.2015, 01:14 41
Author24 — интернет-сервис помощи студентам
Так и есть. С такой строкой работает. Но
Цитата Сообщение от _Ivana Посмотреть сообщение
Тоько зачем же ограничение, что строка не начинается с пробелов
Да, а зачем оно, мы уже его дружно убрали

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

Добавлено через 1 минуту
без UB
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
01.05.2015, 01:15 42
Индийский метод решения проблем - пишем обертку, в которой склеиваем нужную строку к другой из одного символа, запускаем таск со второго и с него же возвращаем результат - фсё работает

Вы обошли вниманием мой алгоритм с ограничениями за О(n). Не интересна реализация, сильные ограничения?
0
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
01.05.2015, 01:18 43
Что-то мне подсказывает, что это тот алгоритм, который я использовал. Он просто до ужаса прост.

Добавлено через 53 секунды
Хотя у меня нету ограничений. Вроде. Может и не тот.
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
01.05.2015, 01:20 44
У меня за один пробег указателем по строке. Быстрее в принципе нельзя, теоретически. Но вот такие ограничения.
0
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
01.05.2015, 01:21 45
Я обошел вниманием потому что не очень понял зачем вообще ограничения.

Добавлено через 1 минуту
Прямо с одним пробегом по строке и строка будет доступна вне функции в видоизмененной форме? Если так, то интересно.
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
01.05.2015, 01:26 46
Но надо знать минимальный код символа в строке. Попробую нарисовать, если параллельные дела не отвлекут.
0
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
01.05.2015, 01:32 47
Да можно не торопиться.

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

Не по теме:

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

0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
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).
0
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
01.05.2015, 07:56 49
_Ivana, интересно не столько увидеть код, сколько понять этот код. В этой теме сейчас ведут активность не те люди, которым лишь бы Лабу на халяву сдать. Я не совсем безнадежен, но мне тяжело понимать без пояснений. А понять-то желание есть. Небольшой такой экскурс тур в алгоритм был бы совсем не лишним.
И лучше избежать тернарных операций. Выглядит неплохо, но читается для ознакомления тяжеловато, приходится разбивать на ифы. И если я могу с горем пополам разбить, могут найтись заинтересованные новички, которые не смогут.
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
01.05.2015, 15:31 50
daslex, а предыдущих моих котов вы поняли? В этом идея такова - чтобы за одну пробежку по строке мы могли решить задачу, нам при каждом входе в функцию необходимо знать накопленное к этому моменту количество дублирующихся пробелов, чтобы указатель записи сместить на это число влево от текущего указателя чтения. В моем коде это переменная r, и собственно, основная суть кота в его расчете. Но помнить это число негде - нет статиков, глобальных и лишних входящих переменных. Но ведь у нас есть халявное доступное внешнее мутабельное состояние - сама входящая строка Поэтому я запоминаю его в предыдущем символе строки - и если у меня значение в предыдущем символе строки до 32 (кода пробела), то это мое смещение, которое я инкрементирую если надо и кладу в текущий символ (после его спасения по указателю записи конечно) - для того чтобы на следующей итерации взять как значение предыдущего указателя Если же смещения нет, то ноль по-умолчанию.

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

Добавлено через 1 минуту
Но спасибо за пояснение. Разобраться с последним будет попроще
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
02.05.2015, 14:36 52
UB вроде только второй, последний по алгоритму не должен (если только я не ошибся нигде), и первый скорее всего тоже не должен, не помню уже.

ЗЫ я согласен, что словесное описание дает больше понимания, чем сам код. Поэтому например на кодефорсес при разборе задач с прошедших раундов дается описание идеи алгоритма, а не пример кода. Но если мы в темах будем вместо работающих котов кидаться описаниями типа "да тут тривиально, брутфорсный набор потом сортировки и бинарный поиск", то это будет напоминать анекдот про рыбака, у которого кончилась наживка, он насадил на крючок бумажку с надписью "жирный червяк" и вытащил бумажку "лещ на 3 кг"
0
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
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";
}
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
02.05.2015, 18:37 54
К вопросу об условиях задачи и одной функции: вы говорили, что у вас одна функция - это так и есть, говорили что нельзя циклы - тоже вроде так и есть. Однако, за красивым инклюдом <string.h> и вызовом strncpy и strlen как раз и скрываются и другие функции, и явные циклы - ставлю 100 денег на то, что там с вайлом реализация внутри, а не рекурсией. Просто к тому, что в следующий раз хорошо бы так формулировать ограничения, чтобы исключить подобные неоднозначности. У меня то все коты не вызывают никаких библиотечных функций.
1
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
02.05.2015, 18:59 55
бесспорно.
В посте №10 тоже такие циклы (в неявном образе) присутствуют. Я об этом знал, но не сказал, что так нельзя .

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

Добавлено через 3 минуты
Ну strncpy можно и заменить на memmove. Тогда только длина строки цикл и имеет.
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
02.05.2015, 19:13 56
Длину строки можно написать и свою рекурсивную с одним аргументом - это тривиально. Вот вызов внутренней функции у вас есть не с одним а с тремя аргументами. Тоже не нарушение - внешняя то вызывается с одним. Но в моих котах и этой вольности нет - все функции, сколько бы их не было, вызываются с одним аргументом. Я наверное слишком жестко понял ограничение на один аргумент.

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

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

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

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

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

Не по теме:

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

0
_Ivana
02.05.2015, 19:51     Рекурсия. Удаление лишних пробелов
  #60

Не по теме:

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

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.05.2015, 19:51

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
60
Ответ Создать тему
Опции темы

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