90后空巢老码农
分类: IT业界
2018-08-04 19:47:51
其实这本书买了好久了,第一章也看了好几遍了,每次看都没有觉得有什么,觉得不用记录在博客上面,但是每一次看的时候,都会有新的收获,自我臭屁一下,感觉就像古人说的“书读百遍其义自见”吧,最终决定还是先将这个这个简单总结一下。
当被推荐这本书,第一反应就是直接去查看作者,其中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) = 2n, 那么T(n) = 2n – 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个的取法,这个结果跟二项展开式貌似有莫大的关联~
嗯今天就先介绍到这里,其中第一章还有一个约瑟夫问题的递归方式,但是后面的章节中还有约瑟夫问题的另一种视角,我决定到时候一并记录下来,方便一点,就没再这里介绍了~~~