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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 86, средняя оценка - 4.76
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
#1

Функция реверса строки - C++

05.11.2010, 04:43. Просмотров 11903. Ответов 84
Метки нет (Все метки)

На собеседовании в одну компанию меня попросили на бумажке написать функцию реверса строки.
Буквально парой дней раньше я услышал о том что на собеседованиях частенько просят решить именно эту задачу. Ее простота насторожила меня и заставила искать наиболее красивое/оптимизированное/необычное решение. И я его таки нашел и малость перестарался. Как я узнал позже интервьюер решил что я дал неверный ответ.
Так какое же у этой простой задачки может быть оригинальное решение?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2010, 04:43
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Функция реверса строки (C++):

ф-ция реверса строки - C++
был вчера на собеседовании, попросили написать ф-цию реверса строки (поменять местами 1й и последний символы, 2й и предпоследний и т.д.),...

Написание программы реверса строки - C++
Не могу понять в чем ошибка выдаёт (2 3 3 3 3 3 3 3 3 3) Прошу помощи в нахождении ошибки. #include "stdafx.h" #include <stdio.h> ...

Программа реверса строки: почему на экран выводится мусор, вместо нужного текста? - C++
Пишу программу реверса строки (меняет местами первый символ и последний, второй и предпоследний и т.д.). На экран выводится мусор, вместо...

Реализация реверса массива - C++
Первый и последний элемент массива трогать не надо. Как его толком перевернуть? По-разному пробовал уже, не хотят циферки по серединке...

Функция перезаписывает символы строки заданным количеством символов другой строки - C++
Программа работает. Но не совсем правильно. В конечной строке появляются непонятные символы, которых быть там не должно. В программе нельзя...

Функция разделения строки в массив отдельных частей этой строки - C++
Помогите написать функцию, которая на вход принимает строку типа String и возвращает уже массив String содержащий отдельные части этой...

84
Kastaneda
Форумчанин
Эксперт С++
4655 / 2863 / 228
Регистрация: 12.12.2009
Сообщений: 7,275
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 13:08 #16
разницы нет)))
0
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:10 #17
Нет. В ответе Genius Ignat нету главной идеи 2-й оптимизации.

Zilon:
Не догоняю, что имеется ввиду, под двойной оптимизацией,
быстрей алгоритма, я не знаю, да и в STL вся суть алгоритма сводиться к тому, же,
только сделана, через итераторы.
Куда быстрее еще.
0
Kastaneda
Форумчанин
Эксперт С++
4655 / 2863 / 228
Регистрация: 12.12.2009
Сообщений: 7,275
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 13:11 #18
Цитата Сообщение от Genius Ignat Посмотреть сообщение
XOR не всегда быстрая операция.
Что значит не всегда? Для процессоров x86 - всегда!
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 13:18  [ТС] #19
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Нет. В ответе Genius Ignat нету главной идеи 2-й оптимизации.
Куда быстрее еще.
Если до вечера никто не догадается - выложу решение. Я почему то думал что сложнее будет с ксором.
И еще:
не алгоритмом единым, а как говориться, и реализацией...
0
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:30 #20
Kastaneda:
Тогда reverse из STL должна использовать XOR swap, я не нашел, почему же умные
люди не написали через XOR.

Добавлено через 11 минут
Что значит не всегда? Для процессоров x86 - всегда!
В природе существует не только x86.
0
Kastaneda
Форумчанин
Эксперт С++
4655 / 2863 / 228
Регистрация: 12.12.2009
Сообщений: 7,275
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 13:34 #21
Genius Ignat, возможно мы говорим немного о разных вещах. Я по поводу ваших слов "XOR не всегда быстрая операция", не понимаю как так "не всегда". Это быстрая операция, но это не значит, что она самая быстрая из команд процессора x86 и ею нужно заменять все подряд. Если reverse из STL написан не через XOR, значит на то есть причины) Снимки, которые я выложил - это справочник по ассемблеру (правда для 16 бит), там видно, что XOR и MOV выполняются за абсолютно равное время, так что реализации реверса через XOR и через Temp (теоретически, смотря какой код сгенерирует компилятор) абсолютно равны по скорости! Использовать XOR или Temp - это дело автора кода.

Добавлено через 1 минуту
А вот про какую еще оптимизацию говорит ТС, я прям не знаю.
0
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:56 #22
Kastaneda:
Вот и не будем, спорить, тем более, тема не особа интересна.

По поводу, обменов, могу предложить использовать массив указателей,
моя идея в сторону оптимизации,
Правда, для символов не какой оптимизации не будет,
а для больших объектов такая оптимизация существенна.

Добавлено через 17 минут
Извиняюсь, по поводу STL ступил,
потому как reverse из STL обобщенная реализация для любых типов,
а XOR работает только со стандартными.
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 14:01  [ТС] #23
Не массив указателей.
0
slice
35 / 78 / 4
Регистрация: 04.11.2010
Сообщений: 249
05.11.2010, 14:41 #24
Так что ле обменивать переменные надо:
C++
1
a ^= (b ^= (a ^= b));
?
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 14:44  [ТС] #25
Кажется да.
Собственно так я это решение и нашел. Мы с другом соревновались кто за меньшее количество строчек это напишет.
0
Kastaneda
Форумчанин
Эксперт С++
4655 / 2863 / 228
Регистрация: 12.12.2009
Сообщений: 7,275
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 15:17 #26
slice, оптимизации здесь нет (я ж такой же код написал)

Не по теме:

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



Добавлено через 41 секунду
Цитата Сообщение от Zilon Посмотреть сообщение
Кажется да.
Собственно так я это решение и нашел. Мы с другом соревновались кто за меньшее количество строчек это напишет.
Так ЭТО по вашему оптимизация???

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

Не по теме:

Хочется вставить свои 5 копеек)))
например есть такой код:

C++
1
2
3
int foo(){
   return 100;
}
а еще есть такой:
C++
1
2
3
4
5
int foo(){
   int x;
   x=100;
   return x;
}
казалось бы первый код короче и выполнится быстрее, но на деле компилятор сгенерирует одинаковый код, что-то типа:
Assembler
1
2
3
mov eax,[some adress] ;пишу сходу , но
mov eax,100 ; можно заморочится и проверить компилятором
mov [some adress],eax
т.е. обе вышепреведенные ф-ции займут одинаковое кол-во байт в программе и выполнятся за одинаковое кол-во тактов.
Нужно понимать, что есть оптимизация.



Не по теме:

Добавлено через 18 минут
заморочился с компилятором, похоже я привел не самый удачный пример(, но общий смысл в том, что разное кол-во строк кода на С/С++ могут компилироваться в одинаковое кол-во ассемблерного кода)

0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 15:26  [ТС] #27
Kastaneda все верно. Это 2 формы одного и того же.
Это не та 2-я оптимизация. За оптимизацию по скорости не волнуйтесь, она там есть. А ксоры, как я уже говорил, просто фишка.

Добавлено через 3 минуты
По поводу строк. Речь шла о строках С++. И хоть 3 ксора компилер развернет, но в одной строчке свап смотрится немного дико, что не может не внушать оптимизма . А 3 приравнивания в одну строку не впихнешь(запетые не в счет).
0
Kastaneda
Форумчанин
Эксперт С++
4655 / 2863 / 228
Регистрация: 12.12.2009
Сообщений: 7,275
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 15:29 #28
Может уже решение в студию??)
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 15:46  [ТС] #29
Ок, досмотрю фильм и налабаю. Может кто-то за полтора часа и придумает.
А вы если подобные задачки знаете - выкладывайте, не стесняйтесь
0
slice
35 / 78 / 4
Регистрация: 04.11.2010
Сообщений: 249
05.11.2010, 16:01 #30
Цитата Сообщение от Zilon Посмотреть сообщение
досмотрю фильм
что смотришь?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2010, 16:01
Привет! Вот еще темы с ответами:

Функция копирует строку в другую строку заданой длины и помещает текст первой строки по центру второй строки - C++
Ребята помогите пожалуйста с прогой оч нужно, а то я сама не могу собразить полностью и как начать Вот само задание: "Функция...

функция и строки - C++
Составить функцию, которая позволяет определить позицию первого вхождения в заданую строку любого символа с другой заданной строки....

Функция копирования строки - C++
Есть строка,написать программу с ф-цией,которая формирует строку-копию.

функция символьной строки - C++
Дана символьная строка.Написать программу, которая оставляет в исходной строке латинские буквы. Обработку строки оформить в виде функции,...


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

Или воспользуйтесь поиском по форуму:
30
Yandex
Объявления
05.11.2010, 16:01
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru