递归上机编程练习.doc

《递归上机编程练习.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上机编程练习1．输入N个字符，然后以倒序输出（用递归实现）。2．裴波那契数列0、1、1、2、3、5、8、13、21、34、55、……从第三项开始，每一项是前两项的和，其递归定义为：求此数列第n项。3．阿克曼函数（Ackerman）定义如下：人们之所以研究该函数，是因为它对于较小的m和n值增长很快。分别用递归算法写出计算阿克曼函数的程序。4．Hanoi（汉诺）塔问题有n个圆盘，依半径大小（半径都不相同），自下而上套在A柱上，每次只能移动最上面一个盘子到另外一个柱子上（除A柱外还有B柱和C柱，开始时这两个柱

2、子上无盘子），大盘子不能压在小盘子上面，现在要求：将A柱上盘子全部移到C柱上总共要移动几步，记录每一步的移动方法。5．直线的交点数平面上有n条直线，且无三线共点，问这些直线能有多少种不同的交点数。输入：n（n≤20）输出：若干行，列出所有相交方案，其中每一行为一个可能的交点数。例如输入：4输出：034566.求二叉树的后序遍历源程序名　　　tree.pas输入文件名　　tree.in输出文件名tree.out二叉树有三种遍历方法：前序、中序和后序。这三种遍历的区别在于对同一个结点在不同时刻进行访问。在进

3、行前序遍历时，每个结点是在其左右子树被访问之前进行访问的；在中序遍历时，首先访问左子树，然后访问子树的根结点，最后访问右子树。在后序遍历时，当左右子树均访问完之后才访问子树的根结点。例如上图中的一棵二叉树，其前序遍历为abdec，中序遍历为dbeac，后序遍历为debca。可以证明，在已知前序和后序遍历的情况下，可以唯一确定二叉树的中序遍历。你的任务就是根据给出的前序和中序遍历，输出后序遍历。输入格式第一行一个字符串，表示树的前序遍历。第二行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。输出

4、格式输出树的后序遍历。样例输入tree.inabdecdbeac样例输出tree.outdebca