4

（これはCSクラスの宿題のように見えますが、CSクラスの宿題ではありません）

0 から 22 までの範囲を表すためにビットフィールドを使用しています。たとえば、入力としていくつかの異なる範囲があります (順序は関係ありません)。読みやすくするために.for0とXforを使用しました。1

.....XXXXX..............
..XXXX..................
.....XXXXXXXXXXXXXXX....
........XXXXXXX.........
XXXXXXXXXXXXXXXXXXXXXXXX

通常、ビットフィールド範囲の数は 10 未満ですが、潜在的に 100 になる可能性があります。その入力から、次のように、相互に排他的な連続した範囲を計算したいと思います。

XX......................
..XXX...................
.....X..................
......XX................
........XX..............
..........XXXXX.........
...............XXXXX....
....................XXXX

(繰り返しますが、出力順序は重要ではありません。相互に排他的で連続している必要があります。つまり、穴があっては.....XXX.......XXXXX....なりません。2 つの個別の範囲に分割する必要があります)。

いくつかのアルゴリズムを試しましたが、いずれもかなり複雑で洗練されていません。私が非常に役立つの.....XXX.......XXXXX....は、穴があることを検出する方法と、穴内のビットの 1 つのインデックスを決定する方法です。

編集:ビットフィールドの範囲は、マップ上のズームレベルを表します。これらは、Mapnik (特に OpenStreetMap で使用されるタイル レンダリング システム) の XML スタイルシートを出力するために使用することを目的としています。

4

2 に答える 2

0

コメントで言及している解決策は次のようなものだと思います。

左または右から開始し（つまり、インデックス= 0）、設定されているビットをスキャンします（最大100回の操作）。xを設定した名前。また、変数block=0を設定します。

index = 1で、yを設定するために繰り返して保存します。x XOR y = 0の場合、両方とも同一のセットであるため、index=2に進みます。x XOR y = z！= 0の場合、範囲[ブロック、インデックス）は連続しています。ここで、x = y、block = indexに設定し、続行します。

それぞれ長さが22のビット配列が100個ある場合、これには2200回程度の操作が必要です。

これは、操作をこれ以上減らすことができないため、最適なソリューションです。各段階で、別のセットがセットと一致しない場合は範囲​​が壊れます。したがって、範囲が壊れているかどうかを確認するには、100ビットすべてをチェックする必要があります。

于 2011-02-04T06:03:09.180 に答える
0

少なくとも、あなたのサブ問題を撃ちます。

私が非常に役立つの .....XXX.......XXXXX....は、穴があることを検出する方法と、穴のビットの1つのインデックスを決定する方法です。

ビットマスク内の最下位および最上位のセット（ "1"）ビットを見つけることは、かなり解決された問題です。たとえば、ffs(3)glibcを参照するか、 http： //en.wikipedia.org/wiki/Bit_array#Find_first_oneを参照してください。

ビットマップの最初と最後のインデックスを指定して、それらiを、、と呼びます。を使用して設定されjたすべてのビットを含むビットマップを計算できます（オフバイワンエラーの謝罪）。ijM = ((1 << i) - 1) & (~((1 << j) - 1))

次に、元のビットマップに穴があるかどうかを、と比較してテストできます M。一致しない場合は、入力xorを使用Mして穴を見つけ、繰り返すことができます。

于 2011-02-02T05:17:54.483 に答える