《编程之美》读书笔记(一)——中国象棋将帅有效位置

《编程之美》读书笔记(一) ——中国象棋将帅有效位置

(原创内容,转载请注明来源,谢谢)

一、问题

如上述棋盘,假设将为点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

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-10-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术之路

算法时间复杂度

     算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算...

19060
来自专栏Python小屋

Python模拟大整数乘法的小学竖式计算过程

让我们先看个图回顾一下小学学过的计算整数乘法的竖式计算过程 ? 然后再来看如何使用Python来模拟上面的过程,虽然在Python中计算任意大的数字乘法都没有问...

36450
来自专栏追不上乌龟的兔子

[多少懂点位运算】续·一行代码解决LeetCode268缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

18540
来自专栏Python专栏

浅尝Python快速排序

15540
来自专栏小二的折腾日记

牛客网刷题总结-剑指offer(1)

这里一般的思路肯定是,从行或者列开始找,根据递增的顺序,找到行或者列之后再判断列或者行,知道找到为止。最好的方法是,从左下角或者右上角开始找。原因是:这样的一行...

11510
来自专栏Android机动车

数据结构学习笔记——总述

数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。

7610
来自专栏生信技能树

R语言中的排序,集合运算,reshape,以及merge总结

不想排版,心情也不好,但是这个知识点很重要,尤其是学习R语言的朋友,请仔细看~ 一直以来我都是随便看了点R的编程教程,因为我学了一点点C,所以还算有基础,现在基...

357110
来自专栏Python小屋

哈夫曼编码原理与Python实现代码(附手动推导过程原稿真迹)

哈夫曼编码依据字符出现概率来构造异字头(任何一个字符的编码都不是其他字符的前缀)的平均长度最短的码字,通过构造二叉树来实现,出现频次越多的字符编码越短,出现频次...

79280
来自专栏无所事事者爱嘲笑

常用的sort打乱数组方法真的有用?

29760
来自专栏窗户

有限域(3)——多项式环的商环构造有限域

  接着上两章内容,我们还是得继续寻找有限域的构造方法。上章证明矩阵环是个单环,自然是没戏了,但我们还可以考虑多项式环。

34920

扫码关注云+社区

领取腾讯云代金券