编程试题-递归练习2.doc

递归第一次

题目描述Description

同学们在做题时常遇到这种函数

f(x)=5(x=0)

f(x)=f(x+1)+f(x+2)+1(x0)

下面就以这个函数为题做一个递归程序吧

输入描述InputDescription

一个数表示f(x)中x值

大家注意就一个数，前面代表样例编号

输出描述OutputDescription

一个数表示值

大家注意就一个数，前面代表样例编号

样例输入SampleInput

样例一：0

样例二：-5

样例输出SampleOutput

样例一：5

样例二：77

数据范围及提示DataSizeHint

x=-30

汉诺塔游戏

题目描述Description

汉诺塔问题（又称为河内塔问题），是一个大家熟知的问题。在A，B，C三根柱子上，有n个不同大小的圆盘（假设半径分别为1-n吧），一开始他们都叠在我A上（如图所示），你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。

游戏中的每一步规则如下：

1.每一步只允许移动一个盘子（从一根柱子最上方到另一个柱子的最上方）

2.移动的过程中，你必须保证大的盘子不能在小的盘子上方（小的可以放在大的上面，最大盘子下面不能有任何其他大小的盘子）

?

如对于n=3的情况，一个合法的移动序列式：

1fromAtoC

2fromAtoB

1fromCtoB

3fromAtoC

1fromBtoA

2fromBtoC

1fromAtoC

?

给出一个数n，求出最少步数的移动序列

输入描述InputDescription

一个整数n

输出描述OutputDescription

第一行一个整数k，代表是最少的移动步数。

接下来k行，每行一句话，NfromXtoY，表示把N号盘从X柱移动到Y柱。X,Y属于{A,B,C}

样例输入SampleInput

3

样例输出SampleOutput

7

1fromAtoC

2fromAtoB

1fromCtoB

3fromAtoC

1fromBtoA

2fromBtoC

1fromAtoC

数据范围及提示DataSizeHint

n=10

递归函数

题目描述Description

对于一个递归函数w(a,b,c)。

如果a=0orb=0orc=0就返回值1。

如果a20orb20orc20就返回W(20,20,20)。

如果ab并且bc就返回w(a,b,c?1)+w(a,b?1,c?1)?w(a,b?1,c)，

其它别的情况就返回w(a?1,b,c)+w(a?1,b?1,c)+w(a?1,b,c?1)?w(a?1,b-1,c-1)

这是个简单的递归函数，但实现起来可能会有些问题。

输入描述InputDescription

会有若干行.每行三个数，表示a,b,c。并以?1,?1,?1结束

输出描述OutputDescription

输出若干行，注意各种中的空格。

样例输入SampleInput

111

222

-1-1-1

样例输出SampleOutput

w(1,1,1)=2

w(2,2,2)=4

数据范围及提示DataSizeHint

a,b,c30,Task11

二叉树的序遍历

题目描述Description

求一棵二叉树的前序遍历，中序遍历和后序遍历

输入描述InputDescription

第一行一个整数n，表示这棵树的节点个数。

接下来n行每行2个整数L和R。第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子编号。

输出描述OutputDescription

输出一共三行，分别为前序遍历，中序遍历和后序遍历。编号之间用空格隔开。

样例输入SampleInput

5

23

45

00

00

00

样例输出SampleOutput

12453

42513

45231

数据范围及提示DataSizeHint

n=16