湖南省首届“湘邮科技杯”大学生程序设计大赛试题

湖南省首届“湘邮科技杯”大学生程序设计大赛试题 试题1n个人围成一圈,并依次编号1~n,。从编号为1的人开始,按顺时针方向每隔一人选出一个, 剩下的人重新围成一圈,如此循环直到剩下两人,这剩下的两人就是幸运儿。如果你想成为最后两个 幸运儿,请问开始时应该站在什么位置?(设3<=n<=50) 输入:开始时的人数n 输出:第1行是选出顺序,第2行是两名幸运儿的开始位置(按升序排列),位置编号之间用一个空格 分开 示例 9 (5 输入: 应该的输出: 2468101237115 试题2在二维字符阵列中寻找指定的字符串 输入:前两行分别指示字符矩阵的宽w和高h(1<=w<=80且1<h<=80)。接下来的h行每行w个字 符便是字符矩阵的内容,再下面的1行为要寻找的字符串的数目n(n<10),其后的n行便是要 寻找的字符串,每个字符串不会超过20个字符 输出:n行,每行保存1个字符串的位置。位置的格式形如(1,2)>(2,6),意为该字符串首字母在字符矩 阵中的位置是第1列2行,尾字母在字符矩阵中的位置是第2列6行 备注:如果某个字符串在字符阵列中出现多次,则只记录任意一个出现位置即可。字符串出现的形式 可能是水平、竖直、向前、向后和斜向。输出的位置顺序应该与输入中的字符串出现顺序一致 区分字符的大小写

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 在二维字符阵列中寻找指定的字符串。 输入：前两行分别指示字符矩阵的宽 w 和高 h（1<=w<=80 且 1<=h<=80）。接下来的 h 行每行 w 个字 符便是字符矩阵的内容，再下面的 1 行为要寻找的字符串的数目 n（n<10），其后的 n 行便是要 寻找的字符串，每个字符串不会超过 20 个字符。 输出：n 行，每行保存 1 个字符串的位置。位置的格式形如(1,2)->(2,6)，意为该字符串首字母在字符矩 阵中的位置是第 1 列 2 行，尾字母在字符矩阵中的位置是第 2 列 6 行。 备注：如果某个字符串在字符阵列中出现多次，则只记录任意一个出现位置即可。字符串出现的形式 可能是水平、竖直、向前、向后和斜向。输出的位置顺序应该与输入中的字符串出现顺序一致。 区分字符的大小写

示例 输入: EYBEYBD K D CJ E N A K E WNQA OAYTUEL E NA M AJ R 22CADW0 E KSIAP B 3 AAAAA BYEBYE BORLAND 输出 (1,3)->(5,7) (6,1)->(1,1) (7,7)->(7,1) 试题3给出一个正方形图案和它的变换图案,称为图案变换对。编写程序,求图案变换对之间的最小 变换。图案是由黑白两种小方块构成的。可能的变换包括: (1)旋转90度:图案顺时针旋转90度,记做rot90 (2)旋转180度:图案顺时针旋转180度,记做rotl80 (3)旋转270度:图案顺时针旋转270度,记做rot270 (4)竖直映像:图案以其上方的一条平行线为轴翻转,记做vr (5)联合变换:图案首先做一次竖直映像变换,然后做一次旋转变换,记做v-rot90或v-rot180或 vr-rot270 (6)保持:图案和变换后的图案完全一样,记做idt (7)错误:无法应用上述变换将初始图案变换成它的变换图案,记做imp 输入:输入文件中包含多组图案变换对。每一对图案数据的起始行都是一个整数,表示正方形图案的 边长a(以一个小方块为单位,1<=a<=100),后续的a行,每一行包含了原图案的一行和变换图案的 对应行,两者之间用一个空格分开。黑色小方块用b表示,白色小方块用o表示 输出:输出文件的每一行对应输入文件的每一个图案变换对。其中每行开始的整数表示对应图案对在 输入文件中出现的序号,紧跟一个空格,然后就是该图案对的最小变换,采用上述记号表示 备注:为了比较不同变换的大小,定义:旋转变换的代价小于映像变换,小角度旋转变换的代价小于 大角度旋转变换,保持变换的代价最小。注意:对本题而言,只有上面列出的变换是合法的,如果某 个图案对可以由多个变换得到,则应选择代价最小的变换

2 示例 输入： 输出： (1,3)->(5,7) (6,1)->(1,1) (7,7)->(7,1) 试题 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<=a<=100），后续的 a 行，每一行包含了原图案的一行和变换图案的 对应行，两者之间用一个空格分开。黑色小方块用 b 表示，白色小方块用 o 表示。 输出：输出文件的每一行对应输入文件的每一个图案变换对。其中每行开始的整数表示对应图案对在 输入文件中出现的序号，紧跟一个空格，然后就是该图案对的最小变换，采用上述记号表示。 备注：为了比较不同变换的大小，定义：旋转变换的代价小于映像变换，小角度旋转变换的代价小于 大角度旋转变换，保持变换的代价最小。注意：对本题而言，只有上面列出的变换是合法的，如果某 个图案对可以由多个变换得到，则应选择代价最小的变换

示例 输 boob。ooob ooobo oboro oobob ooboo oooob boob oooobb boooob booboo bobooo bboobo oboobo ooboob oo booo oobe boob bboo oooo o000 bboo boob oobe boooo oboro 00000 oboro ooboo ooobo ooooh oooob boooo oboo oobe obob booo 000000bb 输出 I rot90 2 rot270 3 idt 4 vr 7 rot180

3 示例 输入： 5 booob oooob obooo ooobo ooobo obooo oobob ooboo oooob bboob 6 oooobb boooob oooboo bobooo bboobo oboobo oobooo ooobob oooboo oobooo ooboob oobooo 2 bo bo ob ob 4 oobo ooob bboo oooo oooo bboo ooob oobo 5 boooo obooo obooo ooboo obooo ooboo ooobo oooob oooob boooo 4 oboo oobo obob booo oooo oobb oobo oooo 2 oo bb bb oo 输出： 1 rot90 2 rot270 3 idt 4 vr 5 imp 6 vr-rot270 7 rot180

试题4在计算机辅助设计CAD)中,有一个经典问题:消除隐藏线(被其它图形遮住的线段)。你需要 设计一个软件,帮助建筑师绘制城市的侧视轮廓图。为了方便处理,限定所有的建筑物都是矩形的, 而且全部建立在同一水平面上。每个建筑物用一个三元组表示(Li,Hi,Ri)其中Li和Ri分别是建 筑物i的左右边缘坐标,H是建筑物i的高度。 下面左图中的建筑物分别用如下三元组表示: (1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28) 下面右图中的城市侧视轮廓线用如下的序列表示: (1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0) 输入:输入文件中包含一系列的建筑物三元组。建筑物的坐标都是正整数且不大于1000。建筑物的数 目不会超过50。每行只有一个三元组。三元组的每个元素之间用一个空格分开。三元组按照Li排序, 即左边缘坐标最小的建筑物三元组会出现在输入文件的第一行。 输出:输出文件中包含一行描述轮廓线的数值序列,其中偶元素代表轮廓线的延伸高度,奇元素代表 轮廓线顶点的水平坐标,如上面的图例所示。 示例 输入: 1115 267 3139 12716 14325 191822 231329 24428 输出: 1113139012716319182232313290

4 试题 4 在计算机辅助设计(CAD)中，有一个经典问题：消除隐藏线（被其它图形遮住的线段）。你需要 设计一个软件，帮助建筑师绘制城市的侧视轮廓图。为了方便处理，限定所有的建筑物都是矩形的， 而且全部建立在同一水平面上。每个建筑物用一个三元组表示（Li, Hi, Ri）其中 Li 和 Ri 分别是建 筑物 i 的左右边缘坐标，Hi 是建筑物 i 的高度。 下面左图中的建筑物分别用如下三元组表示： (1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28) 下面右图中的城市侧视轮廓线用如下的序列表示： （1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0） 输入：输入文件中包含一系列的建筑物三元组。建筑物的坐标都是正整数且不大于 1000。建筑物的数 目不会超过 50。每行只有一个三元组。三元组的每个元素之间用一个空格分开。三元组按照 Li 排序， 即左边缘坐标最小的建筑物三元组会出现在输入文件的第一行。 输出：输出文件中包含一行描述轮廓线的数值序列，其中偶元素代表轮廓线的延伸高度，奇元素代表 轮廓线顶点的水平坐标，如上面的图例所示。 示例 输入： 1 11 5 2 6 7 3 13 9 12 7 16 14 3 25 19 18 22 23 13 29 24 4 28 输出： 1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

试题5也许是因为有10个手指的原因,所以我们把0~9十个数字组合起来表达任意的数值,但这 并不是唯一可能的记数法。在某个外星球居住着一种智慧生物,他们的手跟我们的手构造不同,他们 的记数法也很奇特。他们用三个记号0,1,2的组合来表达数值,这三个记号分别对应数值0,1-1。在 他们的数值系统中,每个数位是右边相邻数位的3倍。因此数10-表示数值8(因为8=1×9+0×3 +-1×1),数-1表示数值-2(因为-2=-1×3+1×1)。 编写程序,读入一组231至231-1之间的数值,输出对应的外星球数值表示。 输入:每行一个10进制数值 输出:每行一个与输入文件对应的外星球数值表示 示例 输入: 2 17 l024 2147483648 输出: 111-0-1 I011010001l-11-1 试题6逻辑表达式有如下形式: (1)原子式,用一个区分大小写的字母表示; (2)组合式:若A和B是逻辑表达式,则(AB)也是,意为“A或B”:(A&B)意为“A和B”; A意为“非A”;(A->B)意为“A推出B”,或等价的“B或非A”。 以上表达式的形式是固定的,其中的括号不能缺少,且字符间没有空格。 对于某个逻辑表达式,如果变换其中原子式的取值(真或假),该表达式的整体取值可能为真,则 称这样的逻辑表达式是可满足的,否则是不可满足的。比如下面的表达式都是可满足的: q (al(b&c)) (-a)->z) 而这些是不可满足的 (q&-q) ((a4-b)&(~alb)&(a&-b)

5 试题 5 也许是因为有 10 个手指的原因，所以我们把 0～9 十个数字组合起来表达任意的数值，但这 并不是唯一可能的记数法。在某个外星球居住着一种智慧生物，他们的手跟我们的手构造不同，他们 的记数法也很奇特。他们用三个记号’0’,’1’,’-’的组合来表达数值，这三个记号分别对应数值 0,1,-1。在 他们的数值系统中，每个数位是右边相邻数位的 3 倍。因此数’10-’表示数值 8（因为 8＝1×9＋0×3 ＋－1×1），数’-1’表示数值-2（因为-2= -1×3＋1×1）。 编写程序，读入一组-231 至 231－1 之间的数值，输出对应的外星球数值表示。 输入：每行一个 10 进制数值 输出：每行一个与输入文件对应的外星球数值表示 示例 输入： 10 2 -17 42 1024 -2147483648 输出： 101 1- -101 1---0 111-0-1 -10110100011---1-1--1 试题 6 逻辑表达式有如下形式： （1）原子式，用一个区分大小写的字母表示； （2）组合式；若 A 和 B 是逻辑表达式，则(A|B)也是，意为“A 或 B”；(A&B)意为“A 和 B”； ~A 意为“非 A”；(A->B)意为“A 推出 B”，或等价的“B 或非 A”。 以上表达式的形式是固定的，其中的括号不能缺少，且字符间没有空格。 对于某个逻辑表达式，如果变换其中原子式的取值（真或假），该表达式的整体取值可能为真，则 称这样的逻辑表达式是可满足的，否则是不可满足的。比如下面的表达式都是可满足的： q (a|(b&c)) ((a&~a)->z) 而这些是不可满足的： (q&~q) (((a|~b)&(~a|b))&(a&~b))