算法思维指导（四次方程）

Question

我最近看到了一个名为 4 Fours 的 logic/math 问题，您需要使用 4 个 fours 和一系列运算符来创建等于所有整数 0 到 N 的方程式。

你会如何编写一个优雅的算法来提出前 100 个...

我首先创建基础计算，例如 4-4、4+4、4x4、4/4、4!、Sqrt 4，并将这些值设为整数。

但是，我意识到这将是一种蛮力方法，用于测试组合以查看它们是否相等，0 然后 1，然后 2，然后 3 等等...

然后我想到找到上述值的所有可能组合，检查结果是否小于 100 并填充一个数组，然后对其进行排序...再次效率低下，因为它可能会找到 1000 个超过 100 的数字

任何有关如何解决此类问题的帮助都会有所帮助...不是实际代码...但如何思考这个问题

谢谢！！

Answer 1

我认为这里的蛮力解决方案是唯一的方法。
这背后的原因是每个数字都有不同的获取方式，并且获取某个 x 可能与获取 x+1.

无关

话虽如此，您可以通过尽可能使用明显的移动来使蛮力解决方案更快一些。
例如，如果我使用“4”三次得到 20 (4*4+4)，显然得到 16、24 和 80。持有一个 100 位的数组并标记达到的数字

Answer 2

类似于子集求和问题，可以使用Dynamic Programming (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 可以产生哪些数字，通过回溯解决方案，您可以找出每个数字是如何构建的。

此方法（使用 DP 实现时）的优点是您不会多次重新计算多个值。我不确定它是否真的对 4 个 4 有效，但我相信理论上它可能是一个重大改进，可以减少对这个问题的泛化限制。

Answer 3

这个答案只是 Amit 的扩展。本质上，您的操作是：

将一元运算符应用于现有表达式以获得新表达式（这不使用任何额外的 4s）
将二元运算符应用于两个现有表达式以获得新表达式（新表达式的 4 数等于两个输入表达式的总和）

对于 1..4 中的每个 n，计算 Expressions(n) - (Expression, Value) 对的列表，如下所示：（对于固定的 n，只在列表中存储 1 个计算结果为任何给定值的表达式）

用 n 4 的连接初始化列表（即 4、44、444、4444）
对于从 1 到 n-1 的 i，以及每个允许的二元运算符 op，添加一个表达式（和值）e1 op e2，其中 e1 是在 Expressions(i) 和 e2 在 Expressions(n-i)
将一元运算符重复应用于目前在步骤 1-3 中计算的 expressions/values。何时停止（递归地应用 3）有点模糊，如果迭代没有产生新值肯定会停止。可能会限制您允许的值的大小或表达式的大小。

示例一元运算符是 !、Sqrt、- 等。示例二元运算符是 +-*/^ 等。您可以轻松地将此方法扩展到具有更多运算符的运算符如果允许的话。

对于任何给定的 n，您可以在第 3 步永不结束方面做一些更聪明的事情。直到 Expressions(j) 对所有 j < i 完成后，简单方法（如上所述）才开始计算 Expressions(i)。这要求我们知道何时停止。另一种方法是为每个n构建一个特定最大长度的表达式，然后如果你需要（因为你还没有找到特定的值），在外循环中扩展最大长度。

Answer 4

这是一个有趣的问题。这里发生了几件不同的事情。一个问题是如何描述进入算术表达式的操作序列和操作数。使用圆括号来确定运算顺序非常混乱，因此我建议将表达式视为运算符和操作数的堆栈，例如 - 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 才能得到 4）和简单的表达式“4”。您还可以放入重量为 2 的 (44)、重量为 3 的 (444) 和重量为 4 的 (4444)。

要构建更大的表达式，请将所有不同的操作应用于那些初始节点。例如，一元取反、阶乘、平方根；二元运算，如堆栈底部的 * 4 用于乘以 4，+ 4、- 4、/ 4、^ 4 用于求幂，以及 + 44,等。一个操作的权重就是该操作需要4s的个数；一元运算的权重为 0，+ 4 的权重为 1，* 44 的权重为 2，等等。您可以将运算的权重添加到它运行的节点的权重上，以获得新权重，因此例如 + 4 作用于权重为 2 和表达式“44”的节点 (44) 将导致权重为 3 和表达式“+ 4 44”的新节点 (48)。如果 48 的结果比 48 的现有结果具有更好的权重，则用该新节点替换 (48)。

你在应用函数的时候要有一定的感觉。 factorial(4444) 将是一个非常大的数字；为您的阶乘函数设置一个域是明智的，这将防止结果变得太大或超出范围。与 / 4 等功能相同；如果您不想处理分数，请说非 4 的倍数在 / 4 的范围之外，并且在这种情况下不要应用运算符。

生成的算法与计算图中距离的 Dijkstra 算法非常相似，尽管不完全相同。

算法思维指导（四次方程）

Guidance on Algorithmic Thinking (4 fours equation)

algorithm

computation-theory