首页 > 代码库 > 1.2中国象棋将帅问题

1.2中国象棋将帅问题

(根据中国象棋的基本原则)在只有双的将帅棋盘上,找出所有双方可以落子的位置(将帅不能碰面),但只能使用一个变量。

直觉上我们想到,只要遍历将帅所有可能的位置,去除将帅冲突的位置即可。可见,剩下的问题就在于如何使用一个变量来做二重循环的遍历。书中解法一给出的方法是将一个Byte变量拆成两个用,前一半代表“帅”可以走的位置,后一个变量代表“将”可以走的位置(事先已经将“将”和“帅”可以走的3*3的位置进行了编号),利用位操作即可获得两个计数器的功能。

书中的解法三采用结构体,C语言中的位域来解决一个变量遍历二重循环的问题,思想上换汤不换药。

真正有趣的是解法二。


(一)

我们先看算法三:

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

(二)

下面我们再看最有意思的算法二:

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);
}
在上面的算法中,“/”与“%”是用一个变量值进行内外层循环的常用伎俩。

在i从81变化到0的过程中,i / 9的变化相当于外层循环的变化,而i % 9的变化则相当于内层的变化。





1.2中国象棋将帅问题