Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1024952
  • 博文数量: 136
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1800
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(136)

文章存档

2020年(34)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: 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个的取法,这个结果跟二项展开式貌似有莫大的关联~

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

阅读(1293) | 评论(0) | 转发(0) |
0

上一篇:栈实现队列

下一篇:stl中空间配置器简介

给主人留下些什么吧!~~