中国象棋将帅问题
中国象棋里面双方的“将”和“帅”各自呆在自己的九宫格里，一步只能横移或纵移一格，而且双方不能见面（既不能处在同一条纵线上）。在残局时有的人会用这一规则走出绝妙杀招。假设一方的“将”为A，另一方的“帅”为B，现在求双方所能出现的所有合法位置，所需变量只能用一个字节来保存。
我们用1~9的数字来，按行优先的顺序来表示每个格点的位置，如下图所示。这样只需要用模余运算就可以得到当前的列号，从而判断A、B是否互斥。
【解法一】用C语言实现
一种比较正经的解法，就是用位运算，设一个char变量，前四个字节存一个变量，后四个字节存一个变量。#include#define HALF_BITS_LENGTH 4 //存储单元长度的一半，即4位#define FULLMASK 255 //存储单元全部bit的mask(掩码)，在二进制表示中，是11111111#define LMASK (FULLMASK << HALF_BITS_LENGTH) //左四位，11110000#define RMASK (FULLMASK >> HALF_BITS_LENGTH) //右四位。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 // 九宫格边界长度 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;}
同样的思路用java实现如下：
package chapter1youxizhileChinesechess;/** * 【解法一】 * 中国象棋将帅问题 * @author DELL * */public class ChineseChess1 { public static final int HALF_BITS_LENGTH = 4; //存储单元长度的一半，这里是4bit public static final int FULLMASK = 255; //全部bit的隐码，即为11111111 public static final int LMASK = (byte)(255 << HALF_BITS_LENGTH)& 0x0FF; //无符号左移，11110000 public static final int RMASK = (byte)(255 >>> HALF_BITS_LENGTH); //无符号右移，00001111 public static int LSET(byte b, int n){ //将b的左半部分设为n return (RMASK & b)^((byte)n << HALF_BITS_LENGTH); } public static int RSET(byte b, int n){ //将b的右半部分是为n return (LMASK & b)^(byte)n ; } public static int LGET(byte b){ //获得b的左半部分 return (LMASK & b) >> HALF_BITS_LENGTH; } public static int RGET(byte b){ //获得b的右半部分 return RMASK & b; } public static final int GRIDW = 3; public static void main(String[] args) { byte b = 0; b = (byte) LSET(b,8); System.out.println(b); for(b=(byte) LSET(b,1);LGET(b)<=GRIDW*GRIDW;b=(byte) LSET(b,LGET(b)+1)){ for(b=(byte) RSET(b,1);RGET(b)<=GRIDW*GRIDW;b=(byte) RSET(b,RGET(b)+1)){ if(LGET(b)%GRIDW != RGET(b)%GRIDW) System.out.println("A = "+LGET(b)+", B = "+RGET(b)); } } }} 【解法二】
package chapter1youxizhileChinesechess;/** * 中国象棋将帅问题 * 【解法二】 * @author DELL * */public class ChineseChess2 { public static void main(String[] args) {// byte i = 81;// while(i!=0){// if(i/9%3!=i%9%3)// System.out.printf("A=%d, B=%d\n", i/9+1,i%9+1);// i--;// } byte i = 1; while(i!=80){ if(i/9%3!=i%9%3) System.out.printf("A=%d, B=%d\n", i/9+1,i%9+1); i++; } }}
【解法三】
有人说是效率最高的：
//中国象棋将帅问题//【解法三】#includestruct{ unsigned char a:4; unsigned char b:4;}i;int main(){ for(i.a=1;i.a<=9;i.a=i.a+1){ for(i.b=1;i.b<=9;i.b=i.b+1){ if(i.a%3!=i.b%3) printf("A = %d, B = %d\n",i.a,i.b); } } return 0;}