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

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

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

一、问题

如上述棋盘,假设将为点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 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

浅谈Python如何处理字符串

本次内容是以以Python 2.7为例来进行讨论的,Python 3x与其类似。 1. Python文件编码 在文件头部一般声明为UTF-8: # encod...

3418
来自专栏云瓣

JS家的排序算法

由于浏览器的原生支持(无需安装任何插件),用JS来学习数据结构和算法也许比c更加便捷些。因为只需一个浏览器就能啪啪啪的调试了。比如下图我学习归并排序算法时,只看...

3178
来自专栏数据结构与算法

20:反反复复

20:反反复复 总时间限制: 1000ms 内存限制: 65536kB描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数,然后将信息(只包含字...

3398
来自专栏Java开发者杂谈

插入排序与归并排序

前言:   排序算法应该算是算法入门级的东西了,这里重新学习算法,先暂时归纳下个人对两种算法的理解。 插入排序: 插入排序可以对应到现实生活中的排队去停车场停...

34912
来自专栏技术沉淀

命令行工具:cut列操作

1797
来自专栏猿人谷

三十分钟掌握STL

这是本小人书。原名是《using stl》,不知道是谁写的。不过我倒觉得很有趣,所以化了两个晚上把它翻译出来。我没有对翻译出来的内容校验过。如果你没法在三十分钟...

2188
来自专栏Python小屋

非计算机专业《Python程序设计基础》教学参考大纲

通过本课程的学习,使得学生能够理解Python的编程模式(命令式编程、函数式编程),熟练运用Python运算符、内置函数以及列表、元组、字典、集合等基本数据类型...

652
来自专栏WeaponZhi

轻松初探Python(六)—函数

这是「AI 学习之路」的第 6 篇,「Python 学习」的第 6 篇 题外话 这周工作日 5 天,我并没有更新文章,但大家并不要以为小之懒惰了。正好相反,自从...

3297
来自专栏机器学习算法与Python学习

Python: 早点知道这些就不会这样了

现在在Python 2的代码中都用import from future来导入Python 3的输出和除法。现在用到的几乎所有库都支持Python 3,因此会很快...

2594
来自专栏应用案例

数据结构试题库答案算法设计题

算法设计题(10分) (1)阅读下列递归算法,写出非递归方法实现相同功能的C程序。 void test(int &sum) { int x; scanf(...

1938

扫描关注云+社区