给定一组数字和运算符，使用最少的运算次数形成给定的数字

Question

我们在测试中被问到以下问题，我不确定如何解决它：

给定一组数字和一组运算符，找到生成该数字的最少运算次数。

例如：
输入
set of digits: {8, 1, 6, 2, 7}
set of operations: {*, /, -}
number to be generated: 981

输出
number of operations: 2

Explanation: 981 = 16 * 62 - 11 [ 2 operations: * and - ]

限制条件：
all numbers to be used as integers
0 <= each number in set of digits <= 9
possible set of operations: { +, -, *, / } [ the division operation will always return an integer ]
0 <= number to be generated <= 999
it is necessary that while performing the operations, any of the calculated values must not exceed 999 or be negative
the precedence of operations will always be from left to right, BODMAS/PEMDAS won't be followed. For example: 16*6+2*11 will be calculated as: ((16*6) + 2) * 11

如能提供解决方案方面的任何帮助，我们将不胜感激。

我认为这个问题可以通过生成一个最接近给定数字的数字来解决，然后可以考虑生成一个新的数字问题。尽管我认为这不会产生形成给定数字所需的最少操作数。

无法编写太多代码，因为我不确定如何找到解决方案。

提前致谢！

Answer 1

我们可以把这个问题看成一个图问题，并使用 BFS 解决它。

首先，我们尝试在不使用任何运算符的情况下从 set of numbers 中创建所有可能的数字，称之为基集。这可以通过将每个数字分解成数字并检查所有这些数字是否属于 set of numbers.

来轻松实现。

for (int i = 0; i < 1000; i++){
   if i can be formed by set of numbers {
      add i to base set;
   } 
}

现在，以基集中的每个数字为起始顶点，通过对基集应用不同的算子遍历到下一个顶点

Queue q = base set
int[] distance = new int[1000]; 
while q is not empty{
   int number = q.pop();
   for(int i : base set){
      for(operator : set of operators) {
          int next = number operator i
          if next < 1000 && next >= 0 && next not visited {
              mark next as visited;
              distance[next] = 1 + distance[number];
              q.add(next);
          } 

      }
   }

} 
return distance[target];

每个顶点都会被访问一次，所以时间复杂度为O(n ^ 2 * m)，其中n是顶点的最大数量（本例中为1000），m是数量运算符

给定一组数字和运算符，使用最少的运算次数形成给定的数字

Given a set of digits and operators, form the given number using least number of operations

algorithm

data-structures

graph

dynamic-programming

breadth-first-search