递规与递推习题汇总.docx

《递规与递推习题汇总.docx》由会员分享，可在线阅读，更多相关《递规与递推习题汇总.docx（18页珍藏版）》请在三一办公上搜索。

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)

5、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【算法分析】本题可以用一个循环从1到

6、n,将其拆为一位一位的数字，并加到相应的变量里，如拆下来是1,则CoUnt1增加1。这种方法最简单，但当n比较大时，程序运行的时间比较长。这种方法的基本程序段如下：fori:=1.tondobeginj：=i；whi1.ej0dobegincountjmod10:=countjmod10+1.;j:=jdiv10;end;end;当n是整型数据时，程序执行的时间不会太长。而n是长整型范围，就以n是一个9位数为例，当i执行到8位数时，每拆分一次内循环要执行8次，执行完8位数累计内循环执行的次数为：9*1.+90*2+900*3+9000*4+90000*5+900000*6+*7+*8时间上让人

7、不能忍受。可以从连续数字本身的规律出发来进行统计，这样速度比较快，先不考虑多余的0的情况，假设从OOoO9999,这一万个连续的数，。到9用到的次数都是相同的，一万个四位数，0到9这十个数字共用了40000次，每个数字使用了4000次。进一步推广，考虑所有的n位数情况，从n个O到n个9,共Ion个n位数，0至U9十个数字平均使用，每个数字共用了n*10ni次。有了这样的规律后，可以从高位向低位进行统计，最后再减去多余的。的个数。以n=3657为例：(用count数组来存放0到9各个数字的使用次数)最高位(千位)为3,从0千、1千至12千，(X)O999重复了3次，每一次从OOO到999,每个基

8、本数字都使用了3*102=300次，重复3次，所以CoUntOcount各增加3*300；另外最高位的0到2作为千位又重复了1000次，coUnt0CoUnt各增加1000,3作为千位用T657次(=nmod100),因此COUnt增加657；接下来对百位6再进行类似的处理，。到9在个位和十位平均重复使用6*20次，所以COUntCOUnt先各增力口6*20,0到5作为百位重复使用了100次,所以CoUntCOUnt再各增加100,6作为百位在这里重复用了57次(=nmod100)；因此CoUnt增加57；对十位和个位也进行相同的处理，得出CoUnt0count9的值；最后再减去多算的0的个数

9、。那么0到底多算了多少次呢？当没有十位及以更高位时，个位的0,只多算了1次；当没有百位及以更高位时，十位的0,多算了10次；当没有千位及以更高位时，百位的0,多算了100次；因此在统计m位数时，0多算了(111)这样一个全是1的m位数。基本算法描述如下：输入n；计算n的位数1.en；将n每一位上的数字存放到数组c里；计算10的0次方到IenT次方并存放到数组b里；i控制位数,fori:=1.endownto1dobegin0到9的使用次数增加平均使用的次数bi-1.*(i-1.)*ci:0到ci-1.的使用次数增加作为当前位使用的次数bi-1.:ci的使用次数增加nmodbi-1.end最后减

10、去多计算的0的个数；输出结果。源程序名empire.?(paszczcpp)可执行文件名输入文件名输出文件名【问题描述】很久以前，有一个强大的帝国，它的国土成正方形状，如图22所示。这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地（正方形中的一格）。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如下图23为n=3时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。因此，他希望通过合国王自然不愿意看到他的诸侯们互相开战，致使国家动荡不安。理的安排诸侯所处的位置，使他们两两之间都不能攻击。现在，给出正方形的边长n

11、,以及需要封地的诸侯数量k,要求你求出所有可能的安置方案数。（nIOO,k2n2-2n+1.）由于方案数可能很多，你只需要输出方案数除以504的余数即可。【输入】仅一行，两个整数n和k,中间用一空格隔开。【输出】一个整数，表示方案数除以504的余数。【样例】【算法分析】重新描述一下问题,其实就是在一个边长为2n-1.的正菱形（如上图2-2为n=3的情形）上摆放k个棋子，使得任意两个棋子都不在同一行、同一列。试问：这样的摆法共有多少种?看到这道题目，我们就会立即想起一道经典的老题目：n皇后问题。这道题目与n皇后问题非常相似。但有两个不同点：一是n皇后问题可以斜着攻击对方棋子，而本题不能；二是n皇

12、后问题是在n,n的正方形棋盘上面放置k个皇后，而本题却是在一个正菱形上摆放。我们试着先将n皇后变为不可斜攻的，再作思考，如果不能够斜着攻击，n皇后的公式是：(C(k,n)2*k1.但是本题不是一个正方形，所以这个公式对本题好像没有任何帮助。看来只能够从另外一个角度思考问题了。首先想到在2n-1列中任意取出k列进行具体分析，这样一来问题就转化成：有一个长为k的数列(无重复元素)，每一个数在一个不定的区间a,b当中，第i个数一定在区间EbU之间，求这样的数列有多少种?如果就是这个问题，那么比较难解决，但若把这个数列放在本题中，就比较简单。因为题目中任意两个区间都是一种包含关系。可以先把区间按照长度

13、排一下序，就可以看出来，再用乘法原理进行求解即可,但是，n最多可到IOO,k最多可到50,穷举要进行C(50,100)种方案！显然无法在规定的时间内出解!那么怎么办呢?再继续分析一下问题发现，里面有重叠子问题。1.1.Z1.如果一个列作为最后一列，且这一列以及前面所有列共放置P个诸侯，设I-I-有q种情况，那么这一列后面的所有列共放置P+1个棋子的方案数都要用1.到q,从而引用乘法原理。而且在穷举过程中，这一个工作做了许多遍，所以干脆用递推。递推前，先把图形转化为类似图2-5的形式(即列排序)。设fij表示以第i列为最后一列，放置j个棋子的总方案数，得出公式：U=-y-U*(-y+i)J1.=

14、I不过还要注意，当k22n-1时，问题无解。2.6括号序列源程序名bracket.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】定义如下规则序列(字符串)：1 .空序列是规则序列；2 .如果S是规则序列，那么和也是规则序列；3 .如果A和B都是规则序列，那么AB也是规则序列。例如，下面的字符串都是规则序列：(),口,(0),(),0,()()而以下几个则不是：(,1.,)(,0),()现在，给你一些由黄，T,，构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列，明和序歹Ib.,b2,，bm,如果存在一组下标IWiKi2i,

15、Wm,使得对一切IWjWn成立，那么为，。2，就叫做b1.，匕2，6”,的子列。【输入】输入文件仅一行，全部由C,),T，T组成，没有其他字符，长度不超过100。【输出】输出文件也仅有一行，全部由C,),T，T组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。【样例】()00最多的嵌套层数为1,如层数为2时的一种为()()【算法分析】对于输入的括号序列字符串，从左向右进行查找，用一个数组来记录查找配对的情况，如果一个括号有相应的括号跟它对应，则将它标记为0,如果没有相应的括号跟它对应，则保存原子始代码的编号，“口”分别为T和

16、1,“()”分别为-2和2。因此对于读入的字符串，首先将其转换为相应的代码存放到数组里，为后面查找匹配做准备。查找匹配时，可用这样的方法：如果当前的字符是右括号，则跟前面的一个没有匹配的左括号对照，看是否匹配，如果匹配，则将两个字符标记为0,查找并定位到左边的第一个没有匹配的左括号(如果有的话)。如果当前的字符是左括号，则记住这个不匹配的左括号的位置，为后面找到右括号时匹配做准备。从第一个字符开始到最后一个字符重复上面的过程，检查处理完毕。输出时考虑到不增加嵌套的层数，以就近的原则，将出现不匹配的一个括号时，输出两个匹配的括号。源程序名hanoi.?(paszctcpp)可执行文件名输入文件名

17、输出文件名【问题描述】设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C,这个状态称为初始状态。现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。移动时有如下要求：一次只能移一个盘；不允许把大盘移到小盘上面。【输入】文件第一行是状态中圆盘总数；第二到第四行分别是初始状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号;第五到第七行分别是目标状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号。【输出】每行一步移动方案，格式为：moveIfromPtoQ最后一行输出最少的步数。【样例】5 move1from

18、AtoB6 321move2fromAtoC254move1fromBtoC0move3fromAtoB12move1fromCtoB3543move2fromCtoA11move1fromBtoC7【算法分析】要从初始状态到目标状态.就是要把每个圆盘分别移到自己的目标状态。怎样才能保证总的移动步数最少呢?关键是首先考虑把编号最大的圆盘移到它的目标状态，因为编号最大的圆盘移到目标位置后就不再移动了，而在编号最大的圆盘没有移到目标之前，编号小的圆盘可能还要移动，即使它已在目标状态。所以编号最大的圆盘一旦固定，对以后的移动不会造成影响。最大的移动好后，再考虑剩余的没有到达目标状态的最大号圆盘直到最

19、小的编号为1的圆盘到目标状态为止。设计一个移动过程：move(k,w),表示把编号k的圆盘移到W柱。2.8排序集合源程序名sort.?(paszc1.cpp)可执行文件名输入文件名输出文件名【问题描述】对于集合N=U,2,n的子集，定义一个称之为“小于”的关系：设SEX1,Xi,(XX2-Xi),S2=Y,Y2,Yj,(YKY2如果存在一个k,(Okmin(i,j),使得XI=YI,，k=Yk,且k=i或X(k+i)Y(g，则称S1“小于”S2。你的任务是，对于任意的n(nW31)及k(k2n),求出第k小的子集。【输入】输入文件仅一行，包含两个用空格隔开的自然数，n和k。【输出】输出文件仅一

20、行，使该子集的元素，由小到大排列。空集输出0。【样例】34123【算法分析】我们知道，n个元素构成的集合有2。种情况。本题的意思是：把这些集合按照某种规则排序，然后输入k,输出第k个集合。所以排序的规则是本题的关键，其实很简单，当n=3时，8个集合排序如下：1.1.,21.,2,31.,322,33,你发现规律了吗?具体算法为:先推出第k小的一个子集的第一个数宇是多少,第一个数字确定了之后，再推出第二个数字,从第一个数字加1一直计算累加集合个数，直到得到不超过k的最大的那个数字，就是第二位数字，这样一直递推，推到最后一个。要注意：终止条件是有了n个数字或者第i个数字为空，这时递推终止，输出最后

21、的结果。源程序名frog.?(pas,c,卬P)可执行文件名输入文件名输出文件名【问题描述】有一条河，左边一个石墩(A区)上有编号为1,2,3,4,，n的n只青蛙，河中有k(1)石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙(不论大小)；(2)青蛙可以：A-B(表示可以从A跳到B,下同)，AiAfC-B,D-B,D-C,C-*D；(3)当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大1号的青蛙上面。你的任务是对于给出的h,k,计算并输出最多能有多少只青蛙可以根据以上规则顺利过河？【样例】23河中间有2个石碳，3个荷叶16最多有16只青蛙可以按照规则过可【算法分析】结论为：f(hzk)=2

22、h(k+1.)从具体到一般，推导过程如下：f(0,0)=1f(Ozk)=k+1.;(如k=3时，有4只青蛙可以过河)f(1.zk)=2(k+1.);(递推思想)依此类推：f(2zk)=(2*(k+1.)*2=22(k+1.);2.10电话号码源程序名phone.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】电话机上每一个数字下面都写了若干个英文字母。分布如下:1.abc2def3ghi4ik1.5mn6opq7rst8uvw9xyz现在给定一个单词表和一串数字密码，请你用单词表中的单词翻译这个密码。【输入】第一行为一个正整数N表示单词表中单词的个数(NW1.O0)；第二行

23、为一个长度不超过100的数字串，表示密码；接下来的N行，每行一个长度不超过20的单词，表示单词表。【输出】仅一行，表示翻译后的原文，如果密码无法翻译，则输出“NoSo1.utions!”，如果密码有多种翻译方式，则输出任意一种即可。【样例】8thishsbbookthiShSthisisbabook【算法分析】本题可以用递归搜索求解。首先，我们注意到一个数字串对应的单词是不惟一的，而反之，一个单词所对应的数字串却是惟一的!所以，我们一开始就读入一大串的数字密码和一些可以出现的单词，我们把每一个单词所表示的密码(是惟一的)存在数组中。然后从密码的开头开始扫描，得出密码的第一个单词有可能的情况，选

24、择其中一种，得出第一个单词，得到除第一个单词以外的后面的子密码。然后用递归实现子密码的破译。若子密码无解，就可以换一种第一个单词的取法，再次试验。如果全是无解，那整个密码也是无解的。另外，首先要判断整个密码串是否是一个单词，避免无限递归。2.11编码源程序名encode.?(pas,c,cpp)可执行文件名输入文件名输出文件名【问题描述】编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。字母表中共有26个字母a,b,，z,这些特殊的单词长度不超过6且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位

25、置。例如：a-*1.b-*2Z-26ab27ac-*28你的任务就是对于所给的单词，求出它的编码。【输入】仅一行，被编码的单词。【输出】仅一行，对应的编码。如果单词不在字母表中，输出0。【样例】ab27【算法分析】对于输入的字符串，首先检查是否符合编码的条件：全是由小写字母组成并且前面的字母不会比后面的字母大。如果符合条件则进行编码，否则输出0。编码时如果不找规律，可以根据顺序，从第一个符合条件的单词a开始往后构造，每构造一个，相应的编码增加1,直到构造到输入的字符串。一个单词的后序单词类似于数字的进位，如十进制中8后面是9,9后面是10一进位的情况，再如99后面是IO0,199后面是200。

26、而这里单词的规则是一串中后面的字符不比前面的大，所以Z后是ab,az后是be,两个字符的单词最大的为yz,三个字符最小的为abc,最大的为xyz,六个字符的单词最小的为abcdef,最大的为UVWXyz,根据上面的进位规则进行构造，构造到输入的字符串时则输出相应的序号。由此可以写出程序。另外可以从数学上寻找递推的规则：一个字符的单词有26个；两个字符的单词有：25+24+23+-+1个；其中abaz共25个,bcbz共24个，cdcz共23个，yz共1个三个字符的单词有：(24+23+22+1)+(23+22+21+-+1)+-+(2+1)+(1)个abcayzbcdbyzWXywyzxyz四个字符的单词有：(23+22+21+-+1)+(22+21+20+1)+-+(2+1)+(1)+abcdaxyz(22+21+20+1.)+(21+20+-+1)+(2+1)+(1)+(1)个wxyzbcdebxyz以此类推，得到相应的数学公式。