0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 26
|
|
1 | |
Рекурсия. Удаление лишних пробелов15.05.2014, 21:42. Показов 11611. Ответов 59
Метки нет (Все метки)
Доброго времени суток! Подскажите как реализовать с помощью рекурсии задачу: описать функцию, которая удаляет из строки все лишние пробелы.
0
|
15.05.2014, 21:42 | |
Ответы с готовыми решениями:
59
Создание программы со своей библиотекой ( удаление элементов с N по M в строке и удаление лишних пробелов(если 2 и более оставить один)) Удаление лишних пробелов Удаление лишних пробелов Удаление лишних пробелов |
daslex
|
29.04.2015, 23:39
Рекурсия. Удаление лишних пробелов
#21
|
Не по теме: Только учтите, мне решение не надо, если кто будет тут лазать в будущем, очень очевидно непонятные им моменты лучше пояснить в комментариях. И в спойлер. Кому будет интересно пусть сами решают.
0
|
30.04.2015, 01:06 | 22 | |||||
Не за 5 секунд, но нарисовал кота - все функции с единственным параметром-указателем, никаких стрингов и stl, конечно неоптимально, но зато в рамках условии:
daslex, спасибо за вызванный интерес, не сразу получается придумать некоторые моменты, но имхо эти идеи могут пригодиться в будущем - например, передача управления другой рекурсивной функции при неудаче.
2
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|
30.04.2015, 01:14 | 23 |
Я когда делал, я использовал только 1 функцию, поэтому вставил в условие, что строка не начинается с пробелов. Так у меня получилось, что это имело значение.
Но ваше решение полностью соответствует условию. Вот ерунда ли ерунда? Не 5 же секунд понадобилось Мое решение в разы не оптимальнее. Смысл-то не в практическом применении в бою, а в самом упражнении
0
|
30.04.2015, 01:21 | 24 |
Ну я просто после общения с некоторыми языками воспринимаю функции как объекты первого класса (типа как переменные) и не стесняюсь их накидывать Хотя согласен, упражнение получилось интересное. Спасибо вам еще раз за предоставленную возможность немножко подумать. Некоторые общие идеи моего кота мне даже понравились.
ЗЫ хотя я слабо представляю как может быть решение еще менее оптимально, чем мое последнее. Типа оно на каждый инкремент указателя считает Фибоначчи экспоненциальной рекурсией просто так для большей неоптимальности?
0
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|
30.04.2015, 01:45 | 25 |
Хотя вру, наверное пооптимальнее все-таки у меня получилось.
на 100000 итерациях с копированием строки для возврата в исходное состояние ваш вариант у меня срабатывает 6 (по time.h clock_t), а мой 1 Вот так вот. Добавлено через 4 минуты Ну у меня пробелы вначале не удаляет' и вообще некорректно со строкой с пробелами вначале работает. Добавлено через 17 минут Теперь удаляет Всего 1 рекурсивная функция. Всего 1 аргумент. Если у меня на ПК на 100000 итерациях, с strcpy для возврата испорченной строки в исходное состояние внутри итераций, вариант Ivana работает 6, то мой вариант срабатывает за 2. Так что если будет желание подумать, тут есть над чем еще подумать. Упражнение не исчерпало свой лимит.
0
|
30.04.2015, 01:46 | 26 |
daslex, кстати, в этом разделе так много новых тем появляется, что я не успеваю их все мониторить на предмет интересности. Если что - зовите меня через личку, как очередной раз надо будет написать бесциклового рекурсивного кота, с удовольствием попробую реализовать
0
|
Iridiscent
|
|||||
30.04.2015, 02:18
#27
|
|||||
Не по теме: подскажите почему вылазит за пределы памяти присвоение в 25 строке как сделать чтобы работало Кликните здесь для просмотра всего текста
*((p+(ab[1]))+(y*(ab[0])))='x'; тоже вылазит
0
|
30.04.2015, 05:04 | 28 | |||||
daslex, а попробуйте вот такого кота - имхо он гораздо оптимальнее по скорости и всего 2 функции. (Я знаю что при первой проверке я залезаю за границы массива )
1
|
378 / 375 / 213
Регистрация: 29.03.2013
Сообщений: 867
|
|
30.04.2015, 10:21 | 29 |
Интересно и познавательно, спасибо Я бы так не написал конечно.
daslex, а можно всё-таки ваш вариант увидеть под спойлером?
0
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|
30.04.2015, 12:47 | 30 |
_Ivana, Вот этот последний на 1000000 итерациях (c strcpy внутри)
в моем случае срабатывет за 24 сек в вашем случае 52 сек Людвиг Бодмер, Я показывать сейчас не хочу. Боюсь убить интерес в начинании. Может в течении недели если решатели не появятся, я вам в личку скину? Мой вариант читается проще чем предложенные. Ну и работает побыстрее слегка. Одна функция же. Но любым привычным итеративным алгоритмам проигрывает. И скорее всего существуют решения оптимальнее того, что у меня есть. Надеюсь вы не против. Я не шучу, когда говорю, что все, что я смог решить по определению просто
1
|
Людвиг Бодмер
|
30.04.2015, 14:08
#31
|
Не по теме: daslex, Хорошо. Нужно конечно поддерживать интригу :) Если в личку скинете через недельку, то буду благодарен вам.
0
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|
30.04.2015, 21:33 | 32 |
Вот заметил, что с включенной оптимизацией вариант Ivana обгоняет мой. O2 на 1000000 итерациях
Мой (не показанный тут вариант решения) у меня работает 14сек Ivana у меня работает 8 сек (такая вот заметная оптимизация) А без оптимизации как я выше писал Мой у меня работает 24сек Ivana 52 сек Это в gnu gcc. Это к сведению.
0
|
30.04.2015, 22:47 | 33 |
А я кстати хотел вас спросить с какими опциями оптимизации вы компилируете и сравниваете время, но постеснялся. Оптимизатор С++ вроде должен неплохо хвостовую рекурсию в итеративном виде реализовывать, безо всяких коллов и сохранения/восстановления в стек всего контекста, поэтому я и ожидал хорошего результата от своего последнего кота, теперь я доволен.
0
|
30.04.2015, 22:59 | 34 | |||||
Может не в тему, но:
Кликните здесь для просмотра всего текста
0
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|||||||||||
01.05.2015, 00:15 | 35 | ||||||||||
Не по теме: Может и в тему, но рекурсия тут причем :coffee: Добавлено через 4 минуты Мы тут решаем задачку.на Рекурсию. (на номера строк не смотреть. это все одна задача)
_Ivana, А попробуйте ваш последний вариант вот в таком виде запустить. У меня получилось не то, что я ожидал. Кликните здесь для просмотра всего текста
0
|
01.05.2015, 00:42 | 36 |
daslex, запустил, без оптимизации, дождался результата, он правильный. Что я не уловил?
ЗЫ кстати, у меня есть идея алгоритма выполняющего условия и работающего за О(n) Но с ограничениями - строка только из символов начиная с некоторого кода, общее число пробелов меньше этого кода.
0
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|
01.05.2015, 00:52 | 37 |
Вы у меня спрашиваете, да я же хуже вас соображаю
Кидаю 2 скрина.(на 1 норм, на другом ноунорм). Код это один и тот же. Слева VS2010, Справа gnu gcc
0
|
01.05.2015, 01:00 | 38 |
Везде ноунорм - первый пробел нужен А у меня в студии как раз все норм Я же писал, что при первой проверке вылезаю за границы массива и так делать нельзя, я надеюсь что там не 0 и не пробел, иначе ноунорм Возможно у вас напарывается на этот случай, но мне лень было усложнять код чтобы его исключать
Добавлено через 1 минуту ЗЫ у меня кстати тоже 10-я студия Не гонюсь за новинками.
0
|
1373 / 596 / 199
Регистрация: 02.08.2011
Сообщений: 2,882
|
|
01.05.2015, 01:06 | 39 |
Но это решение получается не решением. Ну когда пол строки обрезает, это же наглость А вдруг найдется человек который возьмет пример на вооружение. И по закону подлости в самый не подходящий момент самую нужную строчку обрежет
Добавлено через 1 минуту В release у меня вообще зависает в студии
0
|
01.05.2015, 01:08 | 40 |
daslex, проверьте на строке не начинающейся с пробелов (прямо как у вас было ), только вызов замените на task(s+1); - посмотрите на результат. Должно быть норм - если проблема в том о чем я говорил.
0
|
01.05.2015, 01:08 | |
01.05.2015, 01:08 | |
Помогаю со студенческими работами здесь
40
Удаление лишних пробелов Удаление из текста лишних пробелов Удаление лишних пробелов из текста Удаление лишних пробелов в конце строки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |