/*
中国象棋将帅问题:
自古将帅不能照面
__ __ __
10 将
9
8
7
6
5
4
3
2
1 帅
a b c d e f g h i
A表示将,B表示帅,A被限制在{d10,f10,d8,f8}中,B被限制在{d3,f3,d1,f1}中。
每一步A,B可以横向或纵向移动一个。A与B不能在同一条纵向直线上,比如A在d10位置,B就不能在d1,d2,d3位置
请写出一个程序,输出A、B所有合法位置。要求在代码中只能使用一个字节存储变量。
起始就是一个全排列问题
算法:
遍历A的位置
遍历B的位置
判断A、B的位置组合是否满足要求
如果满足则输出
需要存储的是A、B的位置信息,并且每次循环需要更新。
创建一个逻辑坐标系统,用1~9,按照行优先的顺序表示每个格点的位置。这样用模运算可以得到当前的列号,
判断A和B是否互斥。
只用一个变量,存储A和B的两个子的位置信息。
因此只能从位上做文章,用字节8位,256个值,足够表示A、B的位置信息。
因此将该字节一分为而,前4位表示A,后4位表示B,这样每个棋子都有16种位置表示方法,已经足够(牛逼啊)
将byte b(10100101)的右边4位(0101)设为n(0011)
1先清除b右边的bits,用11110000
& 10100101
得到 10100000
| 00000011
得到 10100011
2将byte b(10100101)的左边4位(1010)设为(0011)
清除左边的4bit,同时保存右边的4bit,用与
00001111
&10100101
得到 00000101
将n 0011左移4位
n << 4 = 00110000
做或运算
00000101
| 00110000
得到 00110101
3将得到的byte的数据的右边4位或左边4位(将10100101中的1010及0101)
清除b左边的bits,同时保持右边的bits
00001111
& 10100101
得到 00000101
清除右边的bits,同时保持左边的bits
11110000
&10100101
得到 10100000
结果右移4位 10100000 >> 4 = 00001010
如何在不声明其他变量约束的前提下创建一个for循环。可以重复利用1byte存储单元,把它作为循环计数器
并用前面提到的存取和读入技术进行判断。
还可以用宏来抽象代码。
for( LEST(b,1) ; LEST(b) <= GRIDW * GRIDW ; LSET(b,(LGET(b) + 1)))
*/
/*
关键:
1 因此将该字节一分为二,前4位表示A,后4位表示B,这样每个棋子都有16种位置表示方法,已经足够(牛逼啊)
2 算法:
遍历A的位置
遍历B的位置
判断A、B的位置组合是否满足要求
如果满足则输出
3 #define LEFT_MASK (FULL_MASK << 4) //注意,用define定义东西的时候,若有两个变量,需要加括号
4 #define RIGHT_MASK (FULL_MASK >> 4) //右掩码就是右边4位全是1
5 #define LSET(b,n) (b = ((b & RIGHT_MASK) | ((n) << 4) ) )//将比特b的左边设定为n,主要为循环遍历使用。采用的方法是,
//左边清零(通过与右掩码(00001111)相与即可),然后将数n向左移4位,然后将上述两个数用或即可,注意别漏了赋值操作
//注意n要用括号括起来,他表示一个数,不是一个字符
6 #define LGET(b) ( (b & LEFT_MASK) >> 4)//获取比特b的左边4位的方法是,先将右边4位清零,
//再右移4位即可
7 if(LGET(b) % STEP != RGET(b) % STEP)//牛逼,用九宫格模拟两者取模之后的余数不同,就表示
//不在一条竖线上就可以
*/
#include <stdio.h> #define FULL_MASK 255 //#define HALF_MOVE 4 #define LEFT_MASK (FULL_MASK << 4) //注意,用define定义东西的时候,若有两个变量,需要加括号 #define RIGHT_MASK (FULL_MASK >> 4) //右掩码就是右边4位全是1 #define LSET(b,n) (b = ((b & RIGHT_MASK) | ((n) << 4) ) )//将比特b的左边设定为n,主要为循环遍历使用。采用的方法是, //左边清零(通过与右掩码(00001111)相与即可),然后将数n向左移4位,然后将上述两个数用或即可,注意别漏了赋值操作 //注意n要用括号括起来,他表示一个数,不是一个字符 #define RSET(b,n) (b = ((b & LEFT_MASK) | (n) ) )//将比特b的右边设定为n,采用的方法是: //右边清零(将该数与左掩码(11110000)相与),然后与该数n相或 #define LGET(b) ( (b & LEFT_MASK) >> 4)//获取比特b的左边4位的方法是,先将右边4位清零, //再右移4位即可 #define RGET(b) (b & RIGHT_MASK)//获取比特b的右边4位的方法是,将该数右边4位与右掩码相与即可 #define STEP 3 void ChineseChess_define() { unsigned char b; int iCnt = 0; for(LSET(b,1) ; LGET(b) <= STEP * STEP ; LSET(b,(LGET(b) + 1) ) ) { for(RSET(b,1) ; RGET(b) <= STEP * STEP ; RSET(b,(RGET(b) + 1) ) ) { if(LGET(b) % STEP != RGET(b) % STEP)//牛逼,用九宫格模拟两者取模之后的余数不同,就表示 //不在一条竖线上就可以 { printf("A=%d,B=%d\n",LGET(b),RGET(b)); iCnt++; } } } printf("%d\n",iCnt); } void ChineseChess_mod() { unsigned char i = 81;//?BYTE是什么类型 int iCnt = 0; while(i--) { if(i / 9 % 3 == i % 9 % 3)//?不懂 { continue; } printf("A=%d,B=%d\n",i / 9 + 1 , i % 9 + 1); iCnt++; } printf("%d\n",iCnt); } typedef struct Num { unsigned char a:3; unsigned char b:4; }Num; void ChineseChess_struct() { int iCnt = 0; Num Num1; for(Num1.a = 1 ; Num1.a <= 9 ; Num1.a++) { for(Num1.b = 1 ; Num1.b <= 9; Num1.b++) { if(Num1.a % 3 != Num1.b % 3) { printf("A=%d,B=%d\n",Num1.a,Num1.b); iCnt++; } } } printf("%d\n",iCnt); } void process() { ChineseChess_define(); //ChineseChess_mod(); //ChineseChess_struct();//似乎有错误 } int main(int argc,char* argv[]) { process(); getchar(); return 0; }