《pascal中级教程第二章递归与递推》由会员分享，可在线阅读，更多相关《pascal中级教程第二章递归与递推（20页珍藏版）》请在金锄头文库上搜索。
1、第二章 递归与递推2.1 遍历问题 源程序名 travel.?（pas, c, cpp）可执行文件名 travel.exe输入文件名 travel.in输出文件名 travel.out【问题描述】我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：a a a a/ / b b b b/ / c c c c所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。
2、【输入】输 A 数据共两行，第一行表示该二叉树的前序遍历结果 s1，第二行表示该二叉树的后序遍历结果 s2。【输出】输出可能的中序遍历序列的总数，结果不超过长整型数。【样例】trave1.in trave1.outabc 4bca【算法分析】根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的第一个结点是后序遍历的最后一个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉树的根结点没有左子树，那么先序遍历的第一个结点也是中序遍历的第一个结点，如果一棵二叉树的根结点没有右子树，那么先序遍历的第一个结点是中序遍历的最后一个结点。我们这里还认为就是中序遍历
3、的中间结点，上面两种情况只是特殊的情况。设二叉树的结点总数为 n(对于输入的字符串来说是它的长度)，对于先序遍历的结果，第一个结点为根结点，从第二个结点到最后一个结点分为 n 种情况：根结点的左子树结点个数为 n-1，右子树结点的个数为 0；根结点的左子树结点个数为 n-2，右子树结点的个数为 1；根结点的左子树结点个数为 n-i，右子树结点的个数为 i-1；0 0。那么这里的 n 最大可能是多少呢？可以证明 n 的最大值为字符串的长度加 1 整除 2。递推的程序如下：Program travel(intput,output);VarTotal,I,m:longint;S1,s2:string
4、;BeginAssign(input,travel.in);Assign(output,travel.out);Reset(input); rewrite(output);Readln(s1); readln(s2); total:=1;For i:=1 to length(s1)-1 doBeginM:=pos(s1i,s2);If m1 then if si+1=sm-1 then total:=total*2;End;Writeln(total); close(iinput); close(output);End.2.2 产生数 源程序名 build.?（pas, c, cpp）可执行文
5、件名 build.exe输入文件名 build.in输出文件名 build.out【问题描述】给出一个整数 n(n0 do begincountj mod 10:=countj mod 10+1;j:=j div 10;end;end;当 n 是整型数据时，程序执行的时间不会太长。而 n 是长整型范围，就以 n 是一个 9位数为例，当 i 执行到 8 位数时，每拆分一次内循环要执行 8 次，执行完 8 位数累计内循环执行的次数为：9*1+90*2+900*3+9000*4+90000*5+900000*6+9000000*7+90000000*8时间上让人不能忍受。可以从连续数字本身的规律出发
6、来进行统计，这样速度比较快，先不考虑多余的 0 的情况，假设从 00009999，这一万个连续的数，0 到 9 用到的次数都是相同的，一万个四位数，0 到 9 这十个数字共用了 40000 次，每个数字使用了 4000 次。进一步推广，考虑所有的 n 位数情况，从 n 个 0 到 n 个 9，共 10n 个 n 位数，0 到 9 十个数字平均使用，每个数字共用了 n*10n-1 次。有了这样的规律后，可以从高位向低位进行统计，最后再减去多余的 0 的个数。以 n=3657 为例：(用 count 数组来存放 0 到 9 各个数字的使用次数)最高位(千位)为 3，从 0 千、1 千到 2 千，0
7、00999 重复了 3 次，每一次从 000 到999，每个基本数字都使用了 3*102300 次，重复 3 次，所以 count0count9 各增加3*300；另外最高位的 0 到 2 作为千位又重复了 1000 次，count0 count2 各增加 1000，3 作为千位用了 657 次(n mod 100)，因此 count3增加 657；接下来对百位 6 再进行类似的处理，0 到 9 在个位和十位平均重复使用 6*20 次，所以count0count9先各增加 6*20，0 到 5 作为百位重复使用了 100 次，所以count0count5再各增加 100，6 作为百位在这里重复
8、用了 57 次(n mod 100)；因此count6增加 57；对十位和个位也进行相同的处理，得出 count0count9的值；最后再减去多算的 0 的个数。那么 0 到底多算了多少次呢?当没有十位及以更高位时，个位的 0，只多算了 1 次；当没有百位及以更高位时，十位的 0，多算了 10 次；当没有千位及以更高位时，百位的 0，多算了 100 次；因此在统计 m 位数时， 0 多算了(111)这样一个全是 1 的 m 位数。基本算法描述如下：输入 n；计算 n 的位数 Len；将 n 每一位上的数字存放到数组 c 里；计算 10 的 0 次方到 len-1 次方并存放到数组 b 里；i
9、控制位数，for i:=len downto 1 dobegin0 到 9 的使用次数增加平均使用的次数 bi-1*(i-1)*ci；0 到 ci-1的使用次数增加作为当前位使用的次数 bi-1；ci的使用次数增加 n mod bi-1end最后减去多计算的 0 的个数；输出结果。2.5 诸侯安置 源程序名 empire.?（pas, c, cpp）可执行文件名 empire.exe输入文件名 empire.in输出文件名 empire.out【问题描述】很久以前，有一个强大的帝国，它的国土成正方形状，如图 22 所示。这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封
10、地(正方形中的一格)。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如下图 23 为 n3 时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。国王自然不愿意看到他的诸侯们互相开战，致使国家动荡不安。 因此，他希望通过合理的安排诸侯所处的位置，使他们两两之间都不能攻击。现在，给出正方形的边长 n，以及需要封地的诸侯数量 k，要求你求出所有可能的安置方案数。(nl00，k2n 2-2n+1)由于方案数可能很多，你只需要输出方案数除以 504 的余数即可。【输入】仅一行，两个整数 n 和 k，中间用一空格隔开。【输出】一个整数，表示方案数除
11、以 504 的余数。【样例】empire.in empire.out2 2 4【样例说明】四种安置方案如图 2-4 所示。注意：镜面和旋转的情况属于不同的方案。【算法分析】重新描述一下问题，其实就是在一个边长为 2n-1 的正菱形(如上图 2-2 为 n3 的情形)上摆放 k 个棋子，使得任意两个棋子都不在同一行、同一列。试问：这样的摆法共有多少种?看到这道题目，我们就会立即想起一道经典的老题目：n 皇后问题。这道题目与 n 皇后问题非常相似。但有两个不同点：一是 n 皇后问题可以斜着攻击对方棋子，而本题不能；二是 n 皇后问题是在 n，n 的正方形棋盘上面放置 k 个皇后，而本题却是在一个正
12、菱形上摆放。我们试着先将 n 皇后变为不可斜攻的，再作思考，如果不能够斜着攻击，n 皇后的公式是：(C(k,n) 2*k!。但是本题不是一个正方形，所以这个公式对本题好像没有任何帮助。看来只能够从另外一个角度思考问题了。首先想到在 2n-1 列中任意取出 k 列进行具体分析，这样一来问题就转化成：有一个长为 k 的数列(无重复元素)，每一个数在一个不定的区间a,b当中，第 i 个数一定在区间a i,bi之间，求这样的数列有多少种?如果就是这个问题，那么比较难解决，但若把这个数列放在本题中，就比较简单。 因为题目中任意两个区间都是一种包含关系。可以先把区间按照长度排一下序，就可以看出来，再用乘法
13、原理进行求解即可。但是，n 最多可到 100，k 最多可到 50，穷举要进行 C(50,100)种方案! 显然无法在规定的时间内出解!那么怎么办呢 ?再继续分析一下问题发现，里面有重叠子问题。如果一个列作为最后一列，且这一列以及前面所有列共放置 p 个诸侯，设有 q 种情况，那么这一列后面的所有列共放置 p+1 个棋子的方案数都要用到 q，从而引用乘法原理。而且在穷举过程中，这一个工作做了许多遍，所以干脆用递推。递推前，先把图形转化为类似图 2-5 的形式(即列排序)。设 fi,j表示以第 i 列为最后一列，放置 j 个棋子的总方案数，得出公式：jikijff1 )1(*,不过还要注意，当 k
14、2n-1 时，问题无解。2.6 括号序列 源程序名 bracket.?（pas, c, cpp ）可执行文件名 bracket.exe输入文件名 bracket.in输出文件名 bracket.out【问题描述】定义如下规则序列(字符串)：1空序列是规则序列；2如果 S 是规则序列，那么(S)和S也是规则序列；3如果 A 和 B 都是规则序列，那么 AB 也是规则序列。例如，下面的字符串都是规则序列：()，()，()，()，()()而以下几个则不是：(，)(，()，()现在，给你一些由(， )， ， 构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对
15、于序列 a1，a 2， 和序列nbl，b 2， ，如果存在一组下标 1i 1i2 m，使得 aj 对一切 1jn 成m nijib立，那么 a1，a 2， 就叫做 b1，b 2， 的子列。nm【输入】输入文件仅一行，全部由( ， )， ， 组成，没有其他字符，长度不超过 100。【输出】输出文件也仅有一行，全部由( ， )， ， 组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。【样例】bracket.in bracket.out() ()() 最多的嵌套层数为 1，如层数为 2 时的一种为()()【算法分析】对于输入的括号序列字符串，从左向右进行查找，用一个数组来记录查找配对的情况，如果一个括号有相应的括号跟它对应，则将它标记为 0，如果没有相应的括号跟它对应，则保存原子始代码的编号， “”分别为-1 和 1， “()”分别为
