河內塔的所有狀態的二進制表示

-1

在略有修改的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個職位可以表示。但我無法理解數學關聯。

能否請你解釋一下上面的公式可以表示所有可能的磁盤位置，如果我們進一步轉變釘的數量或N將如何改變，以讓說，5

來源

2017-08-14 G.D

您能詳細說明「公式的作用」是什麼意思嗎？目標是找到一種使用數字編碼磁盤位置的方法，反之亦然，或者通過二進制計數來解決問題？ – templatetypedef

@templatetypedef -goal是爲了理解磁盤位置的編碼以及上述方程如何工作，而不是解決問題。我想了解當N或釘的數量發生變化時，我需要如何修改給出的等式。 –

既然你只有4個釘，位置任何磁盤都可以用2位編碼（00, 01, 10, 11 => 0, 1, 2, 3）。因此乘以2給出每個磁盤2個獨立存儲空間的整數state，其中第一個磁盤從位0開始，第二位在位2，等等...... i第012個磁盤在(i - 1) * 2。左移<<將每個磁盤的數據移動到其正確的位位置。

但是這個代碼可以是「不安全」 - 如果有在遊戲邏輯別處錯誤造成的tower值比3更大，當轉移它將溢出的空間其指定的2位。爲了防止這種情況，做一個位與以鉗數據爲[0,3]：

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

請注意，您還可以使用按位，而不是添加或 - state |= ...。

從例如N = 3提供它看起來像所有板從栓4（即tower[3]）開始。如果您更改爲N = 5，它將再次給您4^N - 1 = 1023，因爲N * 2以下的所有位都將設置爲1.

來源

2017-08-14 22:28:10 meowgoesthedog

非常感謝@meogoesthedog。一個後續問題 - 我們在整數狀態下分配了2位獨立內存，然後在移動到正確位置後我們應該做（1 << 2 * disc）對嗎？爲什麼我們要做（towerIndex << 2 * disc）。也可以請舉一個例子用例，我必須將乘法因子2更改爲其他數字。 –

@ G.D，因爲'tower [disk]'的每個元素都是存儲在這些2位空間中的數據。不知道你是怎麼想出'1 <<'的。爲了論證的緣故，我們用某個整數「m」代替2，「m」是編碼最大*塔索引所需的最小*位數，即塔的數量。如果你需要5到8個塔，你需要每個索引3位（'m = 3'）。一般來說，對於'T'數量的塔，你需要'm = ceil（log2（T））'每個索引的位數。 – meowgoesthedog

假設我們有N = 3和pegs = 3。我們將再次需要2位來表示3個掛鉤，所以方程保持不變。當所有光盤在最後一個塔上時[2]，其狀態= 42，而可能的狀態總數爲3^3 = 27，所以42是無效狀態。什麼需要改變？ –

河內塔的所有狀態的二進制表示

回答

相關問題