algorithm - 逆波兰表示法的简化算法

Question

几天前，我在玩 Befunge，这是一种深奥的编程语言。Befunge 使用 LIFO 堆栈来存储数据。当您编写程序时，从 0 到 9 的数字实际上是 Befunge 指令，它将相应的值压入堆栈。因此，例如，这会将 7 推入堆栈：

34+

为了推动大于 9 的数字，必须对小于或等于 9 的数字进行计算。这将产生 123。

99*76*+

在用 Befunge 解决欧拉问题 1时，我不得不将相当大的数字 999 推入堆栈。在这里，我开始思考如何用尽可能少的指令完成这项任务。通过用中缀符号写下一个术语并取出我想出的共同因素

9993+*3+*

也可以简单地将两个两位数相乘，得到 999，例如

39*66*1+*

我考虑了一会儿，然后决定编写一个程序，该程序根据这些规则以反向波兰表示法对任何给定整数输出最小的表达式。这就是我目前所拥有的（用 NodeJS 和 underscorejs 编写的）：

var makeExpr = function (value) {
    if (value < 10) return value + "";
    var output = "", counter = 0;
    (function fn (val) {
        counter++;
        if(val < 9) { output  += val; return; };
        var exp = Math.floor(Math.log(val) / Math.log(9));
        var div = Math.floor(val / Math.pow(9, exp));
        _( exp ).times(function () { output += "9"; });
        _(exp-1).times(function () { output += "*"; });
        if (div > 1) output += div + "*";
        fn(val - Math.pow(9, exp) * div);    
    })(value);
    _(counter-1).times(function () { output+= "+"; });
    return output.replace(/0\+/, "");
};

makeExpr(999);
// yields 999**99*3*93*++

这段代码天真地构造了表达式，并且显然很长。现在我的问题：

• 是否有一种算法可以简化反向波兰符号中的表达式？
• 在中缀符号中简化会更容易吗？
• 可以证明像这样的表达式9993+*3+*是可能的最小表达式吗？

我希望你能提供一些见解。提前致谢。

Answer 1

还有93*94*1+*，基本上就是27*37。

如果我要解决这个问题，我会首先尝试将数字平均分配。所以给定 999 我会除以 9 得到 111。然后我会尝试除以 9、8、7 等，直到我发现 111 是 3*37。

37 是素数，所以我贪婪地除以 9，得到 4，余数为 1。

这似乎给了我尝试过的半打的最佳结果。当然，测试偶数可分性有点贵。但也许不会比生成一个太长的表达式更昂贵。

使用这个，100 变成55*4*. 102 的结果29*5*6+。

101提出了一个有趣的案例。101/9 = (9*11) + 2。或者，或者，(9*9)+20。让我们来看看：

983+*2+  (9*11) + 2
99*45*+  (9*9) + 20

是直接生成postfix还是生成infix和convert更容易，我真的不知道。我可以看到每个人的优点和缺点。

无论如何，这就是我要采取的方法：首先尝试均分，然后贪婪地除以 9。不确定我将如何构建它。

一旦你弄清楚了，我肯定想看看你的解决方案。

编辑

这是一个有趣的问题。我想出了一个递归函数，它可以可靠地生成后缀表达式，但这不是最佳的。这是在 C# 中。

string GetExpression(int val)
{
    if (val < 10)
    {
        return val.ToString();
    }
    int quo, rem;
    // first see if it's evenly divisible
    for (int i = 9; i > 1; --i)
    {
        quo = Math.DivRem(val, i, out rem);
        if (rem == 0)
        {
            // If val < 90, then only generate here if the quotient
            // is a one-digit number. Otherwise it can be expressed
            // as (9 * x) + y, where x and y are one-digit numbers.
            if (val >= 90 || (val < 90 && quo <= 9))
            {
                // value is (i * quo)
                return i + GetExpression(quo) + "*";
            }
        }
    }

    quo = Math.DivRem(val, 9, out rem);
    // value is (9 * quo) + rem
    // optimization reduces (9 * 1) to 9
    var s1 = "9" + ((quo == 1) ? string.Empty : GetExpression(quo) + "*");
    var s2 = GetExpression(rem) + "+";
    return s1 + s2;
}

对于 999 它会生成9394*1+**，我认为这是最佳的。

这会为 <= 90 的值生成最佳表达式。从 0 到 90 的每个数字都可以表示为两个一位数的乘积，或者通过形式的表达式表示(9x + y)，其中x和y是一位数。但是，我不知道这能保证大于 90 的值的最佳表达式。

Answer 2

当只考虑乘法和加法时，很容易构造最优公式，因为该问题具有最优子结构性质。也就是说，构建的最佳方式[num1][num2]op是从num1并且num2两者也是最优的。如果还考虑重复，那就不再适用了。

和引起重叠子问题，所以动态规划是适用的num1。num2

我们可以简单地，对于一个数字i：

1. 对于每一个1 < j <= sqrt(i)均分i的，尝试[j][i / j]*
2. 对于每一个0 < j < i/2，尝试[j][i - j]+
3. 采用最好的公式

这当然很容易自下而上地进行，只需从i = 0您想要的任何数字开始并逐步增加。不幸的是，第 2 步有点慢，所以在说 100000 之后等待它开始变得烦人。可能有一些我没有看到的技巧。

C# 中的代码（没有经过很好的测试，但似乎可以正常工作）：

string[] n = new string[10000];
for (int i = 0; i < 10; i++)
    n[i] = "" + i;
for (int i = 10; i < n.Length; i++)
{
    int bestlen = int.MaxValue;
    string best = null;
    // try factors
    int sqrt = (int)Math.Sqrt(i);
    for (int j = 2; j <= sqrt; j++)
    {
        if (i % j == 0)
        {
            int len = n[j].Length + n[i / j].Length + 1;
            if (len < bestlen)
            {
                bestlen = len;
                best = n[j] + n[i / j] + "*";
            }
        }
    }
    // try sums
    for (int j = 1; j < i / 2; j++)
    {
        int len = n[j].Length + n[i - j].Length + 1;
        if (len < bestlen)
        {
            bestlen = len;
            best = n[j] + n[i - j] + "+";
        }
    }
    n[i] = best;
}

---

这是优化总和搜索的技巧。假设有一个数组，对于每个长度，都包含该长度可以产生的最大数字。这个数组还给我们的另一件事可能不太明显，它是一种快速确定大于某个阈值的最短数字的方法（通过简单地扫描数组并注意第一个越过阈值的位置）。总之，这提供了一种快速丢弃大部分搜索空间的方法。

例如，长度 3 的最大数是 81，长度 5 的最大数是 728。现在如果我们想知道如何得到 1009（素数，所以没有找到因数），首先我们尝试第一部分的总和长度为 1（1+1008通过9+1000），找到长度9+1000为 9 个字符（95558***+）。

下一步，检查第一部分长度为 3 或更少的总和，可以完全跳过。1009 - 81 = 929, 和 929（如果第一部分是 3 个字符或更少，则总和的第二部分可以是最低的）大于 728，因此 929 及以上的数字必须至少为 7 个字符长。所以如果总和的第一部分是3个字符，那么第二部分必须至少有7个字符，然后最后还有一个+号，所以总共至少有11个字符。到目前为止最好的是 9，所以这一步可以跳过。

下一步，第一部分有 5 个字符，也可以跳过，因为1009 - 728 = 280, 和要达到 280 或更高，我们至少需要 5 个字符。5 + 5 + 1 = 11, 大于 9，所以不要检查。

无需检查大约 500 个总和，我们只需以这种方式检查 9 个，并且使跳过成为可能的检查非常快。这个技巧足够好，在我的 PC 上生成高达一百万的所有数字只需要 3 秒（之前，需要 3 秒才能达到 100000）。

这是代码：

string[] n = new string[100000];
int[] biggest_number_of_length = new int[n.Length];
for (int i = 0; i < 10; i++)
    n[i] = "" + i;
biggest_number_of_length[1] = 9;
for (int i = 10; i < n.Length; i++)
{
    int bestlen = int.MaxValue;
    string best = null;
    // try factors
    int sqrt = (int)Math.Sqrt(i);
    for (int j = 2; j <= sqrt; j++)
    {
        if (i % j == 0)
        {
            int len = n[j].Length + n[i / j].Length + 1;
            if (len < bestlen)
            {
                bestlen = len;
                best = n[j] + n[i / j] + "*";
            }
        }
    }
    // try sums
    for (int x = 1; x < bestlen; x += 2)
    {
        int find = i - biggest_number_of_length[x];
        int min = int.MaxValue;
        // find the shortest number that is >= (i - biggest_number_of_length[x])
        for (int k = 1; k < biggest_number_of_length.Length; k += 2)
        {
            if (biggest_number_of_length[k] >= find)
            {
                min = k;
                break;
            }
        }
        // if that number wasn't small enough, it's not worth looking in that range
        if (min + x + 1 < bestlen)
        {
            // range [find .. i] isn't optimal
            for (int j = find; j < i; j++)
            {
                int len = n[i - j].Length + n[j].Length + 1;
                if (len < bestlen)
                {
                    bestlen = len;
                    best = n[i - j] + n[j] + "+";
                }
            }
        }
    }
    // found
    n[i] = best;
    biggest_number_of_length[bestlen] = i;
}

仍有改进的余地。此代码将重新检查它已经检查过的总和。有一些简单的方法可以使它至少不检查两次相同的总和（通过记住最后一个find），但这在我的测试中没有显着差异。应该可以找到更好的上限。

Answer 3

长度为 9 的 999 有 44 个解：

39149*+**
39166*+**
39257*+**
39548*+**
39756*+**
39947*+**
39499**+*
39669**+*
39949**+*
39966**+*
93149*+**
93166*+**
93257*+**
93548*+**
93756*+**
93947*+**
93269**+*
93349**+*
93366**+*
93439**+*
93629**+*
93636**+*
93926**+*
93934**+*
93939+*+*
93948+*+*
93957+*+*
96357**+*
96537**+*
96735**+*
96769+*+*
96778+*+*
97849+*+*
97858+*+*
97867+*+*
99689+*+*
956*99*+*
968*79*+*
39*149*+*
39*166*+*
39*257*+*
39*548*+*
39*756*+*
39*947*+*

编辑：

我正在进行一些搜索空间修剪改进，很抱歉我没有立即发布。Erlnag 中有脚本。原来的 999 需要 14 秒，但这个在 190 毫秒左右。

编辑2：

9999 有 1074 个长度为 13 的解。需要 7 分钟，其中一些如下：

329+9677**+**
329+9767**+**
338+9677**+**
338+9767**+**
347+9677**+**
347+9767**+**
356+9677**+**
356+9767**+**
3147789+***+*
31489+77***+*
3174789+***+*
3177489+***+*
3177488*+**+*

C 中有一个版本对状态空间进行了更积极的修剪，并且只返回一个解决方案。它要快得多。

$ time ./polish_numbers 999
Result for 999: 39149*+**, length 9

real    0m0.008s
user    0m0.004s
sys     0m0.000s

$ time ./polish_numbers 99999
Result for 99999: 9158*+1569**+**, length 15

real    0m34.289s
user    0m34.296s
sys     0m0.000s

harold报告说他的 C# bruteforce版本在 20 年代产生了相同的数字，所以我很好奇我是否可以改进我的。我通过重构数据结构尝试了更好的内存利用率。搜索算法主要适用于解决方案的长度并且它存在，所以我将这些信息分成一个结构（best_rec_header）。我也提出了解决方案，因为树枝在另一个（best_rec_args）中分开。这些数据仅在给定数字的新更好解决方案时使用。有代码。

Result for 99999: 9158*+1569**+**, length 15

real    0m31.824s
user    0m31.812s
sys     0m0.012s

它仍然太慢了。所以我尝试了一些其他版本。首先，我添加了一些统计数据来证明我的代码没有计算所有较小的数字。

Result for 99999: 9158*+1569**+**, length 15, (skipped 36777, computed 26350)

然后我尝试更改代码以首先计算+更大数字的解决方案。

Result for 99999: 1956**+9158*+**, length 15, (skipped 0, computed 34577)

real    0m17.055s
user    0m17.052s
sys     0m0.008s

它几乎快了两倍。但是还有另一个想法，有时我可能会放弃为受当前best_len限制限制的某些数字寻找解决方案。所以我试图让小数字（最多一半n）无限制（注意255作为best_len第一个操作数查找的限制）。

Result for 99999: 9158*+1569**+**, length 15, (skipped 36777, computed 50000)

real    0m12.058s
user    0m12.048s
sys     0m0.008s

很好的改进，但是如果我通过迄今为止找到的最佳解决方案来限制这些数字的解决方案怎么办。它需要某种计算全局状态。代码变得更复杂，但结果更快。

Result for 99999: 97484777**+**+*, length 15, (skipped 36997, computed 33911)

real    0m10.401s
user    0m10.400s
sys     0m0.000s

它甚至能够计算出十倍大的数字。

Result for 999999: 37967+2599**+****, length 17, (skipped 440855)

real    12m55.085s
user    12m55.168s
sys     0m0.028s

然后我决定也尝试蛮力方法，这甚至更快。

Result for 99999: 9158*+1569**+**, length 15

real    0m3.543s
user    0m3.540s
sys     0m0.000s

Result for 999999: 37949+2599**+****, length 17

real    5m51.624s
user    5m51.556s
sys     0m0.068s

这表明，那是永恒的事情。当蛮力方法从更好的矢量化、更好的 CPU 缓存利用率和更少的分支中获得优势时，现代 CPU 尤其如此。

无论如何，我认为有一些更好的方法可以更好地理解数论或通过算法进行空间搜索，例如 A* 等等。对于非常大的数字，使用遗传算法可能是个好主意。

编辑3：

哈罗德提出了一个新的想法，以消除尝试大量资金的做法。我已经在这个新版本中实现了它。它快了一个数量级。

$ time ./polish_numbers 99999
Result for 99999: 9158*+1569**+**, length 15

real    0m0.153s
user    0m0.152s
sys     0m0.000s
$ time ./polish_numbers 999999
Result for 999999: 37949+2599**+****, length 17

real    0m3.516s
user    0m3.512s
sys     0m0.004s
$ time ./polish_numbers 9999999
Result for 9999999: 9788995688***+***+*, length 19

real    1m39.903s
user    1m39.904s
sys     0m0.032s

Answer 4

别忘了，你也可以推送 ASCII 值！！通常，这更长，但对于更大的数字，它可以变得更短：

如果您需要数字 123，那会 "{"比99*76*+