递规与递推习题汇总.docx

《递规与递推习题汇总.docx》由会员分享，可在线阅读，更多相关《递规与递推习题汇总.docx（17页珍藏版）》请在优知文库上搜索。

1、递规与递推习题汇总2.1遍历问题源程序名trave1.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，己知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的儿棵二叉树：aaaa/bbbb/CCCC所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。【输入】输A数据共两行，第一行表示该二叉树的前序遍历结果si,第二行表示该二叉树的后序遍历结果s2o【输

2、出】输出可能的中序遍历序列的总数，结果不超过长整型数。【样例】abe4bca【算法分析】根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的第一个结点是后序遍历的最后一个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉树的根结点没有左子树，那么先序遍历的第一个结点也是中序遍历的第一个结点，如果一棵二叉树的根结点没有右子树，那么先序遍历的第一个结点是中序遍历的最后一个结点。我们这里还认为就是中序遍历的中间结点，上面两种情况只是特殊的情况。设二叉树的结点总数为n(对于输入的字符串来说是它的长度)，对于先序遍历的结果，第一个结点为根结点，从第二个结点到最

3、后一个结点分为n种情况：根结点的左子树结点个数为n-1,右子树结点的个数为0；根结点的左子树结点个数为n-2,右子树结点的个数为1；根结点的左子树结点个数为n-i,右子树结点的个数为H1.；0=i=nT);根结点的左子树结点个数为0,右子树结点的个数为n-1.。根据这n种情况，分别将二叉树拆分为左子树和右子树，左子树结点个数为nT,右子树结点的个数为iTS=i=0那么这里的n最大可能是多少呢？可以证明n的最大值为字符串的长度加1整除2。递推的程序如下：Programtrave1.(intputzoutput);VarTotaIJzITiiIongint;S1.,s2:string;BeginA

4、ssign(input/);Assign(output/);Reset(input);rewrite(output);Read1.n(si);read1.n(s2);tota1.:=1;Fori:=1.to1.ength(S1.)IdoBeginM:=pos(s1.izs2);Ifm1.thenifsi+1.=sm-1.thentotak=tota1.*2;End;Write1.n(tota1.);c1.ose(iinput);c1.ose(output);End.2.2产生数源程序名bui1.d.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】给出一个整数n(n0,b0)f(a9b)(a+bn)=(aO,b=O)(此时只能做进栈操作)(67=0)(此时只能做出栈操作)边界值：f(0,0)=Io有了这个递归公式后，再写程序就比较简单了，请读者自己写出递归程序。2.4计数器源程序名count.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】一本书的页数为N,页码从1开始编起，请你求出全部页码中，用了多少个0,1,2,9。其中一个页码不含多余的0,如N=1234时第5页不是Oo05,只是5。【输入】一个正整数N(NWIo9),表示总的页码。【输出】共十行：第k行为数字*1的个数。【样例】111411111111【算法分析】本题可以用一个循环