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

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

0

Так и есть. С такой строкой работает. Но

Сообщение от _Ivana Тоько зачем же ограничение, что строка не начинается с пробелов

Да, а зачем оно, мы уже его дружно убрали

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

Добавлено через 1 минуту
без UB

0

Индийский метод решения проблем - пишем обертку, в которой склеиваем нужную строку к другой из одного символа, запускаем таск со второго и с него же возвращаем результат - фсё работает

Вы обошли вниманием мой алгоритм с ограничениями за О(n). Не интересна реализация, сильные ограничения?

0

Что-то мне подсказывает, что это тот алгоритм, который я использовал. Он просто до ужаса прост.

Добавлено через 53 секунды
Хотя у меня нету ограничений. Вроде. Может и не тот.

0

У меня за один пробег указателем по строке. Быстрее в принципе нельзя, теоретически. Но вот такие ограничения.

0

Я обошел вниманием потому что не очень понял зачем вообще ограничения.

Добавлено через 1 минуту
Прямо с одним пробегом по строке и строка будет доступна вне функции в видоизмененной форме? Если так, то интересно.

0

Но надо знать минимальный код символа в строке. Попробую нарисовать, если параллельные дела не отвлекут.

0

Да можно не торопиться.

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

0

Ну собственно вот, один пробег инкрементирующимся указателем по строке, одна хвосторекурсивная функция: Код пробела 32, строка может содержать символы от него и выше по коду, и иметь не более 31 дублирующихся пробелов (не дублирующиеся пробелы не считаются). Ограничение конечно серьезное, но зато сложность как у лучшего итеративного алгоритма - O(n).

0

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

0

daslex, а предыдущих моих котов вы поняли? В этом идея такова - чтобы за одну пробежку по строке мы могли решить задачу, нам при каждом входе в функцию необходимо знать накопленное к этому моменту количество дублирующихся пробелов, чтобы указатель записи сместить на это число влево от текущего указателя чтения. В моем коде это переменная r, и собственно, основная суть кота в его расчете. Но помнить это число негде - нет статиков, глобальных и лишних входящих переменных. Но ведь у нас есть халявное доступное внешнее мутабельное состояние - сама входящая строка Поэтому я запоминаю его в предыдущем символе строки - и если у меня значение в предыдущем символе строки до 32 (кода пробела), то это мое смещение, которое я инкрементирую если надо и кладу в текущий символ (после его спасения по указателю записи конечно) - для того чтобы на следующей итерации взять как значение предыдущего указателя Если же смещения нет, то ноль по-умолчанию.

Добавлено через 3 минуты
ЗЫ если чуть поработать, то можно снять ограничение на количество дублей пробелов, и читать смещение не из одной а из нескольких предыдущих ячеек строки - их более чем хватит, но это сделает кота более громоздким, и честно говоря, мне немного лениво это реализовывать Можете попробовать вы, если есть желание.

1

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

Добавлено через 1 минуту
Но спасибо за пояснение. Разобраться с последним будет попроще

0

UB вроде только второй, последний по алгоритму не должен (если только я не ошибся нигде), и первый скорее всего тоже не должен, не помню уже.

ЗЫ я согласен, что словесное описание дает больше понимания, чем сам код. Поэтому например на кодефорсес при разборе задач с прошедших раундов дается описание идеи алгоритма, а не пример кода. Но если мы в темах будем вместо работающих котов кидаться описаниями типа "да тут тривиально, брутфорсный набор потом сортировки и бинарный поиск", то это будет напоминать анекдот про рыбака, у которого кончилась наживка, он насадил на крючок бумажку с надписью "жирный червяк" и вытащил бумажку "лещ на 3 кг"

0

Добавлено через 35 минут
И едва ли мой алгоритм кому-нибудь может быть интересен. Проще чем решения в лоб сложно придумать.

0

К вопросу об условиях задачи и одной функции: вы говорили, что у вас одна функция - это так и есть, говорили что нельзя циклы - тоже вроде так и есть. Однако, за красивым инклюдом <string.h> и вызовом strncpy и strlen как раз и скрываются и другие функции, и явные циклы - ставлю 100 денег на то, что там с вайлом реализация внутри, а не рекурсией. Просто к тому, что в следующий раз хорошо бы так формулировать ограничения, чтобы исключить подобные неоднозначности. У меня то все коты не вызывают никаких библиотечных функций.

1

бесспорно.
В посте №10 тоже такие циклы (в неявном образе) присутствуют. Я об этом знал, но не сказал, что так нельзя .

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

Добавлено через 3 минуты
Ну strncpy можно и заменить на memmove. Тогда только длина строки цикл и имеет.

0

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

Добавлено через 3 минуты
ЗЫ кстати, возлагаю за это вину на вас - в посте 17 вы мне явно указали на 2 аргумента, я в посте 18 показал как сделать внешнюю функцию-обертку с 1 аргументом, вы не подтвердили что это допустимо, а потом выкладываете своего кота, где внешняя функция вызывает другую с 3 аргументами - имхо нестыковочка

0

Ну, что ж поделать. Я не отрицаю, что моя вина есть. Только было явное указание на 1 функцию foo(S), а не foo(S,S) и больше указаний не было. В этом я свою вину не признаю. О внутренних функциях речи не шло.
Это форс-мажорные обстоятельства, что вы так интерпретировали

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

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

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

Добавлено через 1 минуту
Как и в первоначальной постановке вопроса. Не было у меня такого условия.

0

По пунктам:
1) UB недопустимо, разумеется
2) условий на количество функций не было, и правильно. Это была ваша личная инициатива, но решения с несколькими функциями также засчитываются, даже у вас пара библиотечных юзается
3) насчет количества аргументов остальных функций, вызываемых из основной - тут конечно надо было явно оговорить. Ибо я возьму во внешнюю функцию только указатель на начало строки, и в ней вызову внутреннюю с 2 аргументами - текущий указатель и накопительное количество дублирующихся пробелов - будет быстро - О(n), надежно и просто. И внешняя функция будет с одним аргументом.

0

0

0