现在的位置: 首页 > 综合 > 正文

编程之美 中国象棋将帅问题 位操作

2013年10月14日 ⁄ 综合 ⁄ 共 1462字 ⁄ 字号 评论关闭

编程之美中1.2节讲了将帅问题。问题描述如下:

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

1-3副本

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

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

 

因为只能用一个变量,所以就要通过位操作来保存足够的信息。将一个byte类型的变量的左边4位和右边4位保存不同的信息。

位操作请参照:http://blog.csdn.net/weixingstudio/article/details/6787628 虽然这里的位操作是C#的,但是C++的位操作原理一样。

 

因为只可以使用一个变量,所以在for 循环中也只可以使用为操作来记录信息。

一下是详细代码,代码中注释可以详细的了解原理。

// chess.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "iostream"

#define HALF_BITS_LENGTH 4  
// 记录存储单元长度的一般
#define FULLMASK 255  // 记录完全的mask
#define LMASK (FULLMASK<<HALF_BITS_LENGTH) // 表示左侧的mask, 1111 0000
#define RMASK (FULLMASK>>HALF_BITS_LENGTH) // 右侧的mask, 0000 1111
#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 GRID 3

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	unsigned char b;
	for(LSET(b,1);LGET(b)<=GRID*GRID;LSET(b,(LGET(b)+1)))
	{
		for(RSET(b,1);RGET(b)<=GRID*GRID;RSET(b,(RGET(b)+1)))
		{
			if(LGET(b)%GRID!=RGET(b)%GRID)
			{
				printf("A=%d, B=%d \n", LGET(b),RGET(b));
			}
		}
	}
	return 0;
}

 

 

 

当然,如果不用位操作也可以,还有人提出了可以这样做,通过结构体来操作。

	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++)
		{
			// 相关操作
		}
	}

这个方法既简单又直观,不用管那么复杂的位操作。

抱歉!评论已关闭.