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

Question

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

34+

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

99*76*+

同时解决Euler Problem 1对于 Befunge，我不得不将相当大的数字 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

当只考虑乘法和加法时，很容易构造最优公式，因为该问题具有最优子结构性质。即构建[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，所以不检查。

用这种方法我们只需要检查 9 个，而不是检查大约 500 个和，而且使跳过成为可能的检查非常快。这个技巧非常好，在我的 PC 上只需要 3 秒就可以生成一百万以内的所有数字(以前，生成 100000 需要 3 秒)。

代码如下:

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 )，但这在我的测试中没有显着差异。应该可以找到一个更好的上限。