《具体数学》第一章笔记

今天开始读《Concrete Mathematics》这本书，前言很有趣，值得一看。

正文只读了第一章，不清楚这本书是否真的有豆瓣上别人评论的那么玄乎、那么高深，不过读了前言和第一章之后，起码我觉得这是本非常有趣的数学书，至于牛不牛X，下回分解。

总的来说，第一章理解起来不算难，不过JOSEPHUS问题的小节看到后面的部分就不太明白了，课后的练习也不是太明白，嘛。。暂且放一放，先继续阅读下去再说吧。

第一章三个小节，分别介绍了三个例子：HANOI TOWER、 LINES IN THE PLANE、THE JOSEPHUS PROBLEM。

都是一些递归问题，计算它们求解所需的计算次数，感觉就是披上了马甲的算法分析。

不过有了具体的例子，很好懂，不是平时直接丢给你一个渐近阶就完了。。。

HANOI TOWER

这个例子中讲了一些从问题到解答，再从解答到证明（模式，pattern）的思想探索过程。

通常规律是：

1. 从等小规模输入开始，观察问题的解，从中推测出问题的答案所遵循的模式。
2. 从等大规模输入开始，观察问题的解，这里有两个作用：1）如果步骤1推测出某个模式，就用大规模参数验证它。2）如果步骤1没有推测出某个模式，就反其道而行之，从大规模输入着手，看能不能推出模式，可参考《how to solve it》中的《working backwards》小节。）。
3. 根据以上的步骤提供的线索，寻找并证明问题的一个更准确且紧确（closed form）的解。

另外，《algorithms in c》的5.2节，也讨论了HANOI TOWER问题，谈到了它和递归、分治、二进制这三个东西有令人相当惊讶的联系，给出了HANOI TOWER的一个有趣解法，可以延伸阅读下。

LINES IN THE PLANE

跟章节里其他两个例子来说，这个例子有点平淡无奇，没啥好说的了，唯一的作用是引出了等差数列。

唯二的作用是说明了什么是“closed form”——简单来说，就是可以直接拿一个N，计算出结果的简单数学公式。

THE JOSEPHUS PROBLEM

这是这个章节最有趣的部分了，JOSEPHUS PROBLEM在各类算法和数据结构书上看得多了，没想到还能用二进制移位简单地解决掉，酷，一个数学问题在计算机模型上的完美解决。

 

评论

1 楼 lhjoanna 2011-03-04  

博主，我也在看呢，刚看完第一张~是啊，约瑟夫问题写的太经典了！博主继续写笔记呀~