第一期：zellux，jpz6311whu，Humphrey
第二期：NullDream，conan_holmes，jason_00
第三期：卷积内核，蝶影，tomcatwilson
第四期：xjs1231，DMman，冬天的农夫

=========================================================
               本 次 活 动 介 绍
=========================================================

参与办法  

下载本站独家样章 --->  阅读样章 --->  回复本贴，提交 书评 --->  每周抽奖

第一期 （内含：求二进制数中1的个数，计算字符串的相似度，求二叉树中节点的最大距离，金刚坐飞机问题） ：
点击下载

第二期 （内含：中国象棋将帅问题，饮料供货，不要被阶乘吓倒，寻找发帖“水王”）：

第三期：（内含：连连看游戏设计，1的数目，寻找最大的K个数，精确表达浮点数）

第四期：（内含：子数组的最大乘积，计算字符串的相似度，瓷砖覆盖地板，编程判断两个链表是否相交）

活动时间    
2008年4月11日——2008年5月9日

活动规则
1）本站每周提供书中的4节样章（电子工业出版社授权本站提供的独家样章），供大家阅览，并撰写书评。
2）每位读者可以发表多条书评。
3）本站和博文视点将在每周抽取3名幸运获奖者。
4）书评字数不限，简短精悍、详细全面均可。
5）请直接在此回帖发表书评。

活动奖品
本次活动每周将产生3名获奖者，奖品是《编程之美——微软技术面试心得》图书一本。

感谢电子工业出版社博文视点赞助本次活动！
更多好书、新书信息，敬请关注博文视点官方博客：http://blog.csdn.net/bvbook

=========================================================
               本 书 详 情
=========================================================

IT企业面试真题
CSDN总编 孟岩、资深技术作家 潘爱民 推荐
微软全球副总裁 沈向阳 倾情作序
连续两周互动出版网（China-pub）计算机类销售冠军！

书名：《编程之美——微软技术面试心得》
作者：邹欣等
书号： 978-7-121-06074-8
出版社：电子工业出版社
出版日期：2008年3月
定价：40元
开本：16开
版次：1-1
页码：384页
本书详细信息：http://www.china-pub.com/38070

作者介绍

邹欣，现任微软亚洲研究院技术创新组研发主管。他从1996年起在微软Outlook 产品团队从事开发工作, 2003 年到2005 年，在微软Visual Studio Team System产品团队负责软件质量管理工具的开发。加入微软前，邹欣从事过商用Unix 系统、GPS/GIS 软件开发以及软件测试工作。2007年出版了《移山之道—— VSTS软件开发指南》一书。他1991 年获北京大学计算机软件专业学士学位。1996 年获美国Wayne State University (韦恩州立大学) 计算机软件专业硕士学位

推荐

◆ 微软公司全球资深副总裁沈向洋 推荐序
http://www.amazon.cn/mn/detailApp?prodid=bkbk821857

◆ 这是一本让人着迷的书！ 孟岩评《编程之美——微软技术面试心得》
http://www.china-pub.com/member/bookbar/bookreview.asp?theid=291

◆ 潘爱民倾力推荐《编程之美——微软技术面试心得》
http://blog.csdn.net/panaimin/archive/2008/02/12/2089151.aspx

◆ CSDN读者薛笛:
《编程之美》读书笔记(一)：中国象棋将帅问题
http://blog.csdn.net/bvbook/archive/2008/04/09/2269918.aspx
《编程之美》读书笔记(二): 一摞烙饼的排序问题
http://blog.csdn.net/bvbook/archive/2008/04/10/2277818.aspx

◆ 新浪作者《编程之美》和《无以言退》
http://blog.csdn.net/bvbook/archive/2008/04/04/2248838.aspx

读者评价

● “买了这本书,已经看了三个例题,打算每个晚上看一个实例
平时看<算法导论>总感觉是那么的苦涩,那么的深奥.有些还看了真是难懂.
不过这本书表面上是讲解算法,但更体现一种面对困难,解决问题的心态.
个人还是挺喜欢这类的书,把编程人性化了。”    ——  china-pub读者 拓荒者

● “初看本书书名，一阵恶心，扯到微软面试心得上面可能是出于出版社对销售上面的考虑，个人认为光看这么一本书，并不能帮助你进入微软，要想进入微软，需要的是你的独立思考能力，而这本书更大的作用是在于此，给你一个有趣的题，让你自己去思考，思考出来后再对照他给出的解法答案对比你是否作对，而在这个过程中，你学会了作为一个程序员最重要的东西，独立思考的能力。而不是到网上到处找代码片段，解决方案，Copy/Paste。书已经买了，但是还没有到，我打算到了以后好好的阅读一下本书，看看是否值得这个价钱。”    ——  china-pub读者 CoolJie2001　

● “相当启发人的书。之前从没有想过枯燥的算法可以这么好玩。展开的讨论十分深入细致。值得认真看每一个问题：）当然也有一些缺点，比如尽管有了勘误，但还是有许多细小的错误。比如前后文不一致（貌似不是一个人写的），代码变量使用错误之类的。但如果认真研究了，就能很轻易的找到~。
有些问题避开了一些关键的难点，比如那个n条直线可以将平面空间划分为多少块区域的题，完全避开了如何表示直线和如何计算之间交点的过程。
余下的等看完再写：）”    ——  china-pub读者 speedfirst　

● “虽然没有看完此书，但忍不住说两句。
首先，这本书无疑是严谨的，可以想见付出了巨大的努力。
其次，截至目前看到的内容都很有启发性，令人难忘。
如果一定要挑出一些问题，主要存在这样一些不足
（1）问题描述部分有些弱，应该把问题解释清楚，有些问题的描述并不那么清楚，可以举一些简单的例子来表述，让读者首先了解问题。
（2）展开的部分很好，无懈可击，堪称完美，但有些地方可以增加一些参考文献的引用，帮助更好的理解，另外可以多一些图形化的方法来解释复杂的问题，否则有些地方看起来比较吃力。
（3）代码的部分也很精彩，有些细微的格式有些问题，代码风格很统一，代码刻录成光盘可能更好，这样会占一些书籍篇幅，而且排版的难度会很大。综上，此书堪称IT行业图书的上上之美，不虚此名。”    ——  china-pub读者 cathymm　

● “在微软拿到了一本有各位作者签名的程序之美,感觉还不错,虽然不少问题都是经典的题型了,不过能汇总起来很不简单了,而且从行文的方式上来看适合轻松消遣的书,建议买来看看。    ”    ——  china-pub读者 coolzzz　

● “看完此书才发现自己在编程领域还很嫩啊,编程,我才刚上路呢.”    ——  china-pub读者 lzp22　

● (期待您的评价)

状元、榜眼、探花、进士 每週將公佈！

請各位學生，密切關注！

期待这本书的早日出版。

不过这本书的的定位我还不太清楚（也许是我读得太快太少的原因 ^_^），是想通过它唤醒编程人员对算法的重视呢？还是想展示一下编程的魅力？还是想带一般的编程人员进入更高的境界？还是想。。。

如果是象前面的朋友说的，是想以一种诙谐幽默而不失严谨的方式带读者去游览一番算法的领域，那么我个人觉得还不够浅显哦。象我学设计模式，就读了一本我觉得很不错的书。《Head.First设计模式》，这个作者讲解得很浅显，易懂。至少把不少人说得死难的问题，让一般的读者都可以读懂。而我读算法这个第一章，好像没读懂，大脑还是有点混乱。也许是我接触得少的愿意。

最后还是要感谢一下作者，出了一本不错的书给我们品味。也许它就如那苦丁茶，要慢慢品味，才可以品出它的味儿来。

总之，读这本书的时候，不会感到枯燥，会感觉是在和一个经验丰富的编程老手讨论某些有趣的问题。

问题很简单，求二进制中1的个数。对于一个字节（8bit）的变量，求其二进制表示中"1"的个数，要求算法的执行效率尽可能的高。

先来看看样章上给出的几个算法：

解法一，每次除二，看是否为奇数，是的话就累计加一，最后这个结果就是二进制表示中1的个数。

解法二，同样用到一个循环，只是里面的操作用位移操作简化了。

   1:  int Count(int v)   
   2:  {   
   3:      int num = 0;
   4:      while (v) {   
   5:          num += v & 0x01;   
   6:          v >>= 1;   
   7:      }   
   8:      return num;   
   9:  }

解法三，用到一个巧妙的与操作，v & (v -1 )每次能消去二进制表示中最后一位1，利用这个技巧可以减少一定的循环次数。

解法四，查表法，因为只有数据8bit，直接建一张表，包含各个数中1的个数，然后查表就行。复杂度O(1)。

   1:  int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };   
   2:      
   3:  int Count(int v) {   
   4:      return countTable[v];   
   5:  }
   
好了，这就是样章上给出的四种方案，下面谈谈我的看法。

首先是对算法的衡量上，复杂度真的是唯一的标准吗？尤其对于这种数据规模给定，而且很小的情况下，复杂度其实是个比较次要的因素。

查表法的复杂度为O(1)，我用解法一，循环八次固定，复杂度也是O(1)。至于数据规模变大，变成32位整型，那查表法自然也不合适了。

其次，我觉得既然是这样一个很小的操作，衡量的尺度也必然要小，CPU时钟周期可以作为一个参考。

解法一里有若干次整数加法，若干次整数除法（一般的编译器都能把它优化成位移），还有几个循环分支判断，几个奇偶性判断（这个比较耗时间，根据CSAPP上的数据，一般一个branch penalty得耗掉14个左右的cycle），加起来大概几十个cycle吧。

再看解法四，查表法看似一次地址计算就能解决，但实际上这里用到一个访存操作，而且第一次访存的时候很有可能那个数组不在cache里，这样一个cache miss导致的后果可能就是耗去几十甚至上百个cycle（因为要访问内存）。所以对于这种“小操作”，这个算法的性能其实是很差的。

这里我再推荐几个解决这个问题的算法，以32位无符号整型为例。

   1:  int Count(unsigned x) {   
   2:     x = x - ((x >> 1) & 0x55555555);    
   3:     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);    
   4:     x = (x + (x >> 4)) & 0x0F0F0F0F;    
   5:     x = x + (x >> 8);    
   6:     x = x + (x >> 16);    
   7:     return x & 0x0000003F;    
   8:  }
   
这里用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。

还有一个更巧妙的HAKMEM算法

   1:  int Count(unsigned x) {
   2:     unsigned n;    
   3:      
   4:     n = (x >> 1) & 033333333333;    
   5:     x = x - n;   
   6:     n = (n >> 1) & 033333333333;   
   7:     x = x - n;    
   8:     x = (x + (x >> 3)) & 030707070707;   
   9:     x = modu(x, 63);  
   10:     return x;   
   11:  }
   
首先是将二进制各位三个一组，求出每组中1的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。

因为2^6 = 64，也就是说 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)，这里的等号表示同余。

这个程序只需要十条左右指令，而且不访存，速度很快。

由此可见，衡量一个算法实际效果不单要看复杂度，还要结合其他情况具体分析。

关于后面的两道扩展问题，问题一是问32位整型如何处理，这个上面已经讲了。

问题二是给定两个整数A和B，问A和B有多少位是不同的。

这个问题其实就是数1问题多了一个步骤，只要先算出A和B的异或结果，然后求这个值中1的个数就行了。

总体看来这本书还是很不错的，比较喜欢里面针对一个问题提出不同算法并不断改进的风格。这里提出一点个人的理解，望大家指正 ;-)

(by ZelluX   http://www.blogjava.net/zellux)

很好很强大，不过更像是读书笔记而不是书评。

很多人都说编程的人怀揣着一个改变世界的梦想，无数的年轻人投身其中，用梦想和思考改变世界。微软亚洲研究院的八名程序员和实习生集体创作出了一本“编程之美”，用文字和符号与同道人沟通共同的编程梦想，并把它献给微软亚洲研究院成立十周年。下面，让我们来听听其中一名实习生作者所理解的编程之美。

    我应该算是最早知道将要编写《编程之美－微软面试指南》这本书的少数几个人之一，那时邹欣老师正在对《移山之道》进行最后的润色，而我还在学校里上研究生课程，生平第一次接受正统的计算机专业教育。当邹老师问我要不要参与编写时，做为一名自诩的“文学青年”而不是“计算机高手”，我毫不犹豫地答应了。

         我本科读的是航空学院，在大二时闲得无聊抱着玩的心态才开始真正自学编程的，然后凭着热情和兴趣就一头扎了进来。但是，我心里一直有种隐隐的痛，我可以熟练使用ASP.NET、AJAX很快地做出一个网站来，却对一些基本的数据结构、算法一知半解。唯一一次认真去读《数据结构》那本书还是保研考试前一夜临时抱佛脚，通宵看了排序、树、图之类常考的重点。虽然最后考出来成绩不错，但自己斤两多少，自己最清楚。所以实际上我对许多公司偏重算法的面试一直以来都抱有一种畏惧感和神秘感，而且非常仰慕那些受过ACM、ICPC训练过的同学，尤其是那些能很快分析出问题复杂度的人。
         但是毕竟我不是科班出身，而且只在学校里面做过一些简单的网站项目，这让我在很长一段时间里都抱有一种误解，即认为工程能力和算法解题能力是不相干的两回事，佐证就在于有些人可以很轻松地解出一些算法题却无法用C#写一个真正可用的软件；而像我一样的人可以轻车熟路写出一个“看上去很美”的CMS系统，但面对一些课本上的算法题时却手足无措。而且更要命的在于，简单的网站做多了，我逐渐认为做工程不需要所谓的算法，算法好只能让人拿到更高的课程分数或是竞赛奖项，而在计算机科学这一非常讲究实践的领域中，只有良好的工程能力才有办法真正把某个项目实现。于是在很长一段时间里，我对那些能通过解出很难的算法题拿到很好offer的人都比较嗤之以鼻，并对那些公司的招聘标准感到疑惑不解——明明是我的实践经验和能力上更强，凭什么不要我而是他们呢？

    我觉得自己最大的幸运在于，随后的一些经历让我很快走出了这个误区。在本科的最后一个学期，我幸运地获得了一个前往微软亚洲研究院实习的机会（面试时考了我一道智力题而不是算法题），在实习过程中，我才“真正”地做了一个软件项目，并且通过和其他实习生的交流，“耳濡目染”地看到了许多现实中的研究性软件的开发过程，这些经历带给了我许多前所未有的体验。在现实的软件开发中你会看到各种形式各异的需求，比如在一定数量的帖子中找出发帖最多的“水王”，在这之前我开发过的网站最多也不过几千条记录，所以即使我简单地重复遍历所有记录也能实现这一功能，但是当你面对的是十万甚至百万级别的现实数据时，问题就从最基本的“实现”变成了“更快更高效地实现”了！令我感到汗颜的是，我往往只能用效率最低的复杂度实现类似的功能，而面对如何更优雅更高效地实现它时，我常常感到力不从心。

    这些经历让我逐渐意识到，我所沾沾自喜的工程实践能力实际上只是一种“实现”的能力，而在解决现实世界的实际问题时，更需要的是一种“优美的实现”，因为只有在可接受的时间或空间约束条件下的实现才是真正能解决问题的答案。而如何找到所谓的“优美的实现”，一个人算法能力在这里就起到了决定性的作用。算法实际上是对现实问题的抽象，因为现实问题是复杂的，我们可以把它抽象成模型。寻找合适的数据结构表示问题模型，并通过分析，寻找到对应的解决算法，这种抽丝剥茧的思维方式将会使得开发者事半功倍。那句著名的“软件=算法＋数据结构”并非空穴来风，我也从这些经历中逐渐理解了微软等公司的招聘标准实际上没有错，因为他们需要找的是能真正通过分析解决实际问题的人。如果把工程实践能力比作一辆车的轮子，那只说明这辆车具有了移动的能力，而让这辆车能又快又稳的运行，则需要算法分析能力这台强劲的发动机驱动，这两种能力是相辅相成的。

    我觉得自己比较幸运的是，在我逐渐明白了这些道理后，参与编写了《编程之美》这本书。编书的过程也是我自己动手解里面一道道有趣题目的过程，期间我对一个个优美、巧妙的解法拍案叫绝，在遇到难题或想不通的时候，就通过与其他编者一起讨论解决，这些经历都让我不断体会到“解法之美”和“问题之美”。《编程之美》的许多题目实际上都来源于现实项目中所遇到的具体问题，它们或是实际问题的简化，或是改头换面以其他有趣的场景表示出来。但是万变不离其宗，通过把问题抽象化，并运用算法分析寻找解决方案将是解题的利器。这种思考方式也是我们希望通过本书传递给读者们的。祝大家能在阅读的过程中体会到“美”的无处不在。

我觉得编程的艺术在于品,一个人可以品茶,一个学生可以品题目,一个开发人员就能够品出一种境界.真正的大师属于这种.

一家之言

  下了四个例子：中国象棋将帅问题，饮料供货，不要被阶乘吓倒，寻找发帖“水王”;看了一节后马上对本书起了浓厚的兴趣。这节的内容先不说算法怎么好，就说这语句用的是通俗易懂，而且例子和现实生活挂勾，讲例子和讲故事似的很吸引人。在问题的分析上相当到位使人毛色钝开，一点也不枯燥反而让人觉得很有好，好有意思的样子。

  看了一节后我破不急待的又看了下一节的内容，这里我已经深深的把这节的内容所吸引。我开始不停的咬我的圆朱笔头了（我一看到好东西种有这一个坏习惯，从小养成的）。看到了问题以后我就开始沉思了许久，在脑中想出了许多的解决方案。在心里盘算着那个方案是最优的，作者会是怎么解说的呢！在沉思过后把心里想的内容作上的笔记接着往下看。下面的内容出乎我的意料，有很多书本提出问题后就是重案了并没有怎么去分析，而这本书里却是把每种解决方案都分析了一下。我着着差不多和我想的大多相似，不过又有出点不同反正是说不出的喜欢。

  接下来一口气把那两个例子看玩了，把他的讲法相当的喜欢，只是我的底子差了点看的是一知半解的算法是明白了只是他里面把很多问题都数学化了有点脑子不够用的感觉。可能是我看的太快没有用心去想也有可能是我的基础太差的原因吧！

  看玩了这几个例子后还是有点一游未尽的感觉于是又在网上找了一下他的目录看了目录内容有点少了，哈哈要是能多点就更好了。
  下面来说点与内容无关的东西吧！！
  本书的排版很宽松让人看起来很舒服，不像别的书密密麻麻的都是文字。价格也相当的合适。本书以很有趣味的语言表棕了很想编程思想，本书对于有一定编程功底的人看效果将更加显助，像对于我这样的一般水平人员看有的时候就有点晕呼哈哈脑子不够用的感觉。

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

    关于"中国象棋将帅问题"，该问题的具体描述是：（根据中国象棋的基本原则）在只有双的将帅棋盘上，找出所有双方可以落子的位置（将帅不能碰面），但只能使用一个变量。直觉上我们想到，只要遍历将帅所有可能的位置，去除将帅冲突的位置即可。可见，剩下的问题就在于如何使用一个变量来做二重循环的遍历。书中解法一给出的方法是将一个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重循环原理也是一样，就不再赘述了。

                                                                                                         Jason Hong

  下了四个例子：中国象棋将帅问题，饮料供货，不要被阶乘吓倒，寻找发帖“水王”;看了一节后马上对本书起了浓厚的兴趣。这节的内容先不说算法怎么好，就说这语句用的是通俗易懂，而且例子和现实生活挂勾，讲例子和讲故事似的很吸引人。在问题的分析上相当到位使人毛色钝开，一点也不枯燥反而让人觉得很有好，好有意思的样子。

  看了一节后我破不急待的又看了下一节的内容，这里我已经深深的把这节的内容所吸引。我开始不停的咬我的圆朱笔头了（我一看到好东西种有这一个坏习惯，从小养成的）。看到了问题以后我就开始沉思了许久，在脑中想出了许多的解决方案。在心里盘算着那个方案是最优的，作者会是怎么解说的呢！在沉思过后把心里想的内容作上的笔记接着往下看。下面的内容出乎我的意料，有很多书本提出问题后就是重案了并没有怎么去分析，而这本书里却是把每种解决方案都分析了一下。我着着差不多和我想的大多相似，不过又有出点不同反正是说不出的喜欢。

  接下来一口气把那两个例子看玩了，把他的讲法相当的喜欢，只是我的底子差了点看的是一知半解的算法是明白了只是他里面把很多问题都数学化了有点脑子不够用的感觉。可能是我看的太快没有用心去想也有可能是我的基础太差的原因吧！

  看玩了这几个例子后还是有点一游未尽的感觉于是又在网上找了一下他的目录看了目录内容有点少了，哈哈要是能多点就更好了。
  下面来说点与内容无关的东西吧！！
  本书的排版很宽松让人看起来很舒服，不像别的书密密麻麻的都是文字。价格也相当的合适。本书以很有趣味的语言表棕了很想编程思想，本书对于有一定编程功底的人看效果将更加显助，像对于我这样的一般水平人员看有的时候就有点晕呼哈哈脑子不够用的感觉。

说明一下，获奖名单是由出版社方面（即本次活动的赞助方）确定的。并非我个人想让谁拿就让谁拿的：-）

比较同意前面zellux的一种看法：衡量一个算法实际效果不单要看复杂度，还要结合其他情况具体分析。尤其是当我看到求二进制中1的个数解法四，查表法复杂度O(1)的时候简直要吐血。这难道是算法追求的终极之美？不敢苟同。其实CMU还有一门经典的课程简称ICS，Introduction to Computer System--in programmer's perspective,（zellux提供的一个位算法可以从ICS的Lab作业中找到影子）如果把这本书作为一顿美餐的原材料，那么Introduction to Algorithms就是将这些原材料做成美味大餐的配方，如果再加上《编程之美》中题目作为调味剂，一个六星级程序大厨就这么诞生了，管他MS还是Intel,IBM,Google都可以游刃有余的。

其实我一直都想找这么一本以实例为基础的算法书作为自己的调味剂，而偶遇编程之美恰恰给了我这个机会，不过对待书中的一些为了追求唯美算法而没有考虑系统的地方还是颇有微词的。比方说求10进制1的数目这个题目，一扎眼就发现google曾将它作为的一道面试题（孰先孰后这里不再论证）原题目如下：
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?
以下是一个目前发现的最高效的算法，虽然比很多算法看起来要长许多，但是它不止是得到199981,它把4000000000内的所有都遍历出来了。而且速度还只是几十毫秒，或者更快。书中的第一问的算法2，里面用到了switch，这个在系统编程里面是很忌讳的，因为他要查跳转表，这个东西是要访存两次的。访存的开销是很大的。目前针对JVM中的interpreter的很多优化就是想办法把解释器中的庞大的一个switch想办法替换成更为有效的方式，所以很多人提出了改变class文件的bytecode的编码方式，由基于栈的转成基于寄存器的。
本题目中用到的case数目不是很多所以感觉上差距不会很大，但是这里我只想说明，算法再怎么高级也要考虑到系统和体系结构方面的东西，否则就有可能是空中楼阁，海市蜃楼。
建议就是希望书再版的话，多加入一些系统方面的探讨。胡言乱语了一番，希望不要被bs....
   1. #include "stdafx.h"  
   2.   
   3. #include <windows.h>  
   4. #include <stdlib.h>  
   5.   
   6. int f(int n);  
   7. int count1(int n);  
   8. int cal(unsigned int number,int nwei,int count1,unsigned int ncount);  
   9.   
  10. int gTable[10];  
  11. const unsigned int gMAX = 4000000000L;  
  12.   
  13. int main(int argc, char* argv[])  
  14. {  
  15.   int i;  
  16.   unsigned int n=1;  
  17.   unsigned int ncount = 0;  
  18.   int nwei = 0;  
  19.   int ncount1;  
  20.   
  21.   /*if(argc>1)
  22.   {
  23.     n = atoi(argv[1]);
  24.     ncount = f(n);
  25.     printf("f(%d) = %d\n",n,ncount);
  26.   }*/  
  27.   
  28.   int beginTime=GetTickCount();  
  29.   //init gTable  
  30.   for(i=0;i<10;++i)  
  31.   {  
  32.     n *= 10;  
  33.     gTable[i] = f(n-1);  
  34.   }  
  35.   
  36.   n=0;  
  37.   nwei = 0;  
  38.   ncount1 = 0;  
  39.   while(n<gMAX)  
  40.   {  
  41.     unsigned int temp;  
  42.       
  43.     temp = 1;  
  44.      
  45.     ncount =cal(n,nwei,ncount1,ncount);  
  46.     for(i=0;i<nwei;++i)  
  47.       temp *= 10;  
  48.     n += temp;  
  49.     if( (n/temp)/10 == 1)  
  50.       ++nwei;  
  51.     ncount1 = count1(n);  
  52.   }  
  53.   
  54.   int endTime=GetTickCount();  
  55.   endTime-=beginTime;  
  56.   
  57.   printf("time: %d ms\n",endTime);  
  58. return 0;  
  59. }  
  60.   
  61. int f(int n)  
  62. {  
  63.   int ret = 0;  
  64.   int ntemp=n;  
  65.   int ntemp2=1;  
  66.   int i=1;  
  67.   while(ntemp)  
  68.   {  
  69.     ret += (((ntemp-1)/10)+1) * i;  
  70.     if( (ntemp%10) == 1 )  
  71.     {  
  72.       ret -= i;  
  73.       ret += ntemp2;  
  74.     }  
  75.     ntemp = ntemp/10;  
  76.     i*=10;  
  77.     ntemp2 = n%i+1;  
  78.   }  
  79.   return ret;  
  80. }  
  81.   
  82. int count1(int n)  
  83. {  
  84.   int count = 0;  
  85.   while(n)  
  86.   {  
  87.     if( (n%10) == 1)  
  88.       ++count;  
  89.     n /= 10;  
  90.   }  
  91.   return count;  
  92. }  
  93.   
  94. int cal(unsigned int number,int nwei,int count1,unsigned int ncount)  
  95. {  
  96.   int i,n=1;  
  97.   unsigned int maxcount;  
  98.   if(nwei==0)  
  99.   {  
100.     ncount += count1;  
101.     if(number == ncount)  
102.     {  
103.       printf("f(%d) = %d \n",number,number);  
104.     }  
105.     return ncount;  
106.   }  
107.   for(i=0;i<nwei;++i)  
108.     n *= 10;  
109.   maxcount = ncount + gTable[nwei-1];  
110.   maxcount += count1*n;  
111.   if(ncount > (number +  (n-1)) )  
112.   {  
113.    return maxcount;  
114.   }  
115.   if(maxcount < number)  
116.   {  
117.     return maxcount;  
118.   }  
119.   n /= 10;  
120.   for(i=0;i<10;++i)  
121.   {  
122.     if(i==1)  
123.        ncount = cal(number+i*n,nwei-1,count1+1,ncount);  
124.     else  
125.        ncount = cal(number+i*n,nwei-1,count1,ncount);  
126.   }  
127.     return ncount;  
128. }

看来我的置疑是无法被选中了

这个方法哪里有什么创意。。。

呵呵 貌似这又涉及到软件工程中的实现那阶段的问题了。
我又看了几章。觉得这书可以算是算法书中的科普类读物。
叫《算法之美》到是不错。
我没有全部看完，在我看到的几章中没有涉及到“如何写代码”的细节。
呵呵 算法书中的《苏菲的世界》。

书上写错了，应该是f(10^n - 1) = n * 10^(n - 1);
而不是f(10 ^ (n - 1)) = n * 10^(n - 1); // 注意和上面对比多了括号
使用数学归纳法容易证明。
证明：
当n = 1时有
f(9) = 1, 成立。
设f(10^n - 1) = n * 10^(n - 1)成立，
下面证明f(10^(n+1)-1) = (n+1)*10^n
因为：
f(10^(n+1)-1) = f(10^n - 1)*10 //第一部分，后面解释
                                  + 10^n // 第二部分， 后面解释
第一部分： 0...10^(n+1)-1序列中所有的数去掉最高位，即第n位（没有到n位补零）， 有10个0...(10^n) - 1序列。
第二部分： 这10个0...(10^n) - 1序列中还原最高位为1，需要补(10^n)个1。
于是
f(10^(n+1)-1) = f(10^n - 1)*10 + 10^n =( n*10^(n-1))*10 + 10^n = (n+1)*10^(n+1 - 1)
得证

打字很累

关键该书书名后面还有一个副标题－－－微软技术面试心得，其实该书就是结合实例讲解算法而已，编程过程中可能你并用不到，你写的这些算法在应聘Microsoft成功后也可能还是用不到，但是我认为关键的一点是考到了你的数学方面的能力，有可能书中解法一、解法二...一直到解法N让你看的感觉精妙绝伦，这些解法有可能依然不是最好的解法。还有一个就是考到了你的创新思维，如果在本书中列举的所有算法中你在Microsoft或者其他公司面试中又考到了，你给出一个创新的算法，但并不是已有算法中最好的，你也可能面试PASS。
还有一点就是“编程高手”都喜欢对大家都知道的问题给予新奇的解法，大家看到后自然就感觉到“高手就是高手”了。其实这些都是数学算法的游戏，本书也许就是让读者从游戏当中体验编程之美吧。

恩，这问题是很有意思，涉及到我们最普通的应用“网页搜索”。看后感觉是不是百度也是这么做的呢？有时搜索完毕前几页并不是最想要的，相反后面几页会找到更符合的答案。以前感觉还挺疑惑的，现在和这个联系起来倒是有几分道理了。

老大也有这个感觉？
呵呵

我觉得
他既然用的是多路 归并
很可能最先几趟是严格按照大小顺序排列（用个败者树什么的）
到后面就不是那么 严格

不过 如何不严格 但保证在忍受范围之内 就是要好好思考的事情了

说说第4期的 判断链表相交的问题：
之前有过类似的问题就是判断一个链表有没有环，那个很简单，设置2个不同的步进指针就可以了。看到这个判断相交的问题，我就说说我对第一个扩展问题的想法吧
   如果有环且相交的话，那这2个链表的形式就象一个带2跟挂带的手镯一样的了。中间是个死循环，所以判断链表结尾是行不通的，所以至少需要2个指针来作为退出条件的判断。所以我的思路是： 从A出发2个指针，一个步进一，设为A1，一个步进二,设为A2，从B出发2个指针，同样一个步进一，B1,一个步进二，B2。
   A的2个指针先出发，如果有A2为空了，则没有环。A2守在这儿,等B的指针。 如果A1 == A2, 有环，且相等的地方必为环上的某一个结点。把A2指向A1的下一个结点（这样确保B的指针能在第一时间内与A的指针碰头，如果相交的话）。同样，守在这边。
   B的2个指针出发，边走边判断和B2是否与A1和A2中的一个相等。如果相等则相交。同时要判断B1 是否等于 B2。如果相等则B上有环并且与A没有相交。B2为空，判断是否与A2相等，如相等则相交。不等则不相交。

c[1,1]即为所求

另外 To DMman:
关于无环求交点的问题，你那个方法稍稍有点复杂吧，我那个思路的复杂度我觉得应该是
O(Length(m) + length(n) + ...), 这个是加号不是乘号呢。
大概思路为:

M:            －－－－－－－－
                             |
                               －－－－－－－－－－－－
                             |
N:    －－－－－－－－－－－－
N步进到这： ^ , 即 |length(m) - length(n)|.
然后同时步进，直到2个指针相等^
其中没有任何嵌套的操作，所以就不会有乘法运算了。
欢迎继续讨论。：）

这本书讨论的算法很有启发意义，不过很多似乎都是在竞赛中讨论过的问题，不过很欣赏这种渐进式的解决问题的写法。