《编程之美》--中国象棋将帅问题博客分类： java 服务 java编程之美算法面试

程序员文章站 2024-03-24 20:42:28

...

最近在看微软研究院出版的《编程之美》一书，对于该书中提到的一些问题，特别感觉兴趣，比如下面这个问题：

《编程之美》--中国象棋将帅问题

博客分类： java 服务 java编程之美算法面试

分析：

思考一下，可以这样来解决，

------------------------------------------------------------------------------------------------------------------

遍历 A 的位置

遍历 B 的位置

判断 A 、 B 的位置组合是否满足要求

如果满足，则输出

------------------------------------------------------------------------------------------------------------------

类似于双层循环运算

创建一个逻辑坐标系统，用 1-9 的数字，按照行优先的顺序来表示每个格点的位置。

《编程之美》--中国象棋将帅问题

博客分类： java 服务 java编程之美算法面试

要证明 A 和 B 不在同一列上，只要 A 和 B 所处的格子点数 mod3 不相等就可以。

分析解法一：

该书中提到的解法一的思想是通过位运算来解决上面的问题。一个 8 位的 byte 类型能够表达 2 的 8 次方 =256 个值，所以用它来表示 A 、 B 的位置信息绰绰有余，因此可以把这个字节分成两部分，用前面的 4bit 表示 A 的位置，用后面的 4bit 表示 B 的位置，而 4 个 bit 可以表示 16 个数，这已经够了。

JAVA 中用 byte 来表示位置，可以实现，但只用一个变量，就没了思路（请高手指点） …

分析解法二 ( 这里用 Java 代码实现 ) ：

       int i = 81;

       while(i--!=0){

            if(i/9%3 == i%9%3)
               continue;

            System.out.println("A="+(i/9+1)+" B="+(i%9+1));

       }

代码精简，但 i/9%3 == i%9%3 一句百思不得其解，原理是什么？

想要弄懂 i/9 和 i%9 在 while 循环里代表什么意思，于是做了以下测试

       int i = 81;

       while(i-->0){

           System.out.print(" "+i%9);

       }

       i = 81;

       System.out.println();

       while(i-->0){

           System.out.print(" "+i/9);

       }

---------------------------------------------------------------------------------------------------------------------------------

输出结果：

8 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0

8 8 8 8 8 8 8 8 8 7 7 7 7 7 7 7 7 7 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0

从上面可以看出来， i/9 类似于双层循环的外层循环，保持值不变，直到内层循环循环了 9 次后，值再改变。而 i%9 正好类似于内层循环，值循环依次改变 9 次。

后面都带有 %3 正好是上面提到的 A 和 B 格子对应的数字 mod3 判断是否相等，相等则在一条直线上（ A 和 B 碰面）。

分析解法三：

文中用到了 C 语言的 struct 结构， Java 中没有 struct 语法，可以用类对象形式实现，但就不是声明一个变量，解法中就要声明一个对象。

下面提供一个简易理解的解法：

for(int i=1;i<=9;i++){

           for(int j=1;j<=9;j++){

              if(i%3!=j%3)

                  System.out.println("a="+i+",b="+j);

           }

}

虽然运用了两个变量，但清楚的表达了解题思想

也许用“大道至简”最能表达编程之美提倡的编程精神 … 但又不足以表达它的精神 … 编程需要有清楚的逻辑思维，数据结构等算法，有时候还要对计算机的底层指令及运行原理有一定的认，慢慢的发现，自己原在大学没有好好学的，工作中还要重拾起来 …