約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桁の違いが生じる可能性があります。これは非常に重要です。