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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 86, средняя оценка - 4.76
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 04:43     Функция реверса строки #1
На собеседовании в одну компанию меня попросили на бумажке написать функцию реверса строки.
Буквально парой дней раньше я услышал о том что на собеседованиях частенько просят решить именно эту задачу. Ее простота насторожила меня и заставила искать наиболее красивое/оптимизированное/необычное решение. И я его таки нашел и малость перестарался. Как я узнал позже интервьюер решил что я дал неверный ответ.
Так какое же у этой простой задачки может быть оригинальное решение?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.11.2010, 09:47     Функция реверса строки #2
Zilon, если не секрет, какое решение вы предложили?
Я думаю, что чем проще решение, тем оно лучше, поэтому самое очевидное вот:
C++
1
2
3
int len=strlen(str);
for(int i=len-1;i>=0;i--)
   cout<<str[i];

Не по теме:

как-то видел в объявлении требования к кандидату (программист)
-без фанатизма относящийся к ООП
)))

Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 11:06  [ТС]     Функция реверса строки #3
Свое решение говорить пока что рано, а то поламаю людям весь кайф.
Потом обезательно выложу.
В вашем решении вы попались на один из подводных камней этого задания (как впрочем и я, когда начинал решать эту задачу) - реверс нужно понимать буквально, т.е. записать массив задом наперед. Я вначале пытался выделить дополнительный массив.
Что бы понять в чем фишка нужно написать для себя самое банальное решение, а потом его попытаться оптимизировать.

Добавлено через 10 минут
Предлагаю следующее решение как самое банальное:
C++
1
2
3
4
5
6
7
8
9
10
11
void revers(int arr[], int num)
{
    int temp;
    int i;
    for(i = 0; i < num / 2; i++)
        {
        temp = arr[i];
        arr[i] = arr[num - i - 1];
        arr[num - i - 1] = temp;
    }
}
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
05.11.2010, 11:11     Функция реверса строки #4
Самое банальное - вот так:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void reverse(char *str)
{
    char temp;
    int len;
    int i;
 
    len = strlen(str) - 1;
 
    for (i = 0; i <= len / 2; i++)
    {
        temp = str[i];
        str[i] = str[len - i];
        str[len - i] = temp;
    }
 
    str[len + 1] = '\0';
}
Добавлено через 34 секунды
Ай-яй-яй... Плагиатор я, плагиатор...
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 11:19  [ТС]     Функция реверса строки #5
Для простоты можно считать что размер массива передается, а тип данных int (ну вообщем кому как нравиться). Это все не существенно.
То есть на '\0' в конце строки можно забить.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.11.2010, 11:40     Функция реверса строки #6
C++
1
2
3
4
5
6
   int len=strlen(str)-1;
for(int i=0;i<=(len-1)/2;i++){
   str[i]=str[i]^str[len-i];
   str[len-i]=str[len-i]^str[i];
   str[i]=str[i]^str[len-i];
}
ни чего лишнего)))
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 12:29     Функция реверса строки #7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <string.h>
using namespace std;
 
int main(){
 
char str[32] = "Hello";
 
size_t i(0);
size_t j(strlen(str)-1);
char tmp(0);
//Разворот строки встречными обменами, количество обменов равно: strlen/2
while( j > i ){
 
  tmp = str[i];
  str[i] = str[j];
  str[j] = tmp;
 
  i++;
  j--;
}
cout<<str<<endl;
 
system("pause");
return 0;
}
Смысл алгоритма, такой же что и у алгоритма silent_1991, только записан, немного по другому.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 12:44  [ТС]     Функция реверса строки #8
Цитата Сообщение от Kastaneda Посмотреть сообщение
C++
1
2
3
4
5
6
   int len=strlen(str)-1;
for(int i=0;i<=(len-1)/2;i++){
   str[i]=str[i]^str[len-i];
   str[len-i]=str[len-i]^str[i];
   str[i]=str[i]^str[len-i];
}
ни чего лишнего)))
Да! Это почти оно!
Главная фишка верна.
Осталась еще оптимизация по скорости
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
05.11.2010, 12:45     Функция реверса строки #9
Так вы что, имели ввиду обмен переменных без использования темповой?
a = a + b;
b = a - b;
a = a - b;
Это?
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.11.2010, 12:47     Функция реверса строки #10
быстрее только так:
C++
1
2
3
4
5
6
7
   int len=strlen(str)-1;
int x=(len-1)/2;
for(int i=0;i<=x;i++){
   str[i]=str[i]^str[len-i];
   str[len-i]=str[len-i]^str[i];
   str[i]=str[i]^str[len-i];
}
больше оптимизировать реально не чего!
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 12:49  [ТС]     Функция реверса строки #11
Да это главная фишка. Ее то интервьюер на собеседовании и не понял. Но там есть еще одна хитрость, немного похоже на тот вариант что выложил Genius Ignat.

Добавлено через 54 секунды
Цитата Сообщение от Kastaneda Посмотреть сообщение
быстрее только так:
больше оптимизировать реально не чего!
Можно! Можно и нужно, товарищи!
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
05.11.2010, 12:50     Функция реверса строки #12
Тогда в алгоритм Genius Ignatа надо подставить обмен переменных без темповой - вот и ответ.
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 12:57     Функция реверса строки #13
http://psbatishev.narod.ru/glos/00626.htm
Почитайте раздел: Использование на практике
XOR не всегда быстрая операция.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 13:02  [ТС]     Функция реверса строки #14
Цитата Сообщение от silent_1991 Посмотреть сообщение
Тогда в алгоритм Genius Ignatа надо подставить обмен переменных без темповой - вот и ответ.
Нет. В ответе Genius Ignat нету главной идеи 2-й оптимизации.

Добавлено через 1 минуту
Цитата Сообщение от Genius Ignat Посмотреть сообщение
XOR не всегда быстрая операция.
Согласен. Поэту на практике все же использую обычное приравнивание. Но ксоры - это для красоты и идеи. А можно еще и по скорости.

Офтоп, конешно, но все же. Я так понял что логические задачки находят отклик в сердцах (или мозгах) людей. Поэтому буду в Алгоритмах иногда выкладывать разные логические головоломки.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.11.2010, 13:07     Функция реверса строки #15
XOR
Функция реверса строки
MOV
Нажмите на изображение для увеличения
Название: Безымянный_thumb.jpg
Просмотров: 82
Размер:	53.3 Кб
ID:	48447
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.11.2010, 13:08     Функция реверса строки #16
разницы нет)))
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:10     Функция реверса строки #17
Нет. В ответе Genius Ignat нету главной идеи 2-й оптимизации.

Zilon:
Не догоняю, что имеется ввиду, под двойной оптимизацией,
быстрей алгоритма, я не знаю, да и в STL вся суть алгоритма сводиться к тому, же,
только сделана, через итераторы.
Куда быстрее еще.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.11.2010, 13:11     Функция реверса строки #18
Цитата Сообщение от Genius Ignat Посмотреть сообщение
XOR не всегда быстрая операция.
Что значит не всегда? Для процессоров x86 - всегда!
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 13:18  [ТС]     Функция реверса строки #19
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Нет. В ответе Genius Ignat нету главной идеи 2-й оптимизации.
Куда быстрее еще.
Если до вечера никто не догадается - выложу решение. Я почему то думал что сложнее будет с ксором.
И еще:
не алгоритмом единым, а как говориться, и реализацией...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2010, 13:30     Функция реверса строки
Еще ссылки по теме:

C++ Функция удаления подстроки из строки
C++ ф-ция реверса строки
C++ Функция перезаписывает символы строки заданным количеством символов другой строки

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

Или воспользуйтесь поиском по форуму:
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:30     Функция реверса строки #20
Kastaneda:
Тогда reverse из STL должна использовать XOR swap, я не нашел, почему же умные
люди не написали через XOR.

Добавлено через 11 минут
Что значит не всегда? Для процессоров x86 - всегда!
В природе существует не только x86.
Yandex
Объявления
05.11.2010, 13:30     Функция реверса строки
Ответ Создать тему
Опции темы

Текущее время: 13:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru