如何使C找到所有不同的符号（+，-，*，/）组合以获得一定的输出

Question

我有以下等式： 8 ? 7 ? 6 ? 5 ? 4 ? 3 ? 2 ? 1 = 36 并且我需要编写一个 C 程序来查找哪些运算符（来自 +, -, *, /）而不是 ? 以使等式成立。

我最初的想法是我有 4*7=28 个不同的组合。所以我开始制作数组，首先添加所有 + 然后将 + 的数量减 1 并添加另一个符号并查看等式是否正确。但是我对自己的方向感到困惑。

此外，我在很多 google 搜索中都没有找到任何类似的东西，所以这是我最后的选择。

谢谢！

Answer 1

多棒的拼图...

这是我的解决方案（它变小了，正如我自己预期的那样）。

findOps.c:

#include <assert.h>
#include <stdio.h>

/* too lazy to type this everytimes out... */    
typedef unsigned int uint;

/* enumeration of all supported operators */
enum {
  Add, Sub, Mul, Div
};
/* It is also used as encoding for compact storage with 2 bits. */

/* extracts operator i from ops. */
uint getOp(uint ops, uint i) { return (ops >> 2 * i) & 3; }

/* solves the equation with nValue values and (nValue - 1) ops
 * and returns the result.
 * This considers operator precedences appropriately.
 */
int solve(uint nValues, int values[], uint ops)
{
  int sum = 0; /* accu for add, subtract */
  int prod = values[0]; /* accu for multiply, divide */
  for (int i = 1; i < nValues; ++i) {
    int arg2 = values[i];
    switch (getOp(ops, i - 1)) {
      case Add:
        sum += prod;
        prod = arg2;
        break;
      case Sub:
        sum += prod;
        prod = -arg2;
        break;
      case Mul:
        prod *= arg2;
        break;
      case Div:
        prod /= arg2;
        break;
    }
  }
  sum += prod;
  return sum;
}

/* pretty prints the equation out of internal representation. */
void print(uint nValues, int values[], uint ops, int result)
{
  char chrOp[4] = { '+', '-', '*', '/' };
  printf("%d", values[0]);
  for (uint i = 1; i < nValues; ++i) {
    printf(" %c %d", chrOp[getOp(ops, i - 1)], values[i]);
  }
  printf(" == %d\n", result);
}

/* main function */
int main()
{
  /* assume some kind of input which provides the arguments and intended result */
  int values[] = { 8, 7, 6, 5, 4, 3, 2, 1 };
  enum { nValues = sizeof values / sizeof *values };
  int result = 36;
  /* check all combinations of operators */
  uint opsEnd = 1 << 2 * (nValues - 1);
  assert(8 * sizeof opsEnd >= 2 * (nValues - 1)); /* paranoid check whether opsEnd has enough bits */
  uint ops = 0;
  do {
    if (solve(nValues, values, ops) == result) {
      print(nValues, values, ops, result);
    }
  } while (++ops != opsEnd);
  /* done */
  return 0;
}

在 Windows 7:

cygwin 中进行测试

$ gcc -std=c11 -o findOps findOps.c

$ ./findOps 
8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 == 36
8 * 7 - 6 * 5 + 4 + 3 + 2 + 1 == 36
8 * 7 - 6 - 5 * 4 + 3 + 2 + 1 == 36
8 + 7 * 6 - 5 * 4 + 3 + 2 + 1 == 36
8 * 7 - 6 - 5 - 4 * 3 + 2 + 1 == 36
8 + 7 * 6 - 5 - 4 * 3 + 2 + 1 == 36
8 + 7 + 6 * 5 - 4 * 3 + 2 + 1 == 36
8 * 7 / 6 * 5 - 4 * 3 + 2 + 1 == 36
8 * 7 / 6 * 5 / 4 * 3 + 2 + 1 == 36
8 / 7 * 6 * 5 + 4 + 3 - 2 + 1 == 36
8 + 7 * 6 / 5 * 4 - 3 - 2 + 1 == 36
8 + 7 - 6 + 5 * 4 + 3 * 2 + 1 == 36
8 + 7 / 6 + 5 * 4 + 3 * 2 + 1 == 36
8 * 7 / 6 + 5 * 4 + 3 * 2 + 1 == 36
8 * 7 - 6 - 5 - 4 - 3 * 2 + 1 == 36
8 + 7 * 6 - 5 - 4 - 3 * 2 + 1 == 36
8 + 7 + 6 * 5 - 4 - 3 * 2 + 1 == 36
8 * 7 / 6 * 5 - 4 - 3 * 2 + 1 == 36
8 + 7 + 6 + 5 * 4 - 3 * 2 + 1 == 36
8 / 7 * 6 + 5 + 4 * 3 * 2 + 1 == 36
8 / 7 * 6 * 5 + 4 + 3 / 2 + 1 == 36
8 + 7 + 6 * 5 * 4 / 3 / 2 + 1 == 36
8 * 7 - 6 * 5 / 4 * 3 + 2 - 1 == 36
8 * 7 + 6 - 5 * 4 - 3 - 2 - 1 == 36
8 + 7 / 6 * 5 + 4 * 3 * 2 - 1 == 36
8 - 7 + 6 * 5 + 4 * 3 / 2 - 1 == 36
8 / 7 + 6 * 5 + 4 * 3 / 2 - 1 == 36
8 - 7 + 6 + 5 * 4 * 3 / 2 - 1 == 36
8 / 7 + 6 + 5 * 4 * 3 / 2 - 1 == 36
8 - 7 / 6 + 5 * 4 * 3 / 2 - 1 == 36
8 - 7 + 6 * 5 + 4 + 3 - 2 * 1 == 36
8 / 7 + 6 * 5 + 4 + 3 - 2 * 1 == 36
8 * 7 - 6 - 5 - 4 - 3 - 2 * 1 == 36
8 + 7 * 6 - 5 - 4 - 3 - 2 * 1 == 36
8 + 7 + 6 * 5 - 4 - 3 - 2 * 1 == 36
8 * 7 / 6 * 5 - 4 - 3 - 2 * 1 == 36
8 + 7 + 6 + 5 * 4 - 3 - 2 * 1 == 36
8 + 7 + 6 + 5 + 4 * 3 - 2 * 1 == 36
8 * 7 - 6 * 5 + 4 * 3 - 2 * 1 == 36
8 + 7 + 6 + 5 + 4 + 3 * 2 * 1 == 36
8 * 7 - 6 * 5 + 4 + 3 * 2 * 1 == 36
8 * 7 - 6 - 5 * 4 + 3 * 2 * 1 == 36
8 + 7 * 6 - 5 * 4 + 3 * 2 * 1 == 36
8 * 7 + 6 - 5 * 4 - 3 * 2 * 1 == 36
8 - 7 + 6 + 5 + 4 * 3 * 2 * 1 == 36
8 / 7 + 6 + 5 + 4 * 3 * 2 * 1 == 36
8 - 7 / 6 + 5 + 4 * 3 * 2 * 1 == 36
8 - 7 + 6 * 5 + 4 + 3 / 2 * 1 == 36
8 / 7 + 6 * 5 + 4 + 3 / 2 * 1 == 36
8 / 7 * 6 * 5 + 4 * 3 / 2 * 1 == 36
8 / 7 * 6 + 5 * 4 * 3 / 2 * 1 == 36
8 * 7 - 6 * 5 * 4 / 3 / 2 * 1 == 36
8 - 7 + 6 * 5 + 4 + 3 - 2 / 1 == 36
8 / 7 + 6 * 5 + 4 + 3 - 2 / 1 == 36
8 * 7 - 6 - 5 - 4 - 3 - 2 / 1 == 36
8 + 7 * 6 - 5 - 4 - 3 - 2 / 1 == 36
8 + 7 + 6 * 5 - 4 - 3 - 2 / 1 == 36
8 * 7 / 6 * 5 - 4 - 3 - 2 / 1 == 36
8 + 7 + 6 + 5 * 4 - 3 - 2 / 1 == 36
8 + 7 + 6 + 5 + 4 * 3 - 2 / 1 == 36
8 * 7 - 6 * 5 + 4 * 3 - 2 / 1 == 36
8 + 7 + 6 + 5 + 4 + 3 * 2 / 1 == 36
8 * 7 - 6 * 5 + 4 + 3 * 2 / 1 == 36
8 * 7 - 6 - 5 * 4 + 3 * 2 / 1 == 36
8 + 7 * 6 - 5 * 4 + 3 * 2 / 1 == 36
8 * 7 + 6 - 5 * 4 - 3 * 2 / 1 == 36
8 - 7 + 6 + 5 + 4 * 3 * 2 / 1 == 36
8 / 7 + 6 + 5 + 4 * 3 * 2 / 1 == 36
8 - 7 / 6 + 5 + 4 * 3 * 2 / 1 == 36
8 - 7 + 6 * 5 + 4 + 3 / 2 / 1 == 36
8 / 7 + 6 * 5 + 4 + 3 / 2 / 1 == 36
8 / 7 * 6 * 5 + 4 * 3 / 2 / 1 == 36
8 / 7 * 6 + 5 * 4 * 3 / 2 / 1 == 36
8 * 7 - 6 * 5 * 4 / 3 / 2 / 1 == 36

$

Live Demo on coliru

出于对自己编码能力的充分信任，我随机选择了一行并用 Windows 计算器进行了检查 – 是正确的。

备注：

遍历所有可能的运算符组合，运算符+、-、*、/映射到0 .. . 3. 由于这四个值正好可以用2位来存储，所以所有运算符的序列存储在一个unsigned中。这使得通过所有可能的组合进行迭代变得非常容易——它只是递增 resp。 unsigned.
为了求解方程式，我想起了古代袖珍计算器（没有 () 的支持）是如何做到的（资源非常有限）。我记不太清楚了（几十年前有人向我解释过）但能够重新发明它。由于在 +、-、*、/ 中只有两个可能的优先级，因此使用两个缓冲区就足够了——一个用于累积中间产品，一个用于对于累积的中间总和。
计算是在 int 算法中完成的。这意味着这些计算在自然数和整数运算的约束下是数学正确的。（我没有检查 overflow/underflow/wrap-around，但我有一个 "good feeling" 作为示例编号。根据 solve() 的工作方式，只要没有，除以 0 就不是问题0 输入。）
我遗漏的内容：将文本解析为我在示例中使用的数据结构。我把它留作练习...

如何使C找到所有不同的符号（+，-，*，/）组合以获得一定的输出

How to make C find all different symbol (+,-,*,/) combinations to have a certain output

c

combinations

equation