河内塔中所有状态的二进制表示
binary representation of all states in tower of hanoi
在略微修改的 TOH 中，我们有 4 个钉子。所以反过来我们总共有 4^N 个磁盘位置。
现在，在我正在经历的解决方案之一中，使用以下代码表示给定状态 -
for(int disc = 0; disc < N; disc++){
state += tower[disc]<<(disc*2);
}
tower[disc] --> disc当前所在的塔，可以是(0,1,2,3)
如果我在上面的代码中使用 N=3，它会给我 63，也就是 4^N -1。所以公式有效，即 0-63 所有 64 个位置都可以表示。但我无法理解数学相关性。
您能否解释一下上面的公式如何表示所有可能的磁盘位置，以及如果我们进一步将挂钩数量或 N 更改为 5，它将如何变化。
因为你只有 4 个钉子，所以任何磁盘的位置都可以用 2 位编码 (00, 01, 10, 11 => 0, 1, 2, 3)。因此，乘以 2 为每个磁盘提供 2 位独立内存 space，整数 state，第一个磁盘从第 0 位开始，第二个从第 2 位开始，依此类推... ith 磁盘在 (i - 1) * 2。左移 << 将每个磁盘的数据移动到其正确的位位置。
然而，此代码可以是 "unsafe" - 如果在其他地方的游戏逻辑中存在错误导致 tower 的值大于 3，则在移动它时将 溢出 它指定的 space 的 2 位。为防止这种情况，请按位与 clamp 数据到 [0, 3]:
state += (tower[disc] & 3) << (i * 2);
请注意，您也可以使用按位或而不是加法 - state |= ...。
从示例 N = 3 来看，假设所有板块看起来都从 peg 4 开始（即 tower[3]）。如果您更改为 N = 5，它将再次为您提供 4^N - 1 = 1023，因为 N * 2 以下的所有位都将设置为 1。
在略微修改的 TOH 中，我们有 4 个钉子。所以反过来我们总共有 4^N 个磁盘位置。 现在，在我正在经历的解决方案之一中，使用以下代码表示给定状态 -
for(int disc = 0; disc < N; disc++){
state += tower[disc]<<(disc*2);
}
tower[disc] --> disc当前所在的塔，可以是(0,1,2,3)
如果我在上面的代码中使用 N=3，它会给我 63，也就是 4^N -1。所以公式有效，即 0-63 所有 64 个位置都可以表示。但我无法理解数学相关性。
您能否解释一下上面的公式如何表示所有可能的磁盘位置，以及如果我们进一步将挂钩数量或 N 更改为 5，它将如何变化。
因为你只有 4 个钉子，所以任何磁盘的位置都可以用 2 位编码 (00, 01, 10, 11 => 0, 1, 2, 3)。因此，乘以 2 为每个磁盘提供 2 位独立内存 space，整数 state，第一个磁盘从第 0 位开始，第二个从第 2 位开始，依此类推... ith 磁盘在 (i - 1) * 2。左移 << 将每个磁盘的数据移动到其正确的位位置。
然而，此代码可以是 "unsafe" - 如果在其他地方的游戏逻辑中存在错误导致 tower 的值大于 3，则在移动它时将 溢出 它指定的 space 的 2 位。为防止这种情况，请按位与 clamp 数据到 [0, 3]:
state += (tower[disc] & 3) << (i * 2);
请注意，您也可以使用按位或而不是加法 - state |= ...。
从示例 N = 3 来看，假设所有板块看起来都从 peg 4 开始（即 tower[3]）。如果您更改为 N = 5，它将再次为您提供 4^N - 1 = 1023，因为 N * 2 以下的所有位都将设置为 1。