Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.65/237: Рейтинг темы: голосов - 237, средняя оценка - 4.65
6 / 6 / 0
Регистрация: 05.11.2010
Сообщений: 60

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

05.11.2010, 04:43. Показов 46770. Ответов 85
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
На собеседовании в одну компанию меня попросили на бумажке написать функцию реверса строки.
Буквально парой дней раньше я услышал о том что на собеседованиях частенько просят решить именно эту задачу. Ее простота насторожила меня и заставила искать наиболее красивое/оптимизированное/необычное решение. И я его таки нашел и малость перестарался. Как я узнал позже интервьюер решил что я дал неверный ответ.
Так какое же у этой простой задачки может быть оригинальное решение?
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
05.11.2010, 04:43
Ответы с готовыми решениями:

ф-ция реверса строки
был вчера на собеседовании, попросили написать ф-цию реверса строки (поменять местами 1й и последний символы, 2й и предпоследний и т.д.),...

Написание программы реверса строки
Не могу понять в чем ошибка выдаёт (2 3 3 3 3 3 3 3 3 3) Прошу помощи в нахождении ошибки. #include "stdafx.h" #include...

Программа реверса строки: почему на экран выводится мусор, вместо нужного текста?
Пишу программу реверса строки (меняет местами первый символ и последний, второй и предпоследний и т.д.). На экран выводится мусор, вместо...

85
1261 / 799 / 108
Регистрация: 16.09.2009
Сообщений: 2,010
05.11.2010, 18:56
Студворк — интернет-сервис помощи студентам
Zilon:
А если язык программирования, не позволяет так шалить с адресами,
где тогда оптимизации.
0
6 / 6 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:02  [ТС]
Тебе не видна разница между arr[i] и *left?
первое - это *(arr + i) второе не меняется *left.
4 лишних суммирования.

Добавлено через 4 минуты
Мы в разделе с/с++.
Я решил не уточнять язык исполнения.
0
1261 / 799 / 108
Регистрация: 16.09.2009
Сообщений: 2,010
05.11.2010, 19:03
Zilon:
Такое ощущение, что ты мне экзамен устроил.
Если бы я писал решение через арифметику указателя, тогда индексация отсутствовала,
потому как ее применение было не уместно.
0
6 / 6 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:07  [ТС]
Если что сорри, не хотел тебя задеть.
Однако ясно же сказал "оптимизированное по скорости" и про то что "не алгоритмом единым...", т.е. дело в реализации.
Если бы я начал наводить людей на мысли то в чем тогда смысл головоломки?
1
1261 / 799 / 108
Регистрация: 16.09.2009
Сообщений: 2,010
05.11.2010, 19:12
Zilon:
Ладно, если уж хочешь развития темы, тогда приведи, еще какой нибудь алгоритм
решения данной задачи,
просто ради интереса, я знаю еще три решения, правда, они менее эффективны
чем рассмотренный вариант.
0
6 / 6 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:16  [ТС]
Еще 3 решения? Насколько принципиальны их отличия?
0
1261 / 799 / 108
Регистрация: 16.09.2009
Сообщений: 2,010
05.11.2010, 19:19
Zilon:
на много, возможно ты додумаешься, может даже четвертое придумаешь.
0
6 / 6 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:24  [ТС]
А вариантов может быть много, но все похожи - можно выделить память и 2 раза скопировать данные в разных направлениях, можно с середины начать и пр. Это все в принципе одно и то же. Друге варианты в голову не приходят. Так что там за варианты?

Добавлено через 2 минуты
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Zilon:
на много, возможно ты додумаешься, может даже четвертое придумаешь.
Отличия более принципиальны нежели я назвал?
0
1261 / 799 / 108
Регистрация: 16.09.2009
Сообщений: 2,010
05.11.2010, 19:25
Друге варианты в голову не приходят. Так что там за варианты?
Сначала подумай сам, потом выложу решения(если ни чего не придумаешь),

Если я сейчас выложу, то это читерство получается.
0
6 / 6 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:30  [ТС]
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Если я сейчас выложу, то это читерство получается.
Эти алгоритмы делаю такой же реверс строки, и при этом являются не абсурдными, без всякого читерства вроде вызова библиотечных функций и при этом значительно (то есть отличимо) отличаются алгоритмом от всего здесь написанного? А это вообще реально?
0
1261 / 799 / 108
Регистрация: 16.09.2009
Сообщений: 2,010
05.11.2010, 19:33
Zilon:
Все реально.
0
6 / 6 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:49  [ТС]
И соблюдены все условия? Если да, то я хочу пива. Под пивко раньше алгоритмами занимался.

Добавлено через 13 минут
Из идей только есть только варианты перестановок в разных порядках.
1. начинаем с середины и идем к краям.
2. проходимся змейкой по схеме 1 : n, n-1 : 2, 3 : n - 2, и т.д.
3. Создаем буфер такого же размера, линейно копируем элементы от n-го до 1-го (в обратном порядке) затем мемкопи.

Добавлено через 1 минуту
Но все это (кроме варианта 3) как то похоже.
0
 Аватар для KpeHDeJIb
57 / 57 / 5
Регистрация: 31.10.2010
Сообщений: 103
05.11.2010, 20:35
Мне одному кажется странным что в функции переворачивания строки используется указатель на int, но при этом нигде не проверяется что хвост строки укладывается в sizeof(int)?

И вот уже приведенный вариант используется и у меня, примерно также:
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 <stdio.h>
#include <string.h>
 
inline static void swappchar(char *a, char *b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}
 
char *revert(char *string)
{
    size_t len = strlen(string);
    char   *begin = string, *end = string + len - 1;
 
    while (begin < end)
        swappchar(begin++, end--);
 
    return string;
}
 
int main()
{
    char string[] = "Hello, World! 1234";
    printf("Original string %s\n", string);
    printf("Reverted string %s\n", revert(string));
    return 0;
}
0
 Аватар для Kastaneda
5232 / 3206 / 362
Регистрация: 12.12.2009
Сообщений: 8,143
Записей в блоге: 2
05.11.2010, 20:42
Цитата Сообщение от Zilon Посмотреть сообщение
Вот во что Visual Studia превратила вариант с указателями:
Assembler
1
АСМ код
так в чем выигрыш вашего примера??? Он длиннее всех получился, соответственно занимает больше байт в экзешнике. Разве, что по тактам посчитать, но и то врядли будет быстрее.
0
6 / 6 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 22:32  [ТС]
Цитата Сообщение от KpeHDeJIb Посмотреть сообщение
Мне одному кажется странным что в функции переворачивания строки используется указатель на int
В начале темы было оговорено что для данной задачи можна игнорить '\0'. Пусть это будет просто массив.

Добавлено через 9 минут
Цитата Сообщение от Kastaneda Посмотреть сообщение
так в чем выигрыш вашего примера??? Он длиннее всех получился, соответственно занимает больше байт в экзешнике. Разве, что по тактам посчитать, но и то врядли будет быстрее.
Да, он длиннее. На одну строку. Но я уже не застал те времена когда ради 100 кб размера экзешника готов был бы платить хотя бы 3% скорости. А тут проигаш аж на 4 - 8 байт. Теперь по поводу скорости:
Это:

Assembler
1
2
3
4
5
6
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
на мой суровый взгляд исполняется быстрее чем это:

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+ecx*4+8"
0
 Аватар для KpeHDeJIb
57 / 57 / 5
Регистрация: 31.10.2010
Сообщений: 103
05.11.2010, 23:19
Цитата Сообщение от Zilon Посмотреть сообщение
Поскольку здесь на каждый мув еще считается "esp+ecx*4+8"
Опять на спичках экономите. Теперь покажите мне хоть одну программу, где бы функция разворачивания строки была бы bottleneck
0
6 / 6 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 23:54  [ТС]
О, да. Поскольку именно эти спички являются темой нашей беседы
0
 Аватар для KpeHDeJIb
57 / 57 / 5
Регистрация: 31.10.2010
Сообщений: 103
06.11.2010, 01:18
Цитата Сообщение от Zilon Посмотреть сообщение
О, да. Поскольку именно эти спички являются темой нашей беседы
Просто это спор из разряда "с какой стороны лучше яйцо разбивать, с тупой или с острой".
0
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
06.11.2010, 01:40
KpeHDeJIb, С тупой
0
6 / 6 / 0
Регистрация: 05.11.2010
Сообщений: 60
06.11.2010, 01:52  [ТС]
Вобщем то начинали мы с интересных вариантов реализации.
А что оптимизирование - это уже частное мнение каждого.
Наконец подводя черту под тем что быстрее выкладываю результаты "критерия истины":

Эксперимент был проведен на таком коде:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <locale.h>
 
 
void revertArray(int arr[], int N);
void revertPointer(int arr[], int N);
void revertEqu(int arr[], int N);
 
 
int main (void)
{
    clock_t start, finish;
    int i;
    int N = 1024 * 1024 * 4;
 
    int* arr = (int*) calloc(1, N * sizeof(int));
    if(NULL == arr)
    {
        printf("Allocation memory error\n");
        system("pause");
        return 1;
    }
 
    system("pause");
 
    srand(5);
    for(i = 0; i < N; i++)
        arr[i] = rand();
    
    //array
    printf("array\n");
    start = clock();
 
    for(i = 0; i < 200; i++)
        revertArray(arr, N);
 
    finish = clock();
    printf("for array       time left - %d\n", (int) (finish-start));
 
    //pointers_XOR
    printf("pointers_XOR\n");
    start = clock();
    
    for(i = 0; i < 200; i++)
        revertPointer(arr, N);
 
    finish = clock();
    printf("for pointers_XOR   time left - %d\n", (int) (finish-start));
 
    //pointers_=
    printf("pointers_=\n");
    start = clock();
    
    for(i = 0; i < 200; i++)
        revertEqu(arr, N);
 
    finish = clock();
    printf("for pointers_=    time left - %d\n", (int) (finish-start));
 
    free(arr);
 
    system("pause");
    return 0;
}
 
void revertPointer(int arr[], int N)
{
        int* left = arr;
        int* right = &arr[N - 1];
 
        while(left < right)
        {
                *left ^= *right;
                *right ^= *left;
                *(left++) ^= *(right--);
        }
}
 
void revertEqu(int arr[], int N)
{
        int* left = arr;
        int* right = &arr[N - 1];
        int temp;
 
        while(left < right)
        {
            temp = *left;
            *left++ = *right;
            *right-- = temp;
        }
}
 
 
void revertArray(int arr[], int N)
{
    int tmp;
    int i = 0;
    int j = N - 1;
 
    while( j > i ){
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
 
        i++;
        j--;
    }
}
Параметры и результаты в картинках ниже:
Миниатюры
Функция реверса строки   Функция реверса строки  
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
06.11.2010, 01:52

Есть ли функция реверса одномерного массива?
Есть ли функция реверса массива? Массив такой: static int nom = new int;

Защита от реверса проекта
Подскажите, в какую сторону копать, хочу, чтобы программа не могла быть запущена в отладчике?

Реализация реверса массива
Первый и последний элемент массива трогать не надо. Как его толком перевернуть? По-разному пробовал уже, не хотят циферки по серединке...

Защита от реверса ( md5 )
Люди посоветуйте как сделать проверку по md5 файла. Всё работает, НО. Я когда считаю хэш и вставляю его в исходники, хэш уже билда сразу...

Полумост для реверса мотора
Доброго времени суток. У меня есть вот такая схема полумоста, но я никак не могу понять откуда всетаки появляется минус? в чем фишка...


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

Или воспользуйтесь поиском по форуму:
60
Ответ Создать тему
Новые блоги и статьи
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
Установка MinGW GCC 16.2 и CMake
8Observer8 10.08.2026
VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо
anaschu 10.08.2026
Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства
russiannick 07.08.2026
1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru