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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 86, средняя оценка - 4.76
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 04:43     Функция реверса строки #1
На собеседовании в одну компанию меня попросили на бумажке написать функцию реверса строки.
Буквально парой дней раньше я услышал о том что на собеседованиях частенько просят решить именно эту задачу. Ее простота насторожила меня и заставила искать наиболее красивое/оптимизированное/необычное решение. И я его таки нашел и малость перестарался. Как я узнал позже интервьюер решил что я дал неверный ответ.
Так какое же у этой простой задачки может быть оригинальное решение?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
06.11.2010, 03:52     Функция реверса строки #61
без учёта нуль-символа
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
#include <stdio.h>
 
void f(char s[], int size);
 
int main(void)
{
    char line[100] = "abcde";
    
    f(line, 5);
    
    printf("%s" "\n", line);
    
    return 0;
}
 
void f(char s[], int size)
{
    if (size > 1) {
        int t = s[0];
        s[0] = s[size - 1];
        s[size - 1] = t;
        f(s + 1, size - 2);
    }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
VASSUV
MiThEoN
 Аватар для VASSUV
412 / 278 / 15
Регистрация: 31.10.2009
Сообщений: 403
Записей в блоге: 2
06.11.2010, 04:03     Функция реверса строки #62
а если через рекурсию
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "stdafx.h"
#include "string.h"
#include <conio.h>
void revers(char arr[], int num,int x)
{
    if(x<num/2)
    {
        arr[x]=arr[x]+arr[num-1-x];
        arr[num-1-x]=arr[x]-arr[num-1-x];
        arr[x]=arr[x]-arr[num-1-x];
        revers(arr,num,x+1);
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    char arr[]={"edovaz an 'tatobar lathcem ay"};
    revers(arr,strlen(arr),0);
    puts(arr);
    getch();
    return 0;
}
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
06.11.2010, 04:35     Функция реверса строки #63
Ничё себе, раздулась тема... Ну и я что-нибудь напишу - вдруг кому пригодится...
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
 
template <typename T>
inline void swap(T & a, T & b) {
    T c(a);
    a = b;
    b = c;
}
 
template <typename T>
T * reverse(T * arr, size_t size){
    T * head = arr;
    T * tail = arr + size - 1;
    while ( head < tail )
        swap(*head++, *tail--);
    return arr;
}
 
template <typename T>
void dump(std::ostream & ost, T * arr, size_t size, std::string sep = " "){
    while ( size-- )
        ost << *arr++ << sep;
}
 
int main(){
    int iArray [] = { 1, 2, 3, 4, 5 };
    char str [] = "abcdefgh";
    double dArray [] = { 1.1, 2.2, 3.3, 4.4 };
 
    std::cout << "\nInteger array: ";
    dump(std::cout, iArray, sizeof(iArray) / sizeof(*iArray));
    std::cout << "\nReverse array: ";
    dump(std::cout, reverse(iArray, sizeof(iArray) / sizeof(*iArray)), sizeof(iArray) / sizeof(*iArray));
    std::cout << "\nDouble array: ";
    dump(std::cout, dArray, sizeof(dArray) / sizeof(*dArray));
    std::cout << "\nReverse array: ";
    dump(std::cout, reverse(dArray, sizeof(dArray) / sizeof(*dArray)), sizeof(dArray) / sizeof(*dArray));
    std::cout << "\nChar string: " << str << std::endl;
    std::cout << "Reverse string: " << reverse(str, strlen(str)) << std::endl;
 
    system("pause");
    return 0;
}
Про стандартную функцию reverse в курсе, про оптимизацию не рассказывайте
VASSUV
MiThEoN
 Аватар для VASSUV
412 / 278 / 15
Регистрация: 31.10.2009
Сообщений: 403
Записей в блоге: 2
06.11.2010, 05:01     Функция реверса строки #64
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "stdafx.h"
#include "string.h"
#include <conio.h>
void revers(char *charstr1,char *charstr2){
    if(charstr1!=charstr2){
        *charstr1=*charstr1+*charstr2;
        *charstr2=*charstr1-*charstr2;
        *charstr1=*charstr1-*charstr2;
        revers(charstr1+1,charstr2-1);
    }
}
int _tmain(int argc, _TCHAR* argv[]){
    char arr[]={"edovaz an 'tatobar lathcem ay"};
    revers(arr,arr+strlen(arr)-1);
    puts(arr);
    getch();
}
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
06.11.2010, 05:17     Функция реверса строки #65
для разнообразия
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
27
#include <stdio.h>
#include <stdlib.h>
 
#define SWAP(a, b) ({ *(a) += *(b); *(b) = *(a) - *(b); *(a) = *(a) - *(b); })
 
void reverse(int * arr, size_t size) { 
    if ( size < 2 )
        return;
    SWAP(arr, (arr + size - 1)); 
    reverse(arr + 1, size - 2); 
}
    
int main(void){
    int i;
    int arr[] = { 1, 2, 3, 4, 5 };
    
    printf("Array:   ");
    for ( i = 0; i < sizeof(arr) / sizeof(*arr); ++i )
        printf("%d ", arr[i]);
    reverse(arr, (sizeof(arr) / sizeof(*arr)));
    printf("\nReverse: ");
    for ( i = 0; i < sizeof(arr) / sizeof(*arr); ++i )
        printf("%d ", arr[i]);
    printf("\n");
    
    exit(0);
}
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
06.11.2010, 05:19     Функция реверса строки #66
VASSUV,
C++
1
revers(arr,arr+strlen(arr)-1);
несколько символов в середине

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
#include <stdio.h>
 
void reverse(char s[], int size);
 
/* recursive reverse of a line */
int main(void)
{
    char line[100] = "abcdefghijklmn";
    
    printf("%s" "\n", line);
    reverse(line + 5, 4);
    printf("%s" "\n", line);
    return 0;
}
 
void reverse(char s[], int size)
{
    if (size > 1) {
        int t = s[0];
        s[0] = s[size - 1];
        s[size - 1] = t;
        reverse(s + 1, size - 2);
    }
}
Код
[guest@localhost q]$ ./t
abcdefghijklmn
abcdeihgfjklmn
[guest@localhost q]$
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
06.11.2010, 05:38     Функция реверса строки #67
Если уж по разнообразию пошли.
C++
1
std::reverse(Arr, Arr+N);
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
06.11.2010, 05:45     Функция реверса строки #68
ForEveR, так тут же весь прикол в том, чтобы свой велосипед собрать...
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
06.11.2010, 06:05     Функция реверса строки #69
easybudda, Знаю)

Пусть медленный но все же. Без учета ноль-символа для строк.

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
27
28
#include <iostream>
#include <cstring>
#include <algorithm>
#include <iterator>
 
template<class T>
T* rev(const T* elem, size_t N)
{
     T* Arr;
     Arr=new T[N];
     for(size_t i=0, j=N-1; i<N, j!=-1; ++i, --j)
     {
           Arr[i]=elem[j];
     }
     return Arr;
}
 
int main()
{
     const int N=5;
     int* Arr=new int[N];
     for(int i=0; i<N; ++i)
         Arr[i]=i+1;
     Arr=rev(Arr, N);
     std::copy(Arr, Arr+N, std::ostream_iterator<int>(std::cout, " "));
     std::cout<<std::endl;
     return 0;
}
VASSUV
MiThEoN
 Аватар для VASSUV
412 / 278 / 15
Регистрация: 31.10.2009
Сообщений: 403
Записей в блоге: 2
06.11.2010, 06:51     Функция реверса строки #70
Помогите никак не могу связать!
ни с union ни с type
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "stdafx.h"
#include "string.h"
#include <conio.h>
typedef char UINT;
void revers(UINT * charstr1,UINT * charstr2){
    if(charstr1!=charstr2 && charstr1!=charstr2+1){
        *charstr1=*charstr1+*charstr2;
        *charstr2=*charstr1-*charstr2;
        *charstr1=*charstr1-*charstr2;
        revers(charstr1+1,charstr2-1);
    }
}
int _tmain(int argc, _TCHAR* argv[]){
    int i;
    UINT A[]={1,2,3,4,5};
    UINT B[] = "abcdefgh";
    UINT C[] = {1.1, 2.2, 3.3, 4.4 };
    revers(A,A+sizeof(A)/sizeof(*A)-1);
    revers(B,B+strlen(B)-1);
    revers(C,C+sizeof(C)/sizeof(*C)-1);
    getch();
}
Добавлено через 40 минут
ни чеого лучшего что-то придумать не могу
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
27
28
29
#include "stdafx.h"
#include "string.h"
#include <conio.h>
void revers(double * charstr1,double * charstr2){
    if(charstr1!=charstr2 && charstr1!=charstr2+1){
        *charstr1=*charstr1+*charstr2;
        *charstr2=*charstr1-*charstr2;
        *charstr1=*charstr1-*charstr2;
        revers(charstr1+1,charstr2-1);}}
void revers(int * charstr1,int * charstr2){
    if(charstr1!=charstr2 && charstr1!=charstr2+1){
        *charstr1=*charstr1+*charstr2;
        *charstr2=*charstr1-*charstr2;
        *charstr1=*charstr1-*charstr2;
        revers(charstr1+1,charstr2-1);}}
void revers(char * charstr1,char * charstr2){
    if(charstr1!=charstr2 && charstr1!=charstr2+1){
        *charstr1=*charstr1+*charstr2;
        *charstr2=*charstr1-*charstr2;
        *charstr1=*charstr1-*charstr2;
        revers(charstr1+1,charstr2-1);}}
int _tmain(int argc, _TCHAR* argv[]){
    int A[]={1,2,3,4,5};
    char B[]="abcdefgh";
    double C[]={1.1,2.2,3.3,4.4,5.5};
    revers(A,A+sizeof(A)/sizeof(*A)-1);
    revers(B,B+strlen(B)-1);
    revers(C,C+sizeof(C)/sizeof(*C)-1);
    getch();}
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
06.11.2010, 07:05     Функция реверса строки #71
VASSUV, use templates, Luke!
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
06.11.2010, 08:48     Функция реверса строки #72
Это не объективный показатель, мало ли что могло происходить в системе в это время, проц мог пару квантов урвать на что-нибудь более нужное, а время тикало))
По поводу этого:
Assembler
1
2
3
4
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
Это просто исходник, если открыть скомпилированную прогу каким-нгибудь дизаассемблером, то будет видно, что все адреса уже посчитаны, т.е. в момент выполнения программы это считаться не будет (это сделает линкер во время сборки).
Реально же выяснить какой выриант выполняется быстрее - считать такты процессора)) Но мне лень этим заниматься, а спец.прог для этого я не знаю (хз, может они и есть))

P.S. это я так, чтоб разговор поддержать)))

Добавлено через 3 минуты
Ой, не заметил на сколько тема разраслась, вышесказанное это к посту, где скрины с временем выполнения разных ф-ций.
VASSUV
MiThEoN
 Аватар для VASSUV
412 / 278 / 15
Регистрация: 31.10.2009
Сообщений: 403
Записей в блоге: 2
06.11.2010, 11:29     Функция реверса строки #73
Цитата Сообщение от ForEveR Посмотреть сообщение
use templates, Luke!
Who such Luke??
KpeHDeJIb
 Аватар для KpeHDeJIb
56 / 56 / 3
Регистрация: 31.10.2010
Сообщений: 103
06.11.2010, 13:35     Функция реверса строки #74
Ну и с копированием раз еще не было варианта
C
1
2
3
4
5
6
7
8
9
10
11
12
char *revert(const char *string, size_t length)
{
    size_t i = 0, j = length;
    char *reverted = malloc(length + 1);
 
    reverted[j--] = 0;
 
    while (i < length)
        reverted[i++] = string[j--];
 
    return reverted;
}
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
06.11.2010, 23:14  [ТС]     Функция реверса строки #75
Цитата Сообщение от VASSUV Посмотреть сообщение
а если через рекурсию
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include "stdafx.h"
void revers(char arr[], int num,int x)
{
    if(x<num/2)
    {
        arr[x]=arr[x]+arr[num-1-x];
        arr[num-1-x]=arr[x]-arr[num-1-x];
        arr[x]=arr[x]-arr[num-1-x];
        revers(arr,num,x+1);
    }
}
}
Когда то тоже придумал вариант с отниманием, но помоему он оказался не (всегда) рабочий.
А рекурсия на реверсе - это конечно изящно, но совершенно недопустимо.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
06.11.2010, 23:23     Функция реверса строки #76
Ну, частенько рекурсии учат на примере факториала, но вод допустима ли она там? Однако учат же.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
06.11.2010, 23:30  [ТС]     Функция реверса строки #77
Цитата Сообщение от Kastaneda Посмотреть сообщение
Это не объективный показатель, мало ли что могло происходить в системе в это время, проц мог пару квантов урвать на что-нибудь более нужное, а время тикало))
На скриншоте видно, что приоритет задачи был "высокий". Во время рекурсии у меня даже таскменеджер зависал, хоть у него и повышений приоритет. Тем более что я запускал тест неоднократно.

По поводу этого:
Assembler
1
2
3
4
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
Это просто исходник, если открыть скомпилированную прогу каким-нгибудь дизаассемблером, то будет видно, что все адреса уже посчитаны, т.е. в момент выполнения программы это считаться не будет (это сделает линкер во время сборки).
Что за ересь! Ни значение esp, а темболее eax ecx не может быть заранее определено! И причем здесь линкер??? Это же не адреса вызываемых функций.
[QUOTE]

Добавлено через 4 минуты
Цитата Сообщение от silent_1991 Посмотреть сообщение
Ну, частенько рекурсии учат на примере факториала, но вод допустима ли она там? Однако учат же.
Вот именно - учат. И не более. Мне тоже рекурсия нравиться.
Идейная штука, на фрактал похожа.
Но жизнь диктует нам свои правила в виде 64 Кб на стек (в 2005 студии по дефолту). И не всегда мы можем диктовать свои условия в виде 16Мб, например если пишем либу.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
06.11.2010, 23:32     Функция реверса строки #78
Я считаю, что учить надо на примерах, где рекурсия действительно необходима (или основательно упрощает задачу). Иначе студенты так и будут всю жизнь факториал да возведение в степень рекурсивно писать, но не больше - не учили же их так.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
06.11.2010, 23:39  [ТС]     Функция реверса строки #79
Цитата Сообщение от KpeHDeJIb Посмотреть сообщение
Ну и с копированием раз еще не было варианта
Это апогей нашей дискуссии!

Добавлено через 2 минуты
Скорее всего на рекурсию обращают столько внимания потому что она очень хорошо показывает "что такое функция".
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.11.2010, 23:42     Функция реверса строки
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
06.11.2010, 23:42     Функция реверса строки #80
Да ладно, не надо её настолько недооценивать, называя просто прикольной штукой и не более. Код, например, быстрой сортировки намного проще, короче и нагляднее в своей рекурсивной реализации, нежели итеративной.

И фракталы, кстати, тоже не просто "прикольная штука". Они возникли при решении вполне практической и жизненной задачи.
Yandex
Объявления
06.11.2010, 23:42     Функция реверса строки
Ответ Создать тему
Опции темы

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