请注意：为我糟糕的风格、低效的代码和普遍的愚蠢道歉。我这么做纯粹是出于兴趣。我没有妄想我会成为一名专业的程序员。
如何解决这个问题(假设它可以解决)。要明确的是，你想取一个int x和一个int y，并返回一些y等于x的表达式。例如，如果我输入9和2，最短的解之一(我很确定)将是((2+2)x2)+(2/2)，总共有4个运算符。你可以假设正整数，因为这是我大部分时间都在做的事情。
我找到了一个严格的偏解，它返回任何数字的解，但通常不是最小的。这里它是用python编码的：
def re_express(n, a, expression):
if n==0:
print(expression)
else:
if a**a < n:
n -= a**a
expression += "+" + str(a) + "^" +str(a)
re_express(n, a, expression)
elif a*a < n:
n -= a*a
expression += "+" + str(a) + "*" + str(a)
re_express(n, a, expression)
elif a < n:
n -= a
expression += "+" + str(a)
re_express(n, a, expression)
else:
n -= 1
expression += "+" + str(a) + "/" + str(a)
re_express(n, a, expression)
我也认为我有一个返回了一个非常小的解决方案，但不能保证它是最小的解决方案。我手工模拟了它，它得到了正确的2和9的例子，而我的第一个算法产生了一个5运算符的解决方案：2^2+2^2+2/2。但对于大的n，它会很快变慢。我用伪代码写了下来。
function re_express(n, a, children, root, solutions):
input: n, number to build
a, number to build with
children, an empty array
root, a node
solutions, an empty dictionary
if not root:
root.value = a
if the number of layers in the tree is greater than the size of the shortest solution, return the shortest solution
run through each mathematical operator and create a child node of root as long as the child will have a unique value
each child.value = operator(root, a)
for each child: child.parent = root
for each child: child.operator = operator as a string
loop through all children and check to see what number you need to produce n with each operator, if that number is in the list of children
when you find something like that then you have paths back up the tree, use the following loop for both children (obviously a child with only i
i = 0
while child != root:
expression += “(“ + str(a) + child.operator
child = child.parent
expression += str(a)
for in range(i):
expression += “)”
then you combine the expressions and you have one possible solution to add up to n and you have one possible answer
store the solution in solutions with the key as the number of operators used and the value as the expression in string form
re_express(n, a, children, root, solutions)
正如你所知，该算法的big-O是垃圾，它甚至没有给出一个有保证的解决方案，所以必须有更好的方法。
我们可以使用Dijkstra算法的变体来找到结果。然而，我们并没有真正的图表。如果我们将数字视为图的节点，那么边将从一对节点和一个运算开始，并在另一个数字结束。但这只是一个细节，并没有阻止Dijkstra的想法。
想法如下：我们从y开始，探索越来越多的数字，我们可以使用一组预定义的运算来表达这些数字。对于每个数字，我们存储需要多少运算来表达它。如果我们找到了一个我们已经看到的数字(但上一个表达式需要更多运算)，我们会更新数字的属性(这是Dijktra术语中的路径长度)。
让我们做示例x = 9, y = 2。
最初，我们可以用零运算来表示2。所以，我们把它放在我们的数字列表中：
2: 0 operations
从这个列表中，我们现在需要找到操作次数最少的数字。这是至关重要的，因为它保证了我们再也不需要访问这个数字了。所以我们取2。我们修复它，并探索可以使用2和所有其他固定数表达的新数。现在，我们只有2个，所以我们可以表达(使用+ - * /)：
2: 0 operations, fixed
0: 1 operation (2 - 2)
1: 1 operation (2 / 2)
4: 1 operation (2 + 2 or 2 * 2)
我们走吧。取下一个运算次数最少的数字(不管是哪一个)。我要0。我们不能真正用零来表示新的数字，所以：
2: 0 operations, fixed
0: 1 operation (2 - 2), fixed
1: 1 operation (2 / 2)
4: 1 operation (2 + 2 or 2 * 2)
现在让我们学习1。新数字的运算次数将是输入数字的运算数量加1的总和。因此，使用1，我们可以
2 + 1 = 3 with 0 + 1 + 1 = 2 operations (2 + (2 / 2))
0 + 1 = 1 with 3 operations --> the existing number of operations for `0` is better, so we do not update
1 + 1 = 2 with 3 operations
2 - 1 = 1 with 2 operations
0 - 1 = -1 with 3 operations *new*
1 - 2 = -1 with 2 operations *update*
1 - 0 = 1 with 3 operations
1 - 1 = 0 with 3 operations
2 * 1 = 2 with 2 operations
0 * 1 = 0 with 3 operations
1 * 1 = 1 with 3 operations
2 / 1 = 2 with 2 operations
0 / 1 = 0 with 3 operations
1 / 2 = invalid if you only want to consider integers, use it otherwise
1 / 0 = invalid
1 / 1 = 1 with 3 operations
所以，我们现在的名单是：
2: 0 operations, fixed
0: 1 operation (2 - 2), fixed
1: 1 operation (2 / 2), fixed
3: 2 operations (2 + 2/2)
4: 1 operation (2 + 2 or 2 * 2)
-1: 2 operations (2/2 - 2)
继续拿4，以此类推。一旦你达到了你的目标数字x，你就以尽可能小的方式完成了。
在伪代码中：
L = create a new list with pairs of numbers and their number of operations
put (y, 0) into the list
while there are unfixed entries in the list:
c = take the unfixed entry with the least number of operations
fix c
if c = x:
finish
for each available operation o:
for each fixed number f in L:
newNumber = o(c, f)
operations = c.numberOfOperations + f.numberOfOperations + 1
if newNumber not in L:
add (newNumber, operations) to L
else if operations < L[newNumber].numberOfOperations:
update L[newNumber].numberOfOperations = operations
repeat for o(f, c)
如果将运算列表与数字(或它们的前置运算)一起存储，则可以在末尾重构表达式。
优先级队列不会使用简单的列表，而是可以快速检索操作次数最少的未固定条目。
这是我针对这个问题的代码，我认为这不是最快、最优化的算法，但它应该总能找到最好的答案。首先，让我们假设我们没有括号，并用这些操作['+', '*', '/', '-']来解决寻找将a转换为n的最小操作数的子问题。为了解决这个问题，我们使用BFS。首先，我们定义了一个方程类：
class equation:
def __init__(self, constant, level=0, equation_list=None):
self.constant = constant
if equation_list != None:
self.equation_list = equation_list
else:
self.equation_list = [constant]
self.level = level
def possible_results(self):
return recursive_possible_results(self.equation_list)
def get_child(self, operation):
child_equation_list = self.equation_list + [operation]
child_equation_list += [self.constant]
child_level = self.level + 1
return equation(self.constant, child_level, child_equation_list)
构造函数获得一个常量，它是我们表达式中的常量(这里是a)，一个级别，它指示该方程中使用的运算次数，以及一个equation_list是方程表达式的列表表示。对于第一个节点(root)，我们的级别为0，并且我们的equation_list只有常数。
现在，让我们计算所有可能的方法，用括号括起一个方程。我们使用一个递归函数，它返回所有可能的结果及其表达式的列表：
calculated_expr = {}
def is_operation(symbol):
return (symbol in operations)
def recursive_possible_results(equation_list):
results = []
if len(equation_list) == 1:
return [{'val': equation_list[0], 'expr': str(equation_list[0])}]
key = ''
for i in range(len(equation_list)):
if is_operation(equation_list[i]):
key += equation_list[i]
if key in calculated_expr.keys():
return calculated_expr[key]
for i in range(len(equation_list)):
current_symbol = equation_list[i]
if is_operation(current_symbol):
left_results = recursive_possible_results(equation_list[:i])
right_results = recursive_possible_results(equation_list[i+1:])
for left_res in left_results:
for right_res in right_results:
try:
res_val = eval(str(left_res['val']) + current_symbol + str(right_res['val']))
res_expr = '(' + left_res['expr'] + ')' + current_symbol + '(' + right_res['expr'] + ')'
results.append({'val': res_val, 'expr': res_expr})
except ZeroDivisionError:
pass
calculated_expr[key] = results
return results
(我认为这是代码中需要进一步优化的部分，因为我们不止一次地计算一堆方程。也许是一个好的动态编程算法…)
对于广度优先搜索，我们不需要从根开始探索整棵树。例如，对于将2转换为197，我们至少需要7个操作，因为我们有6个操作的最大数量是128，并且仍然小于197。因此，我们可以从第7级开始搜索树。这里有一个代码来创建我们的第一级节点(方程)：
import math
import itertools
def create_first_level(n, constant):
level_exprs = []
level_number = int(math.log(n, constant)) - 1
level_operations = list(itertools.product(operations, repeat=level_number))
for opt_list in level_operations:
equation_list = [constant]
for opt in opt_list:
equation_list.append(opt)
equation_list.append(constant)
level_exprs.append(equation(constant, level_number, equation_list))
return level_exprs
最后，我们调用我们的BFS并得到结果：
def re_express(n, a):
visit = set()
queue = []
# root = equation(a)
# queue.append(root)
# Skip levels
queue = create_first_level(n, a)
while queue:
curr_node = queue.pop(0)
for operation in operations:
queue.append(curr_node.get_child(operation))
possible_results = curr_node.possible_results()
for pr in possible_results:
if pr['val'] == n:
print(pr['expr'])
print('Number of operations: %d' % curr_node.level)
queue = []
break
re_express(9, 2)
这是输出：
(((2)+(2))*(2))+((2)/(2))
Number of operations: 4