ハノイの塔のすべての州のバイナリ表現

Question

若干修正されたTOHでは、4つのペグがあります。したがって順番に合計4^Nのディスク位置があります。 今はスルー行っていた解決策の一つに、所定の状態は、コードの下に使用して表されている -

for(int disc = 0; disc < N; disc++){ 
     state += tower[disc]<<(disc*2); 
    } 

タワー[ディスク] - >することができ、ディスクが現在位置している塔、（0,1 、2,3）

上記のコードでN = 3を使用すると、63が得られます。これは4^N -1です。したがって、数式は機能します。つまり、0〜63のすべての64の位置を表すことができます。私は数学的な相関関係を理解することができません。

あなたはすべての可能なディスクの位置を表すことができ、我々はさらにあなたが唯一の4つのペグの位置を持っているので、5

Answer 1

を言うことができますするペグまたはNの数を変更した場合、それがどのように変化するかをどのように式の上に説明していただけますどのディスクもちょうど2ビット（00, 01, 10, 11 => 0, 1, 2, 3）で符号化できます。したがって、2での乗算は、各ディスクに整数state内の2つの独立したメモリ空間を与え、最初のディスクはビット0から始まり、2番目のビットはビット2となります。iディスクは(i - 1) * 2です。左シフト<<は、各ディスクのデータを正しいビット位置に移動します。 towerの値が空白のことでしょうオーバーフローその指定された2ビットシフト3、より大きいことが原因とどこか別のゲームロジックに誤りがあった場合 -

しかし、このコードは、「安全でない」ことができます。 - state |= ...あなたはまた、ビット単位のORの代わりの追加を使用することができます

state += (tower[disc] & 3) << (i * 2);

注：これを防ぐために、ビット単位のAND クランプデータに[0,3]に操作を行います。

実施例N = 3から、すべてのプレートがペグ4から始まっているように見える（すなわち、tower[3]）。 N = 5に変更すると、N * 2より下のビットがすべて1に設定されるので、もう一度4^N - 1 = 1023が返されます。