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

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

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

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

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

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

ф-ция реверса строки - 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 содержащий отдельные части этой...

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
accept
4821 / 3241 / 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
412 / 278 / 15
Регистрация: 31.10.2009
Сообщений: 415
Записей в блоге: 2
Завершенные тесты: 1
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
Эксперт С++
9461 / 5474 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
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
412 / 278 / 15
Регистрация: 31.10.2009
Сообщений: 415
Записей в блоге: 2
Завершенные тесты: 1
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
Эксперт С++
9461 / 5474 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
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
4821 / 3241 / 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
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
06.11.2010, 05:38     Функция реверса строки #67
Если уж по разнообразию пошли.
C++
1
std::reverse(Arr, Arr+N);
easybudda
Эксперт С++
9461 / 5474 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
06.11.2010, 05:45     Функция реверса строки #68
ForEveR, так тут же весь прикол в том, чтобы свой велосипед собрать...
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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
412 / 278 / 15
Регистрация: 31.10.2009
Сообщений: 415
Записей в блоге: 2
Завершенные тесты: 1
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
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
06.11.2010, 07:05     Функция реверса строки #71
VASSUV, use templates, Luke!
Kastaneda
Форумчанин
Эксперт С++
4511 / 2853 / 227
Регистрация: 12.12.2009
Сообщений: 7,249
Записей в блоге: 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
412 / 278 / 15
Регистрация: 31.10.2009
Сообщений: 415
Записей в блоге: 2
Завершенные тесты: 1
06.11.2010, 11:29     Функция реверса строки #73
Цитата Сообщение от ForEveR Посмотреть сообщение
use templates, Luke!
Who such Luke??
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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.11.2010, 23:14     Функция реверса строки
Еще ссылки по теме:

Функция, Указатели, Строки - C++
Уважаемые програмисты требуется помощ в решении задач . По теме &lt;&lt;Функция&gt;&gt; 1.Написать функцию, которая возвращает значение...

Функция и реверс строки - C++
1. Составить программу, которая реверсирует каждое слово строки str. 2. Написать и протестировать функцию STRP(str1, str2), которая...

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

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

Функция для считывания строки - C++
Требуется написать функция для считывания строки, используя динамическое выделения памяти? Как это по лучше сделать подскажите? Было бы...


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

Или воспользуйтесь поиском по форуму:
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);
    }
}
}
Когда то тоже придумал вариант с отниманием, но помоему он оказался не (всегда) рабочий.
А рекурсия на реверсе - это конечно изящно, но совершенно недопустимо.
Yandex
Объявления
06.11.2010, 23:14     Функция реверса строки
Ответ Создать тему
Опции темы

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