Recombine Number to Equal Math Formula

Question

私は数学/アルゴリズムの問​​題を考えていましたが、解決方法を教えていただきありがとうございます。

数字がある場合（たとえば479）、数字またはそれらの組み合わせを元の数字と一致する数式に再結合したいと思います。 すべて桁はそう、（従って、479は、4、7、9、47、79を可能にする）が、各桁だけ一度を使用することができるそれらの元の順序に使用されるべきであるが、番号に組み合わせることができます4x47x9のようなものを今のように2回使用したようなことはできません。

ここで私がどのように考えているかを実証する例を示します。この例は数学的には間違っていますが、私は実際に動作する良い例を思いつくことができませんでしたが、入力と期待される出力を示しています。

例入力：29485235

出力例：私が言ったように2x9+48/523^5

、私の例ではは足ししない（2x9 + 523分の48^5は29485235にはなりません）が、私は疑問に思いました実際に元の順序でソース番号の数字からなるそのような式を見つけることを可能にするアルゴリズムがある場合、計算で元の数が得られます。

使用した数学のタイプでは、括弧（）とAdd/Sub/Mul/Div/Pow/Sqrtがあります。

これを行う方法に関するアイデアはありますか？私の考えは、無差別に数を切り刻み、一致する結果が得られることを望む計算をするだけで、それを強制的に強制することにありました。しかし、もっと良い方法がありますか？

編集：それは非オリジナルの順序で任意の簡単だ、またはあなたは、上記の「条件」の一部を無視して、これを解決するためのアイデアを持っている場合、それはまだ、そのような解決について移動する方法を理解するために大いに役立つだろう問題。

Answer 1

このような数字は、私が思い起こされるように、現存すると非常にまれです。いくつかの数字は、の異なるの順番（例えば、25（5²）など）でコンポーネントの数字で表すことができます。

また、数値が数字で大きくなるにつれて順列の数が非常に急激に増加することを考えると、無差別に解を解くことはできません。

EDIT：部分溶液。

いくつかのケースを解決する部分的な解決策は、その数をその素因数に分解することです。その素因数がすべて同じで、指数と因子が両方とも数値の桁に存在する場合（たとえば25の場合）、特定の解決策があります。

ほとんどの数字はです。は、このような種類のパターンに該当します。これは、乗算またはpow（）を主要な原動力として実行します。加えてもそれだけでは十分ではありません。

Answer 2

私はCarol Voordermanを複製するニューラルネットワークを構築していません。このような問題のパターンを見ても人間はかなり賢明ですが、そのような洞察をエンコードするのは本当に難しいです。

約6桁かそこらまでの番号については

Answer 3

、私はそれ以下のスキームに従ってブルートフォースを言うと思います：

1）（リストにあなたの初期値を分割し、配列、何でも、言語に応じて）数字の最初は、これらは数字です。

2）数字の各ペアについて、演算子の1つを使用してそれらを結合します。結果がターゲット番号であれば、成功を返します（あなたの途中で実行されたすべての操作を出力します）。それ以外の場合は、整数の場合は、ちょうど計算した数字と使用していない数字からなる新しいリストを繰り返し表示します。または、整数でない中間結果を許可すると、検索スペースがいくらか大きくなります。二項演算は、次のとおりのみオリジナル数字のいずれかである数に用いてもよいし、製造されてきた

• 追加
• 減算
• 乗算
• 分割
• パワー
• CONCATENATE（連結によって）。

3）平方根を許すことは、単数演算子であるため、探索空間を無限に広げます。だから、適用できる回数を制限する方法が必要ですし、それがどうなるのかよく分かりません（答えが1に近づくにつれて精度が低下するかもしれません）。整数中間値のみを許可するもう1つの理由です。

4）指数関数化によって、オーバーフローが急速に発生します。 2 ^（9 ^（4^8））は大きすぎて直接すべての桁を格納することはできませんが（基底2ではかなり明白ですが）;-)]。したがって、大きな中間値を持つ解を見つけられない可能性があることに同意する必要があります。そうでなければ、因子の点で算術演算を行うためのコードを書く必要があります。これらは明らかに加算とはうまく相互作用しませんので、いくつかの推定を行う必要があります。例えば、2 ^（9 ^（4^8））がどこにも（2^35）近くにないことが分かる要因の数を見るだけで、（2 ^（9^4^8））+ 5）/（2^35）である。たとえそれが整数であったとしても、それはおそらく29485235ではありません（これは確かにそうではありません - この特定の例を除外する別の方法です）。私はこれらの数値を扱うのは他の問題よりも難しいと思いますので、おそらくあなたは自分の言語に応じて64ビットの整数に収まる結果に始まる一桁の数字に制限するべきです。

5）すべての数字を連結するだけで、すべての入力に対して簡単な解を除外するのを忘れました。しかし、処理するのはかなり簡単ですが、現在のサブ問題へのルート上で非連結演算を実行したかどうかを示す再帰を介してパラメータを維持するだけです。あなたがしていない場合は、偽の一致を無視してください。

6桁の見積もりは、解決策がない場合でも数分の1秒で実行されるCountdownソルバを書くのはかなり簡単だという事実に基づいています。この問題は、数字を順番に使用しなければならないという点で異なりますが、より多くの操作があります（カウントダウンではべき乗、平方根、連結、または整数以外の中間結果が許可されません）。全体的に私は、平方根とオーバーフローの問題を解決すれば、この問題は匹敵すると思います。あなたが1秒未満で1つのケースを解くことができれば、合理的な時間内に何百万人もの候補者にあなたの方法を強制することができます。

10桁では、大量の再帰が必要な100億件のケースを考慮する必要があるため、ブルートフォースは不可能に見えます。だから私はあなたが2人の間のどこかに力任せの限界を打つだろうと思う。

また、私の単純なアルゴリズムの冗長性はまだありません。（4,7,9,1）→（47,9,1）→（47、 91）、その後、（4,7,9,1）→（4,7,91）→（47,91）を行う。したがって、重複が発生する場所を見つけ出して回避しない限り、2回試みます（47,91）。リストに2つの数字しかないときは、明らかにそれほど効果がありませんが、リストに7つの数字がある場合は、おそらく、それらの4つを6つの異なる方法で一緒に追加し、結果として生じる4つの数字の問題を6回解決します。ここでの巧妙さはカウントダウンの試合には必要ないが、この問題で私が知っていることは、ブルートフォース8桁とブルートフォース9桁の違いがかなり大きいことだ。