Разминка для мозгов: реверс строки

Задача Написать код функции, которая выводит на экран строку-аргумент в обратном порядке. Шаблон программы прилагается. Запрещается использовать внешние библиотеки, кроме функций/объектов, необходимых для вывода на экран. Запрещается изменять шаблон программы: ваш код должен быть только там, где указано комментарием. Функция должна корректно отрабатывать случай пустой строки и случай нулевого указателя.

Постарайтесь написать наиболее эффективный код.

Публикуйте пожалуйста только свой вариант функции reverse.

#include <iostream>

#ifdef _MSC_VER
#include <cstdlib>
#endif

using namespace std;

const char *test_str = "0123456789";

void reverse(const char *s) {

    // здесь должен быть ваш код

}

int main()
{
    cout << "[";
    reverse(test_str);
    cout << "]" << endl;

    cout << "[";
    reverse("");
    cout << "]" << endl;

    cout << "[";
    reverse(NULL);
    cout << "]" << endl;

#ifdef _MSC_VER
    system("pause");
#endif
    return 0;
}

Вывод программы должен выглядеть так:

[9876543210]
[]
[]

*) Для удобства отладки под Visual Studio в шаблон программы вставлены операторы условной компиляции: добавляется pause перед закрытием окна программы.

Как вариант

void reverse(const char *s) {

    if (NULL == s || "" == s)
        cout << "";
    else{
        for (int i = 9; i >= 0; i--)
            cout << s[i];
    }
}

Могу предложить вот такой код:

void reverse(const char *s) 
{
    if ( s && *s )
    {
        int l;
        for ( l = 0; s[l]; l++ ) ;
        for ( l-=1; l >= 0; l-- ) cout << s[l]; 
    }
}

P.S.: Череп, если нет оптимальных решений, то ты, пожалуйста, не выкладывай код, дай нам ещё немного подумать

void reverse(const char *s) {
    unsigned int len = 0;
    if (s != NULL) {
        // strlen из <cstring> использовать нельзя :(
        while (*s != '\0') {
            ++s;
            ++len;
        }
        while (len > 0) {
            --s;
            --len;
            cout << *s;
        }
    }
}

Юрий, у тебя код строго подвязан к длине строки в 10 или 0 символов. Строка может быть произвольной длины. Реверс строки фиксированной длины — это даже не интересно )) Кроме того, у тебя вывод пустой строки явно лишний.

porshe, хорошо. Чуть-чуть теряешь время на доступе к элементу массива через индекс. И, чисто стилистическое замечание: не рекомендуется использовать односимвольные переменные, особенно, если их легко спутать с другим символом. Особенно этим грешит буква l, которая похожа и на цифру 1, и на букву I. Но это так, к слову.

selevit, код рабочий. Можно немного ускорить за счёт более оптимального вычисления длины строки.

PS 1. На счёт «оптимального решения»: такового не существует ;) И существовать не может. А НЕоптимальное — может. Вот такой парадокс. Дело в том, что оптимальное решение может быть оптимальным или по объёму машинного кода, или по скорости выполнения (хорошо, конечно, когда и код компактный и выполняется быстро, но такое бывает крайне редко). И объём кода, и скорость выполнения при приближении к точке оптимума начинают зависеть от компилятора, операционки, архитектур компьютера и процессора. Поэтому ни я, ни кто-либо другой, абсолютный оптимум определить не сможет.

PS 2. И вообще, целью этого небольшого соревнования является разминка мозгов, поиск нестандартного (но работающего!) решения, попытка оптимизации очевидного решения. Отнеситесь к этому как к разгадыванию головоломки... и как к обмену опытом. Анализируйте и критикуйте чужой код.

Череп, а ещё будет? мне очень интересно. :) Или дай, пожалуйста ссылку на подобные задания.

Вот так, кстати работает оригинальный strlen() из glibc. Кошмар :)

size_t strlen (const char *str) {
    const char *char_ptr;
    const unsigned long int *longword_ptr;
    unsigned long int longword, himagic, lomagic;

    /* Handle the first few characters by reading one character at a time.
       Do this until CHAR_PTR is aligned on a longword boundary.  */
    for (char_ptr = str; ((unsigned long int) char_ptr
                & (sizeof (longword) - 1)) != 0;
            ++char_ptr)
        if (*char_ptr == '\0')
            return char_ptr - str;

    /* All these elucidatory comments refer to 4-byte longwords,
       but the theory applies equally well to 8-byte longwords.  */

    longword_ptr = (unsigned long int *) char_ptr;

    /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
       the "holes."  Note that there is a hole just to the left of
       each byte, with an extra at the end:

    bits:  01111110 11111110 11111110 11111111
    bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD

    The 1-bits make sure that carries propagate to the next 0-bit.
    The 0-bits provide holes for carries to fall into.  */
    himagic = 0x80808080L;
    lomagic = 0x01010101L;
    if (sizeof (longword) > 4)
    {
        /* 64-bit version of the magic.  */
        /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
        himagic = ((himagic << 16) << 16) | himagic;
        lomagic = ((lomagic << 16) << 16) | lomagic;
    }
    if (sizeof (longword) > 8)
        abort ();

    /* Instead of the traditional loop which tests each character,
       we will test a longword at a time.  The tricky part is testing
       if *any of the four* bytes in the longword in question are zero.  */
    for (;;)
    {
        longword = *longword_ptr++;

        if (((longword - lomagic) & ~longword & himagic) != 0)
        {
            /* Which of the bytes was the zero?  If none of them were, it was
               a misfire; continue the search.  */

            const char *cp = (const char *) (longword_ptr - 1);

            if (cp[0] == 0)
                return cp - str;
            if (cp[1] == 0)
                return cp - str + 1;
            if (cp[2] == 0)
                return cp - str + 2;
            if (cp[3] == 0)
                return cp - str + 3;
            if (sizeof (longword) > 4)
            {
                if (cp[4] == 0)
                    return cp - str + 4;
                if (cp[5] == 0)
                    return cp - str + 5;
                if (cp[6] == 0)
                    return cp - str + 6;
                if (cp[7] == 0)
                    return cp - str + 7;
            }
        }
    }
}

Я тоже поддерживаю porshe и хотел бы развития подобного рода «провокаций» :) Мне кажется такого рода общение подогревает интерес к изучению языка. Череп давай!!!

void reverse(const char *s) {
    int i = 0;
    if(s == NULL){
        cout << "";
    }
    else{
    while(s[i] != 0){
        i++;
    }
    while(i >= 0){
        cout << s[i];
        i--;
    }
}
}

нуууу...или как-то так

лично у мну код работает

SuperUSer, да ваш код работает, но тут лишняя строчка

if ( s == NULL )
    cout << "";

По условию там ничего не должно выводиться, а у вас выведется "", а это переведёт курсор на новую строку.
Я бы переделал ваш код так:

void reverse(const char *s) {
    int i = 0;
    if(s != NULL ) {
       while(s[i] != 0){
          i++;
       }
       while(i >= 0){
           cout << s[i];
          i--;
    }

}
}

porshe, код

if ( s == NULL )
    cout << "";

не переведёт курсор на новую строку: здесь нет вывода символа новой строки "\n" или endl. Но действительно этот кусок явно лишний.

superUSer, гораздо хуже, что код выводит лишний символ: концевой '\0'. Должно быть так:

void reverse(const char *s) {

    int i = 0;
    if(s != NULL ) {
        while(s[i] != 0){
            i++;
        }
        while(i > 0) {
            cout << s[--i];
        }
    }
}

Ещё несколько вариантов функции реверса строки.

Вариант 1.
Очень похож на вариант, предложенный selevit. Но длина строки вычисляется эффективнее. Последний цикл (собственно вывод), на уровне машинного кода, практически идентичен.

void reverse(const char *s) {
    if (s && *s) {
        unsigned int len = 0;
        const char *ch = s;
        while (*ch)
            ch++;
        len = ch - s;
        while (len--)
            cout << *--ch;
    }
}

Вариант 2.
Примерно на ту же тему, что и предыдущий вариант, но без вычисления длины строки.

void reverse(const char *s) {
    if (s && *s) {
        const char *ch = s;
        while (*ch)
            ch++;
        while (ch > s)
            cout << *--ch;
    }
}

Вариант 3.
Этот вариант [видимо] не столь эффективен и имеет существенное ограничение на длину строки (понятно почему?). Но показателен, как демонстрация совершенно другого подхода к решению задачи.

void reverse(const char *s) {
    if (s && *s) {
        reverse(s + 1);
        cout << (char)*s;
    }
}

Кстати, этот вариант, как алгоритм, имеет может быть и наиболее эффективным, но для другого языка. В этом варианте кода не изменяется ни одна переменная и нет ни одного присваивания.

По поводу оригинального strlen() из glibc.

На сколько я понял, здесь сначала выводят указатель на границу длинного целого (unsigned long int), а потом ищут длинное целое, в котором имеется нулевой байт. Когда такое длинное целое найдено, уже по нему находят адрес занулённого байта и по разности адресов начала строки и занулённого байта вычисляют длину строки. Побайтовое чтение происходит только на первом этапе, при выходе на границу длинного целого, и на последнем этапе, при анализе длинного целого с занулённым байтом.

Ориентировано скорее на достаточно длинные строки.

Смысл — минимизировать операции обращения к памяти. Считывание из памяти идёт не побайтно, а сразу по 4 или по 8 байтов (в зависимости от архитектуры). Далее, скорее всего, для анализа будут использованы регистры процессора, что очень быстро.

Ссылок на подобные задания не дам, поскольку не знаю таковых. Ищите, наверное есть такие ресурсы. Гугл вам в помощь.

Есть ресурсы, посвящённые олимпиадному программированию. Как правило, на этих ресурсах есть архив задач и система автоматизированной проверки выполненных заданий. Но там основной упор делается всё-таки на логическое решение задачи, а не на технику кодинга. Впрочем тоже интересно.

Ссылки можно посмотреть здесь.

Могу порекомендовать набор задач для начинающих на сайте Timus Online Judge. На русском. Я попробовал — всё прекрасно работает.

Cranium, I seen that you have athorized and changed your nickname. I couldn't understand at once what a new person at the blog with new nick. What a wind of change? :)

Юрий, система авторизации сайта code-live.ru к сожалению не поддерживает ники на кириллице. Пришлось переводить свой ник на латынь. Череп -> Cranium.

Так ты теперь под каким ником будешь на форуме?

Если логиниться будет влом, то под русским ))
Статьи или большие посты — точно под латинским — тут оказывается редактировать сообщения можно.