搜索
第二章递归与递推2.1遍历问题源程序名travel.???（pas,c,cpp）可执行文件名travel.exe输入文件名travel.in输出文件名travel.out【问题描述】我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：aaaa//\\bbbb/\/\cccc所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。【输入】输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。【输出】输出可能的中序遍历序列的总数，结果不超过长整型数。【样例】trave1.intrave1.outabc4bca【算法分析】根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的第一个结点是后序遍历的最后一个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉树的根结点没有左子树，那么先序遍历的第一个结点也是中序遍历的第一个结点，如果一棵二叉树的根结点没有右子树，那么先序遍历的第一个结点是中序遍历的最后一个结点。我们这里还认为就是中序遍历的中间结点，上面两种情况只是特殊的情况。设二叉树的结点总数为n(对于输入的字符串来说是它的长度)，对于先序遍历的结果，第一个结点为根结点，从第二个结点到最后一个结点分为n种情况：根结点的左子树结点个数为n-1，右子树结点的个数为0；根结点的左子树结点个数为n-2，右子树结点的个数为1；……根结点的左子树结点个数为n-i，右子树结点的个数为i-1；{0＝i=n-1)；……根结点的左子树结点个数为0，右子树结点的个数为n-1。根据这n种情况，分别将二叉树拆分为左子树和右子树，左子树结点个数为n-i，右子树结点的个数为i-l(0＝i＝n-1)，先序遍历的结果是从第二个结点(字符)开始取，而后序遍历的结果里是从第1个结点字符开始取。也就是说对于每一种情况，分两步处理：第一步在先序遍历和后序遍历的结果里取左子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目；第二步在先序遍历和后序遍历的结果里取右子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目。这两步都递归调用了统计过程，不再递归调用的条件就是当统计的是空树或只有一个结点的树，这时返回的值是可能有的中序遍历结果数目。结合“分类相加原理”和“分步相乘原理”，可以得到下面的递归函数：Functioncount(先序结果first，后序结果last:string):longint;beginLen:=遍历结果的长度；如果len为0或1，则返回结果即count:=l否则begint为当前统计后符合条件的数目，初值为0；分类统计fori:=len-1downto0dobegin在first中取出长度为i的左子树结果LF；在last中取出长度为i的左子树结果LL；在first中取出长度为len-1-i的左子树结果RF；在last中取出长度为len-1-i的右子树结果RL；如果LF、LL符合基本规则(LF的首字符跟LL的尾字符相同、LF中，所有的字符在LL中也都有)并且RF、RL也符合基本规则，那么t:=t+count(LF，LL)*count(RF，RL);{分步相乘、分步相加}{这里count函数中递归调用了count}end;返回值为t即count:=t;end;end;其中，检查先序结果和后序结果两个字符串是否符合基本规则，可以再通过一个函数来实现：functioncheck(先序字符串F，后序字符串L)：boolean；beginCheck:=true;如果F的首字符不等于L的尾字符则check:=false;从F的第二个字符取到最后一个字符，如果该字符不在L中，则check:=false;end;【思考与提高】上面的算法通过递归，结合统计的基本原理“分步相乘，分类相加”，从而统计出所有可能解的个数，如果输入的两个字符串没有解，上述算法同样能得到结果。在肯定有解的情况下，上述算法最终可以递归调用到0、1个结点，如果有多组解，那么调用到两个结点时，如先序为ab、后序为ba，此时有可能有如下两种结构：aa/\bb这两种结构的中序遍历结果分别为：ba、ab，有两种。根据分步相乘的原理，对比两个字符串，每出现一次如上的情况，可能有的结构数目(结构不同，中序遍历结果也不同，因此可能有的二叉树结构的数目就是可能有的中序遍历结果数目)就乘以2一次，最终得到总的数目。这也可以理解为一种递推的方法。从这里可以看到，在肯定有解的情况下，给定先序遍历的结果和后序遍历的结果，可能有2n种可能的结构，也就是中序遍历可能得到2n种不同的结果，其中n＝0。那么这里的n最大可能是多少呢？可以证明n的最大值为字符串的长度加1整除2。递推的程序如下：Programtravel(intput,output);VarTotal,I,m:longint;S1,s2:string;BeginAssign(input,’travel.in’);Assign(output,’travel.out’);Reset(input);rewrite(output);Readln(s1);readln(s2);total:=1;Fori:=1tolength(s1)-1doBeginM:=pos(s1[i],s2);Ifm1thenifs[i+1]=s[m-1]thentotal:=total*2;End;Writeln(total);close(iinput);close(output);End.2.2产生数源程序名build.???（pas,c,cpp）可执行文件名build.exe输入文件名build.in输出文件名build.out【问题描述】给出一个整数n(n1030)和m个变换规则(m≤20)。约定：一个数字可以变换成另一个数字，规则的右部不能为零，即零不能由另一个数字变换而成。而这里所说的一个数字就是指一个一位数。现在给出一个整数n和m个规则，要你求出对n的每一位数字经过任意次的变换(0次或多次)，能产生出多少个不同的整数。【输入】共m+2行，第一行是一个不超过30位的整数n，第2行是一个正整数m，接下来的m行是m个变换规则，每一规则是两个数字x、y，中间用一个空格间隔，表示x可以变换成y。【输出】仅一行，表示可以产生的不同整数的个数。【样例】build.inbuild.out123621223【算法分析】如果本题用搜索，搜索的范围会很大(因为n可能有30位!)，显然无法在规定的时间内出解。而我们注意到本题只需计数而不需要求出具体方案，所以我们稍加分析就会发现，可以用乘法原理直接进行计数。设F[i]表示从数字i出发可以变换成的数字个数(这里的变换可以是直接变换，也可以是间接变换，比如样例中的1可以变换成2，而2又可以变换成3，所以1也可以变换成3；另外自己本身不变换也是一种情况)。那么对于一个长度为m位的整数a，根据乘法原理，能产生的不同的整数的个数为：F[a[1]]*F[a[2]]*F[a[3]]*…*F[a[m]]。下面的问题是如何求F[i]呢？由于这些变换规则都是反映的数字与数字之间的关系，所以定义一个布尔型的二维数组g[0..9，0..9]来表示每对数字之间是否可以变换，初始时都为False；根据输入的数据，如果数字i能直接变换成数字j，那么g[i，j]置为True，这是通过一次变换就能得到的；接下来考虑那些间接变换可得到的数字对，很明显：如果i可以变为k，k又可以变为j，那么i就可以变为j，即：fork:=0to9dofori:=0to9doforj:=0to9dog[i,j]＝g[i,j]or(g[i,k]andg[k,j])；最后还要注意，当n很大时，解的个数很大，所以要用高精度运算。2.3出栈序列统计源程序名stack.???（pas,c,cpp）可执行文件名stack.exe输入文件名stack.in输出文件名stack.out【问题描述】栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。【输入】【输出】就一个数n(1≤n≤1000)。一个数，即可能输出序列的总数目。【样例】stack.instack.out35【算法分析】在第一章练习里，我们通过回溯的方法计算并输出不同的出栈序列，这里只要求输出不同的出栈序列总数目，所以我们希望能找出相应的递推公式进行处理。从排列组合的数学知识可以对此类问题加以解决。我们先对n个元素在出栈前可能的位置进行分析，它们有n个等待进栈的位置，全部进栈后在栈里也占n个位置，也就是说n个元素在出栈前最多可能分布在2*n位置上。出栈序列其实是从这2n个位置上选择n个位置进行组合，根据组合的原理，从2n个位置选n个，有C(2n,n)个。但是这里不同的是有许多情况是重复的，每次始终有n个连续的空位置，n个连续的空位置在2n个位置里有n+1种，所以重复了n+1次。所以出栈序列的种类数目为：C(2n,n)/(n+1)=2n*(2n-1)*(2n-2)…*(n+1)/n!/(n+1)=2n*(2n-1)*(2n-2)*…*(n+2)/n!。考虑到这个数据可能比较大，所以用高精度运算来计算这个结果。本题实际是一个经典的Catalan数模型。有关Catalan数的详细解释请参考《组合数学》等书。【思考与提高】我们知道，在某个状态下，所能做的操作(移动方法)无非有两种：（1）将右方的等待进栈的第一个元素进栈；（2）将栈顶的元素出栈，进入左边的出栈序列。设此时右方、栈、左方的元素个数分别为a，b，c。我们就能用(a,b,c)表示出当前的状态。显然n=a+b+c，则c=n-a-b。即已知a和b，c就被确定，所以我们可以用(a,b)来作为状态的表示方法。则起始状态为(n,0)，目标状态为(0,0)。又由上面的两种移动方法，我们可类似的得到两种状态转移方式：再设f(a,b)为从状态(a,b)通过移动火车变为状态(0,0)的所有移动方法。类似于动态规划的状态转移方程，我们可写出以下递归式：）（此时只能做出栈操作）（此时只能做进栈操作)0()1,()0,0()1,1()0,0()1,()1,1()(),(abafbabafbabafbafnbabaf边界值：f(0,0)=1。有了这个递归公式后，再写程序就比较简单了，请读者自己写出递归程序。2.4计数器源程序名count.???（pas,c,cpp）可执行文件名count.exe输入文件名count.in输出文件名count.out【问题描述】一本书的页数为N，页码从1开始编起，请你求出全部页码中，用了多少个0，1，2，…，9。其中—个页码不含多余的0，如N＝1234时第5页不是0005，只是5。【输入】一个正整数N(N≤109)，表示总的页码。【输出】共十行：第k行为数字k-1的个数。【样例】count.incount.out111411111111【算法分析】本题可以用一个循环从1到n，将其拆为一位一位的数字，并加到相应的变量里，如拆下来是1，则count[1]增加1。这种方法最简单，但当n比较大时，程序运行的时间比较长。这种方法的基本程序段如下：fori:=1tondobeginj:=i;whilej0dobegincount[jmod10]:=count[jmod10]+1;j:=jdiv10;end;end;当n是整型数据时，程序执行的时间不会太长。而n是长整型