汉诺塔问题是递归的经典案例了。今天看到matrix67写的位运算简介及实用技巧, 所以尝试用位运算来实现汉诺塔的非递归算法。
核心思路是 Gray码改变的是第几个数,Hanoi塔就该移动哪个盘子。 而我们知道二进制数和格雷码有对应关系,第 $n$ 位格雷码等于 n ^ (n >> 1)
,则第 $n$ 位格雷码到第 $n+1$ 位格雷码变化的位数可以通过二者相异或求得:(n ^ (n >> 1)) ^ ((n + 1) ^ ((n + 1) >> 1))
,而这等价于 n ^ (n + 1)
。
完整的代码如下
#include <stdio.h>
#define FLIP(x) ((x) + 'A' - 1)
#define DISP(x, y) printf("%c -> %c\n", FLIP(x), FLIP(y))
int qlog2(unsigned int x);
int main() {
int n;
scanf("%d", &n);
int pos[n], circle[3];
for (int i = 0; i < n; i++) pos[i] = 1;
circle[2] = 1;
if (n % 2 == 0) {
circle[0] = 2;
circle[1] = 3;
} else {
circle[0] = 3;
circle[1] = 2;
}
int i = 0, even = 1, j;
unsigned int m = 0;
while ((j = qlog2(m ^ (m + 1))) < n) {
m++;
if (even) {
DISP(pos[j], circle[i]);
pos[j] = circle[i++];
i %= 3;
} else {
DISP(pos[j], 6 - pos[j] - pos[0]);
pos[j] = 6 - pos[j] - pos[0];
}
even = 1 - even;
}
return 0;
}
int qlog2(unsigned int x) {
int n = 1;
if ((x >> 16) == 0) {
n += 16;
x <<= 16;
}
if ((x >> 24) == 0) {
n += 8;
x <<= 8;
}
if ((x >> 28) == 0) {
n += 4;
x <<= 4;
}
if ((x >> 30) == 0) {
n += 2;
x <<= 2;
}
n -= (x >> 31);
return 31 - n;
}