《编程之美》读书笔记(一) ——中国象棋将帅有效位置
(原创内容,转载请注明来源,谢谢)
一、问题
如上述棋盘,假设将为点A,帅为点B。将只能在d10、d8、f10、f8点内部的正方形移动(共9个点 可以移动),帅假设点B只能在d3、d1、f3、f1的正方形移动,类似将。
现要求A、B不能在同一直线,求出A、B的所有合法位置,只能用一个变量。
二、分析
1、问题简化
首先,用1-9的九宫格位置,存储A、B点的位置,如下图:
则,每个数字对3取模,就可以确定所在的列,即可以确定A、B两点是否在同一列。
2、只能用一个变量
只能用一个变量,但是需要遍历A、B的位置,需要两个变量来存储数据,而且希望尽量节省空间。
三、求解
1、个人解法
看了书上第一种解法,一堆的位运算感觉很复杂。个人想到的是,既然要输出A、B两点的位置,其实可以用11-99中的数字,除去逢10的(即未定义的数字)以及同一列的数据,就可以得到想要的结果,而且只要用一个变量。
用PHP写法如下:
for($i=11;$i<100;$i++){
if(0 == $i%10 || $i%10%3 == intval($i/10)%3) continue;
echo “A=”.$i%10.” B=”.intval($i/10).”\n”;
}
用java写法如下:
for(inti=11;i<100;i++){
if(0 == i%10 || int(i%10)%3 == (int)(i/10)%3) continue;
System.out.println(“A=”+i%10+” B=”+(int)(i/10));
}
2、书中解法二(解法一位运算太复杂忽略)
C++的写法,如下:
BYTEi = 81;
while(i--){
if(i/9%3 == i%9%3) continue;
printf(“A=%d, B=%d\n”, i/9+1, i%9+1);
}
我发现这种解法比我的少了一重的判断,这个算法还是利用了1-9这9个数字,比我减少的是对于是否是0的判断。
经过计算,我发现确实这样筛选已经可以筛掉包含0的情况。
另外,结果输出的时候,采用和9计算后加1,这样可以在结果中返回所需的11-99中正确的数字。因为其从81开始,进入循环就减1了,因此除以9最多是8,和取模的结果范围一样,都是0-8,则加1就可以获取1-9。
3、书中解法三
解法三,个人认为已经超出只能用1个变量这个要求了,但是作者说这个效率更高,代码如下:
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);
}
}
}
——written by linhxx 2017.10.04