4

数学/アルゴリズムの問​​題について考えていたので、解決方法についてご意見をいただければ幸いです。

数字 (たとえば 479) がある場合、その数字またはそれらの組み合わせを元の数字と一致する数式に再結合したいと考えています。すべての数字は元の順序で使用する必要がありますが、数字に組み合わせることができます (したがって、479 は 4、7、9、47、79 を許可します)。ただし、各数字は一度しか使用できないため、4x47x9 のようなものは使用できません。現在、数字の 4 は 2 回使用されています。

今、私がそれをどのように考えているかを示すための例です。実際に機能する良い例を思い付くことができなかったため、この例は数学的に正しくありませんが、入力と期待される出力を示しています。

入力例:29485235

出力例:2x9+48/523^5

私が言ったように、私の例は合計されませ(2x9+48/523^5 は 29485235 にはなりません)。計算すると元の数が得られる元の順序。

使用される数学の種類については、括弧 () と Add/Sub/Mul/Div/Pow/Sqrt と言えます。

これを行う方法についてのアイデアはありますか?私の考えは、数字をランダムに切り刻み、一致する結果を期待して計算を行うことで、単純にブルートフォースすることでした。でももっと良い方法があるはずですよね?

編集:元の順序ではない方が簡単な場合、または上記の「条件」のいくつかを無視してこれを解決するアイデアがある場合でも、そのような問題を解決する方法を理解することは非常に役立ちます.

4

3 に答える 3

4

約6桁程度までの数字の場合、次のスキームに従ってブルートフォース攻撃を行います。

1)初期値を数値のリスト(言語に応じた配列など)に分割します。最初は、これらは数字です。

2)数値のペアごとに、演算子の1つを使用してそれらを結合します。結果が目標数である場合は、成功を返します(そして、途中で実行されたすべての操作を印刷します)。それ以外の場合、整数の場合は、計算したばかりの数値と使用しなかった数値で構成される、新しい小さいリストを繰り返します。または、整数以外の中間結果を許可することもできます。これにより、検索スペースがいくらか大きくなります。二項演算は次のとおりです。

  • 追加
  • 減算
  • かける
  • 分ける
  • パワー
  • 連結(元の数字であるか、連結によって生成された数値にのみ使用できます)。

3)平方根を許可すると、単項演算子であるため、検索スペースが無限大に膨れ上がります。したがって、適用できる回数を制限する方法が必要になりますが、それがどうなるかはわかりません(答えが1に近づくと、精度が低下する可能性がありますか?)。これは、整数の中間値のみを許可するもう1つの理由です。

4)べき乗は急速にオーバーフローを引き起こします。2 ^(9 ^(4 ^ 8))は大きすぎて、すべての数字を直接格納できません[ただし、基数2では、それらが何であるかはかなり明白です;-)]。したがって、中間値が大きい解を見逃す可能性があることを受け入れる必要があります。そうでない場合は、係数の観点から算術演算を実行するための一連のコードを作成する必要があります。これらは明らかに加算とうまく相互作用しないので、いくつかの見積もりをしなければならないかもしれません。たとえば、因子の数の大きさを見るだけで、2 ^(9 ^(4 ^ 8))は(2 ^ 35)にほど遠いので、(2 ^(9 ^( 4 ^ 8))+ 5)/(2 ^ 35)。整数であっても、29485235になることはありません(確かにそうではありません-この特定の例を除外する別の方法です)。

5)すべての数字を連結するだけの、入力の簡単な解決策を除外するのを忘れました。ただし、これは非常に簡単に処理できますが、現在のサブ問題へのルートで非連結操作を実行したかどうかを示すパラメーターを再帰で維持するだけです。まだ行っていない場合は、誤った一致を無視してください。

私の6桁の見積もりは、解決策がない場合でも、ほんの一瞬で実行されるカウントダウンソルバーを作成するのがかなり簡単であるという事実に基づいています。この問題は、数字を順番に使用する必要があるという点で異なりますが、より多くの演算があります(カウントダウンでは、べき乗、平方根、連結、または非整数の中間結果は許可されません)。全体として、平方根とオーバーフローの問題を解決すれば、この問題は同等だと思います。1つのケースをほんの一瞬で解決できれば、妥当な時間内に100万人の候補者を総当たり攻撃することができます(PCをオンのままにしてもかまわないと仮定します)。

10桁では、100億のケースを考慮する必要があり、それぞれにかなりの再帰が必要になるため、ブルートフォースは不可能に見えます。ですから、2つの間のどこかでブルートフォースの限界に達すると思います。

また、上部にある私の単純なアルゴリズムにはまだ多くの冗長性があります-それはあなたが(4,7,9,1)->(47,9,1)->(47,91)、そしてその後、(4,7,9,1)->(4,7,91)->(47,91)も実行します。したがって、これらの重複が発生する場所を特定して回避しない限り、(47,91)を2回試行します。明らかに、リストに2つの数字しかない場合はそれほど問題にはなりませんが、リストに7つの数字がある場合は、たとえば6つの異なる方法で4つを足し合わせて、結果として生じる4つの数字の問題を解決したくないでしょう。回数。ここでの巧妙さはカウントダウンゲームには必要ありませんが、この問題で私が知っている限り、ブルートフォース8桁とブルートフォース9桁の違いが生じる可能性があります。これは非常に重要です。

于 2009-08-22T09:57:07.233 に答える
1

そのような数は、私が思い出す限り、現存するとしても非常にまれです。一部の数値は、たとえば 25 (5²) のように、構成桁を異なる順序で表すことができます。

また、数が桁数で増加するにつれて順列の数が非常に急速に増加することを考えると、ブルート フォース ソリューションを試みることは、せいぜい絶望的です。

編集:部分的な解決策。

一部のケースを解決する部分的な解決策は、数値を素因数分解することです。素因数がすべて同じで、指数と因数の両方が数値の桁に存在する場合 (25 の場合など)、特定の解があります。

これらの種類のパターンに分類されるほとんどの数値は乗算または pow() のいずれかを主要な原動力として使用します。追加しても十分に増加しません。

于 2009-08-22T09:22:26.290 に答える
-1

Carol Voorderman を複製するニューラル ネットワークを構築する以外には、ブルート フォースが機能する以外には何も見えません。人間は、このような問題のパターンを認識するのは非常に賢いですが、そのような洞察をコード化するのは非常に困難です。

于 2009-08-22T09:23:14.387 に答える