Ищите альтернативное решение для генерации последовательности данных

Question

У меня проблема, скажем:

Создать новую строку из предыдущего один следующий по одному правилу.
1, 11, 21, 1211, 111221, 312211, 13112221, ...

1. «1»: означает одно число 1, поэтому следующая строка будет «11»
2. «11»: означает два числа 1, поэтому следующая строка будет «21»
3. «21»: означает одно число 2 и одно число 1, поэтому следующая строка будет «1211» ....

А вот мое решение:

#include <string>
#include <iostream>

using namespace std;

class look_n_say {
public:
    look_n_say( int n ) : n( n ) {
    }

    friend ostream& operator <<( ostream& out, const look_n_say& rhs ) {
        string result;
        string init_str( "1" );
        out << init_str << endl;
        for( int i = 1; i < rhs.n; ++i ) {
            result = rhs.get_new_str( init_str );   
            out << result << '\n';
            init_str = result;
            result.clear();
        }
        return out;
    }

private:
    string get_new_str( const string& str ) const {
        int cnt( 1 );
        string result;
        for( string::size_type i = 0, len = str.length(); i < len; ++i ) {
            if( i < len - 1 && str[i] == str[i + 1] ) {
                ++cnt;
            }
            else {
                result.append( 1, cnt + 48 );
                result.append( 1, str[i] );
                cnt = 1;
            }
        }
        return result;
    }

private:
    int n;
};

int main() {
    look_n_say lns( 10 );
    cout << lns << endl;
    return 0;
}        

Причина, по которой я не удовлетворен своим решением, заключается в том, что я пропустил элегантное решение с использованием алгоритма STL. Я думал о std::transform, но не нашел способа применить его. Есть ли лучший способ решить эту проблему? Кто-нибудь может поделиться со мной? Буду очень признателен за любые отзывы и комментарии о моем стиле кодирования! Пожалуйста, скажите мне, насколько плох мой стиль кодирования, и я буду учиться на этом.

Спасибо
Чан

Answer 1

Насколько мне известно, не существует STL "однострочный", который может генерировать эту последовательность.Вы можете использовать комбинацию алгоритмов, чтобы попытаться разграничить все диапазоны смежных последовательных значений, возможно, используя std::adjacent_difference, но я искренне думаю, что рукописный цикл будет более элегантным.

На неродственной ноте,Я не уверен, что поддерживаю ваше решение разработать look_n_say, как у вас.Когда вы написали класс, у вас есть объект, единственная цель которого - записать значения в ostream.Вы не можете запрашивать отдельные значения из ряда, а также не можете изменять количество значений, которые вы получаете после создания объекта.Вы также с готовностью пересчитываете первые n номера каждый раз, когда звоните operator <<, что может быть крайне неэффективно.Я бы посоветовал изменить класс на:

1. Кэшировать ранее сгенерированные значения, чтобы вы могли получить их позже.
2. Разрешить пользователю запрашивать любое число поиска и произнесения, котороеони хотят, а не просто извлекают первые n из них.

Один из возможных вариантов может выглядеть следующим образом:

class LookAndSaySeries {
public:
    string getTerm(size_t index) const; // Get the appropriate term of the series.

private:
    /* Previously-retrieved values, marked mutable since getTerm() will modify even
     * though it's a semantically-const operation.
     */
    mutable vector<string> cachedValues; // Values you've handed back before.
    void generateNext() const;
};

string LookAndSaySeries::getTerm(size_t index) const {
     /* Keep generating values until you have enough to satisfy the request. */
     while (index >= cachedValues.size())
         generateNext();

     return cachedValues[index];
}

void LookAndSaySeries::generateNext() const {
     /* ... insert logic here to generate next term ... */
     cachedValues.push_back(/* ... that value ... */);
}

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

Answer 2

Модные штаны STL подход:

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

typedef std::vector<int> T;

void thingy(const T &v, const int n)
{
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ""));
    std::cout << std::endl;

    if (n > 0)
    {
        T w;
        for (T::const_iterator it = v.begin(); it != v.end(); )
        {
            T::const_iterator it2 = std::find_if(it, v.end(),
                                    std::bind1st(std::not_equal_to<int>(), *it));
            w.push_back(std::distance(it, it2));
            w.push_back(*it);
            it = it2;
        }

        thingy(w, n-1);
    }
}


int main()
{
    T v;
    v.push_back(1);
    thingy(v, 5);
}

Answer 3

Одиночные шаги в этом алгоритме по существу применяют кодировку длины серии к предыдущей последовательности.Существует несколько решений для RLE на Rosetta Stone , включая одно для C ++.Возможно, стоит взглянуть на это.

Однако это решение также не использует причудливых стандартных библиотечных алгоритмов.