朴秀峰xfpiao@.ppt.ppt

朴秀峰
xfpiao@
递归
问题求解与程序设计
递归算法一般用于解决三类问题
函数的定义是递归的
问题的解法是递归的
数据的结构形式按递归定义
视觉的递归效应
4
递归的意义
自己调用自己
从前有个庙,庙里有个老和尚,老和尚给小和尚讲故事,讲的故事是:
庄生梦蝶
庄子梦中化为蝴蝶, 梦醒之后,蝴蝶复化为庄周。庄子问道,到底是蝴蝶化为庄周, 还是庄周化为蝴蝶.
“从前有个庙,庙里有个老和尚,老和尚给小和尚讲故事,讲的故事是: ”
程序举例
菲波那契数列
二叉树
逆波兰表达式
放苹果
红与黑
八皇后问题
木棍问题
菲波那契数列
问题描述
菲波那契(i) 数列是指这样的数列:数列的第一个和第二个数都为 1,接下来每个数都等于前面 2 个数之和。给出一个正整数 a,要求菲波那契数列中第 a 个数是多少。
输入样例
输出样例
4
5
2
19
1
5
1
4181
1
设第 n 项值为 f (n),则 f(n) = f(n-1)+f(n-2),已知 f (1)=1,f (2)=1,
则从第3项开始,可以用公式求。
菲波那契数列
int f(int a)
{ if( a == 1 || a == 2 ) return 1;
return f(a - 1) + f(a - 2);
}
int main()
{ int n;
scanf("%d", &n);
for(int i = 1; i <= n ; i++){
int a;
scanf("%d", &a);
printf("%d\n", f(a));
}
}
思考题
楼梯有 n 个台阶,上楼可以一步上 1 阶,也可以一步上 2 阶。一共有多少种上楼的方法?
定义:小步为上 1 级台阶,中步为上 2 级台阶,大步为上 3 级台阶。
楼梯有 n 个台阶,某人上楼可任意使用小步、中步和大步,共有多少种上楼的方法?
楼梯有 n 个台阶,某人上楼可任意使用小步和中步,但不能连续迈中步,共有多少种上楼的方法?
楼梯有 n 个台阶,某人上楼可任意使用小步和中步,但不能连续迈小步,共有多少种上楼的方法?
有 2 行 n 列的长方形方格,要求用 n 个 1*2 的骨牌铺满。有多少种铺法?
二叉树
问题描述
如图所示,由正整数1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点(编号是1 的结点)都有一条唯一的路径,比如从10 到根结点的路径是(10, 5, 2, 1),从4 到根结点的路径是(4, 2, 1),从根结点1 到根结点的路径上只包含一个结点1,因此路径就是(1)。
二叉树
问题描述
对于两个结点 x 和 y,假设它们到根结点的路径分别是(x1, x2, ... ,1) 和(y1, y2, ... ,1)(这里显然有 x = x1,y = y1),那么必然存在两个正整数 i 和 j,使得从 xi 和 yj 开始,有 xi = yj ,xi +1 = yj + 1,xi + 2 = yj + 2,...
现在的问题就是,给定 x 和 y,如何求 xi(也就是yj)。