2022年递归与递推 .pdf

《2022年递归与递推 .pdf》由会员分享，可在线阅读，更多相关《2022年递归与递推 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、21 遍历问题【问题描述】我们都很熟悉二叉树的前序、中序、后序遍历， 在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历， 相应的， 已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。【输入】输入数据共两行， 第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。【输出】输出可能的中序遍历序列的总数，结果不超过长整型数。【样例】travel.in abc cba travel.ou

2、t 4 22 产生数【问题描述】给出一个整数n(n1030)和 m 个变换规则 (m20)。约定： 一个数字可以变换成另一个数字，规则的右部不能为零，即零不能由另一个数字变换而成。而这里所说的一个数字就是指一个一位数。现在给出一个整数n 和 m 个规则，要你求出对n 的每一位数字经过任意次的变换(0 次或多次 )，能产生出多少个不同的整数。【输入】共 m+2 行，第一行是一个不超过30 位的整数n，第 2 行是一个正整数m，接下来的m行是 m 个变换规则，每一规则是两个数字x、y，中间用一个空格间隔，表示X 可以变换成Y。【输出】仅一行，表示可以产生的不同整数的个数。【样例】build.in

3、1 2 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 2 1 2 2 3 build.out 6 23 出栈序列统计【问题描述】栈是常用的一种数据结构，有 n 个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push 和 pop，前者是将一个元素进栈，后者是将栈顶元素弹出。 现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，,

4、 ，n，经过一系列操作可能得到的输出序列总数。【输入】就一个数 n(1n1000)。【输出】一个数，即可能输出序列的总数目。【样例】stack.in 3 stack.out 5 24 计数器【问题描述】一本书的页数为N， 页码从 1 开始编起， 请你求出全部页码中，用了多少个0，1，2， , ，9。其中一个页码不含多余的0，如 N=1234 时第 5 页不是 0005，只是 5。【输入】一个正整数N(N 109)，表示总的页码。【输出】共十行：第k 行为数字 k-1 的个数。【样例】count.in 11 count.Out 1 4 1 1 1 1 1 1 名师资料总结 - - -精品资料欢迎

5、下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 1 1 25 诸侯安置【问题描述】很久以前，有一个强大的帝国，它的国土成正方形状，如图2 2 所示。这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地(正方形中的一格)。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如下图2-3 为 n=3 时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。国王自然不愿意看到他的诸侯们互相开战，致使

6、国家动荡不安。因此，他希望通过合理的安排诸侯所处的位置，使他们两两之间都不能攻击。现在，给出正方形的边长n，以及需要封地的诸侯数量k，要求你求出所有可能的安置方案数。 (n100，k 2n2-2n+1) 由于方案数可能很多，你只需要输出方案数除以504 的余数即可。【输入】仅一行，两个整数n 和 k，中间用一空格隔开【输出】一个整数，表示方案数除以504 的余数。【样例】empire.in 2 2 empire.out 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7

7、页 - - - - - - - - - 4 【样例说明】四种安置方案如图2-4 所示。注意：镜面和旋转的情况属于不同的方案。26 括号序列【问题描述】定义如下规则序列(字符串 )：1空序列是规则序列；2如果 S 是规则序列，那么(S)和 s也是规则序列；3如果 A 和 B 都是规则序列，那么AB 也是规则序列。例如，下面的字符串都是规则序列：()， ，() ，() ，() ，()() 而以下几个则不是：(， ，)(，()，() 现在，给你一些由( ， ) ， ， 构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列a1，a2，, ， an和序列b

8、1，b2，, ，bn，如果存在一组下标1i1i2,inm，使得aj=bj对一切 1jn成立，那么 a1，a2，, ， an就叫做 b1，b2，bm的子列。【输入】输入文件仅一行，全部由( ， ) ， ， 组成，没有其他字符，长度不超过100 【输出】输出文件也仅有一行，全部由( ， ) ， ， 组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的的规则序列中嵌套的层数尽可能地少。【样例】bracket.in () bracket.out ()() 最多的嵌套层数为1，如层数为2时的一种为 ()() 27 新汉诺塔【问题描述】设有 n 个大小不等的中空圆盘，按

9、从小到大的顺序从1 到 n 编号。将这 n 个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称为初始状态。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。移动时有如下要求：一次只能移一个盘；不允许把大盘移到小盘上面。【输入】文件第一行是状态中圆盘总数；第二到第四行分别是初始状态中A、B、C 柱上圆盘的个数和从下到上每个圆盘的编号；第五到第七行分别

10、是目标状态中A、B、C 柱上圆盘的个数和从下到上每个圆盘的编号。【输出】每行一步移动方案，格式为：move I from P to Q 最后一行输出最少的步数。【样例】Hanoiin 5 3 3 2 1 2 5 4 0 1 2 3 5 4 3 1 1 Hanoiout move 1 from A to B move 2 from A to C move 1 from B to C move 3 from A to B move 1 from C to B move 2 from C to A move 1 from B to C 7 28 排序集合【问题描述】对于集合 N=1 ，2， , ，

11、n的子集，定义一个称之为“小于”的关系：设 S1=X1，X2，, ，Xi，(x1x2, Xi)，S2=Y1，Y2，, ， Yi ，(Y1Y2,Yi)，如果存在一个k，(Okmini ，j)，使得 X1=Y1，, ， Xk=Yk，且 k=i 或 X(k+1)Y(k+1)，则称S1“小于” S2。你的任务是，对于任意的n(n31)及 k(k2n)，求出第k 小的子集。【输入】输入文件仅一行，包含两个用空格隔开的自然数，n 和 k。【输出】输出文件仅一行，是该子集的元素，由小到大排列。空集输出0。【样例】sort.in 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -

12、 - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 3 4 sort.out 1 2 3 29 青蛙过河【问题描述】有一条河，左边一个石墩(A 区)上有编号为1，2，3，4， , ， n 的 n 只青蛙，河中有k个荷叶 (c 区)，还有 h 个石墩 (D 区)，右边有一个石墩(B 区)，如下图2-5 所示。 n 只青蛙要过河 (从左岸石墩A 到右岸石墩B)，规则为：(1)石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙(不论大小 )；(2)青蛙可以： A-B( 表示可以从A 跳到 B，下同 )，AC，AD，CB

13、，DB，DC，cD；(3)当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大1 号的青蛙上面。【你的任务】给出 h，k，输出最多能有多少只青蛙可以根据以上规则顺利过河? 【样例】frog.in 2 3 河中间有2 个石墩， 3 个荷叶 ) frog.out 16 最多有 16 只青蛙可以按照规则过河 210 电话号码【问题描述】电话机上每一个数字下面都写了若干个英文字母。分布如下：1abc 2def 3ghi 4jkl 5mn 6opq 7rst 8uvw 9xyz 现在给定一个单词表和一串数字密码，请你用单词表中的单词翻译这个密码。【输入】第一行为一个正整数N 表示单词表中单词的个数(N1

14、00)；第二行为一个长度不超过100 的数字串，表示密码；接下来的 N 行，每行一个长度不超过20 的单词，表示单词表。【输出】仅一行，表示翻译后的原文，如果密码无法翻译，则输出“No Solutions! ” ，如果密码有多种翻译方式，则输出任意一种即可。【样例】phone.in 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 8 73373711664 thi shs this is b a boo k phone.out

15、thi shs b boo k 21l 编码【问题描述】编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。字母表中共有26 个字母 a，b， , ， z，这些特殊的单词长度不超过6 且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置。例如：a1 b2 z26 ab27 ac28 你的任务就是对于所给的单词，求出它的编码。【输入】仅一行，被编码的单词。【输出】仅一行，对应的编码。如果单词不在字母表中，输出0。【样例】encode.in ab encode.out 27 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -