データ

Question

私は問題を抱えている

のシーケンスを生成するための別の解決策を探して、のは言わせて：

1つのルールによって、次の以前の 1から新しい文字列を生成します。
1、11、21、 1211、111221、312211、13112221、...

1. "1"：つの番号1を意味するので、次の文字列が "11"
2. 「11あろう21 『
3. 『21： "1ので、次の文字列があろう2つの数値を意味する』 1211 『 』一の番号2などつの番号1は、次の文字列があることを意味し、』....

そして、私の解決策はここにあります：

#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番を熱心に再計算しますが、これは非常に非効率的です。

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

このアルゴリズムの1ステップでは、基本的に前のシーケンスにrun-length encodingが適用されます。 Rosetta StoneにはRLEの解決策がいくつかありますが、C++用のソリューションもあります。多分これは垣間見る価値があります。

ただし、この解決策ではファンシーな標準ライブラリアルゴリズムも使用していません。

Answer 3

ファンシーパンツの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); 
}