pascal中级教程第二章递归与递推.doc

第二章 递归与递推2.1遍历问题 源程序名 travel.?（pas, c, cpp）可执行文件名 travel.exe输入文件名 travel.in输出文件名 travel.out【问题描述】 我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：aaaa / / b b b b / / cccc所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。【输入】 输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。【输出】 输出可能的中序遍历序列的总数，结果不超过长整型数。【样例】rave1.outabc4bca【算法分析】 根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的第一个结点是后序遍历的最后一个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉树的根结点没有左子树，那么先序遍历的第一个结点也是中序遍历的第一个结点，如果一棵二叉树的根结点没有右子树，那么先序遍历的第一个结点是中序遍历的最后一个结点。我们这里还认为就是中序遍历的中间结点，上面两种情况只是特殊的情况。 设二叉树的结点总数为n(对于输入的字符串来说是它的长度)，对于先序遍历的结果，第一个结点为根结点，从第二个结点到最后一个结点分为n种情况： 根结点的左子树结点个数为n-1，右子树结点的个数为0； 根结点的左子树结点个数为n-2，右子树结点的个数为1； 根结点的左子树结点个数为n-i，右子树结点的个数为i-1；0i=n-1)； 根结点的左子树结点个数为0，右子树结点的个数为n-1。 根据这n种情况，分别将二叉树拆分为左子树和右子树，左子树结点个数为n-i，右子树结点的个数为i-l(0i0。那么这里的n最大可能是多少呢？可以证明n的最大值为字符串的长度加1整除2。递推的程序如下：Program travel(intput,output); VarTotal,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(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）可执行文件名 build.exe输入文件名 build.in输出文件名 build.out【问题描述】 给出一个整数n(n0 do begin countj 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时间上让人不能忍受。可以从连续数字本身的规律出发来进行统计，这样速度比较快，先不考虑多余的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千，000999重复了3次，每一次从000到999，每个基本数字都使用了3*102300次，重复3次，所以count0count9各增加3*300； 另外最高位的0到2作为千位又重复了1000次，count0count2各增加1000，3作为千位用了657次(n mod 100)，因此count3增加657； 接下来对百位6再进行类似的处理，0到9在个位和十位平均重复使用6*20次，所以count0count9先各增加6*20，0到5作为百位重复使用了100次，所以count0count5再各增加100，6作为百位在这里重复用了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控制位数，for i:=len downto 1 do begin 0到9的使用次数增加平均使用的次数bi-1*(i-1)*ci； 0到ci-1的使用次数增加作为当前位使用的次数bi-1； ci的使用次数增加n mod bi-1 end 最后减去多计算的0的个数； 输出结果。2.5诸侯安置 源程序名 empire.?（pas, c, cpp）可执行文件名 empire.exe输入文件名 empire.in输出文件名 empire.out【问题描述】很久以前，有一个强大的帝国，它的国土成正方形状，如图22所示。 这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地(正方形中的一格)。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如下图23为n3时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。 国王自然不愿意看到他的诸侯们互相开战，致使国家动荡不安。 因此，他希望通过合理的安排诸侯所处的位置，使他们两两之间都不能攻击。 现在，给出正方形的边长n，以及需要封地的诸侯数量k，要求你求出所有可能的安置方案数。(nl00，k2n2-2n+1) 由于方案数可能很多，你只需要输出方案数除以504的余数即可。【输入】仅一行，两个整数n和k，中间用一空格隔开。【输出】一个整数，表示方案数除以504的余数。【样例】empire.inempire.out2 24【样例说明】四种安置方案如图2-4所示。注意：镜面和旋转的情况属于不同的方案。【算法分析】 重新描述一下问题，其实就是在一个边长为2n-1的正菱形(如上图2-2为n3的情形)上摆放k个棋子，使得任意两个棋子都不在同一行、同一列。试问：这样的摆法共有多少种? 看到这道题目，我们就会立即想起一道经典的老题目：n皇后问题。这道题目与n皇后问题非常相似。但有两个不同点：一是n皇后问题可以斜着攻击对方棋子，而本题不能；二是n皇后问题是在n，n的正方形棋盘上面放置k个皇后，而本题却是在一个正菱形上摆放。我们试着先将n皇后变为不可斜攻的，再作思考，如果不能够斜着攻击，n皇后的公式是：(C(k,n)2*k!。但是本题不是一个正方形，所以这个公式对本题好像没有任何帮助。看来只能够从另外一个角度思考问题了。 首先想到在2n-1列中任意取出k列进行具体分析，这样一来问题就转化成：有一个长为k的数列(无重复元素)，每一个数在一个不定的区间a,b当中，第i个数一定在区间ai,bi之间，求这样的数列有多少种?如果就是这个问题，那么比较难解决，但若把这个数列放在本题中，就比较简单。 因为题目中任意两个区间都是一种包含关系。可以先把区间按照长度排一下序，就可以看出来，再用乘法原理进行求解即可。但是，n最多可到100，k最多可到50，穷举要进行C(50,100)种方案! 显然无法在规定的时间内出解!那么怎么办呢?再继续分析一下问题发现，里面有重叠子问题。如果一个列作为最后一列，且这一列以及前面所有列共放置p个诸侯，设有q种情况，那么这一列后面的所有列共放置p+1个棋子的方案数都要用到q，从而引用乘法原理。而且在穷举过程中，这一个工作做了许多遍，所以干脆用递推。递推前，先把图形转化为类似图2-5的形式(即列排序)。设fi,j表示以第i列为最后一列，放置j个棋子的总方案数，得出公式：不过还要注意，当k2n-1时，问题无解。2.6括号序列 源程序名 bracket.?（pas, c, cpp）可执行文件名 bracket.exe输入文件名 bracket.in输出文件名 bracket.out【问题描述】定义如下规则序列(字符串)：1空序列是规则序列；2如果S是规则序列，那么(S)和S也是规则序列；3如果A和B都是规则序列，那么AB也是规则序列。例如，下面的字符串都是规则序列：()，()，()，()，()()而以下几个则不是：(，)(，()，() 现在，给你一些由(，)，构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列a1，a2，和序列bl，b2，如果存在一组下标1i1i2m，使得aj对一切1jn成立，那么a1，a2，就叫做b1，b2，的子列。【输入】输入文件仅一行，全部由(，)，组成，没有其他字符，长度不超过100。【输出】输出文件也仅有一行，全部由(，)，组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。【样例】bracket.inbracket.out()()()最多的嵌套层数为1，如层数为2时的一种为()()【算法分析】 对于输入的括号序列字符串，从左向右进行查找，用一个数组来记录查找配对的情况，如果一个括号有相应的括号跟它对应，则将它标记为0，如果没有相应的括号跟它对应，则保存原子始代码的编号，“”分别为-1和1，“()”分别为-2和2。 因此对于读入的字符串，首先将其转换为相应的代码存放到数组里，为后面查找匹配做准备。 查找匹配时，可用这样的方法： 如果当前的字符是右括号，则跟前面的一个没有匹配的左括号对照，看是否匹配，如果匹配，则将两个字符标记为0，查找并定位到左边的第一个没有匹配的左括号(如果有的话)。如果当前的字符是左括号，则记住这个不匹配的左括号的位置，为后面找到右括号时匹配做准备。 从第一个字符开始到最后一个字符重复上面的过程，检查处理完毕。 输出时考虑到不增加嵌套的层数，以就近的原则，将出现不匹配的一个括号时，输出两个匹配的括号。2.7新汉诺塔 源程序名 hanoi.?（pas, c, cpp）可执行文件名 hanoi.exe输入文件名 hanoi.in输出文件名 hanoi.out【问题描述】 设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称为初始状态。 现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。 移动时有如下要求： 一次只能移一个盘； 不允许把大盘移到小盘上面。【输入】文件第一行是状态中圆盘总数；第二到第四行分别是初始状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号；第五到第七行分别是目标状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号。【输出】每行一步移动方案，格式为：move I from P to Q最后一行输出最少的步数。【样例】Hanoi.inHanoi.out5move 1 from A to B3 3 2 1move 2 from A to C2 5 4move 1 from B to C0move 3 from A to B1 2move 1 from C to B3 5 4 3move 2 from C to A1 1move 1 from B to C7【算法分析】要从初始状态到目标状态就是要把每个圆盘分别移到自己的目标状态。怎样才能保证总的移动步数最少呢?关键是首先考虑把编号最大的圆盘移到它的目标状态，因为编号最大的圆盘移到目标位置后就不再移动了，而在编号最大的圆盘没有移到目标之前，编号小的圆盘可能还要移动，即使它已在目标状态。所以编号最大的圆盘一旦固定，对以后的移动不会造成影响。最大的移动好后，再考虑剩余的没有到达目标状态的最大号圆盘直到最小的编号为1的圆盘到目标状态为止。设计一个移动过程：move(k,w)，表示把编号k的圆盘移到w柱。2.8排序集合 源程序名 sort.?（pas, c, cpp）可执行文件名 sort.exe输入文件名 sort.in输出文件名 sort.out【问题描述】对于集合N=1,2,n的子集，定义一个称之为“小于”的关系：设S1=X1,X2,Xi，（X1X2Xi），S2=Y1, Y2, ,Yj，（Y1Y2Yj），如果存在一个k，（0kmin(i,j)），使得X1=Y1，Xk=Yk，且k=i或X(k+1)Y(k+1)，则称S1“小于”S2。你的任务是，对于任意的n(n31)及k(k2n)，求出第k小的子集。【输入】输入文件仅一行，包含两个用空格隔开的自然数，n和k。【输出】输出文件仅一行，使该子集的元素，由小到大排列。空集输出0。【样例】sort.insort.out3 41 2 3【算法分析】 我们知道，n个元素构成的集合有2n种情况。本题的意思是：把这些集合按照某种规则排序，然后输入k，输出第k个集合。所以排序的规则是本题的关键，其实很简单，当n3时，8个集合排序如下：1l,2l,2,31,322,33，你发现规律了吗?具体算法为：先推出第k小的一个子集的第一个数宇是多少，第一个数字确定了之后，再推出第二个数字，从第一个数字加1一直计算累加集合个数，直到得到不超过k的最大的那个数字，就是第二位数字，这样一直递推，推到最后一个。要注意：终止条件是有了n个数字或者第i个数字为空，这时递推终止，输出最后的结果。2.9青蛙过河源程序名 frog.?（pas, c, cpp）可执行文件名 frog.exe输入文件名 frog.in输出文件名 frog.out【问题描述】左岸石礅A荷叶C右岸石礅B河心石礅Dh个石礅k个荷叶 有一条河，左边一个石墩(A区)上有编号为1，2，3，4，n的n只青蛙，河中有k个荷叶(C区)，还有h个石墩(D区)，右边有一个石墩(B区)，如下图25所示。n只青蛙要过河(从左岸石墩A到右岸石墩B)，规则为：(1)石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙(不论大小)；(2)青蛙可以：AB(表示可以从A跳到B，下同)，AC，AD，CB，DB，DC，CD；(3)当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大1号的青蛙上面。你的任务是对于给出的h，k，计算并输出最多能有多少只青蛙可以根据以上规则顺利过河?【样例】frog.infrog.out2 3 河中间有2个石礅，3个荷叶16最多有16只青蛙可以按照规则过河【算法分析】结论为：f(h,k)=2h(k+1)从具体到一般，推导过程如下：f(0,0)=1f(0,k)=k+1;（如k=3时，有4只青蛙可以过河）f(1,k)=2(k+1);（递推思想）依此类推：f(2,k)=(2*(k+1)*2=22(k+1);2.10电话号码源程序名 phone.?（pas, c, cpp）可执行文件名 phone.exe输入文件名 phone.in输出文件名 phone.out【问题描述】电话机上每一个数字下面都写了若干个英文字母。分布如下： 1abc 2def 3ghi 4ikl 5mn 6opq 7rst 8uvw 9xyz 现在给定一个单词表和一串数字密码，请你用单词表中的单词翻译这个密码。【输入】第一行为一个正整数N表示单词表中单词的个数(N100)；第二行为一个长度不超过100的数字串，表示密码；接下来的N行，每行一个长度不超过20的单词，表示单词表。【输出】 仅一行，表示翻译后的原文，如果密码无法翻译，则输出“No Solutions!”，如果密码有多种翻译方式，则输出任意一种即可。【样例】phone.inphone.out8thi shs b boo k73373711664thishsthisisbabook【算法分析】 本题可以用递归搜索求解。首先，我们注意到一个数字串对应的单词是不惟一的，而反之，一个单词所对应的数字串却是惟一的!所以，我们一开始就读入一大串的数字密码和一些可以出现的单词，我们把每一个单词所表示的密码(是惟一的)存在数组中。然后从密码的开头开始扫描，得出密码的第一个单词有可能的情况，选择其中一种，得出第一个单词，得到除第一个单词以外的后面的子密码。然后用递归实现子密码的破译。若子密码无解，就可以换一种第一个单词的取法，再次试验。如果全是无解，那整个密码也是无解的。另外，首先要判断整个密码串是否是一个单词，避免无限递归。2.11编码 源程序名 encode.?（pas, c, cpp）可执行文件名 encode.exe输入文件名 encode.in输出文件名 encode.out【问题描述】 编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规