c++ - 生成 Conway 'look and say' 数字

Question

我受到启发编写了一个小型 C++11 程序，该程序将生成所谓的 Conway 数，或“看和说”数。本质上，给定第 n 个术语，例如11112，下一个就是前一个词的读音；在我们的例子中是 4112，因为有 4 个 1 而只有一个 2。另一个例子:'13' 到 '1113'。

为了完整起见，以下是完整的程序源代码(如果不是使用 MS Visual Studio 编译，则省略 stdafx.h include):

#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>

using namespace std;

void print_usage(){

    cout << endl << "Conway Number Generator";
    cout << endl << "Arguments: initializer followed by nth term to be printed" << endl;
}

string say(string s){

    // Returns string said phonetically
    // e.g. '111' becomes '31'

    unsigned int sz = s.size();

    if (sz == 1){
        s.insert(0, "1");
    }
    else{
        s.insert(0, to_string(sz));
        s.erase(2, sz-1);
    }
    return s;
}

string get_next(string x){

    // Returns next term in Conway sequence

    unsigned prev_point = 0;
    vector<string> grp;
    string tmp;
    tmp.resize(x.size());

    // Organize sequence in group of identical consecutive characters

    for (unsigned int i = 0; i < x.size(); ++i){

        if (i != x.size() - 1){

            if (x.at(i) != x.at(i + 1)){
                tmp.assign(x, prev_point, i - prev_point);
                grp.push_back(tmp);
                prev_point = i + 1;
                tmp.clear();
            }
        }
        else if (i != 0){

            if (x.at(i) != x.at(i - 1)){
                tmp = x.at(i);
                grp.push_back(tmp);
                tmp.clear();
            }
        }
    }

    // Phonetically say each group

    // Could use a lambda: transform(begin(grp), end(grp), begin(said_grp)[=](string s){return say(s);});
    // if I create a new vector<string> said_grp to copy in
    // That didn't help the runtime error

    for (auto& i : grp)
        i = say(i);

    // Join each vector<string> entry into a single string

    string next_seq;
    next_seq = accumulate(begin(grp), end(grp), string(""));
    return next_seq;
}

string conway(string init, int n){

    // Print out nth Conway term
    // starting sequence at init

    for (int i = 1; i <= n; ++i)
        init = get_next(init);
    return init;
}

int main(int argc, const char* argv[]){

    if (argc < 3){
        print_usage();
        return 0;
    }
    cout << endl << "Conway number: " << conway(argv[1], stoi(argv[2])) << endl;
    return 0;
}

一般方法:

1. 接受两个参数:Conway 序列的第一项，以及一个整数 n 选择计算该序列的第 n 项。
2. conway(...) 函数循环将 get_next() 应用于初始字符串 n 次。
3. say() 函数“读出”数字。
4. get_next() 的功能是将整个数字拆分成连续的相同数字；然后每个都被 say() 转换。

我遇到的问题是一个错误，std::out_of_range，来 self 的 say() 函数的返回语句。但是，我记得单独使用各种输入测试 say()，它从未导致异常。我必须以某种方式错误地使用它。正如我在代码注释中指出的那样，我之前尝试使用 STL 转换而不是带有 lambda 的 for 循环，同样的错误。

---

注意:对 Conway 序列感兴趣的人，请参阅 Conway 的原始论文。他们承认了一些有趣的性质，而且似乎他们产生了一个称为康威常数的常数，该常数被证明是代数的。

Answer 1

正如我在评论中提到的，这是使用调试器解决的完美问题。 80 多个(非常聪明的)人看过你的代码，但没有人能够仅仅通过查看就完全解决它(尽管 @hlt 得到了很多)。经过一些调试后，我想我已经掌握了其余部分。让我们看看这些片段。

如 hlt 所说，您需要在 get_next() 中基于范围的 for 循环中使用 auto&，否则您实际上永远不会更改 grp 并且您不断取回您的原始号码。参见 this question了解更多信息。

另外，感谢 hlt，您缺少了一段关于零长度字符串输入的逻辑。但是，您的 get_next() 函数中还缺少另一部分。以输入 ./conway 111 2 为例。数字 111 实际上永远不会被放入 grp 因为所有的字符都是相同的，所以 if (x.at(i) != x.at (i + 1)) 和 if (x.at(i) != x.at(i - 1)) 都不会计算为真；因此，您将得到一个空字符串作为结果。缺少的部分包含在下面。

for (unsigned int i = 0; i < x.size(); ++i){

    if (i != x.size() - 1){

        if (x.at(i) != x.at(i + 1)){
            tmp.assign(x, prev_point, i+1 - prev_point);
            grp.push_back(tmp);
            prev_point = i + 1;
            tmp.clear();
        }
    }
    else if (i != 0){

        if (x.at(i) != x.at(i - 1)){
            tmp = x.at(i);
            grp.push_back(tmp);
            tmp.clear();
        }
        else
        {
            tmp.assign(x, prev_point, i+1 - prev_point);
            grp.push_back(tmp);
            tmp.clear();
        }
    }

我在上面的评论中提到的最后一个问题，并包含在此处的代码中。要将正确长度的子字符串分配给 tmp，您需要 i+1-prev_point 而不是 i-prev_point。

开始时我说我认为我已经捕获了其余的错误，但这可能不是真的。我建议用大量具有不同特征(例如 1、12121212、0000、1222、2221 等)的数字及其预期结果编写一些测试。如果它们中的任何一个给出了意想不到的结果，那么是时候返回调试器了。