-1

这是我的问题：“我给你 4 个数字 1、2、3、4。我希望你使用所有这四个数字来创建数字 1、2、3 等的数学表达式。获胜者将是产生从 1 向上的最长数字范围。您可以使用数学符号 + - * / 。此外，允许使用括号和平方根。请注意，您可以将数字并排放置以形成 2 或 3 位数字. 例子是：

1 = ( 3/1 ) - ( 4/ 2 )

2 = ( 2 * 3 ) – ( 4/1)

3 = 21 / ( 3 + 4 )

4 = "

所以我需要一个算法：

    `Input: an integer`

    `Output: an expression formed by digits 1,2,3,4`

现在我只能想到蛮力算法：

First try the expression which formed by only one-digit number. In this expression, try all 4 operators +,-,*,/ in every possible position. Then try to put more bracket.

Then try try the expression which formed by two-digit number and two one digit number...

但是实现这个算法很困难，因为我想不出所有的情况。

有人有更好的想法吗？

4

2 回答 2

1

表达式可以包含多次出现的数字吗？

如果没问题，您只需要编号为 1 到 4 的表达式。您可以通过重复将 4 添加到一个基本表达式来计算其他自然数。

如果数字必须恰好出现一次，请暂时忽略括号和平方根。那么您最多有 7 个长度的表达式：4 个数字（并列的数字形成一个数字）和最多 3 个（中缀）运算符。这应该适合穷举搜索。

具有 7 个插槽的表达式的示例计数：

（7选4）*4！*（4选3）*3！

7 个位置中的 4 个位置，在这些位置上排列 4 个数字，从 4 个运算符中选择 3 个，排列它们的顺序。

括号最多添加 6 个插槽：每个运算符最多 1 对（否则您的表达式在语法上将不正确）。

平方根可以位于任何被数字占用的插槽的前面，位于左括号的前面和另一个平方根的前面。请注意，由于每个数字可能只出现一次，因此不使用平方根可表示的最大数是有界的。由于根收缩任何数字> 1，迭代平方根应用程序的最大数量也是有界的（我认为最大为 4）

于 2013-09-05T23:10:13.367 回答
0

从数字求解器开始，例如来自 Rosetta Code 的这些- 您希望将目标设为变量，而不是这些程序中固定的 24 个。然后，您需要通过连接（或不连接）您的输入数字来生成所有可能的数字集，并将它们放在求解器中。

更好的是，如果您以 Python 求解器为例，它将根据输入数字生成方程并评估它们以寻找给定的目标。而不是寻找一个特定的目标，你可以存储方程产生的任何整数的集合（连同产生它们的方程，然后在最后排序并从你拥有的 1 中提取最长的序列。保证从 1 中给出最长的序列.

于 2013-09-06T06:53:01.963 回答