`
阿尔萨斯
  • 浏览: 4107092 次
社区版块
存档分类
最新评论

编程之美 - 中国象棋将帅问题

 
阅读更多

下过中国象棋的朋友都知道,双方的“将”和“帅”相隔遥远,并且它们不能照面。在象棋残局中,许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将”和“帅”二子(如图1-3所示)(为了下面叙述方便,我们约定用A表示“将”,B表示“帅”):

1-3副本

图1-3

AB二子被限制在己方3×3的格子里运动。例如,在如上的表格里,A被正方形{d10, f10, d8, f8}包围,而B被正方形{d3, f3, d1, f1}包围。每一步,AB分别可以横向或纵向移动一格,但不能沿对角线移动。另外,A不能面对B,也就是说,AB不能处于同一纵向直线上(比如Ad10的位置,那么B就不能在d1d2以及d3)。

请写出一个程序,输出AB所有合法位置。要求在代码中只能使用一个变量。

分析与解法

问题的本身并不复杂,只要把所有AB互相排斥的条件列举出来就可以完成本题的要求。由于本题要求只能使用一个变量,所以必须首先想清楚在写代码的时候,有哪些信息需要存储,并且尽量高效率地存储信息。稍微思考一下,可以知道这个程序的大体框架是:

遍历A的位置

遍历B的位置

判断A、B的位置组合是否满足要求。

如果满足,则输出。

因此,需要存储的是AB的位置信息,并且每次循环都要更新。为了能够进行判断,首先需要创建一个逻辑的坐标系统,以便检测A何时会面对B。这里我们想到的方法是用1~9的数字,按照行优先的顺序来表示每个格点的位置(如图1-4所示)。这样,只需要用模余运算就可以得到当前的列号,从而判断AB是否互斥。

图1-4 用1~9的数字表示A、B的坐标

第二,题目要求只用一个变量,但是我们却要存储AB两个子的位置信息,该怎么办呢?

可以先把已知变量类型列举一下,然后做些分析。

对于bool类型,估计没有办法做任何扩展了,因为它只能表示true和false两个值;而byte或者int类型,它们能够表达的信息则更多。事实上,对本题来说,每个子都只需要9个数字就可以表达它的全部位置。

一个8位的byte类型能够表达28=256个值,所以用它来表示AB的位置信息绰绰有余,因此可以把这个字节的变量(设为b)分成两部分。用前面的4 bit表示A的位置,用后面的4 bit表示B的位置,那么4个bit可以表示16个数,这已经足够了。

问题在于:如何使用bit级的运算将数据从这一byte变量的左边和右边分别存入和读出。

下面是做法:

n 将byte b(10100101)的右边4 bit(0101)设为n(0011):

首先清除b右边的bits,同时保持左边的bits:

11110000(LMASK)

& 10100101(b

-----------

10100000

然后将上一步得到的结果与n做或运算

10100000(LMASK & b

^ 00000011(n

------------

10100011

n 将byte b(10100101)左边的4 bit(1010)设为n(0011):

首先,清除b左边的bits,同时保持右边的bits:

00001111(RMASK)

& 10100101(b

-----------

00000101

现在,把n移动到byte数据的左边

n << 4 = 00110000

然后对以上两步得到的结果做或运算,从而得到最终结果。

00000101(RMASK & b

^ 00110000(n << 4)

-----------

00110101

n 得到byte数据的右边4 bits或左边4 bits(e.g. 10100101中的1010以及0101):

清除b左边的bits,同时保持右边的bits

00001111(RMASK)

& 10100101(b

-----------

00000101

清除b的右边的bits,同时保持左边的bits

11110000(LMASK)

& 10100101(b

-----------

10100000

将结果右移4 bits

10100000 >> 4 = 00000101

最后的挑战是如何在不声明其他变量约束的前提下创建一个for循环。可以重复利用1byte的存储单元,把它作为循环计数器并用前面提到的存取和读入技术进行操作。还可以用宏来抽象化代码,例如:

for (LSET(b, 1); LGET(b) <= GRIDW * GRIDW; LSET(b, (LGET(b) + 1)))

【解法一】

代码清单1-6

#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 <stdio.h>

#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, 2, …, 8, 9,依照行优先的顺序,如图1-5所示:

“将”(A)的格子

“帅”(B)的格子

图1-5

A = 1, B = 2

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 = 2

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 = 2

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);

}

但是很快又有另一个人说他的解法才是效率最高的:

代码清单1-7

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);

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics