递归关系

1.算术序列 （等差序列）： 2 5 8 11 ？ 17 …… 答案是：14

特点：相邻两个数的差是固定的常数d！（注意：d可以是负数）

通项公式：若初始项为a1：则递推关系为 an=a1+(n-1)*d；

对应的各项为：a1，a1+d，a1+2d，....,a1+(n-1)*d;

求和公式：

公式1：平均数 * n 结果为 只需要知道：头，尾，n

公式2：代入公式1，可变形为 n*a1+n*(n-1)*d/2 只需要知道：头或尾、d、n

唉，都一样。

练习：自己设计题目训练 通项公式（5题）、求和公式（5题）

2.几何序列 （等比序列） 2 4 8 ？ 32 64 ….. 答案是：16

特点：相邻两个数的比是固定的常数q！（注意：q可以是负数，分数，什么都有可能）

通项公式：若初始项为a1：则递推关系为

对应的各项为：a1，a1*q，a1*q^2，....

求和公式：

公式: 只需要知道：头，q，n

练习：自己设计题目训练 通项公式（5题）、求和公式（5题）

3.Fibonacci序列 0 1 1 2 3 5 ? 13 21……答案是：11

特点：每一项是它前两项的和(最前面两项要给出来的，f0=，f1=1)

通项公式：

求和公式：前n项的和Sn= f(0)+f(1)+f(2)+…+f(n)= f(n+2)-1

:以下是Fibonacci的示例:

1.楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法?

2.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?

3.有n*2的一个长方形方格,用一个1*2的骨牌铺满方格。求铺法总数？

想进一步学习？请到：http://hi.baidu.com/yuanwenxue/blog/item/a0d1a934d3e65bbfd1a2d366.html

4.分平面的最大区域数(只是记公式是没用的)

1.直线分平面的最大区域数的序列为:

2，4，7，11，....

递推公式是: fn=f(n-1)+n=n(n+1)/2+1

2.折线分平面的最大区域数的序列为:

2, 7, 16,29, ...,

递推公式是:fn=(n-1)(2n-1)+2n;

3.封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为:

2, 4, 8, 14,...,

递推公式是:fn=f(n-1)+2(n-1)=n^2-n+2

练习

1平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？

C(7,2)*(5+6)+C(5,2)*(7+6)+C(6,2)*(7+5)+7*6*5=21*11+10*13+15*12+210=231+130+180+210=751

2平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？

21*10+21*15+10*15+21*30+10*42+15*35=1155+525+570=2250

3由3个a，1个b和2个c构成的所有字符串中，包含子串“abc”的共有（ D ）个。

A. 20 B. 8 C. 16 D. 12 E. 24

4由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（ D ）个。

A. 40320 B. 39600 C. 840 D. 780 E. 60

8*7!/2!/4!-4*C(5,2)-4*5=8*3*5*7-40-20=840-60=780

补充练习：

一、 问题求解

1）已知8个元素为（26、75、15、23、14、62、72、19），按照依次插入结点的方法生成一颗二叉排序树，则该树的深度为_____？
2）编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1、2、3、…、20、21、…，一圈又一圈。问：当数到数字N时，所在纸牌的编号为______？

3）“蜂巢问题”：有一只蜜蜂沿如下图所示的蜂巢爬行，蜂巢编号为1到n，上面的为奇数，下面的为偶数，它只能由小号爬入大号相邻的巢，如果它从1号开始向N号爬，共有多少种不同的走法？
4）“圆桌问题”之相邻不重复：有n个人坐在一张圆桌上吃饭，要求每天每一个人两边相邻的人不同，问这样最多可以安排多少天？如3个人时只能1天，4个人时也只能是1天，而5个人可以安排2天。
5）一个二叉树的前序遍历结果为ABCDE，中序遍历结果为BADCE，那么它的后序遍历结果是什么？

6）一个商场有m种颜色的小球，每种小球足够多，在这m种小球中挑选n个小球的选法有多少种？如 m=2，n=3 时有4种选法分别是：两种小球的个数分别为03，12，21，30．问：当m=4，n=4时,选法数=__________。
7）如果一棵m度树中有n1个度为1的结点，n2个度为2的结点，…….有nm个度为m的结点,则该树中叶结点的的个数=______________.

8）已知:1到10中有两个数1、7不能被2，3，5整除，那1到1000中有多少个数不能被2，3，5 整除？
9）有30个连续的自然数，在其中选三个数，这三个数的和能整除3，共有多少种选法？

10）下图中用点表示城市，点与点之间的联线表示城市间的道路：

试问：①能否找出一条从A城市出发，经过图中所有道路一次后又回到出发点的通路来？

②能否从A出发，找出去每个城市且只去一次的通路来？若能，则写出通路；否则说明理由。

11）为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀{运算符在前， 如X/Y写为/XY}和后缀{运算符在后，如X/Y写为XY/}的表达式。在这样的表示中可以不用括号即可确定求值的顺序，如：(P+Q)*(R-S) →*+PQ-RS或 → PQ+RS-*

①试将下面的表达式改写成前缀与后缀的表示形式：(a) A+B*C/D (b) A-C*D+B^E

②试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示： +△A*B△C {前缀式中△表示一元运算符取负号，如△A表示（-A）}

12）设A是一个n阶上三角阵，将这个上三角阵按列序存储一维数组b[n*(n+1)/2]中，如果a[I,j]存放在b[k]，那么请给出求解k的计算公式。设A是一个一维数组a[m*n]，现将这个数组按列序存储在一个m*n的矩阵B中，如果a[k]存放在b[I,J]，那么请给出求解I,J的计算公式。

13）用邻接矩阵表示下面的无向图：

答案：

1：4

2：1＋（N－1） mod 13
3：f(n)=f(n-1)+f(n-2) (n>2) f(1)=1 f(2)=1
4：(n-1)/2 (n为奇数时) n/2-1 （n为偶数时）
5：BDECA

6：35
7：n2+2n3+…+(m-1)nm+1

8：266
9：c(10,3)*3+c(10,1)*c(10,1)*c(10,1)=1360

10：①能

②不能，因为C与四个城市邻接，不可能一次遍历

11：注意：先依中缀或前缀表达式画出表达式树，再根据后序遍历方法写出后缀表达式

1）前缀：+A/*BCD，后缀：ABC*D/+；2）中缀：-A+B*(-C)；后缀：A△BC△*+

12：1）K=I+J(J-1)/2 2）K=I+(J-1)N

13： 1 2 3 4 5 6 7

1 0 1 0 0 0 0 0

2 1 0 1 1 0 0 0

3 0 ……