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

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

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

一、问题

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

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

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

2036
来自专栏Android机动车

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

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

591
来自专栏人工智能LeadAI

讨厌算法的程序员 1 | 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生出一...

2887
来自专栏技术之路

算法时间复杂度

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

1836
来自专栏Python小屋

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

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

4698
来自专栏程序员叨叨叨

5.2 数组类型

在着色程序中,数组通常的使用目的是:作为从外部应用程序传入大量参数到 Cg 的顶点程序中的形参接口,例如与皮肤形变相关的矩阵数组,或者光照参数数组等。

561
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(06-10打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

1082
来自专栏杨建荣的学习笔记

Java随机数算法(一)(r11笔记第14天)

问:如何生成一个随机的字符串?答:让新手退出VIM 。 这可能也是随机字符的一种由来:) 我们今天要说的是随机数算法,这个我策划了好久,但是进展缓慢。...

4087
来自专栏ml

向前字典排序

          next_permutation算法对区间元素进行一次组合排序,使之字典顺序大于原来的排序,有如下两个使用原形,对迭代器区间[first,l...

2589

扫码关注云+社区