在這種情況下，我將如何循環所有各種可能性？

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

以下bool advance(string& s)功能會給你的任意長度的'+'，'-'和' '字符串的所有組合除一人外，並返回false如果沒有更多可用。

char advance(char c) 
{ 
    switch (c) 
    { 
     case ' ': return '+'; 
     case '+': return '-'; 
     default: case '-': return ' '; 
    } 
} 

bool advance(string& s) 
{ 
    for (int i = 0; i < s.size(); ++i) 
     if ((s[i] = advance(s[i])) != ' ') 
      return true; 

    return false; 
} 

你必須先用一個只含有所需長度空格的字符串餵它，然後重複「推進」它。用法：

string s = " "; 
while (advance(s)) 
    cout << '"' << s << '"' << endl; 

上面的代碼將打印

"+ " 
"- " 
" + " 
"++ " 
"-+ " 
" - " 
. 
. 
. 
" ---" 
"+---" 
"----" 

注意，只有4位的「第一」組合不打印。

你可以將這些組合與你的lhs交錯，跳過空格來產生表達式。

Answer 2

的基本思想：生成+，-運算符（包括其中操作者丟失的情況下）的所有可能的變型中，然後分析該字符串，將獲得的總和。

方法：結合起來，很容易證明我們可以通過將運算符（或不存在）與基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$ 

Answer 3

另一個非常類似的方法，在普通的COK，在C++中，如果你真的想這樣說。）並且有點可配置

相同的基數3數字技巧用於枚舉void，+和 - 運算符的組合。

將該字符串處理爲正值或負值的列表，並將其相加。

其他貢獻是非常緊湊和優雅，但使用一些C技巧來縮短代碼。
這一個有希望更詳細一點，雖然不是很漂亮。

#include <iostream> 
#include <string> 
using namespace std; 

#include <string.h> 
#include <math.h> 

void solver (const char * str, int result) 
{ 
    int op_max = pow(3, strlen(str)); // number of operator permutations 

    // loop through all possible operator combinations 
    for (int o = 0 ; o != op_max ; o++) 
    { 
     int res = 0; // computed operation result 
     int sign = 1; // sign of the current value 

     int val = str[0]-'0'; // read 1st digit 
     string litteral;  // litteral display of the current operation 

     // parse remaining digits 
     int op; 
     for (unsigned i=1, op=o ; i != strlen (str) ; i++, op/=3) 
     { 
      // get current digit 
      int c = str[i]-'0'; 

      // get current operator 
      int oper = op % 3; 

      // apply operator 
      if (oper == 0) val = 10*val + c; 
      else 
      { 
       // add previous value 
       litteral += sign*val; 
       res += sign*val; 

       // store next sign 
       sign = oper == 1 ? 1 : -1; 

       // start a new value 
       val = c; 
      } 
     } 

     // add last value 
     litteral += sign*val; 
     res += sign*val; 

     // check result 
     if (res == result) 
     { 
      cout << litteral << " = " << result << endl; 
     } 
    } 
} 

int main(void) 
{ 
    solver ("123456789", 120); 
} 

注：我使用std::string s出於懶惰，雖然他們是出了名的緩慢。