0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 26
|
|
1 | |
Рекурсия. Удаление лишних пробелов15.05.2014, 21:42. Показов 11587. Ответов 59
Метки нет (Все метки)
Доброго времени суток! Подскажите как реализовать с помощью рекурсии задачу: описать функцию, которая удаляет из строки все лишние пробелы.
0
|
15.05.2014, 21:42 | |
Ответы с готовыми решениями:
59
Создание программы со своей библиотекой ( удаление элементов с N по M в строке и удаление лишних пробелов(если 2 и более оставить один)) Удаление лишних пробелов Удаление лишних пробелов Удаление лишних пробелов |
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|
01.05.2015, 01:14 | 41 |
Так и есть. С такой строкой работает. Но
Да, а зачем оно, мы уже его дружно убрали Добавлено через 1 минуту Решение полностью соответствует первоначально поставленной задаче. Но можно ведь и не цепляться к начальным пробелам и решить с ними. Добавлено через 1 минуту без UB
0
|
01.05.2015, 01:15 | 42 |
Индийский метод решения проблем - пишем обертку, в которой склеиваем нужную строку к другой из одного символа, запускаем таск со второго и с него же возвращаем результат - фсё работает
Вы обошли вниманием мой алгоритм с ограничениями за О(n). Не интересна реализация, сильные ограничения?
0
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|
01.05.2015, 01:18 | 43 |
Что-то мне подсказывает, что это тот алгоритм, который я использовал. Он просто до ужаса прост.
Добавлено через 53 секунды Хотя у меня нету ограничений. Вроде. Может и не тот.
0
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|
01.05.2015, 01:21 | 45 |
Я обошел вниманием потому что не очень понял зачем вообще ограничения.
Добавлено через 1 минуту Прямо с одним пробегом по строке и строка будет доступна вне функции в видоизмененной форме? Если так, то интересно.
0
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|
01.05.2015, 01:32 | 47 |
Да можно не торопиться.
Добавлено через 4 минуты Не по теме: мне оно скорее всего непонятно будет. я не такой умный, чтоб сходу все улавливать, если что.
0
|
01.05.2015, 02:47 | 48 | |||||
Ну собственно вот, один пробег инкрементирующимся указателем по строке, одна хвосторекурсивная функция:
0
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|
01.05.2015, 07:56 | 49 |
_Ivana, интересно не столько увидеть код, сколько понять этот код. В этой теме сейчас ведут активность не те люди, которым лишь бы Лабу на халяву сдать. Я не совсем безнадежен, но мне тяжело понимать без пояснений. А понять-то желание есть. Небольшой такой экскурс тур в алгоритм был бы совсем не лишним.
И лучше избежать тернарных операций. Выглядит неплохо, но читается для ознакомления тяжеловато, приходится разбивать на ифы. И если я могу с горем пополам разбить, могут найтись заинтересованные новички, которые не смогут.
0
|
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
|
02.05.2015, 14:36 | 52 |
UB вроде только второй, последний по алгоритму не должен (если только я не ошибся нигде), и первый скорее всего тоже не должен, не помню уже.
ЗЫ я согласен, что словесное описание дает больше понимания, чем сам код. Поэтому например на кодефорсес при разборе задач с прошедших раундов дается описание идеи алгоритма, а не пример кода. Но если мы в темах будем вместо работающих котов кидаться описаниями типа "да тут тривиально, брутфорсный набор потом сортировки и бинарный поиск", то это будет напоминать анекдот про рыбака, у которого кончилась наживка, он насадил на крючок бумажку с надписью "жирный червяк" и вытащил бумажку "лещ на 3 кг"
0
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
||||||
02.05.2015, 17:26 | 53 | |||||
Не по теме: Если бы код попроще был написан, его не нужно полностью описывать. Добавлено через 35 минут И едва ли мой алгоритм кому-нибудь может быть интересен. Проще чем решения в лоб сложно придумать. Кликните здесь для просмотра всего текста
0
|
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
|
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
|
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
|
02.05.2015, 19:51 | |
Удаление лишних пробелов Удаление из текста лишних пробелов Удаление лишних пробелов из текста Удаление лишних пробелов в конце строки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |