中文XML论坛--(第四期获奖名单公布，最新4节的电子版pdf已开放下载) 预览电子版，写书评，赢取《编程之美—微软技术面试心得》(微软亚洲研究院邹欣等主编)，每周送出3本，机会多多！，欢迎参加由博文视点和本站联合举办的有奖征集书评活动

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

来晚了，也参加！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

编程之美——从中国象棋将帅问题说起

高中到大学期间看过不少算法书，从经典的《算法导论》，到比较新的Umesh的《Algorithms》、Tardos的《Algorthim Design》，都曾经细读过一段时间，这些书的一个特点就是很系统、正规，通常捧起来就能啃上一个下午。

一个偶然的机会在书店看到了《编程之美》，接触到了另一种教学风格。严格的说，这本书也不能算是算法书，因为里面涉及的知识范围不止是算法，比如有一道趣味题是解决如何控制CPU占用率曲线的问题，这和实际的编程联系的更为紧密，而通常的算法书更偏向于理论，甚至大多数算法都是用伪代码描述的。

这本书的一大特点就是首先给出一个易于描述和理解的常见问题，接着会给出若干种思维方式各异的方法，值得细细品味。

以“中国象棋将帅问题”为例，要求只使用一个代码输出所有将帅的合法布局位置。看到这道题，第一反应恐怕就是设计一个函数，使得两个二维坐标能用一个变量来表述，而解法一也采用了这种最直观的思想，利用了二进制把27*27个状态放到了一个整型中，定义了几个简单实用的宏（另外值得一提的是这本书对二进制的与、或、位移等操作使用得很漂亮，在其他例题中也能看到类似的精彩代码），然后通过这些宏用两重循环完成了各种状态的枚举。

另外值得一提的是，这本书的中代码都很简单明了，“寻找发帖‘水王’”中，给出了这样一个高效的算法后，如何实现又是一个问题。书上给出的这段代码只有短短十几行，却高效可行，毫不啰嗦，令人叹服。

总的来说，这本书的风格就是趣味轻快，却包含着大量知识，随手拿起看一两章就会有很大的收获。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

本书评转载自：http://blog.csdn.net/kabini/archive/2008/04/07/2256421.aspx

总体感觉是书中的内容没有“脱离群众”，很多都是我们平时生活、工作中经常能遇到的。题目不见得难，基本上给一本《算法导论》和足够的时间，大多数人都能解决其中的问题。但注意副标题--“微软技术面试心得”，这就给这本书定下一个基调：面对这些我们并不陌生、也并非特别困难的问题，在有限的时间里，（可能）比较紧张的心情之下，如何充分发挥自己分析问题和解决问题的能力，如何正确且漂亮地解决问题才是关键。我想，在平时学习的时候或许我们左手《算法导论》，右手《编程之美》效果会更好一些。

关于"中国象棋将帅问题"，该问题的具体描述是：（根据中国象棋的基本原则）在只有双的将帅棋盘上，找出所有双方可以落子的位置（将帅不能碰面），但只能使用一个变量。直觉上我们想到，只要遍历将帅所有可能的位置，去除将帅冲突的位置即可。可见，剩下的问题就在于如何使用一个变量来做二重循环的遍历。书中解法一给出的方法是将一个Byte变量拆成两个用，前一半代表“帅”可以走的位置，后一个变量代表“将”可以走的位置（事先已经将“将”和“帅”可以走的3*3的位置进行了编号），利用位操作即可获得两个计数器的功能。书中的解法三采用结构体来解决一个变量遍历二重循环的问题，思想上换汤不换药。真正有趣的是解法二，它的代码如下：

int var = 81;
while( var-- )
{
if( var / 9 % 3 == var % 9 % 3 )//发生冲突
continue;
else
printf(/** 打印可行的位置 **/);
}

当看到这个解法的时候，我心里有一些感慨。短短几行，体现了简约之美，虽然可能有牛人说这没什么了不起，但我觉得如果在面试这个问题的时候能写下这样的代码，我会很有成就感。在大多数时候我们无需知道希尔排序的时间复杂度的一点几次方是怎么算出来的，也无需去证明一个最优化问题是否满足“拟阵”的条件，我们只需要在这样一个“简单”的问题上做得漂亮，就够了。

回过头来分析这个解法。“将”和“帅”各在自己的3*3的格子间里面走动，我们共需要验证9*9=81种位置关系，这也是i=81的由来。此外我们要明白i/9和i%9的含义。我们知道，整数i可以由部两分组成，即var=(var/9)*9+var%9 ，其中var<n。我们注意到，在i从81到0变化的过程中，var%9的变化相当于内层循环，var/9的变话相对于内层循环。这样，作者就妙地用一个变量i同时获得了两个变量的数值。

简单即是美，相对于解法一的大段代码，我更希望我以后再面试中写出解法二。

其实这个问题还可以进行一些扩展，即如何利用一个变量达到三重循环的效果。也就是说，如果给定下面的循环：

int counter = 0;
for( int i = 0; i < 5; i++ )
for( int j = 0; j < 4; j++ )
for( int k = 0; k < 3; k++ )
{
System.out.println("counter="+counter+"\t, i="+i+", j="+j+", k="+k);
counter++;
}
其结果如下：
counter=0 , i=0, j=0, k=0
counter=1 , i=0, j=0, k=1
counter=2 , i=0, j=0, k=2
counter=3 , i=0, j=1, k=0
counter=4 , i=0, j=1, k=1
....中间略
counter=59 , i=4, j=3, k=2

问题是（1）我们如何用一个打印出相同的结果？（2）如果是N重循环呢？

面对第一个问题，实际上就是对原始的中国象棋将帅问题进行了一个扩展，即在棋盘上添加一个“王”，其行走规则和将帅一样。于是棋盘变成了三国争霸:-) ，将帅王可以走动的格子数分别为3、4、5，它们之间的互斥条件可以按需要设定。

这时，就需要只用一个变量遍历一个三重循环。直观的方法是像方法一那样把一个4字节的INT拆开来用。我这里只关注方法二。

只用一个变量解决扩展的中国象棋将帅问题，我们的代码应该是如下的样子：
int var = 3*4*5;
while( var-- )
{
if( /** 冲突条件 **/ )//发生冲突
continue;
else
printf(/** 打印可行的位置 **/);
}

在冲突条件中，我们需要知道var取得某个特定的值（即第var+1次循环）的时候的i，j，k分别是多少（这样我们才能判定将帅位置是否冲突）

从上例的结果中我们可以看到，counter的值（即当前的循环次数）和三元组（i，j，k）是一一对应的，越是外层的循环变化越慢，他们满足什么关系呢？

k的取值最好确定，我们都知道是var%3。
在原始的将帅问题中我们知道,j的值应该是 var/3，但是由于j上面还有一层循环，就需要做些调整，变成var/3%4
最外层循环i的值则为(var/(3*4))%5.

即：k=var%3 //其下没有循环了
j=var/3 //其下有几个循环长度为3的循环
i=var/(3*4). //其下有几个循环长度为3*4的循环

于是4重循环的公式我们也可以轻松得出：
for( int i = 0; i < 5; i++ )
for( int j = 0; j < 4; j++ )
for( int k = 0; k < 3; k++ )
for( int p = 0; p < 3; p++ )

p=var%2 //其下没有循环了
k=var/2 //其下有几个循环长度为2的循环
j=var/(2*3)) //其下有几个循环长度为2*3的循环
i=var/(2*3*4)//其下有几个循环长度2*3*4的循环

下面就是一个变量实现三重循环
int var = 2*3*4*5;
while( var-- > 0){
System.out.println("var="+var+" , i="+((var/(2*3*4))%5)+
", j ="+((var/(2*3))%4)+",
k="+((var/2)%3)+",
p="+var%2);
}

结果是：
var=119 , i=4, j=3, k=2, p=1
var=118 , i=4, j=3, k=2, p=0
var=117 , i=4, j=3, k=1, p=1
...中间略
var=5 , i=0, j=0, k=2, p=1
var=4 , i=0, j=0, k=2, p=0
var=3 , i=0, j=0, k=1, p=1
var=2 , i=0, j=0, k=1, p=0
var=1 , i=0, j=0, k=0, p=1
var=0 , i=0, j=0, k=0, p=0

N重循环原理也是一样，就不再赘述了。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我看的是《寻找发帖“水王”》，初看此文感觉眼前一亮，让接触计算机多年的我感觉到一阵清新。原来计算机算法可以这么简单，而又这么富有技巧，相信这本书可以在轻松解题之余，提高每位读者对算法分析和设计的能力；而更重要的，使读者学会从不同常人的角度对求解问题进行巧妙抽象的思维。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

嗯，不错，拓宽思路了
适合对算法初步了解的人

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

饮料那个，推导公式是不是写错了，
opt(V',i) = max{k*Hi + opt(V' - Vi * k, i-1)},应该是i+1吧，怎么是i-1呢

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

每看一个问题解法一，就迫不及待的看第二种解法！精彩！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

本人书评：
概读本书，认为本书所给的问题有点类似信息学竞赛里的，即贴近生活，强调解决问题的能力。本书的一大特点就是先从一般思路来分析问题，但是却碰到效率问题，接着运用算法思想如分治，递推思路来解决效率瓶颈，其中分析过程循循善诱，如在其中一个问题”寻找发帖水网”，首先作者给出了先排序，在统计的常规思路，但是却碰到时间复杂度太高问题，作者首先从统计问题入手，利用了水王ID肯定是ID列表中间项，从而使统计的O(N)转为O(1).接着解决排序问题，又分析问题，发现如果删除列表里的两个ID,水王ID数还是超过1/2.最后作者来给问题来个点睛，认为从复杂问题转化简单问题，其中问题本质没有变，即水王ID在ID表的数量超过1/2.
本书对问题进行了点睛分析，如果读者思考问题之后再来阅读分析定能受益匪浅，本人认为本书可以作为算法课的课外辅助教材.阅完本书若能理解，体会作者分析问题，解决问题的思路，相信算法能力将有长足进步.总之本书是一本帮助读者提高用计算机解决问题能力的好书.

Jason Hong

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

中国的义务教育，完全是填鸭式的教育，很多书籍也存在同样的问题，但是，《编程之美》就不存在这个问题，没有被强迫接受的感觉，阅读过程完全处在一种轻松愉悦的状态，这样的阅读恐怕更容易接受吧，呵呵……
期待早日看到这本书……


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	128.906ms