《具体数学》--- 第一章 读书笔记
具体数学书上写的东西真的很实用,感觉收获不小!!~
第一章主要讲的是递归问题(Recurrent Problems):
递归问题当然就涉及到了递推式和通项公式的求法啦,这都是高中学的小知识,
没想到到了大学还是那么管用。
这章主要讲了三个问题:
1、The Tower of Hanoi (汉诺塔问题)
2、Lines In the Plane (直线分空间问题)
3、The Josephus Problem (约瑟夫环问题)
三个非常经典的问题,前两个在高中都学过数学解法,也是一个很简单的递推问
题,最后一个收获还是满大的!~
先说说前两个问题:
1、问题就不用叙述了,人人都知道这问题,解法呢?!
设 f[n]表示将 n 个盘子从 1 号柱子移到 3 号柱子的最少次数,这样的
话,有如下递推式:
f[n] = 2 * f[n-1] + 1; ( f[0] = 0 ; f[1]
= 1)
通项公式如下: f[n] = 2 ^ n - 1;
2、问题是这样的:问用 n 条直线最多能将平面分成多少个区域?
这也是一个很简单的递归问题: L[n] = L[n-1] +
n; (L[0] = 1)
通项公式如下:L[n] = n * (n + 1) / 2 +
1 ( n>= 0 )
如果不用直线的话,用一个一般的折线,那么 n 个这样的折线最多可以拆分平面:
D[n] = L[2*n] - 2 * n;
D[n] = 2 * n ^ 2 - n + 1;
如果用"Z"字型的线,n 个折线最可拆分平面:
http://acm.zju.edu.cn/show_problem.php?pid=1652
Z[n] = Z[n-1] + 9*n - 8;
Z[n] = (9*n^2 - 7*n + 2) / 2;
3、问题是这样的:把 N 个人围成一个圆圈,按顺时针进行编号,从 1 一直编到
N,然后从 1 开始,每隔一个人杀一个人(2,4,6.....),完成一圈后,继续按这
个规定杀人,问给定一个 N,最后存活的那个人一开始的编号是几?
http://acm.zju.edu.cn/show_problem.php?pid=2072