《具体数学》第一章读书笔记

其实这本书买了好久了，第一章也看了好几遍了，每次看都没有觉得有什么，觉得不用记录在博客上面，但是每一次看的时候，都会有新的收获，自我臭屁一下，感觉就像古人说的“书读百遍其义自见”吧，最终决定还是先将这个这个简单总结一下。

当被推荐这本书，第一反应就是直接去查看作者，其中Donald E. Knuth的照片好像在大学某门专业基础课上见过，当时就决定要剁手了~~~

废话少说，这本书第一章就介绍了三个递归问题，下面就一一陈述一下。

1. 汉诺塔问题

这个大家应该都有见过吧（如果没见过，下边的也不用看了，赶紧找本计算机相关的基础书籍看看吧。。。），说实话，我在当年在第一次看见这个问题的时候，真的是好几脸懵比的。。。因为当时还处在高中那种数学思维里面，一时间没转过来，纠结了好久才逐渐摸到门，但是这本书的解法让我感觉我特么又回到了高中，首先，它先抽象了整个问题的解为T(n), 求出其递推公式：
T(n) = 2T(n-1) + 1; 然后进而用高中数学的方法，设U(n) = T(n) + 1; 那么原式就转换为
U(n) = 2U(n-1)，非常完美了~，直接能找到U(n)的通项公式U(n) = 2ⁿ, 那么T(n) = 2ⁿ – 1。 太特么机智了，当时自己刚接触的时候，还是傻乎乎的去想怎么移动，哎，low到爆，直接转换成数学模型，然后求解出来，代码就自动跟着出来了~

2. 直线相交划分区域问题

第一章的第二个问题是“n条直线，最多能把一个完整平面划分为几个区域？”

解答也是很递归了，设原问题解为L(n)，当第n条直线到来之时，前面已经有了L(n-1)个区域，n-1条线，第n条直线想要尽可能多的划分区域，必须与原来的n-1条直线相交于不同的点，这就可以将原来的区域多分出n个来（参考锯木头），这样的话就得出地推公式为L(n) = L(n-1) + n; 进而推出通项公式为L(n) = n(n+1)/2 + 1; 之后，这道题目又在两个方向上进行了延伸

a) 线是折线，区域怎么划分在这里直接给出答案了P(n) = P(n-1) + m*(n-1) + 1; 其中P(n) 为所求结果，P(n-1)为前一次结果， m为两个形状最多交点个数， n为形状个数~

b) 第二个维度的扩展就是在维度上，这道题目的原题以及扩展a都是在二维的基础上，在课后习题中就从一维将其，扩展到2、3、4、5.。。。维了，也是直接给出答案吧

Res1(n) = C(n, 0) + C(n, 1);

Res2(n) = C(n, 0) + C(n, 1) + C(n, 2);

Res3(n) = C(n, 0) + C(n, 1) + C(n, 2) + C(n, 3);

…

Resm(n) = C(n, 0) + C(n, 1) + … + C(n, m);

上式中1,2,3，m分别代表维度，C(n, m)表示从n个数中取出m个的取法，这个结果跟二项展开式貌似有莫大的关联~

嗯今天就先介绍到这里，其中第一章还有一个约瑟夫问题的递归方式，但是后面的章节中还有约瑟夫问题的另一种视角，我决定到时候一并记录下来，方便一点，就没再这里介绍了~~~