Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2  Все   Вниз
  Печать  
Автор Тема: Задачка  (Прочитано 32912 раз)
0 Пользователей и 1 Гость смотрят эту тему.
NetRaider
Гость
« : 20-09-2003 05:55 » 

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

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

Реализовать функцию обращения(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
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 21-09-2003 18:48 » 

Предпочитаю 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;
    }
  }
« Последнее редактирование: 19-11-2007 20:06 от Алексей1153++ » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
NetRaider
Гость
« Ответ #2 : 22-09-2003 01:21 » 

Код:
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;
    }
  }

Тут баг есть  Ага. Запись за границу входного буфера.
« Последнее редактирование: 19-11-2007 20:07 от Алексей1153++ » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #3 : 22-09-2003 09:16 » 

Действительно. Тогда вот так:
Код:
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;
    }
  }
« Последнее редактирование: 19-11-2007 20:08 от Алексей1153++ » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
grozny
Гость
« Ответ #4 : 22-09-2003 23:12 » 

мой вариант (оформлено как консольное приложение, 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;
}

« Последнее редактирование: 19-11-2007 20:11 от Алексей1153++ » Записан
grozny
Гость
« Ответ #5 : 22-09-2003 23:27 » 

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

А мне захотелось написать на указателях, без счётчиков и без целого деления напополам (что есть сдвиг на 1, ну да все в курсе, я полагаю).
Записан
sas
Гость
« Ответ #6 : 23-09-2003 06:52 » 

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
« Последнее редактирование: 19-11-2007 20:12 от Алексей1153++ » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 23-09-2003 09:56 » 

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

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
grozny
Гость
« Ответ #8 : 23-09-2003 15:20 » 

Цитата: RXL

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


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

Предпочитаю читать код с хорошо отделёнными конструкциями, с одним предписанием на строчку. До меня так быстрее доходит Улыбаюсь. Дело вкуса, конешно.
Записан
NetRaider
Гость
« Ответ #9 : 24-09-2003 07:17 » 

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

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

А вот мой монстрик из трех строк:
Код:
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));
}
« Последнее редактирование: 19-11-2007 20:14 от Алексей1153++ » Записан
sas
Гость
« Ответ #10 : 24-09-2003 08:11 » 

Цитата: 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));
}

Nice!

--- sas
« Последнее редактирование: 19-11-2007 20:15 от Алексей1153++ » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #11 : 24-09-2003 09:41 » 

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

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #12 : 24-09-2003 09:49 » 

RXL,  Отлично
Записан

А птичку нашу прошу не обижать!!!
Serega
Гость
« Ответ #13 : 24-09-2003 11:10 » new

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #14 : 24-09-2003 13:11 » 

Это уже лучше...
Но что делать - условие задачи...  Вот такой я вот
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Alexandru Pojoga
Гость
« Ответ #15 : 21-10-2003 17:45 » 

Может, рекурсивно?
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #16 : 21-10-2003 19:47 » 

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

А птичку нашу прошу не обижать!!!
grozny
Гость
« Ответ #17 : 21-10-2003 20:05 » 

Цитата: Alexandru Pojoga
Может, рекурсивно?

в теории красиво, но очень накладно. Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10.
Записан
Alexandru Pojoga
Гость
« Ответ #18 : 22-10-2003 03:00 » 

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

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

А вот это не понимаю. Как так? Стек же он огромный?
Записан
grozny
Гость
« Ответ #19 : 22-10-2003 23:19 » 

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

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

...
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
Гость
« Ответ #20 : 25-10-2003 00:01 » 

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

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

В 1 МБ вполне жить можно...  Жжешь
Записан
grozny
Гость
« Ответ #21 : 25-10-2003 01:56 » 

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

Да уж, рекурсия красива только на бумаге. А так...
Записан
lapulya
Молодой специалист

ru
Offline Offline

« Ответ #23 : 13-11-2003 15:31 » 

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

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

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

void main()
{
   int d = sum_seq(1000);
}
Записан

С уважением Lapulya
grozny
Гость
« Ответ #24 : 17-11-2003 20:45 » 

прогон = program run , execution . Древнесоветский программерский арго. Тогда все термины переводили во избежание низкопоклонства перед западом (и многие удачно, я бы сказал)
Записан
Alf
Гость
« Ответ #25 : 18-11-2003 09:19 » 

Цитата: Alexandru Pojoga
Да уж, рекурсия красива только на бумаге. А так...
По-моему, она и на деле неплохо выглядит. Впрочем, посудите сами:
Код:
#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):
-Компактный код. Причем главное даже не то, что должен быстро выполняться, а то, что легко читается, и практически негде сделать ошибку. Нет ни циклов, где можно просчитаться с количеством повторов, границами индексов или условием выхода, ни сложной логики ветвления.

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


Наконец, рекурсия просто красива сама по себе. Хорошо сказал Дойч: "Итерация свойственна человеку, рекурсия - божественна".
« Последнее редактирование: 19-11-2007 20:24 от Алексей1153++ » Записан
Anonymous
Гость
« Ответ #26 : 18-11-2003 10:30 » 

Цитата: grozny
Цитата: Alexandru Pojoga
Может, рекурсивно?

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

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

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

ru
Offline Offline
Сообщений: 13


« Ответ #28 : 18-11-2003 15:18 » 

Цитата

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


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

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

Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #29 : 18-11-2003 15:23 » 

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

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Страниц: [1] 2  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines