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

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

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

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

05.11.2010, 04:43. Просмотров 11932. Ответов 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
Форумчанин
Эксперт С++
4656 / 2864 / 228
Регистрация: 12.12.2009
Сообщений: 7,276
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 09:47 #2
Zilon, если не секрет, какое решение вы предложили?
Я думаю, что чем проще решение, тем оно лучше, поэтому самое очевидное вот:
C++
1
2
3
int len=strlen(str);
for(int i=len-1;i>=0;i--)
   cout<<str[i];

Не по теме:

как-то видел в объявлении требования к кандидату (программист)
-без фанатизма относящийся к ООП
)))

1
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 11:06  [ТС] #3
Свое решение говорить пока что рано, а то поламаю людям весь кайф.
Потом обезательно выложу.
В вашем решении вы попались на один из подводных камней этого задания (как впрочем и я, когда начинал решать эту задачу) - реверс нужно понимать буквально, т.е. записать массив задом наперед. Я вначале пытался выделить дополнительный массив.
Что бы понять в чем фишка нужно написать для себя самое банальное решение, а потом его попытаться оптимизировать.

Добавлено через 10 минут
Предлагаю следующее решение как самое банальное:
C++
1
2
3
4
5
6
7
8
9
10
11
void revers(int arr[], int num)
{
    int temp;
    int i;
    for(i = 0; i < num / 2; i++)
        {
        temp = arr[i];
        arr[i] = arr[num - i - 1];
        arr[num - i - 1] = temp;
    }
}
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
05.11.2010, 11:11 #4
Самое банальное - вот так:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void reverse(char *str)
{
    char temp;
    int len;
    int i;
 
    len = strlen(str) - 1;
 
    for (i = 0; i <= len / 2; i++)
    {
        temp = str[i];
        str[i] = str[len - i];
        str[len - i] = temp;
    }
 
    str[len + 1] = '\0';
}
Добавлено через 34 секунды
Ай-яй-яй... Плагиатор я, плагиатор...
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 11:19  [ТС] #5
Для простоты можно считать что размер массива передается, а тип данных int (ну вообщем кому как нравиться). Это все не существенно.
То есть на '\0' в конце строки можно забить.
0
Kastaneda
Форумчанин
Эксперт С++
4656 / 2864 / 228
Регистрация: 12.12.2009
Сообщений: 7,276
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 11:40 #6
C++
1
2
3
4
5
6
   int len=strlen(str)-1;
for(int i=0;i<=(len-1)/2;i++){
   str[i]=str[i]^str[len-i];
   str[len-i]=str[len-i]^str[i];
   str[i]=str[i]^str[len-i];
}
ни чего лишнего)))
0
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 12:29 #7
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
#include <iostream>
#include <string.h>
using namespace std;
 
int main(){
 
char str[32] = "Hello";
 
size_t i(0);
size_t j(strlen(str)-1);
char tmp(0);
//Разворот строки встречными обменами, количество обменов равно: strlen/2
while( j > i ){
 
  tmp = str[i];
  str[i] = str[j];
  str[j] = tmp;
 
  i++;
  j--;
}
cout<<str<<endl;
 
system("pause");
return 0;
}
Смысл алгоритма, такой же что и у алгоритма silent_1991, только записан, немного по другому.
1
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 12:44  [ТС] #8
Цитата Сообщение от Kastaneda Посмотреть сообщение
C++
1
2
3
4
5
6
   int len=strlen(str)-1;
for(int i=0;i<=(len-1)/2;i++){
   str[i]=str[i]^str[len-i];
   str[len-i]=str[len-i]^str[i];
   str[i]=str[i]^str[len-i];
}
ни чего лишнего)))
Да! Это почти оно!
Главная фишка верна.
Осталась еще оптимизация по скорости
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
05.11.2010, 12:45 #9
Так вы что, имели ввиду обмен переменных без использования темповой?
a = a + b;
b = a - b;
a = a - b;
Это?
0
Kastaneda
Форумчанин
Эксперт С++
4656 / 2864 / 228
Регистрация: 12.12.2009
Сообщений: 7,276
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 12:47 #10
быстрее только так:
C++
1
2
3
4
5
6
7
   int len=strlen(str)-1;
int x=(len-1)/2;
for(int i=0;i<=x;i++){
   str[i]=str[i]^str[len-i];
   str[len-i]=str[len-i]^str[i];
   str[i]=str[i]^str[len-i];
}
больше оптимизировать реально не чего!
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 12:49  [ТС] #11
Да это главная фишка. Ее то интервьюер на собеседовании и не понял. Но там есть еще одна хитрость, немного похоже на тот вариант что выложил Genius Ignat.

Добавлено через 54 секунды
Цитата Сообщение от Kastaneda Посмотреть сообщение
быстрее только так:
больше оптимизировать реально не чего!
Можно! Можно и нужно, товарищи!
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
05.11.2010, 12:50 #12
Тогда в алгоритм Genius Ignatа надо подставить обмен переменных без темповой - вот и ответ.
0
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 12:57 #13
http://psbatishev.narod.ru/glos/00626.htm
Почитайте раздел: Использование на практике
XOR не всегда быстрая операция.
0
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 13:02  [ТС] #14
Цитата Сообщение от silent_1991 Посмотреть сообщение
Тогда в алгоритм Genius Ignatа надо подставить обмен переменных без темповой - вот и ответ.
Нет. В ответе Genius Ignat нету главной идеи 2-й оптимизации.

Добавлено через 1 минуту
Цитата Сообщение от Genius Ignat Посмотреть сообщение
XOR не всегда быстрая операция.
Согласен. Поэту на практике все же использую обычное приравнивание. Но ксоры - это для красоты и идеи. А можно еще и по скорости.

Офтоп, конешно, но все же. Я так понял что логические задачки находят отклик в сердцах (или мозгах) людей. Поэтому буду в Алгоритмах иногда выкладывать разные логические головоломки.
0
Kastaneda
Форумчанин
Эксперт С++
4656 / 2864 / 228
Регистрация: 12.12.2009
Сообщений: 7,276
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 13:07 #15
XOR
Функция реверса строки
MOV
Нажмите на изображение для увеличения
Название: Безымянный_thumb.jpg
Просмотров: 86
Размер:	53.3 Кб
ID:	48447
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2010, 13:07
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
05.11.2010, 13:07
Ответ Создать тему
Опции темы

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