问算法思维指南(4 4方程)

EN

这是个有趣的问题。这里发生了几件不同的事情。一个问题是如何描述进入算术表达式的操作和操作数的顺序。使用括号来建立操作顺序是非常麻烦的，因此我建议将表达式看作是操作和操作的堆栈，比如- 4 4 ( 4-4 )、+ 4 * 4 4 (4*4)+4、* 4 + 4 4 for (4+4)*4等等，这就像HP计算器上的反向波兰符号。那么，您就不必担心括号了，当我们构建越来越大的表达式时，表达式的数据结构将在下面有所帮助。

现在我们来讨论构建表达式的算法。在这种情况下，不起作用，我认为，因为(例如)要在0到100的范围内构造一些数字，您可能不得不暂时超出该范围。

一个更好的方法来概念化这个问题，我认为，是作为宽度优先搜索(BFS)的一个图表。从技术上讲，这个图是无限的(所有正整数，所有整数，或者所有有理数，取决于你想要得到的精细程度)，但是在任何时候你都只能得到图的有限部分。稀疏图数据结构将是合适的。

图上的每个节点(数)都有一个与其相关的权重，达到该节点所需的最少4个节点数，以及达到该结果的表达式。最初，您将只从节点(4)开始，并使用与其相关的数字1(生成4需要1)和简单的表达式"4“。你也可以投球(44)与重量2，(444)与重量3，(4444)与重量4。

要构建更大的表达式，请将所有不同的操作应用于这些初始节点。例如，一元否定，阶乘，平方根；二进制运算，如堆栈底部的* 4，乘以4，+ 4，- 4，/ 4，^ 4进行指数运算，还有+ 44等。运算的权重是该运算所需的4s数；一元操作的权重为0，+ 4的权重为1，* 44的权重为2，等等。您将将操作的权重添加到其操作的节点的权重中，以获得新的权重，因此，例如，对权重为2的节点(44)和表达式"44“的+ 4将导致权重为3的新节点(48)和表达式"+ 4 44”。如果用于48的结果具有比现有的结果48更好的权重，则将该新节点替换(48)。

在应用函数时，您将不得不使用某种意义。阶乘(4444)将是一个非常大的数字；为您的阶乘函数设置一个域是明智的，这将防止结果变得太大或超出界限。对于像/4这样的函数，如果您不想处理分数，那么假设4的非倍数不在/4的范围之内，并且在这种情况下不应用运算符。

得到的算法非常类似于Dijkstra在图中计算距离的算法，尽管不是完全相同。

我认为这里的蛮力解决方案是唯一的出路。

这背后的原因是，每个数字都有不同的方法来获得它，而获得一个特定的x可能与获取x+1无关。

话虽如此，在可能的情况下，您可以通过使用明显的动作来使蛮力解决方案更快一些。

例如，如果我使用"4“三次(4*4+4)达到20次，显然可以达到16、24和80。持有100位的数组并标记所达到的数字

类似于子集和问题，可以使用动态规划(DP)通过以下递归公式来求解：

D(0,0) = true
D(x,0) = false     x!=0
D(x,i) = D(x-4,i-1) OR D(x+4,i-1) OR D(x*4,i-1) OR D(x/4,i-1)

通过使用DP技术计算上面的数字，可以很容易地找出使用这4's可以生成哪些数字，并且通过返回解决方案，您可以了解每个数字是如何生成的。

此方法的优点(在使用DP实现时)是不多次重新计算多个值。我不确定它是否真的有效，但我相信，从理论上讲，这可能是一个重大的改进，一个限制较少的概括这个问题。