3

このタスクは実際には宿題として与えられましたが、宿題の割り当ての要件は、配列Aでいくつかの手順を実行した後、配列Aが配列Bと一致する場合にtrueまたはfalseを返すことができる再帰メソッドを作成することでした。この質問に再帰的に答えました。よりインテリジェントなアプローチがあるかどうか、このタイプの割り当てに対処するために使用できる特定のパターンまたは方程式があるかどうかを調べることに興味があります。宿題のタグはまだ関連していますが、念のために追加しました。

詳細は次のとおりです。同じ長さの2つのブール配列が与えられます。指定された配列「init」がターゲット配列「target」と一致する場合はtrueを返します。キャッチは次のとおりです。1つのインデックスの値をtrueからfalseに、またはその逆に「反転」するたびに、インデックスの値は左右になります。現在のインデックスの値も反転します（もちろん、そのようなインデックスが配列の範囲内にある場合）。次に例を示します。

boolean[] init =   {true, false, true, false, true, false};
boolean[] target = {false, true, false, true, false, true};

この場合、init配列の最初のスポット[0]を反転できるため、答えは真です。結果は次のようになります。

boolean[] init =   {false, true, false, false, true, false);
boolean[] target = {false, true, false, true, false, true};

次に、init配列の4番目のスポット[3]を反転し、init配列とターゲット配列が一致するようにします。

boolean[] init =   {false, true, false, true, false, true};
boolean[] target = {false, true, false, true, false, true};

再帰的には、「反転状態」または「反転状態」なしの2つのオプションをテストし、各テストの配列のインデックスを進めていました。これにより、すべてのオプションが再帰的にチェックされ、一致するものが見つかった場合は最終的にtrueが返されます。

ここで私の質問に戻りますが、多くのオプションをチェックすることなく、この種の問題に対するより良いアプローチはありますか？再帰的である必要はありません...実際のところ、そうでない場合は最善かもしれません:)ですので、お気軽にアイデアや提案を共有してください。

ありがとう！

4

3 に答える 3

1

さて、私は実装を書くつもりはありませんが、ここに基本的なロジックがあります。たとえば、どの値を変更する必要があるかを把握します。{true、false、false、true} with {true、true、false、false} = {true！= true、false！= true、false！= false、true！= false} = {false、true、false、true }

ここで、0から（サイズ2）までのすべての値がfalseに等しくなるまで、この新しい配列を反転しようとします。私たちはこれを直線的に行うことができることを知っています。a [0] == trueの場合、a [1]で反転し、a [1] == trueの場合、a[2]で反転します。サイズ-2まで、各値をステップスルーするだけです。

最終的には、真または偽の最後の値を除いて、配列全体が偽になります。ここで問題となるのは、最後の値だけがtrueの場合、すべての値がfalseになるように配列を変換することは可能ですか？

于 2012-06-09T09:41:21.373 に答える
1

実装を高速化する方法（指定されたルールで配列を変換できるかどうかの質問にyes / noと答える）：

  • 真と偽の値の配列ではなく、すべてをビットとして表します。次に、ビット反転パターンは次のとおりです。1100... 00、1110 ... 00、0111 ... 00、...、0000...11。BFS（またはDFS）を実行することにより、ビットフリッピングパターンが配列を変換できるすべての可能な方法を検索します。

  • ビットセット（言語がそのような低レベルの実装を許可するか、そのようなライブラリで提供される場合）またはchar/booleanの配列で変換が可能かどうかを格納します。これにより、変換で使用されるスペースが削減されます。配列/ビットセットのサイズは2^nです。

  • 可能なすべての変換を取得したら、入力とターゲットをXORすることにより、O（1）の要素の数を固定して質問に答え、そのような変換が存在するかどうかを確認できます。さて、要素の数が変化する場合、多くの利点はありません。

時間を1〜3秒未満に保ちながら、最大20〜23ビットまで拡張できるはずです（C ++コードを想定）。Javaの場合、おそらく少し遅くなりますが、30秒未満である必要があります。

ただし、時間計算量は現在の方法よりも優れています。

変換パターン0000...01を検索して（可能な変換の空間全体を検索するのではなく、早期に終了する）、DarcyRaynerが提案した方法を使用することもできます。最悪の場合の複雑さは、現在の方法よりも優れています。

この問題の数学的解決策があるかどうかはわかりません。現在、これはすべてブルートフォースです。

編集

数学的には、Darcy Raynerが提案した方法（最後の2ビットで分析することにより）を使用して、差を最大で1に貪欲に減らすことができることを証明することができます。

また、パターン全体をいつでも否定できることも証明できます。つまり、長さ3kの場合、些細な、長さ3k + 1の場合、両端を反転し、中央の3つのすべてのグループを長さ3k + 2の場合、反転します。一方の端に、中央に3つのすべてのグループがあります。

したがって、最後のビットが1の場合、パターン全体を反転できます。元の長さが3k+1の場合、3kの差（真）になります。これは簡単に反転できます。元の長さが3kの場合、最終的に3k-1の差が生じます。これは、一方の端で反転し、3つのグループごとに反転できます。これら2つの場合（長さ3k + 1および長さ3k）、変換は常に可能です。

私は現在、3k+2の場合の反証はありません。

于 2012-06-09T10:02:52.590 に答える
1

解説

nビットの場合、さまざまな変更に対してn回の操作が可能です。

  • 操作の順序は関係ありません！（可換、連想）
  • 操作を2回実行すると、同じ状態が復元されます。（反射）

したがって、すべてのソリューションはn個の操作のサブセットであり、任意の順序で実行されます。

  • アルゴリズムには関係ありません： k> 4の連続する変更されていないビットがある場合、[i+2]から[k-1-2]に中間ビットがある操作を除外できます。
  • 最大3つの操作が特定のビットに影響を与えます。したがって、すべての異なるビットについて、選択する操作を収集できます。
  • これらの3つの操作のうち1つのビットに対して1つまたは3つの操作を選択する必要があります（2つの操作で復元されます）。
于 2012-06-09T11:03:44.417 に答える