Задачка

[NetRaider]

Что-то тут активности почти никакой...

Предлагаю всем, кто хочет решить следующую задачу:

Реализовать функцию обращения(reverse) слов в строке. Например:
"1111" -> "1111"
"abcd dcba" -> "dcba abcd"
"123456 23" -> "654321 32"
"www kelehs moc" -> "www shelek com"
и т.д.

Условия:
1)Слова состоят из алфавитно-цифровых символов.
2)Разделитель слов - один или несколько пробелов.
3)Других символов нет.

Прототип ф-ии: void word_reverse(std::string& str)

Победителю приз - другая задачка  

[RXL]

Предпочитаю C.

Код:

void word_reverse(char *s) {
  char *w,c;
  int i,l;

  for(w=s;*w;w++) if(*w!=' ') {
    for(l=0;w[l]!=' ' && w[l];l++);
    for(i=0;i<(l/2);i++) | c=w[i]; w[i]=w[l-i-1]; w[l-i-1]=c; }
    w+=l;
    }
  }

[NetRaider]

Код:

void word_reverse(char *s) {
  char *w,c; 
  int i,l; 

  for(w=s;*w;w++) if(*w!=' ') {
    for(l=0;w[l]!=' ' && w[l];l++); 
    for(i=0;i<(l/2);i++) { c=w[i]; w[i]=w[l-i-1]; w[l-i-1]=c; }
    w+=l; 
    }
  }

Тут баг есть  . Запись за границу входного буфера.

[RXL]

Действительно. Тогда вот так:

Код:

void word_reverse(char *s) {
  char *w,c; 
  int i,l; 

  for(w=s;*w;w++) if(*w!=' ') {
    for(l=0;w[l]!=' ' && w[l];l++);
    for(i=0;i<(l/2);i++) { c=w[i]; w[i]=w[l-i-1]; w[l-i-1]=c; }
    w+=l;
    if(*w) break;
    }
  }

[grozny]

мой вариант (оформлено как консольное приложение, MSVC 7.1):

Код:

#include "stdafx.h"

#include <ctype.h>
#include <conio.h>
void reverseWord(char*s)
{
    char    c;
    char* beg;  //word begins here
    char* end;  //word ends here
    char* cp=s; //current pointer

    while(*cp)
    {
        beg=cp;end=beg;
        for(cp=end;*end && !isspace(end[1]);end++,cp=end);
        
        if(!*end && end>beg) 
            --end;
        else
            cp+=2;
        
        while(end>beg)
        {
            c=*end;
            *end--=*beg;
            *beg++=c;
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    char phrase1[]="Defines the entry point for the console application   }; 
    //corner cases:
    char phrase2[]=""; 
    char phrase3[]=" ";
    char phrase4[]="blah";
    char* phrase;
    char* phrases[]={phrase1,phrase2,phrase3,phrase4,"\xFF"};

    for(int i=0;*phrases[i]!='\xFF';i++)
    {
        phrase=phrases[i];
        printf("before : '%s'\n",phrase);
        reverseWord(phrase);
        printf("1st run: '%s'\n",phrase);
        reverseWord(phrase);
        printf("2nd run: '%s'\n",phrase);
        printf("==================================\n");
    }
    getch();
    return 0;
}

[grozny]

Пояснения:
- можно улучшить в 2-х местах: сделать обмен через XOR и пооптимальнее организовать вычисления end в серединке. А то он елозит туда-сюда. Дальше думать неохота.
 
В предыдущем решении всё правильно и хорошо. Ну разве что за исключением сравнения с литералом ' ' - макрос isspace(x) портабельнее и яснее. Да и читать тяжело

А мне захотелось написать на указателях, без счётчиков и без целого деления напополам (что есть сдвиг на 1, ну да все в курсе, я полагаю).

[sas]

C++ variant. Did not compile though, so sorry for possible errors

Код:

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const string FINISH_WORK = "quit";

//
// cin.getline also possible...
string& read_str( string& s )
{
    s = "";

    char c;
    while ( cin.get( c ) && c != '\n' ) 
        s += c;

    return s;
}

string& reverse_words( string& s )
{
    string::iterator si = s.begin(), ei, send = s.end();
    while ( true ) {
        while ( si != send && ::isspace( *si ) ) ++si; 
        if ( si == send ) break;
        ei = si + 1;
        while ( ei != send && !::isspace( *ei ) ) ++ei;
        reverse( si, ei );
        if ( ei == send ) break;
        si = ei + 1;
    }
    return s;
}

int main()
{
    cout << "Reverse chars in all typed words.\n\n\tTo exit please type \""
         << FINISH_WORK << "\" (no double quotes around)\n\n";
    string s;
    while ( true ) {
        cout << "\nPlease enter your sentence below (\"" 
             << FINISH_WORK << "\" to exit):\n";
        if ( read_str( s ) == FINISH_WORK ) break;
        cout << "Original [" << s << "]" << endl; // need endl here
        cout << "Reversed [" << reverse_words( s ) << "]\n"; 
    }
    return 0;
}

Thanks
--- sas

[RXL]

Ну разве что за исключением сравнения с литералом ' ' - макрос isspace(x) портабельнее и яснее. Да и читать тяжело

isspace() работает согласно настройки локали и, как правило, детектит не только пробел (по "С" локали - \f,\r,\n,\t,\v). По заданию же есть только символы isalnum() и разделитель ' ', и поэтому получаются лишние вычисления. На крайний случай можно сделать свой макрос (x==' ').
А чем тяжело читать? На мой вкус и цвет - очень просто и компактно. Чем компактнее, тем меньше глазам по строчкам бегать и легче сосредоточиться на понимании.

[grozny]

isspace() работает согласно настройки локали и, как правило, детектит не только пробел (по "С" локали - \f,\r,\n,\t,\v). По заданию же есть только символы isalnum() и разделитель ' ', и поэтому получаются лишние вычисления. На крайний случай можно сделать свой макрос (x==' ').
А чем тяжело читать? На мой вкус и цвет - очень просто и компактно. Чем компактнее, тем меньше глазам по строчкам бегать и легче сосредоточиться на понимании.

Дык! Именно - согласно локали... Слова могут отделяться не только пробелами. А лишних вычислений там - ещё одно сравнение.
А если на Юникод или широкий символ переходить, то тебе все литералы придётся вылавливать и менять.

Предпочитаю читать код с хорошо отделёнными конструкциями, с одним предписанием на строчку. До меня так быстрее доходит . Дело вкуса, конешно.

[NetRaider]

Слова могут отделяться не только пробелами. А лишних вычислений там - ещё одно сравнение.
А если на Юникод или широкий символ переходить, то тебе все литералы придётся вылавливать и менять.

Могут..., но не в этой задаче

А вот мой монстрик из трех строк:

Код:

void word_reverse(std::string& str, const char delim = ' ') 
{
    std::string::size_type begin = 0, end = 0;
    while(((begin = str.find_first_not_of(delim, end)) != str.npos)) 
        std::reverse(str.begin() + begin, str.begin() + (((end = str.find_first_of(delim, begin)) == str.npos) ? str.length(): end));	
}

[sas]

Слова могут отделяться не только пробелами. А лишних вычислений там - ещё одно сравнение.
А если на Юникод или широкий символ переходить, то тебе все литералы придётся вылавливать и менять.

Могут..., но не в этой задаче

А вот мой монстрик из трех строк:

Код:

void word_reverse(std::string& str, const char delim = ' ') 
{
    std::string::size_type begin = 0, end = 0;
    while(((begin = str.find_first_not_of(delim, end)) != str.npos)) 
        std::reverse(str.begin() + begin, str.begin() + (((end = str.find_first_of(delim, begin)) == str.npos) ? str.length(): end));	
}

Nice!

--- sas

[RXL]

grozny, в принципе согласен, но с "А лишних вычислений там - ещё одно сравнение" не соглашусь. Если бы набор был фиксированный, то наверно да, а у нас набор зависит от локали. Следовательно isspace() выполняет цикл сравнения с группой символов.

NetRaider, здорово.
А нет ли в std::string готовой ф-ии word_reverse() ?

[Гром]

RXL,  

[Serega]

RXL, на самом деле isspace конечно же не сравнивает в цикле, это было бы слишком накладно, все делается с помощью таблицы

[RXL]

Это уже лучше...
Но что делать - условие задачи...

[Alexandru Pojoga]

Может, рекурсивно?

[Гром]

Alexandru Pojoga, ты из румынии и так хорошо читаешь по русски??? Ну дела - во география расширилась.

[grozny]

Может, рекурсивно?

в теории красиво, но очень накладно. Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10.

[Alexandru Pojoga]

Я вообще-то из Молдавии, только живу в Румынии.

>> Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10.

А вот это не понимаю. Как так? Стек же он огромный?

[grozny]

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

Кстати, в теоретическом программировании доказана теорема, согласно которой рекурсия всегда представима в виде набора линейного кода и условных переходов.

...
The Stack Allocations (/STACK:reserve[,commit]) option sets the size of the stack in bytes.

To find this option in the development environment, click Settings on the Project menu. Then click the Link tab, and click Output in the Category box. The Reserve text box (or in the reserve argument on the command line) specifies the total stack allocation in virtual memory. The default stack size is 1 MB.

не так уж и дофига по нынешним временам...

[Alexandru Pojoga]

> The default stack size is 1 MB.
> не так уж и дофига по нынешним временам...

Я написал маленькую функцию, у VC6 на каждый call уходит 92 байта (плюс локальные переменные).

В 1 МБ вполне жить можно...  

[grozny]

Да кто б спорил. Зависит от задачи. Мне надо было разобрать списки, содержащие покрытие неких фрагментов памяти на разном кол-ве прогонов и пометить что на каком прогоне исполнялось. Разбивка/сортировка перекрывающихся по прогонам отрезков отлично ложится на рекурсию. НО: при типичной конфигурации в 10 тыс. отрезков/прогон и всего лишь 6 прогонах наступала полная задница всей красивой рекурсии.

[Alexandru Pojoga]

Да уж, рекурсия красива только на бумаге. А так...

[lapulya]

а что подразумевается под словом прогон (может я просто чего то не монимаю)

вот это работает без проблем...

int sum_seq(int a)
{
   return (a-- > 0) ?  a + sum_seq(a) : 0;
}

void main()
{
   int d = sum_seq(1000);
}

[grozny]

прогон = program run , execution . Древнесоветский программерский арго. Тогда все термины переводили во избежание низкопоклонства перед западом (и многие удачно, я бы сказал)

[Alf]

Да уж, рекурсия красива только на бумаге. А так...

По-моему, она и на деле неплохо выглядит. Впрочем, посудите сами:

Код:

#include "stdafx.h"

void ReverceWord(char* &p)
{
  char c;
  if (c = *p) 
    if (' ' != c) {
      ReverceWord(++p);
      printf("%c", c);
    }
}

void ReverceStr(char* &p)
{
  while (*p)
    if (' ' != *p) {
      ReverceWord(p);
      else
        printf("%c", *p++);
    }
}

int main(int argc, char* argv[])
{
  char Buffer[100];
  char *P = Buffer;
  scanf("%[^\n]s", Buffer);
  ReverceStr(P);
  printf("\n");
  return 0;
}

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

-Возможно, более низкое по сравнению с итерационным подходом быстродействие. (А возможно, и нет. Хорошо бы взять да и померить реальную скорость предложенных алгоритмов на одном компе.)

Достоинства (IMHO):
-Компактный код. Причем главное даже не то, что должен быстро выполняться, а то, что легко читается, и практически негде сделать ошибку. Нет ни циклов, где можно просчитаться с количеством повторов, границами индексов или условием выхода, ни сложной логики ветвления.

-Автономность. Как можно заметить, я вынужденно использовал только функции форматированного ввода-вывода для взаимодействия с внешним миром. Не использовались никакие другие библиотечные функции (не из пижонства, а просто в этой задаче они не нужны).
Кстати, вызовы библиотечных функций тоже не бесплатны и могут сильно повлиять на скорость работы программы.


Наконец, рекурсия просто красива сама по себе. Хорошо сказал Дойч: "Итерация свойственна человеку, рекурсия - божественна".

[Anonymous]

Может, рекурсивно?

в теории красиво, но очень накладно. Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10.

Не всяко.
Был уверен, что это не так, но захотелось убедиться воочию. в предыдущую программку ввел "слово" размером 50. Проскочила.
Длиннее было лень буквы считать, тем более что наверняка этот предел уж куда больше.
Раз уж залез в отладчик,заодно глянул на поведение стека (лень было на пальцах байты считать). Оказалось, что на каждый рекурсивный вызов функции ReverceWord отводится 0x5C байт (92 десятичное).
Кстати, заодно уж и в MSDN заглянул. Как отметил grozny, размер стека по умолчанию 1Мб. Если маловато, опция линкера /STACK:reserve[,commit] позволяет установить желаемое значение. Так что для разумного использования рекурсии стек помехой не будет.

[Alf]

Прошу прощения, малость промахнулся. В предыдущем сообщении Гость = Alf

[Алексей++]

for(w=s;*w;w++) if(*w!=' ') {

это цитата из первого пота Эр-Экселя.

зачем в серединке  *w возникло ?

[Джон]

это проверка условия - 0 значит ничего нет - false