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

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

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

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

05.11.2010, 04:43. Просмотров 12438. Ответов 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
Jesus loves me
Эксперт С++
4697 / 2901 / 238
Регистрация: 12.12.2009
Сообщений: 7,385
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 16:20 #31
Цитата Сообщение от Zilon Посмотреть сообщение
А вы если подобные задачки знаете - выкладывайте, не стесняйтесь
Вообще-то есть тема http://www.cyberforum.ru/cpp-beginners/thread153746.html , помимо того, что выделенно в первом посте, там еще много чего (типа того, что здесь обсуждается)
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:12  [ТС] #32
Только что досмотрел "V значит вендетта". Ух-ты! Вот какой фильм. Год вокруг него ходил, сморя на постер, решил что это отстой. Оказалось нет.
Минут через 10 выложу решение.

Добавлено через 10 минут
Вот полное решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
void revert(int arr[], int N)
{
    int* left = arr;
    int* right = &arr[N - 1];
 
    while(left < right)
    {
        *left ^= *right;
        *right ^= *left;
        *(left++) ^= *(right--);
    }
}
0
Genius Ignat
1237 / 775 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:17 #33
Zilon:
В чем прикол, использование арифметики указателей?? или что??.
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:33  [ТС] #34
По пунктам.
1. ушел i--; +1 операция
2. пришло left++ и right-- -1 операция
Что такое arr[i]? Согласно стандарту arr[i] = *(arr + i);
В этом вареанте
C++
1
2
3
4
5
6
7
while( j > i ){
  tmp = str[i];
  str[i] = str[j];
  str[j] = tmp;
  i++;
  j--;
}
наименьшее количество лишних суммирований (4 лишних), хотя мы так же имеем 2 итератора.
3. Итого если сравневать с самым быстрым из выложенных (Genius Ignat) имеем выиграш 4 суммирования. Учитывая что количество операций невелико (помоему меньше 15) то теперь имеем 11. Позже могу посмотреть асм. код.
А ведь исходный вариант имел еще больше сумирований:
C++
1
2
3
4
5
6
    for(i = 0; i < num / 2; i++)
        {
        temp = arr[i];
        arr[i] = arr[num - i - 1];
        arr[num - i - 1] = temp;
    }
и деление в цикле (хотя компилер скорей всего его вынес за цикл.)
0
Genius Ignat
1237 / 775 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:44 #35
Zilon:
Ну и чем хотел меня удивить, надо было мне в начале, с арифметикой сделать, и вопрос был бы решен.
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:45  [ТС] #36
Вот во что Visual Studia превратила вариант с указателями:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
00401081  lea         eax,[esp+8] 
00401085  lea         ecx,[esp+20h] 
00401089  lea         esp,[esp] 
00401090  mov         edx,dword ptr [ecx] 
00401092  xor         dword ptr [eax],edx 
00401094  mov         edx,dword ptr [eax] 
00401096  xor         dword ptr [ecx],edx 
00401098  mov         edx,dword ptr [ecx] 
0040109A  xor         dword ptr [eax],edx 
0040109C  sub         ecx,4 
0040109F  add         eax,4 
004010A2  cmp         eax,ecx 
004010A4  jb          revertTest+70h (401090h)
Вот решение Genius Ignat:

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
00401084  xor         eax,eax 
00401086  mov         ecx,6 
0040108B  jmp         revertTest+70h (401090h) 
0040108D  lea         ecx,[ecx] 
00401090  mov         esi,dword ptr [esp+ecx*4+8] 
00401094  mov         edx,dword ptr [esp+eax*4+8] 
00401098  mov         dword ptr [esp+eax*4+8],esi 
0040109C  mov         dword ptr [esp+ecx*4+8],edx 
004010A0  inc         eax  
004010A1  dec         ecx  
004010A2  cmp         ecx,eax 
004010A4  jg          revertTest+70h (401090h)
А вот исходное:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
00401081  xor         eax,eax 
00401083  lea         ecx,[esp+20h] 
00401087  jmp         revertTest+70h (401090h) 
00401089  lea         esp,[esp] 
00401090  mov         esi,dword ptr [ecx] 
00401092  mov         edx,dword ptr [esp+eax*4+8] 
00401096  mov         dword ptr [esp+eax*4+8],esi 
0040109A  mov         dword ptr [ecx],edx 
0040109C  inc         eax  
0040109D  sub         ecx,4 
004010A0  cmp         eax,3 
004010A3  jl          revertTest+70h (401090h)
0
Genius Ignat
1237 / 775 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:45 #37
Zilon:
Ну и чему тут можно удивиться,
надо было мне в начале, с арифметикой сделать, и вопрос был бы решен.
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:48  [ТС] #38
Цитата Сообщение от Genius Ignat Посмотреть сообщение
надо было мне в начале, с арифметикой сделать, и вопрос был бы решен
Что ты имеешь ввиду?
0
Genius Ignat
1237 / 775 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:51 #39
Zilon:
То, что переделывать было уже нечего, разве что XOR припаять.
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:54  [ТС] #40
Удивляться или нет - это личное дело каждого.
Мы говорили о варианте более оптимизированном по скорости чем те что были выложены. Вот он. Обоснование я уже выложил, но по моему это и так видно. А как я писал ранее - оптимизация будет не столько алгоритмическая сколько на уровне реализации. Хотя работая с такими атомарными вещами они алгоритм сливается с реализацией.
0
Genius Ignat
1237 / 775 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:56 #41
Zilon:
А если язык программирования, не позволяет так шалить с адресами,
где тогда оптимизации.
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:02  [ТС] #42
Тебе не видна разница между arr[i] и *left?
первое - это *(arr + i) второе не меняется *left.
4 лишних суммирования.

Добавлено через 4 минуты
Мы в разделе с/с++.
Я решил не уточнять язык исполнения.
0
Genius Ignat
1237 / 775 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 19:03 #43
Zilon:
Такое ощущение, что ты мне экзамен устроил.
Если бы я писал решение через арифметику указателя, тогда индексация отсутствовала,
потому как ее применение было не уместно.
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:07  [ТС] #44
Если что сорри, не хотел тебя задеть.
Однако ясно же сказал "оптимизированное по скорости" и про то что "не алгоритмом единым...", т.е. дело в реализации.
Если бы я начал наводить людей на мысли то в чем тогда смысл головоломки?
1
Genius Ignat
1237 / 775 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 19:12 #45
Zilon:
Ладно, если уж хочешь развития темы, тогда приведи, еще какой нибудь алгоритм
решения данной задачи,
просто ради интереса, я знаю еще три решения, правда, они менее эффективны
чем рассмотренный вариант.
0
05.11.2010, 19:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2010, 19:12
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
45
Ответ Создать тему
Опции темы

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