在字符串中使用递归？

Question

我是一名编码初学者，我参加了一次分班评估，我一直试图得出这个评估的逻辑question.Even评估后我试图参考并解决，但后来我不能't.Some 帮助将不胜感激...... 我不记得约束等，但问题是这样的。他们给出了两个字符串“11100”和“1111000”作为输入。（它们是前两个字符串）第三个字符串的公式如下：
No。个数 = 1 x 没有。第二串中的那些 + 2 x 没有。第一个字符串中的零数。
零数 = 2 x 数。第二个字符串中的零 + 2 x 没有。第一个字符串中的那些。

基本上对于第 n 个数字公式是这样的：
没有。第 n 个字符串中的个数 = 1 x 没有。第 (n-1) 个字符串中的一个 + 2 x 没有。第 (n-2) 个字符串中的零
没有。零的数量 = 2 x 没有。第二 (n-1) 个零点 + 2 x 没有。第 (n-2) 个字符串中的一个。

所以他们会给出一个数字 n 并且对于那个位置我们需要找到字符串。
请帮助我，我已经为这个问题苦苦挣扎了好几个星期....
如果能用 C++ 回答，我将不胜感激，因为我对它有很好的理解。

Answer 1

也许有人可以在某个时候提出对此的改进建议，但这是我可以快速汇总的内容。

第一个观察结果：实际的字符串并不重要。我们需要存储的只是零的数量和一的数量，我们可以在 POD 结构中做到这一点。

第二个观察：这看起来很像斐波那契数列的变体，我们可以使用类似的算法。每个第 n 个字符串都依赖于前面的两个个字符串。因此我们需要三个字符串来遍历这个序列：下一个（此处为 n3）、当前字符串（此处为 n2）和前一个字符串（此处为 n1）。 n3完全可以根据你的公式计算出来。对于下一次迭代，我们“循环遍历”字符串，因此 - 再次 - n2 成为当前字符串，而 n1 成为之前的字符串。

C++20 中的代码：

#include <algorithm>
#include <iostream>
#include <string_view>

struct Occurences
{
    unsigned zeros;
    unsigned ones;
};

std::ostream &operator<<(std::ostream &out, Occurences const &occ)
{
    out << '[' << occ.zeros << ", " << occ.ones << ']';
    return out;
}

void findNthOccurence(Occurences n1, Occurences n2, unsigned nMax)
{
    for (unsigned n = 3; n <= nMax; ++n)
    {
        Occurences n3{.zeros = 2 * n2.zeros + 2 * n1.ones,
                      .ones = n2.ones + 2 * n1.zeros};
        n1 = n2;
        n2 = n3;

        std::cout << n << ": " << n2 << '\n';
    }
}

int main()
{
    std::string_view const str1{"11100"};
    std::string_view const str2{"1111000"};

    Occurences const n1{.zeros = static_cast<unsigned>(std::ranges::count(str1, '0')),
                        .ones = static_cast<unsigned>(str1.size()) - n1.zeros};
    Occurences const n2{.zeros = static_cast<unsigned>(std::ranges::count(str2, '0')),
                        .ones = static_cast<unsigned>(str2.size()) - n2.zeros};


    std::cout << "[zeros, ones]\n"
              << "1: " << n1 << "\n2: " << n2 << '\n';

    findNthOccurence(n1, n2, 10U);
}

输出：

[zeros, ones]
1: [2, 3]
2: [3, 4]
3: [12, 8]
4: [32, 14]
5: [80, 38]
6: [188, 102]
7: [452, 262]
8: [1108, 638]
9: [2740, 1542]
10: [6756, 3758]

打印实际生成的（长）字符串很简单，此处省略。

最后请注意，虽然公式是递归定义的，但我们实际上并不需要递归实现它。

在字符串中使用递归？

Use of recursion in strings?

c++

string

algorithm

recursion

data-structures