c++ - 在这种情况下，我将如何循环遍历所有各种可能性？

Question

我看到一个我决定尝试的编程作业，它基本上是用户输入类似“123456789=120”的地方，程序必须在不同的位置插入一个“+”或“-”来做出声明真的。例如，在这种情况下，它可以做 123+4-5+6-7+8-9 = 120。只有 3^8 种可能的组合，所以我认为暴力破解它是可以的，但我不我确切地知道我可以按什么顺序进入/如何实际实现它。更具体地说，我不知道插入“+”和“-”时的顺序。这是我所拥有的:

#include <iostream>
#include <cmath>

using namespace std;

int string_to_integer(string);

int main()
{
    string input, result_string;
    int result, possibilities;

    getline(cin, input);

    //remove spaces
    for(int i = 0; i < input.size(); i++)
    {
        if(input[i] == ' ')
        {
            input.erase(i, 1);
        }
    }

    result_string = input.substr(input.find('=') + 1, input.length() - input.find('='));
    result = string_to_integer(result_string);
    input.erase(input.find('='), input.length() - input.find('='));

    possibilities = pow(3, input.length() - 1);
    cout << possibilities;

}

int string_to_integer(string substring)
{
    int total = 0;
    int power = 1;

    for(int i = substring.length() - 1; i >= 0; i--)
    {
        total += (power * (substring[i] - 48));
        power *= 10;
    }

    return total;
}

Answer 1

基本思路:生成+、-运算符的所有可能变体(包括运算符缺失的情况)，然后解析字符串并获得总和。

方法:在组合方面，很容易证明我们可以通过将运算符(或没有运算符)与基数 3 数字相关联来做到这一点。所以我们可以迭代每个 8 位三元数，但不是打印 0、1 和 2，我们将在字符串中的下一个数字之前附加一个“+”、一个“-”或什么都不附加。

请注意，我们实际上为此不需要字符串；也可以直接使用数字和运算符等，即时计算结果。我只采用了基于字符串的方法，因为它解释起来简单，实现起来也很简单，此外，它还为我们提供了一些视觉反馈，有助于理解解决方案。

现在我们已经构建了我们的字符串，我们可以解析它了；最简单的解决方案是为此目的使用 C 标准库函数 strtol()，它将考虑符号并返回一个带符号的整数。因此，我们只需在一个简单的循环中对所有有符号整数求和即可。

代码:

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>

int main()
{
    const char *ops = " +-";

    // 3 ^ 8 = 6561
    for (int i = 0; i < 6561; i++) {
        // first, generate the line
        int k = i;
        std::string line = "1";
        for (int j = 0; j < 8; j++) {
            if (k % 3)
                line += ops[k % 3];

            k /= 3;
            line += (char)('2' + j);
        }

        // now parse it
        int result = 0;
        const char *s = line.c_str();
        char *p;

        while (*s) {
            int num = strtol(s, &p, 10);
            result += num;
            s = p;
        }

        // output
        std::cout << line << " = " << result << (result == 120 ? " MATCH" : "") << std::endl;
    }

    return 0;
}

结果:

h2co3-macbook:~ h2co3$ ./quirk | grep MATCH
12-3-45+67+89 = 120 MATCH
1+2-34-5+67+89 = 120 MATCH
12-3+4+5+6+7+89 = 120 MATCH
1-23+4+56-7+89 = 120 MATCH
1+2+34-5+6-7+89 = 120 MATCH
123+4+5-6-7-8+9 = 120 MATCH
1+2-3+45+6+78-9 = 120 MATCH
12-3+45+67+8-9 = 120 MATCH
123+4-5+6-7+8-9 = 120 MATCH
123-4+5+6+7-8-9 = 120 MATCH
h2co3-macbook:~ h2co3$