全部博文（103）
分类： C/C++
2008-05-13 23:44:27
A、B二子被限制在己方3×3的格子（横向与纵向分别有三个可以运动到的位置）里运动。例如,在如上的表格里，A被正方形{d10,f10,d8,f8}所包围，而B被正方形{d3, f3, d1, f1}包围。每一步，A、B分别可以横向或纵向移动一格，但不能沿对角线移动。另外，A不能面对B，也就是说，A和B不能处于同一纵向直线上（比如A在d10的位置，那么B就不能在d1,d2以及d3）。
请写出一个能够生成A、B所有可能位置，并且在控制台上打印出来的C程序。要求在代码中只能使用一个变量。
分析和解答：
问题的本身并不复杂，我们只要把所有A、B互相排斥的条件列举出来就可以完成本题的要求。由于本题要求只能使用一个变量，所以我们必须首先想清楚在写代码的时候，有哪些信息需要存储，并且尽量少地存储信息。稍微思考一下，我们可以知道这个程序的大体框架是：
遍历A的位置
遍历B的位置
判断A，B的位置组合是否满足要求。
如果满足，则输出。
因此，我们需要存储的是A，B的位置信息，并且每次循环都要更新。为了能够进行判断，我们首先需要创建一个逻辑的坐标系统以便检测A何时会面对B。这里我们想到的方法是用1~9的数字，按照行优先的顺序来表示每个格点的位置。这样，我们只需要用模余运算就可以得到当前的列号，从而判断是否A、B互斥。
第二，题目要求只用一个变量，但是我们却要存储A和B两个子的位置信息，该怎么办呢？
条件的确非常苛刻，我们可以先把已知变量类型列举一下，然后做些分析。
对于bool类型，我们估计没有办法做任何扩展了，因为它只能表示true和false两个值；而byte或者int类型，它们能够表达的信息则更多。事实上，对本题来说，每个子都只需要9个数字就可以表达它的全部位置。
一个八位byte类型能够表达28=256个值，所以用它来表示A、B的位置信息是绰绰有余。因此我们可以把这个一字节的变量（设为b）分成两部分。用前4bit表示A的位置，用后面的4bit表示B的位置。4个bit可以表示16个数，这已经足够了。
问题在于：如何使用bit级的运算将数据从这一byte变量的左边和右边分别存入和读出。
下面是做法：
首先清除b的右边的bits，同时保持左边的bits:
11110000 (LMASK)
& 10100101 (b)
-----------
10100000
然后将上一步得到的结果与n做或运算
10100000 (LMASK & b)
^ 00000011 (n)
------------
10100011
首先，清除b的左边的bits，同时保持右边的bits:
00001111 (RMASK)
& 10100101 (b)
-----------
00000101
现在，把n移动到一byte数据的左边
n << 4 = 00110000
然后对以上两步得到的结果做或运算，从而得到最终结果。
00000101 (RMASK & b)
^ 00110000 (n << 4)
-----------
00110101
清除b的左边的bits，同时保持右边的bits
00001111 (RMASK)
& 10100101 (b)
-----------
00000101
清除b的右边的bits，同时保持左边的bits
11110000 (LMASK)
& 10100101 (b)
-----------
10100000
将结果右移4bits
10100000 >> 4 = 00001010
最后的挑战是如何在不声明其他变量的约束下创建一个for循环。我们可以重复利用1byte的存储单元，把它作为循环计数器并用前面提到的存取和读入技术进行操作。我们还可以用宏来抽象化代码，例如：
for (LSET(b, 1); LGET(b) <= GRIDW * GRIDW; LSET(b, (LGET(b) + 1)))
【解法】
#define HALF_BITS_LENGTH 4
//这个值是记忆存储单元长度的一半，在这道题里是4bit
#define FULLMASK 255
//这个数字表示一个全部bit的mask，在二进制表示中，它是11111111。
#define LMASK (FULLMASK << HALF_BITS_LENGTH)
//这个宏表示左bits的mask，在二进制表示中，它是11110000。
#define RMASK (FULLMASK >> HALF_BITS_LENGTH)
这个数字表示右bits的mask，在二进制表示中，它表示00001111。
#define RSET(b, n) (b = ((LMASK & b) ^ n))
//这个宏，将b的右边设置成n
#define LSET(b, n) (b = ((RMASK & b) ^ (n << HALF_BITS_LENGTH)))
//这个宏，将b的左边设置成n
#define RGET(b) (RMASK & b)
//这个宏得到b的右边的值
#define LGET(b) ((LMASK & b) >> HALF_BITS_LENGTH)
//这个宏得到b的左边的值
#define GRIDW 3
//这个数字表示将帅移动范围的行宽度。
#include
#define HALF_BITS_LENGTH 4
#define FULLMASK 255
#define LMASK (FULLMASK << HALF_BITS_LENGTH)
#define RMASK (FULLMASK >> HALF_BITS_LENGTH)
#define RSET(b, n) (b = ((LMASK & b) ^ n))
#define LSET(b, n) (b = ((RMASK & b) ^ (n << HALF_BITS_LENGTH)))
#define RGET(b) (RMASK & b)
#define LGET(b) ((LMASK & b) >> HALF_BITS_LENGTH)
#define GRIDW 3
int main()
{
unsigned char b;
for (LSET(b, 1); LGET(b) <= GRIDW * GRIDW;
LSET(b, (LGET(b) + 1)))
for (RSET(b, 1); RGET(b) <= GRIDW * GRIDW;
RSET(b, (RGET(b) + 1)))
if (LGET(b) % GRIDW != RGET(b) % GRIDW)
printf("A = %d, B = %d\n",
LGET(b), RGET(b));
return 0;
}
【输出】:
格子的位置用N来表示，N = 1…9, 依照行优先的顺序，如下图所示：
|
“将”（A）的格子: |
|
|
“帅”（B）的格子: |
|
|
A = 1, B = 3 A = 1, B = 5 A = 1, B = 6 A = 1, B = 8 A = 1, B = 9 A = 2, B = 1 A = 2, B = 3 A = 2, B = 4 A = 2, B = 6 A = 2, B = 7 A = 2, B = 9 A = 3, B = 1 A = 3, B = 2 A = 3, B = 4 A = 3, B = 5 A = 3, B = 7 A = 3, B = 8 |
A = 4, B = 3 A = 4, B = 5 A = 4, B = 6 A = 4, B = 8 A = 4, B = 9 A = 5, B = 1 A = 5, B = 3 A = 5, B = 4 A = 5, B = 6 A = 5, B = 7 A = 5, B = 9 A = 6, B = 1 A = 6, B = 2 A = 6, B = 4 A = 6, B = 5 A = 6, B = 7 A = 6, B = 8 |
A = 7, B = 3 A = 7, B = 5 A = 7, B = 6 A = 7, B = 8 A = 7, B = 9 A = 8, B = 1 A = 8, B = 3 A = 8, B = 4 A = 8, B = 6 A = 8, B = 7 A = 8, B = 9 A = 9, B = 1 A = 9, B = 2 A = 9, B = 4 A = 9, B = 5 A = 9, B = 7 A = 9, B = 8 |
考虑了这么多因素，总算得到了本题的一个解法，但是MSRA里却有人说，下面的一小段代码也能达到同样的目的：
BYTE i = 81;
while(i--)
{
if (i / 9 % 3 == i % 9 % 3) continue;
printf(“A = %d, B = %d\n”, i / 9 + 1, i % 9 + 1);
}
但是很快另一个人却说他的解法才是效率最高的：
struct {
unsigned char a:4;
unsigned char b:4;
} i;
for (i.a = 1; i.a <= 9; i.a++)
for (i.b = 1; i.b <= 9; i.b++)
if (i.a % 3 == i.b % 3)
printf(“A = %d, B = %d\n”, i.a, i.b);
读者能自己证明一下么？
注：这一题目由微软亚洲研究院工程师Matt Scott提供，他在学习中国象棋的时候想出了这个题目，后来一位应聘者给出了比他的“正解”简明很多的答案，他们现在成了同事。
