1

数日前 、難解なプログラミング言語であるBefungeをいじりました。Befunge は LIFO スタックを使用してデータを保存します。プログラムを書くとき、0 から 9 までの数字は、実際には、対応する値をスタックにプッシュする Befunge 命令です。たとえば、これは 7 をスタックにプッシュします。

34+

9 より大きい数値をプッシュするには、9 以下の数値で計算を行う必要があります。これにより、123 が得られます。

99*76*+

オイラー問題 1を Befunge で解決しているときに、かなり大きな数値 999 をスタックにプッシュする必要がありました。ここで、できるだけ少ない指示でこのタスクを達成するにはどうすればよいか考え始めました。用語を中置記法で書き留め、思いついた共通因数を取り出すことで

9993+*3+*

999 を生成する 2 つの 2 桁の数を単純に乗算することもできます。

39*66*1+*

これについてしばらく考えた後、与えられた整数に対して逆ポーランド記法でこれらの規則に従って最小の式を出力するプログラムを作成することにしました。これは私がこれまでに持っているものです（underscorejsでNodeJSで書かれています）：

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+*可能な限り最小のものであると証明できますか?

いくつかの洞察を与えることができれば幸いです。前もって感謝します。

4

4 に答える 4

2

掛け算と足し算だけを考えると、最適な式を構築するのは非常に簡単です。なぜなら、その問題には最適な部分構造の性質があるからです。つまり、ビルドする最適な方法[num1][num2]opは fromnum1であり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 文字の長さか ( )9+1000を見つけます。9+100095558***+

最初の部分の長さが 3 以下の合計をチェックする次のステップは、完全にスキップできます。1009 - 81 = 929、および 929 (最初の部分が 3 文字以下の場合に合計の 2 番目の部分が取り得る最小値) は 728 よりも大きいため、929 以上の数字は少なくとも 7 文字の長さである必要があります。したがって、合計の最初の部分が 3 文字の場合、2 番目の部分は少なくとも 7 文字である必要があり、最後に + 記号もあるため、合計は少なくとも 11 文字です。これまでの最高は 9 だったので、この手順は省略できます。

最初の部分に 5 文字ある次のステップもスキップできます1009 - 728 = 280。280 以上にするためには、少なくとも 5 文字が必要だからです。5 + 5 + 1 = 11、9より大きいので、チェックしないでください。

約 500 個の合計をチェックする代わりに、この方法で 9 個をチェックするだけで済み、スキップを可能にするためのチェックは非常に高速です。このトリックは、100 万までのすべての数値を生成するのに、私の 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;
}

まだまだ改善の余地ありです。このコードは、すでにチェックした合計を再チェックします。少なくとも同じ合計を 2 回チェックしないようにする簡単な方法がありますが (最後の を覚えておくことでfind)、私のテストでは大きな違いはありませんでした。より良い上限を見つけることができるはずです。

于 2013-11-24T11:28:33.480 に答える
2

もありますが93*94*1+*、これは基本的に27*37です。

私がこの問題に取り組むとしたら、まず数を均等に割ることから始めます。したがって、999 が与えられた場合、9 で割ると 111 になります。次に、111 が 3*37 であることを発見するまで、9、8、7 などで割ろうとします。

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

後置を直接生成する方が簡単なのか、中置を生成して変換する方が簡単なのか、私にはよくわかりません。それぞれに利点と欠点が見られます。

とにかく、それが私が採用するアプローチです。最初は均等に分割してから、貪欲に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 までのすべての数値は、2 つの 1 桁の数値の積として、または形式の式で表すことができます。(9x + y)ここで、xとyは 1 桁の数値です。ただし、これが 90 を超える値の最適な式を保証するかどうかはわかりません。

于 2013-11-22T21:41:30.783 に答える