这一个系列的读书笔记本来是写在CSDN的博客上的,本来是不应该再费力气转移到这里来,但是总觉得对于好书应该给予更多的支持。更何况邹老师和其他作者把部分书稿费拿出来资助贫困小学,实在是应该大力提倡。所以决定把我的部分Blog内容搬迁到这里来,不能全拿过来只是因为评论不能贴图,呵呵。希望也能以此为契机敦促自己把原本计划中的读书笔记写完,也算完成自己的一个心愿。
大致翻看之后,总体感觉是书中的内容没有“脱离群众”,很多都是我们平时生活、工作中经常能遇到的。题目不见得难,基本上给一本《算法导论》和足够的时间,大多数人都能解决其中的问题。但注意副标题--“微软技术面试心得”,这就给这本书定下一个基调:面对这些我们并不陌生、也并非特别困难的问题,在有限的时间里,(可能)比较紧张的心情之下,如何充分发挥自己分析问题和解决问题的能力,如何正确且漂亮地解决问题才是关键。我想,在平时学习的时候或许我们左手《算法导论》,右手《编程之美》效果会更好一些。
中国象棋将帅问题由于比较简单,所以我们暂时不用请出《算法导论》。该问题的具体描述是:(根据中国象棋的基本原则)在只有双的将帅棋盘上,找出所有双方可以落子的位置(将帅不能碰面),但只能使用一个变量。直觉上我们想到,只要遍历将帅所有可能的位置,去除将帅冲突的位置即可。可见,剩下的问题就在于如何使用一个变量来做二重循环的遍历。书中解法一给出的方法是将一个Byte变量拆成两个用,前一半代表“帅”可以走的位置,后一个变量代表“将”可以走的位置(事先已经将“将”和“帅”可以走的3*3的位置进行了编号),利用位操作即可获得两个计数器的功能。书中的解法三采用结构体来解决一个变量遍历二重循环的问题,思想上换汤不换药。真正有趣的是解法二,它的代码如下:
int var = 81;
while( var-- )
{
if( var / 9 % 3 == var % 9 % 3 )//发生冲突
continue;
else
printf(/** 打印可行的位置 **/);
}
当看到这个解法的时候,我心里有一些感慨。在前几个月,我一直未MSRA面试没通过而恼火。但看到这个解法之后,我觉得我确实还要再努力一些才行。短短几行,体现了简约之美,仅看看这个就值回钱了(开玩笑)。虽然可能有牛人说这没什么了不起,但我觉得如果我在面试这个问题的时候能写下这样的代码,我会很有成就感。在大多数时候我们无需知道希尔排序的时间复杂度的一点几次方是怎么算出来的,也无需去证明一个最优化问题是否满足“拟阵”的条件,我们只需要在这样一个“简单”的问题上做得漂亮,就够了。
回过头来分析这个解法。“将”和“帅”各在自己的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重循环原理也是一样,就不再赘述了。
PS:看到最后一例的结果是不是与《算法导论》中平摊分析一章的二进制计数器很像?只不过这里进制不一样而已:-)
[勘误: P19 代码清单1-7的第七行,应该改为if(i.a%3 != i.b%3)]
谨以此文与大家共勉 2008/04/05
《编程之美》读书笔记(一):中国象棋将帅问题
对“《编程之美》读书笔记(一):中国象棋将帅问题”的回应
《编程之美》热门书评
-
迟来的书评和感想──给喜爱编程的朋友
181有用 3无用 Milo 2010-02-24
这本书我读了两遍,分別是两个印次。读第一遍是这书刚出版的时候买的第一版,读第二遍是因为最近认识了本书作者及编辑,我说以前看到本书的一些小错处,出版社就寄了第7次印刷本给我。在新年前花了一个星期把书尽量仔细地看了一遍,发现这印次仍有一些小问题及程序的bugs,已连同其他意见回馈给作者。 我其实不太喜欢...
-
我所了解的微软面试
81有用 0无用 蓬山远 2012-11-11
2014 05 22本文是一年半以前写的了。这一年半之间微软发生了很大的变化,我自己也发生了很大的变化,时过境迁,世殊事异。大家就看个乐子好了,不宜再当作经验去套用了。------------------------------------------------------------------...
-
数据结构和算法是程序的根本——为什么?!
49有用 0无用 bluedavy 2009-07-10
转自博客。应该是差不多两个月前收到了这本书,一直到最近才抽出时间来看了下,这本书的开篇的第一题现在基本已经成了经典中的经典了,相信很多人都因为这个控制CPU使用率的题从而买了这本书的,在我自己看过这本书后我同时相信买了这本书的人应该会觉得非常的值得,要写出合理实现需求、高性能以及大数据量的程序,数据...
-
一本未看完的书 一段未走完的旅途
21有用 3无用 Dear Al 2010-03-29
答应了Lisa写这篇书评 买这本书是大四的时候了 大学接近尾声 作为一名计算机软件方向的本科毕业生 我们学校竟未开过一门类似于算法导论之类的课程 哦 对了 是有一门类似的数据结构 它和Linux是我大学阶段最喜欢的专业课了 不过那些内容 唉 那时候很喜欢在CSDN上瞎晃 于是便迷恋上了高纳德 接受了...
-
享受用程序语言思维的乐趣
20有用 0无用 gaomiao 2009-07-17
闲暇时喜欢翻书,但也许是习惯了屏幕前飞快的阅读速度,如今看书已不像原先啃书那般细致。阅读时往往对引出道理的故事很感兴趣,而到了讲道理的细节,便一扫而过。然而最近在读的《编程之美》一书,却是无论如何也无法像读其他书籍那样浮光掠影般翻看,而是字斟句酌,生怕遗漏了半点细节。如果说在看《算法导论》这样的经典...