4

ブロックのコレクションがあるとしましょう。12は赤、8は青、5は黄色、1は緑です。これらのオブジェクトを、赤いブロックが隣り合っていない、青いブロックが隣り合っていない単一の配列に出力するアルゴリズムを作成する必要があります。出力は次のようになります。

赤、青、赤、青、赤、青、黄色、青、緑、赤、黄色など。

これまでのプログラミング経験では、これを複数回行うためのアルゴリズムを作成しなければならない場所に来ました。私が最後にやったのは約2年前のスタートアップで働いていた。このようなアルゴリズムをPythonで実装しましたが、ソースコードが利用できません。作成するのに少なくとも100行かかったことを覚えています。

このアルゴリズムには名前がありますか？再度実装する必要はありません。

4

3 に答える 3

6

この問題の名前はわかりません。以下は私がそれを解決するために思いついたアルゴリズムです。

残りの各ブロックの数を追跡する必要があります。

repeat:
output 1 block of largest color set.
output 1 block from the second largest color set.

出力：

rbrbrbrbrgrbrgrbrgrbr grbgy

注：このアルゴリズムを実行する前に、最大のカラーセットのサイズが1+他のカラーのサイズの合計より大きいかどうかを確認する必要があります。もしそうなら、解決策はありません。

注：2番目に大きいセットからを選択する必要はありません。ループの2番目のピックは、最大でないカラーセットのいずれかから取得できます。

于 2012-06-14T20:41:28.167 に答える
1

頭のてっぺんから-挿入するすべてのブロックを含むキューを作成します（つまり、上記の例を使用すると、キューには12個の赤、8個の青、5個の黄色、1個の緑が含まれます）。キューから配列のすべての偶数インデックスに要素を挿入し、次にすべての奇数インデックスに挿入します（つまり、インデックス0、2、4、6、8、10、12、14、16、18、20、22に赤いブロックを挿入します。次に、24、1、3、5、7、9、11、13に青を挿入し、15、17、19、21に黄色を挿入し、23に緑を挿入します）

ブロックのいくつかの組み合わせでは、このタスクは不可能であることに注意してください。アルゴリズムを実行する前に、最大数のブロックのセットに、すべてのブロックの合計を2で割った数よりも多くのブロックがないことを確認する必要があります。

于 2012-06-14T20:06:51.887 に答える
0

  1. まず、そのような配列が存在するかどうかを確認する必要があります。

    たとえば、赤が4つ、青が1つしかない場合、それは存在しません。

    したがって、最大のコレクションの数が他のすべてのコレクションの合計から1を引いた数よりも少ない場合、有効な解決策はありません。

  2. 次に、最大のコレクションのすべてのアイテム、たとえば赤をリストとして配置します。

    リストの各項目の間に、他の要素を挿入できるスポットです

    e.g. _ red _ red _ red _ red _ red _ red ...

  3. これで、コレクションごとに他のアイテムをそれらのスポットに挿入できます。コレクションの順序は重要ではありません。

    e.g. blue red blue red blue red blue red yellow red yellow red _ red _ red ..

    あなたはそれらのスポットを常に左から右へ（または常に右から左へ）消費する必要があります。

    スポットが足りなくなったら、左（または右）からやり直して、新しいスポットにアイテムを挿入します。

    e.g. green blue _ red _ blue _ red _ blue _ red _ blue _ red _ yellow _ red ...
于 2012-06-14T21:12:55.303 に答える