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

@Zilon · Регистрация: 05.11.2010

Author24 — интернет-сервис помощи студентам

На собеседовании в одну компанию меня попросили на бумажке написать функцию реверса строки.
Буквально парой дней раньше я услышал о том что на собеседованиях частенько просят решить именно эту задачу. Ее простота насторожила меня и заставила искать наиболее красивое/оптимизированное/необычное решение. И я его таки нашел и малость перестарался. Как я узнал позже интервьюер решил что я дал неверный ответ.
Так какое же у этой простой задачки может быть оригинальное решение?

accept · 06.11.2010, 03:52

без учёта нуль-символа

C

#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 · 06.11.2010, 04:03

а если через рекурсию

C++

#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 · 06.11.2010, 04:35

Ничё себе, раздулась тема... Ну и я что-нибудь напишу - вдруг кому пригодится...

C++

#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 · 06.11.2010, 05:01

C++

#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 · 06.11.2010, 05:17

для разнообразия

C

#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 · 06.11.2010, 05:19

VASSUV,

C++

1	revers(arr,arr+strlen(arr)-1);

несколько символов в середине

C

#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 · 06.11.2010, 05:38

Если уж по разнообразию пошли.

C++

1	std::reverse(Arr, Arr+N);

@easybudda · 06.11.2010, 05:45

ForEveR, так тут же весь прикол в том, чтобы свой велосипед собрать...

@ForEveR · 06.11.2010, 06:05

easybudda, Знаю)

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

C++

#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 · 06.11.2010, 06:51

Помогите никак не могу связать!
ни с union ни с type

C++

#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++

#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 · 06.11.2010, 07:05

VASSUV, use templates, Luke!

@Kastaneda · 06.11.2010, 08:48

Это не объективный показатель, мало ли что могло происходить в системе в это время, проц мог пару квантов урвать на что-нибудь более нужное, а время тикало))
По поводу этого:

Assembler

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 · 06.11.2010, 11:29

Сообщение от ForEveR

use templates, Luke!

Who such Luke??

@KpeHDeJIb · 06.11.2010, 13:35

Ну и с копированием раз еще не было варианта

C

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 · 06.11.2010, 23:14 **[ТС]**

Сообщение от VASSUV

а если через рекурсию

C++

#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 · 06.11.2010, 23:23

Ну, частенько рекурсии учат на примере факториала, но вод допустима ли она там? Однако учат же.

@Zilon · 06.11.2010, 23:30 **[ТС]**

Сообщение от Kastaneda

Это не объективный показатель, мало ли что могло происходить в системе в это время, проц мог пару квантов урвать на что-нибудь более нужное, а время тикало))

На скриншоте видно, что приоритет задачи был "высокий". Во время рекурсии у меня даже таскменеджер зависал, хоть у него и повышений приоритет. Тем более что я запускал тест неоднократно.

По поводу этого:

Assembler

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 · 06.11.2010, 23:32

Я считаю, что учить надо на примерах, где рекурсия действительно необходима (или основательно упрощает задачу). Иначе студенты так и будут всю жизнь факториал да возведение в степень рекурсивно писать, но не больше - не учили же их так.

@Zilon · 06.11.2010, 23:39 **[ТС]**

Сообщение от KpeHDeJIb

Ну и с копированием раз еще не было варианта

Это апогей нашей дискуссии!

Добавлено через 2 минуты
Скорее всего на рекурсию обращают столько внимания потому что она очень хорошо показывает "что такое функция".

silent_1991 · 06.11.2010, 23:42

Да ладно, не надо её настолько недооценивать, называя просто прикольной штукой и не более. Код, например, быстрой сортировки намного проще, короче и нагляднее в своей рекурсивной реализации, нежели итеративной.

И фракталы, кстати, тоже не просто "прикольная штука". Они возникли при решении вполне практической и жизненной задачи.

@easybudda Модератор 12453 / 7478 / 1752 Регистрация: 25.07.2009 Сообщений: 13,748
	06.11.2010, 05:45	68
	ForEveR, так тут же весь прикол в том, чтобы свой велосипед собрать... 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	06.11.2010, 07:05	71
	VASSUV, use templates, Luke! 0

@VASSUV MiThEoN 466 / 323 / 42 Регистрация: 31.10.2009 Сообщений: 546 Записей в блоге: 2
	06.11.2010, 11:29	73
	Сообщение от ForEveR use templates, Luke! Who such Luke?? 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	06.11.2010, 23:23	76
	Ну, частенько рекурсии учат на примере факториала, но вод допустима ли она там? Однако учат же. 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	06.11.2010, 23:32	78
	Я считаю, что учить надо на примерах, где рекурсия действительно необходима (или основательно упрощает задачу). Иначе студенты так и будут всю жизнь факториал да возведение в степень рекурсивно писать, но не больше - не учили же их так. 0

@Zilon 6 / 6 / 0 Регистрация: 05.11.2010 Сообщений: 60
		1
	Функция реверса строки 05.11.2010, 04:43. Показов 44413. Ответов 85 Метки нет (Все метки) На собеседовании в одну компанию меня попросили на бумажке написать функцию реверса строки. Буквально парой дней раньше я услышал о том что на собеседованиях частенько просят решить именно эту задачу. Ее простота насторожила меня и заставила искать наиболее красивое/оптимизированное/необычное решение. И я его таки нашел и малость перестарался. Как я узнал позже интервьюер решил что я дал неверный ответ. Так какое же у этой простой задачки может быть оригинальное решение? 0

@Zilon 6 / 6 / 0 Регистрация: 05.11.2010 Сообщений: 60
	06.11.2010, 23:39 [ТС]	79
	Сообщение от KpeHDeJIb Ну и с копированием раз еще не было варианта Это апогей нашей дискуссии! Добавлено через 2 минуты Скорее всего на рекурсию обращают столько внимания потому что она очень хорошо показывает "что такое функция". 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	06.11.2010, 23:42	80
	Да ладно, не надо её настолько недооценивать, называя просто прикольной штукой и не более. Код, например, быстрой сортировки намного проще, короче и нагляднее в своей рекурсивной реализации, нежели итеративной. И фракталы, кстати, тоже не просто "прикольная штука". Они возникли при решении вполне практической и жизненной задачи. 0