大学生程序设计大赛试题.pdf

1 湖南省首届 湘邮科技杯 大学生程序设计大赛试题 试题 1 试题 1 n 个人围成一圈 并依次编号 1 n 从编号为 1 的人开始 按顺时针方向每隔一人选出一个 剩下的人重新围成一圈 如此循环直到剩下两人 这剩下的两人就是幸运儿 如果你想成为最后两个 幸运儿 请问开始时应该站在什么位置 设 3 n 50 输入输入 开始时的人数 n 输出输出 第 1 行是选出顺序 第 2 行是两名幸运儿的开始位置 按升序排列 位置编号之间用一个空格 分开 示例示例 输入 输入 12 应该的输出 应该的输出 2 4 6 8 10 12 3 7 11 5 1 9 试题 2 试题 2 在二维字符阵列中寻找指定的字符串 输入输入 前两行分别指示字符矩阵的宽 w 和高 h 1 w 80 且 1 h 80 接下来的 h 行每行 w 个字 符便是字符矩阵的内容 再下面的 1 行为要寻找的字符串的数目 n n 2 6 意为该字符串首字母在字符矩 阵中的位置是第 1 列 2 行 尾字母在字符矩阵中的位置是第 2 列 6 行 备注备注 如果某个字符串在字符阵列中出现多次 则只记录任意一个出现位置即可 字符串出现的形式 可能是水平 竖直 向前 向后和斜向 输出的位置顺序应该与输入中的字符串出现顺序一致 区分字符的大小写 2 示例示例 输入 输入 输出 输出 1 3 5 7 6 1 1 1 7 7 7 1 试题 3 试题 3 给出一个正方形图案和它的变换图案 称为图案变换对 编写程序 求图案变换对之间的最小 变换 图案是由黑白两种小方块构成的 可能的变换包括 1 旋转 90 度 图案顺时针旋转 90 度 记做 rot90 2 旋转 180 度 图案顺时针旋转 180 度 记做 rot180 3 旋转 270 度 图案顺时针旋转 270 度 记做 rot270 4 竖直映像 图案以其上方的一条平行线为轴翻转 记做 vr 5 联合变换 图案首先做一次竖直映像变换 然后做一次旋转变换 记做 vr rot90 或 vr rot180 或 vr rot270 6 保持 图案和变换后的图案完全一样 记做 idt 7 错误 无法应用上述变换将初始图案变换成它的变换图案 记做 imp 输入 输入 输入文件中包含多组图案变换对 每一对图案数据的起始行都是一个整数 表示正方形图案的 边长 a 以一个小方块为单位 1 aB 意为 A 推出 B 或等价的 B 或非 A 以上表达式的形式是固定的 其中的括号不能缺少 且字符间没有空格 对于某个逻辑表达式 如果变换其中原子式的取值 真或假 该表达式的整体取值可能为真 则 称这样的逻辑表达式是可满足的 否则是不可满足的 比如下面的表达式都是可满足的 q a b 2 这种自然数对表示方式可以表示 n 元组 一个三元组 a b c 可以表示成 P2 a P2 b c 一个四元组 a b c d 可以表示成 P2 a P2 b P2 c d 于是对于任意 n 2 有 Pn a1 an P2 a1 Pn 1 a2 an 例如 P3 2 0 1 12 3 对于任意长度的元组 记 L P2 n Pn a1 an 例如 L 12 4 假设有 n 辆坦克 位置分别为 x1 y1 xn yn 那么我们使用下式对这 n 辆坦克进 行加密可以得到一个自然数 N N L 现在 你的任务是对截获的加密自然数进行解密 算出坦克围成的多边形区域的面积 围成的多边形的边互不相交 例如 给定三辆坦克坐标分别为 1 1 2 0 和 0 0 最后得 到的加密自然数即为 2141 而如果给定一个被截获的自然数 2141 我们逆推上述过程可以 得到三辆坦克的坐标 1 1 2 0 和 0 0 它们围成的区域的面积为 1 输入输入输入输入 输入文件的第一行是一个正整数 N 表示截获的加密自然数数目 后续 N 行中 每 一行都包含一个加密自然数 输出输出输出输出 输出数据要保持输入的顺序 输出的每一行包含一个小数 表示被破译区域的面积 面积值必须只有一个小数位 多余的小数位应被截去 示例示例示例示例 输入输入输入输入 2 2141 206 输出输出输出输出 1 0 0 5 试题试题试题试题 5 5 5 5 在一次你举行的生日聚会上 你需要把所有你认识的人 不包括自己 分为两个队 使得每个人都只属于一个队 每个队至少有一名成员 队中的每个人都认识其所在队中的其 他人 另外 两个队成员数目应该尽可能地接近 可能有不同的解决方案 你可以找到并输 出任何一种方案 或者说明解决方案不存在 输入输入输入输入 输入文件包含若干样例 文件第一行给出样例的数目 M 在每个样例中 所有人都 被唯一地分配一个从 到 的整数 表示此人的 ID 每个样例第一行仅包含一个整数 2 N 100 表示需要被分队的总人数 后续 行中 每行代表一个人 按其 ID 升序排列 每行包含一列互不相同的数字 Aij 1 Aij N Aij i 用空格隔开 这列数字代表第 i 个人所认识的人的 ID 每行用 0 结尾 输出输出输出输出 对于每个样例 如果所需划分方案不存在 则输出 No solution 输出不含引号 否则用两行输出结果 输出的第一行中第一个数字表示第一个队的总人数 后面依次输出第 一队中每个人的 ID 每个 ID 用空格隔开 同理 第二行中第一个数字表示第二个队的总人 数 后面输出第二队中每个人的 ID 并用空格隔开 行尾没有空格 优先输出人数少的队 队中成员的 ID 按升序排列 每个样例的输出用一个空行隔开 示例示例示例示例 输入输入输入输入 2 3 2 0 1 3 0 2 0 5 2 3 5 0 1 4 5 3 0 1 2 5 0 输出输出输出输出 1 3 2 1 2 2 4 2 3 1 3 5 1 2 3 0 4 3 2 1 0 试题试题试题试题 6 6 6 6 上下文无关文法 CFG 是用来描述语言的一种强大的方法 大多数编程语言如 C C Java 和 Pascal 等都用到了上下文无关文法进行编译 一个 CFG 包含一系列产生式 规则 用来对字符进行变换 每一条规则都有如下形式 V w 其中 V 是一个符号 w 是一个字符串 符号分为两类 终结符 和 变量 在上述规则中 V 被限定为变量 而 w 可以包含终结符和变量 上下文无关 的意思即指 V 总能被 w 替换 不管 V 所处的上下文是怎么样的 在所有变量中 有且只有一个被当作 起始变量 为了 使用 CFG 产生字符串 需要先由一个起始变量开始 不断地应用产生式规则改写此字符串 直到最后串中全部为终结符 例如 终结符为 z 起始变量为 S 我们有如下规则 1 S CB 2 S ZZ 3 A CB 4 A ZZ 5 B ZZ 6 C BA 7 Z z 我们从 S 开始 选择一个规则来替换字符串 如果选择规则 1 我们可以把 替换成 CB 得到字符串 CB 如果选择规则 6 我们把 C 替换成 BA 得到字符串 BAB 如果再选择规 则4 我们把A替换成ZZ 可得到字符串BZZB 即可以这样表示这一过程 S CB BAB BZZB ZZZZB ZZZZZZ zZZZZZ zzZZZZ zzzZZZ zzzzZZ zzzzzZ zzzzzz 所以这个文法能表示 2 N 个字符 z 组成的字符串 N 为奇数 对于 一个给定的 CFG 和一些字符串 你的任务是判断每个字符串是否属于文法能表示的语言 输入输入输入输入 为了简化问题 我们可以把形如 S u S v S w 的产生式转化成 S u v w 另外 输入的 CFG 是以乔姆斯基范式 Chomsky normal form CNF 的形式给出的 一个 转化成 CNF 形式的 CFG 具有如下形式 A BC A a 其中 a 是任意终结符 A B 和 C 可以是任何变量 但 B 和 C 不是起始变量 CNF 也允许形 如 S 的产生式 其中 S 为起始变量 代表空字符串 所以 CFG 也可以产生空串 我们 在本题中忽略这种情形 输入文件仅包含一个已转化成 CNF 形式的 CFG 以及至多 50 个字符串 我们使用仅 一个小写字母作为终结符 使用若干大写字母作为变量 S 依然为起始变量 CFG 占据若干 行 须换成 并不是所有可能的变量都对应一条产生式规则 但有产生式的变量 至少可以有一条产生式规则 CFG 以一个占据单独一行的 结束 CFG 之后紧跟若干字 符串 每个都占据单独的一行 读完所有字符串时代表读到了输入文件结尾 输出输出输出输出 对于每个字符串 输出一行 如果此字符串属于给定 CFG 所能描述的语言 则输出 YES 输出中没有引号 否则输出 NO 输出中无引号 示例示例示例示例 输入输入输入输入 S CB ZZ A CB ZZ B ZZ C BA Z z zzzzzz z a 输出输出输出输出 YES NO NO 试题试题试题试题 7 7 7 7 汽车厂里有个装配机器人 它有 N 个首尾相连的手臂 link 手臂 1 连接着手臂 2 手臂 2 连接着手臂 3 手臂 N 1 连接着手臂 N 每个手臂都是具有特定长度的直杆 手 臂之间靠关节 servo 互连 如关节 2 连接了手臂 1 和手臂 2 关节 N 连接了手臂 N 1 和手臂 N 手臂 1 通过关节 1 与地面相连 关节 1 位于笛卡尔坐标系的原点 即 x 0 y 0 z 0 地 面与 xy 平面重合 关节中有电机伺服装置可以调整互连手臂的相对角度 手臂 N 的末端 有个机械手可以抓取零件 启动前机器人的所有关节都是无旋转的 0 度 所有手臂都垂直于地面 xy 平面 并 与 Z 轴重合 启动后每个关节都可以绕某个方向旋转至多 90 度 其中关节 1 可以使所有手 臂绕 y 轴在 xz 平面内旋转 关节 2 可以使除手臂 1 之外的所有手臂绕 x 轴在 yz 平面内旋转 注意 由于关节 1 的作用 这里的 x 轴和 yz 平面可能都是已发生偏转的 按照类似规则 奇数编号的关节可以使其后的手臂在 xz 平面 可能是有偏转的 内旋转 偶数编号的关节 可以使其后的手臂在 yz 平面 可能是有偏转的 内旋转 从旋转坐标轴的正向朝坐标原点 望去 若手臂发生逆时针旋转则定义该旋转为正向偏转 机器人手臂的旋转姿态有两个约束条件 首先 机器人的手臂不能旋转到地面以下 其 次手臂之间不能相交 相邻手臂通过关节接触除外 你只需检验机器人手臂最终姿态的合法性即可 给定机器人的手臂数目 每只手臂的长度及关节的旋转角度 请首先确定其姿态是否合 法 如果合法请给出机械手的空间位置 需精确到小数点后 3 位 若不合法则指出不合法的 原因及造成这种不合法状态的编号最小的责任关节 若两只手臂的最短距离小于 0 001 就认 为它们相交了 输入输入输入输入 输入文件中有多个样例 文件的第 1 行给出了样例数目 N 此后的 N 行依次给出每 个机器人样例的具体内容 手臂的数目 N 每个手臂的长度 每个关节的旋转角度 长度和 角度值都是按所属手臂或关节的编号依次给出 注意 长度和角度都是实数 手臂的数目 是整数 机器人手臂的数目不多于 10 个 输出输出输出输出 对于每种输入样例 请首先输出样例的编号 由 1 开始 然后 若该机械人手臂的姿 态是合法的 请输出机械手在题干第一段所述笛卡尔坐标系中的三维坐标 坐标值精确到小 数点后 3 位 否则请输出不合法的原因和编号最小的责任关节 行尾没有空格 请参考下文 所附的输入输出例子 示例示例示例示例 输入输入输入输入 8 2 25 15 0 90 0 1 1 0 45 0 2 1 1 0 45 4 1 2 3 4 90 0 0 0 3 1 1 1 0 90 90 2 1 1 45 0 45 4 1 1 1 2 0 90 0 90 8 10 1 1 1 1 1 1 2 0 0 90 0 90 0 90 0 输出输出输出输出 Case 1 robot s hand is at 0 000 15 000 25 000 Case 2 robot s hand is at 0 707 0 000 0 707 Case 3 robot s hand is at 0 000 0 707 1 707 Case 4 robot s hand is at 10 000 0 000 0 000 Case 5 robot s hand is at 1 000 1 000 1 000 Case 6 robot s hand is at 1 207 0 707 1 207 Case 7 servo 4 attempts to move arm below floor Case 8 servo 8 causes link collision 试题试题试题试题 8 8 8 8 四叉树经常用于对数字图像进行压缩编码 给定一幅 n n 的图像 n 是 2 的幂 且 1 n 16 它的四叉树编码按如下方式进行 从一棵仅有一个结点的树开始 此结点称为根结 点 把整幅图像的 n n 区域全部关联到此结点 后续的过程按递归方式进行 1 如果图像区域中关联到当前结点的像素具有像素值 p 则此结点为一叶子结点 并 被赋给一个值 p 2 否则 给当前结点添加 4 个子结点 图像区域被划分成四个正方形的象限 每个象 限被分配给一个子结点 算法在每个子结点上递归进行 在此过程结束时 我们可以获得一棵四叉树 此树的每个内部结点都有四个子结点 每 个叶子结点都被分配给一个强度值 代表被分配到此叶结点的图像强度值 如图所示为一幅 图像和其四叉树编码树 我们假定四个子结点从左到右依次代表 上左 上右 下左 下右 四个象限 为了方便地标记四叉树中的结点 我们给每个结点按如下方式进行编号 1 根结点被编号为 0 2 如果一个结点的编号值为 k 则其四个子结点从左到右编号为 4k 1 4k 2 4k 3 4k 4 被编码成四叉树的图像可以使用一个密码进行加密 加密方式为 每当对图像执行一次 划分 对其四个分支的顺序实施重组 在每个结点上 重组方式可能不同 但无论如何 重 组方式完全由密码和结点编号决定 不幸的是 有人开发了一个编码程序 EncodeImg 此程序有 保存密码 功能 用相同 的密码可以对多幅图像进行加密 在仔细考察一幅精心选择的 测试图像 后发现 用相同 的密码实施加密后得到的任何图像 皆可以在不用密码的情况下被破解 事实上 在一幅 测 试图像 中 每个像素值都有一个唯一像素值 范围为 0 到 n2 1 且按从左到右 从上 到下递增的顺序分配的 例如 当 n 16 时 测试图像如下 假定你得到了那个编码程序 EncodeImg 你可以用它对 测试图像 进行加密 现在 给你一棵 测试图像 的编码树 你需要写一个程序 对使用相同的密码加密的任何其它图 像进