一
直想找本书来把自己的数学补一补，没有办法，既然选择了research，也就选择了一直要与数学为伴。在amazon上发现了这本"Concrete
Mathematics"。光是看这本书作者，就绝对值得一读。读了前言，原来这本书是The Art of Computer
Programming中数学基础部分的扩充版本，它对algorithm analysis and
design一定会有很大的帮助。一时兴起，看了看第一章，讲的是recurrent problem，第一个例子就是经典的the tower of
Hanoi，讲的很细致，重点在于如何利用recurrent来解决实际问题。既然读了一些，索性做个小小的总结：
通常一个recurrent problem都会经历四个阶段：
- Start from small extreme cases。通过分析观察small cases，可以发现general pattern。
- Generalize the problem。因为这样可以很有效的控制问题的规模以及更好的描述问题。
- Find Recurrent Mathematical Expression of the solution，并且证明其正确性，但这不是终点，因为result Tn依赖于Tn-1，当n很大时，想要获得答案将会引入大量的计算。
- Find Close formed Mathematical Expression of the solution。并且利用mathematical induction证明其正确性。close formed意为result Tn不依赖于Tn-1，通过最基本的运算即可获得答案。运算量大大的降低了。
Recent Comments