测试所有数学顺序的算法

Question

我想实现，用户可以输入 ints (int[]) 的数组，以及所需的 target.

那么程序应该可以在add, subtract中测试所有可能性, 乘法和除法，以及return正确，如果给出任何可能性的话。

示例：

int[] = {1, 4, 6, 3}, target = 8

（程序测试所有内容，从 1+4+6+3 到 1/4/6/3）

想要的结果

1+4+6-3

是正确答案，因为 1+4+6-3 == 8

Answer 1

让我们试试蛮力 - 我们只有几个公式（3**4 == 81 个）要测试。首先，让我们生成所有格式：

using System.Data;
using System.Linq;

...

private static IEnumerable<string> Formulae(int[] numbers) {
  char[] alphabet = new char[] { '+', '-', '*', '/' };

  int[] current = new int[numbers.Length - 1];

  do {
    yield return string.Concat(numbers
      .Select((d, i) => $"{(i > 0 ? alphabet[current[i - 1]].ToString() : "")}{d}"));

    for (int i = 0; i < current.Length; ++i)
      if ((current[i] = (current[i] + 1) % alphabet.Length) != 0)
        break;
  }
  while (!current.All(i => i == 0));
}

然后我们Compute每个公式：

private static string Solve(int[] numbers, int target) {
  using (DataTable table = new DataTable()) {
    foreach (string formula in Formulae(numbers)) {
      try {
        int result = Convert.ToInt32(table.Compute(formula, null));

        if (result == target)
          return $"{formula} = {target}";
      }
      catch (DivideByZeroException) {
        ;
      }
    }
  }

  return "No solution";
}

演示：

Console.Write(Solve(new int[] { 1, 4, 6, 3 }, 8));

结果：

1+4+6-3 = 8

如果您想获得所有解决方案，您只需稍加修改:

private static IEnumerable<string> AllSolutions(int[] numbers, int target) {
  using (DataTable table = new DataTable()) {
    foreach (string formula in Formulae(numbers)) {
      int result; 

      try {
        result = Convert.ToInt32(table.Compute(formula, null));
      }
      catch (DivideByZeroException) {
        continue;
      }

      if (result == target)
        yield return $"{formula} = {target}";
    }
  }
}

演示：

Console.Write(string.Join(Environment.NewLine, 
  AllSolutions(new int[] { 1, 4, 6, 3 }, 8)));

结果：

1+4+6-3 = 8
1*4*6/3 = 8

编辑：在上面的实现中我使用了整数除法，例如

1 / 4 == 0

如果要使用浮点除法，即

1.0 / 4.0 = 0.25

你应该稍微修改一下代码：

// note ".0" in the very end of the Select 
private static IEnumerable<string> Formulae(int[] numbers) {
  ...
  yield return string.Concat(numbers
    .Select((d, i) => $"{(i > 0 ? alphabet[current[i - 1]].ToString() : "")}{d}.0"));
  ...
}

private static IEnumerable<string> AllSolutions(int[] numbers, 
                                                int target, 
                                                double tolerance = 1e-8) {
  using (DataTable table = new DataTable()) {
    foreach (string formula in Formulae(numbers)) {
      double result = Convert.ToDouble(table.Compute(formula, null));

      // Compare with tolerance
      if (Math.Abs(result - target) < tolerance)
        yield return $"{formula} = {target}";
    }
  }
}

测试所有数学顺序的算法

Algorithm for testing all mathematical order

c#

algorithm

math