他の6桁の数字から100番を作る方法

数週間前、ここで説明した問題とはまったく関係のない問題への答えを探して、私は自発的に次の投稿を見つけました： 123456789から100または0の数字を作る方法 。



それを読んだ後、私は6ヶ月前に同じですが、わずかにグローバルな問題をどのように解決したかを思い出しました。 この記事では、解決方法を共有し、アルゴリズムで「遊ぶ」機会を与えたいと思います。 しかし、最初に、少しの背景。

背景

むかしむかし、人々がスマートフォンを持っていなかったとき、公共交通機関で旅行している間、誰もができる限り最善を尽くしました。 このような退屈しない方法の1つは、楽しいゲームでした。これは、バスに乗るだけでなく、「頭をかき立てる」のにも役立ちました。 そのように聞こえます。 バスのチケットには6桁の番号があります。 数値の間に角括弧と数学演算の符号を配置して、演算後に100になる式を取得する必要があります。演算のセットは標準です：加算、減算、乗算、除算。



誰がこのゲームを教えたのか、どの友人に感染したのかは覚えていませんが、これまで定期的にこのような楽しみを愛してきました。 そして今、半年前、私は次の例を見つけました。







組み合わせが困難であることが判明したか、その時点で私は長い間練習していませんでしたが、この例では約15分間輸送されました。この時間の途中で、この数字は解決策がないサブセットに含めることができるという厄介な考えが頭の中に現れました。 私は最終的に例を決定しましたが、数時間は役に立たずに輸送できるという認識からの堆積物が残っていました。 さらに、特定の数であっても、そのような性質を証明することは問題になります（もちろん、数論の教授でない場合）。 したがって、プログラミングの助けを借りてこの問題を解決することにしました。

ソリューションとアルゴリズム

警告 この記事の著者はプロのプログラマーではありません。 ただし、提案されたアルゴリズムまたはその実装を改善するための有用なヒントを感謝して受け入れます。



列挙の助けを借りて問題を解決します。 この場合、ソリューションの3つの異なる特性を整理する必要があります。

1. 元の番号のサブ番号へのさまざまなパーティション。
2. パーティションごとに、操作の異なる配置。
3. 操作の各配置について-操作の異なる順序（括弧の配置）。

最初のサイクル

最初のサイクルでは、次のパーティションを生成します。 これを行うために、順序付けられた一連の数字の形式で任意の6桁の数字を提示し、その間に5つの「コンテナー」があります：1_2_3_4_5_6。 各コンテナには、隣接する番号を接着することを意味する1または隣接する番号が異なる番号に属する0のいずれかを配置できます。 パーティションには合計で2 ^ 5 = 32の異なるオプションがあり、それほど多くはありません。 例で示されているパーティションは、シーケンス10101でエンコードされています。



このようなオプションを要素ごとに並べ替えることができます。初期パーティション（00000）を設定し、31回連続して2進数システムの単位を追加します。

第二サイクル

2番目のサイクルでは、N + 1個の数字とそれらの間にN個のコンテナーがあります。 コンテナの数Nは、パーティションコードのゼロの数によって決まることに気付くかもしれません。 しかし、ここでより重要なのは、セット（+、-、*、/）のさまざまな操作をこれらの新しいコンテナーに分解する必要があるという認識です。 最悪の場合、N = 5であるため、最悪の推定値は4 ^ 5 = 1024の操作配置の変形です。



前の操作と同様の方法で操作の配置を整理できます。 各操作を独自のキー（0、1、2、3）でエンコードし、操作の初期セット00000を設定し、4 ^ N-1回、4進数システムでユニットを追加します。

第三サイクル

そして最後に、3番目のサイクルでは、ブラケットを配置する必要があります。 もちろん、私たちはこれを完全に「額」にせず、何とかしてブラケットを配置し、開閉のバランスを数えます。 同じNコンテナの場合、操作の優先順位を付けるだけでよいことに注意してください。 N個の操作があるので、セット（0、...、N）からすべての順序付けられた数字の配列を整理する必要があります。 可能なすべての実行順序の数はN！、最悪の場合は5！に等しくなります。 = 120。



操作の優先順位付けの反復は、シーケンス内の数字のさまざまな順列（0,1,2,3,4）を並べ替えることによって実行できます。 私のプログラムでは、シーケンス内の数字を順番に入れ替える、明白ではないアルゴリズムを実装しました。 （もし私が今書いているなら、おそらくもっと理解しやすいものを実装するでしょう）。

組み合わせチェック

さて、問題を解決するために残されていることはほとんどありません-3つのコードと初期番号のセットを使用して式の結果を計算し、結果が100の場合、エンコードされた式を印刷する手順を作成します。 最悪の場合、N + 1桁の数値のすべてのオプションを列挙するには、2 ^ N⋅4 ^ N⋅N！ 式。 6桁の数字の場合、これは390万式に相当します。 式では4 ^ N⋅N！であるため、推定値は大幅に過大評価されます。 実際には、Nではなく、最初のパーティションのゼロの数になります。

おわりに

結論として、私は2つのコメントをしたいと思います。



まず、私のプログラムは最初にintの標準操作を使用しました。 この問題を解決するとき、人々は有理数の分野で働いているため、プログラムによって発行された多くの決定を実際に使用することはできません。 しばらくして、合理的な数字で小さなモジュールを作成し、タスクにねじ込みました。



第二に、私のプログラムでは、5番目の操作の胚があります-べき乗。 この操作が実装されない理由は次のとおりです。 まず、累乗するためのリミッターを追加する必要があります（たとえば、2 ^ 2 ^ 2 ^ 2 ^ 2 ^ 2の数はメモリに収まらないため）。 次に、この場合、計算は有理数のフィールドを残します（たとえば、2 ^（1/2））。

参照資料

GitHubの C ++で提案されたアルゴリズムのソフトウェア実装を広めました。

さらに、コンパイルに煩わされたくない人は、同じリリースからWindowsの実行可能ファイルをダウンロードできます。