发布时间 : 星期一 文章pascal教程2--递归与递推更新完毕开始阅读37894208f78a6529647d5370
第二章 递归与递推
2.1 遍历问题
源程序名 travel.*（pas, c, cpp） 可执行文件名 travel.exe 输入文件名 travel.in 输出文件名 travel.out 【问题描述】
我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树： a a a a / / \\ \\ b b b b / \\ / \\ c c c c 所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。 【输入】
输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。 【输出】
输出可能的中序遍历序列的总数，结果不超过长整型数。 【样例】 trave1.in trave1.out abc 4 bca
【算法分析】 根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的第一个结点是后序遍历的最后一个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉树的根结点没有左子树，那么先序遍历的第一个结点也是中序遍历的第一个结点，如果一棵二叉树的根结点没有右子树，那么先序遍历的第一个结点是中序遍历的最后一个结点。我们这里还认为就是中序遍历的中间结点，上面两种情况只是特殊的情况。
设二叉树的结点总数为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个结点字符开始取。也就是说对于每一种情况，分两步处理：第一步在先序遍历和后序遍历的结果里取左子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目；第二步在先序遍历和后序遍历的结果里取右子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目。这两步都递归调用了统计过程，不再递归调用的条件就是当统计的是空树或只有一个结点的树，这时返回的值是可能有的中序遍历结果数目。
结合“分类相加原理”和“分步相乘原理”，可以得到下面的递归函数： Function count (先序结果first，后序结果last : string) : longint; begin Len:=遍历结果的长度； 如果len为0或1，则返回结果即count:=l 否则 begin t为当前统计后符合条件的数目，初值为0； 分类统计for i:=len-1 downto 0 do begin 在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; 其中，检查先序结果和后序结果两个字符串是否符合基本规则，可以再通过一个函数来实现： function check(先序字符串F，后序字符串L)：boolean； begin Check:=true; 如果F的首字符不等于L的尾字符则check:=false; 从F的第二个字符取到最后一个字符，如果该字符不在L中，则check:=false; end; 【思考与提高】
上面的算法通过递归，结合统计的基本原理“分步相乘，分类相加”，从而统计出所有
可能解的个数，如果输入的两个字符串没有解，上述算法同样能得到结果。
在肯定有解的情况下，上述算法最终可以递归调用到0、1个结点，如果有多组解，那么调用到两个结点时，如先序为ab、后序为ba，此时有可能有如下两种结构：
a a / \\ b b
这两种结构的中序遍历结果分别为：ba、ab，有两种。 根据分步相乘的原理，对比两个字符串，每出现一次如上的情况，可能有的结构数目(结构不同，中序遍历结果也不同，因此可能有的二叉树结构的数目就是可能有的中序遍历结果数目)就乘以2一次，最终得到总的数目。这也可以理解为一种递推的方法。
从这里可以看到，在肯定有解的情况下，给定先序遍历的结果和后序遍历的结果，可能有2n种可能的结构，也就是中序遍历可能得到2n种不同的结果，其中n>＝0。那么这里的n最大可能是多少呢？可以证明n的最大值为字符串的长度加1整除2。
递推的程序如下： Program travel(intput,output); Var Total,I,m:longint; S1,s2:string; Begin Assign(input,’travel.in’); Assign(output,’travel.out’); Reset(input); rewrite(output); Readln(s1); readln(s2); total:=1; For i:=1 to length(s1)-1 do Begin M:=pos(s1[i],s2); If m>1 then if s[i+1]=s[m-1] then total:=total*2; End; Writeln(total); close(iinput); close(output); End. 2.2 产生数
源程序名 build.???（pas, c, cpp） 可执行文件名 build.exe 输入文件名 build.in 输出文件名 build.out 【问题描述】
给出一个整数n(n<1030)和m个变换规则(m≤20)。
约定：一个数字可以变换成另一个数字，规则的右部不能为零，即零不能由另一个数字变换而成。而这里所说的一个数字就是指一个一位数。
现在给出一个整数n和m个规则，要你求出对n的每一位数字经过任意次的变换(0次或多次)，能产生出多少个不同的整数。 【输入】
共m+2行，第一行是一个不超过30位的整数n，第2行是一个正整数m，接下来的m行是m个变换规则，每一规则是两个数字x、y，中间用一个空格间隔，表示x可以变换成y。
【输出】 仅一行，表示可以产生的不同整数的个数。 【样例】 build.in build.out 1 2 3 6 2 1 2 2 3
【算法分析】
如果本题用搜索，搜索的范围会很大(因为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，即： for k:=0 to 9 do for i:=0 to 9 do for j:=0 to 9 do
g[i,j]＝g[i,j]or(g[i,k] and g[k,j])；
最后还要注意，当n很大时，解的个数很大，所以要用高精度运算。