【有书共读】 《编程之美》第一章读书笔记

《编程之美》读书笔记

序

既然出自微软MSRA，这本书就不可避免的与微软面试相关。而与其说这是一本讲解编程面试思路技巧的书，不如简简单单将其视为一本故事书。只不过故事中的主角是破题思路，载体是计算机语言罢了。因此，这本书，其实是一本讲解的颇为有趣的故事书，基于，数学。

第一章

书中第一章都是基于各种生活中的游戏，并对其规则和胜负等情况进行讨论。为了保证文字和逻辑流畅性，本读书笔记将打乱书中的问题讨论顺序，将同一类问题放在一起讨论。

故事从编者作为面试官开始。开篇一题，如何将Windows任务管理器显示CPU占用率为50%，说难不难，说简单却也不简单。犹记得小时候打开任务管理器，惊奇的发现其中CPU占用率随时间画出来的曲线，随意一挥鼠标，CPU占用率立刻随之改变。如果愿意，快速移动鼠标几乎能使占用率达到100%。所以说如果我能让计算机以一个合适的频率自己挥动鼠标，那么一条50%的直线貌似也不是那么难。当然电脑自然是不能自己移动鼠标了，所以我们需要一个程序，让电脑知道以CPU一半的能力工作一段时间。因此，我们只要知道CPU整体的工作能力，再让CPU睡一半时间觉就好了。（具体的解决方法在书的第七页）显然，这种方法不能通过简单复制的方法对多有的电脑有效。我们可以用GetTickCount()来获取工作时间具体的时间，再令睡觉的时间等于工作时间就好了。当然更为精细的话我们可以通过Perfmon.exe来获取支持Windows运行的程序吃掉的资源，从而可以更好的调控CPU占用率。书第9-11页讲述动态控制CPU占用率曲线的方法，其实也就是获得每个循环的CPU占用率从而进行控制。基于此，CPU的显示图形控制就完全不是问题了。

而之后相关操作系统的问题就是1.10（书中第62页），如何使用双线程下载提高下载速度。这题思路相对简单，只需要保证任务完成的确认，两个线程协调，两个线程尽可能同时工作和数据排序就可以，代码如书中65页所示。相对来说这道题不如其他的题目有趣味性，主要作用是让我们了解一下下载这一日常常见操作背后的小故事。

出去1.1和1.10，第一章还有16个问题，其中1.2、1.14、1.15、1.16、1.17和1.18分别讲述了中国象棋将帅、连连看、数独、24点、俄罗斯方块和扫雷这六个游戏的基本规则、情况分类和解法。俄罗斯方块设计到了很少一部分最优解的设计理念。对于游戏部分，由于已经有了成熟的规则以及获胜条件，我们可以直接依据这些条件进行后续计算。1.3-1.13（除去1.10）则是通过生活中常见的问题或者日常游戏来寻找解决方法，并通过进一步细化来简化计算的步骤和运算量。对于日常生活中提出的小问题或者游戏来说，则需要我们先去仔细思考这些问题的出发点和发展方向，从而提出可能的方法来进行求解。

1.2中主要讨论了中国象棋中的将帅不能见面问题，即将帅在中间没有其他子的情况下不能拥有相同的横坐标。问题为了简化去掉了其他旗子的判断（即使加上也就是一个判断，并不复杂），仅通过“将帅”各自拥有的9个坐标的进行分类讨论。为了增加难度，要求读者仅用一个变量来完成判断。作者将一个8位byte类型拆开，前面四位储存“将”的位置坐标，而后面四位储存“帅”的位置坐标。通过对前后4bit之间的关系进行是否见面的判断。接着作者提出了简化的方法，可以在第18页自行读取。简化的思路很简单，“将帅”各自的9个坐标进行组合可以有81种不同的实现方式。直接使用1-81代表这81种实现方法就可以很简单的找到27种forbidden的情况。

1.14中讨论了连连看这个小游戏的实现方法。由于题目要求相连的两个相同的块之间线段最短且小于3个转弯，我们可以直接从转弯数入手。第一步必然是分开空格子和实心格子。对于实心格子来说取任意一个格子，向四面射出水平和垂直的直线，要求直线通过的格子仅为空格子（直线长度可以为0），并定义第一轮找到的直接可以连起来的实心格子为S0。可以看出S0是我们所取格子通过0个转弯达到的格子的集合。然后将达到S0过程中直线所有经过的空格子选取出来，对每一个空格子做向四面的水平和垂直的直线，这些直线通过空格子达到的实心格子为S1。那么S1中去掉S0的部分就是最开始格子通过一个转弯达到的格子，记为S1’=S1-S0。对找S1过程中的空格子再做相同的操作可以找到S2，那么S2’=S2-S1-S0即为通过开始格子两个转弯可以达到的格子。而大于两次转弯才能达到的部分就不在题目需要考虑的范围之内了。通过对每一个格子进行上述计算我们可以得出所有的可能解（即可以消去的部分），而如果这个解为空集就说明当前没有可行的消去步骤，需要从新打乱来使游戏可以继续进行下去。92页的第二个拓展问题很有意思，我个人认为是通过计算相对坐标或者最短记录的一致来确定这种循环过程。

1.15讨论了数独，数独的玩法规则如果不清楚的话可以看93页。这个游戏在这里并没有展开讲，只是说了创建一个合适的数独的方法。最简单的必然是一个一个向里面填，如果填写违反了规则则回到上一个修改。虽然慢确一定能填出复合要求的数独。另一种必要不充分方法则是通过将小的九宫格颠倒顺序填进四周的小九宫格（9！=362880种）。由于讲的东西不充分不做展开。

1.16讨论了24点，规则如100页所示。解24点很粗暴，直接穷举法7680种完成爆破，得到所有的情况。后续的简化主要通过储存中间变量，并通过下一次遇到此中间变量时直接调用来减少运算。Fork（A,B）将可能出现的重复的中间变量用了一个符号进行表示，等于是明确了大量重复出现的中间变量。

1.17讨论了俄罗斯方块，游戏最基本的规则在108页。其中模拟数据结构实用的0,1数组很有借鉴意义，即对应于高低电位也对应与黑白块。同时将不同的下降块用相同尺寸的数组来储存也为初学者提醒了不要太在意各种积木块的“异”，而要将其尽可能“同”起来。之后的可行区间比较简单，即不要有下降块高电位与本身高电位相重叠部分，也不要有下降块高电位到游戏区域外的情况发生。相比较来说最优解总是好玩的，何为最优与如何最优是问题的关键所在。如果看过俄罗斯方块高手比赛的话大家可以发现一个问题，这些高手倾向于把最边上一列留出来等待“长条”，从而通过一次消去四行来提高消除单位块的分值。但是这样是否是最优，如果整个体系中“长条”所占半分比极少怎么办？因此，作者提出了一个评分体系，通过消除、产生“洞”和剩余块的高度来进行评判。其实真正细分的话还和产生“洞”的相对位置、是否需要赶紧消除保证游戏继续进行等因素相关。而留着一列等“长条”这种做法是否为最优解也要进一步印证。就像AlphaGo提出的新的围棋布阵方式与古谱不完全相同一样。

1.18是扫雷的体系，书中只给出了图和游戏规则，并没有对游戏继续进行进一步讲解，毕竟二维体系会麻烦很多。书中提出了两个问题，其中第一个其实就是最优解，只要点击概率小的格子就好啦!我认为仅能求解出已知区域周围一圈格子的含雷概率，外面的格子的概率只能是剩余雷的平均概率。

基于这些游戏我们可以学习到如何用计算机语言去表述具体的游戏规则。而鉴于书上讨论的游戏规则大部分是静态条件下的，因此穷举法是一个最简单的拿到所有情况的方法。然而穷举法相对来说在时间和空间占用上比较大，因此书中有提到利用二分法、上下界限和剪枝等方法来减少计算时间和计算量。

1.3-1.13（除去1.10）则为我们提供了更多好玩的游戏。1.3是翻饼，1.4是买书，1.5是找机器，1.6是饮料，1.7是光影，1.8是电梯，1.9是见面会，1.11-1.13是拿石头。这些游戏不仅要求我们提出规则，还要我们在规则允许条件下其寻找胜利方法和胜利的最优解法。这就要求我们进一步学习更为深入的思路来提高运算效率。这一块没必要具体讨论每一个题目的详细解法，将其中思路提出来供读者参考。

因为这些游戏不再是一个静态的场景，而是要动起来去完成整个过程。因此思考中要跟着游戏运作起来，首先想一个简单的情况，在简单情况下整个游戏的运行如何，稍微复杂一点的情况又如何。不要小看简单情况下所得解的作用，这个解不仅为我们打开这道题提供了突破口，还为我们程序中剪枝提供了合理的边界。然后随着游戏的运作去寻找合适的方法来减少解决问题的复杂度。对于1.3提出了上下界，1.4、1.8和1.9提出了贪心原理和贪心原理的修正，1.5主要用了异或和，1.7用了数学归纳法，1.11-1.13用的是不规范的数学归纳法。主要思路是先确定有解，在通过问题的结构去进一步破解，可以采用必要不充分解。这里对1.8电梯问题（书上53页）重点讨论一下。这道题明显有解，我们可以认为第M-N层是其最优解，如果仅有一个解的话M=N。那么大体上可以想到所有人需要走的楼层数与停靠楼层的关系图应该是一个在M-N为底的类似二次函数的

折线图，这个折线图每一段的斜率取决于每一层的人数，相对人数越多越陡。而后面的思考题中上下楼体力不同则相当于添加了一个权重，使折线图上升下降部分的斜率改变而已。