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

湖南省首届“湘邮科技杯”大学生程序设计大赛试题 试题1n个人围成一圈,并依次编号1~n,。从编号为1的人开始,按顺时针方向每隔一人选出一个, 剩下的人重新围成一圈,如此循环直到剩下两人,这剩下的两人就是幸运儿。如果你想成为最后两个 幸运儿,请问开始时应该站在什么位置?(设3(2,6),意为该字符串首字母在字符矩 阵中的位置是第1列2行,尾字母在字符矩阵中的位置是第2列6行 备注:如果某个字符串在字符阵列中出现多次,则只记录任意一个出现位置即可。字符串出现的形式 可能是水平、竖直、向前、向后和斜向。输出的位置顺序应该与输入中的字符串出现顺序一致 区分字符的大小写

1 湖南省首届“湘邮科技杯”大学生程序设计大赛试题 试题 1 n 个人围成一圈, 并依次编号 1～n，。从编号为 1 的人开始，按顺时针方向每隔一人选出一个， 剩下的人重新围成一圈，如此循环直到剩下两人，这剩下的两人就是幸运儿。如果你想成为最后两个 幸运儿，请问开始时应该站在什么位置？（设 3(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))

编写程序,判断某个逻辑表达式的可满足性。 输入:每一行都是一个逻辑表达式(整个表达式最多10个原子式,且不超过150个字符) 输出:每行包含一个字符,’y'表示输入文件对应行中的逻辑表达式是可满足的,或者'n表示输入文件 对应行中的逻辑表达式是不可满足的 示例 输入 (a(b&c)) (4-b)&(-a|b)&(a&-b) 输出: 试题7一家银行希望采用光学字符识别系统自动读出支票中的账号,组成账号的每个数字都是7段数 位体。一种图象处理软件可以将组成数字的横段和竖段分别转换成 ASCII码中的竖线“’和下划线 如果显示正常,则10个数字的序列应该具有如下形态 支票中的账号有9位数字,但由于光学扫描装置可能会漏检某些数位段,所以9位数字未必都能正确 地被扫描转换成对应的∵字符形式。为了容错和纠错,对于一个9位账号d9d8.d,设定其校 验条件为 (dl+2d2+3d3+….+9d9) mod 11=0 你需要设计一个程序,从扫描转换的结果推测原始的账号,假定 (1)若经扫描转换的某组数字全部保存了正确的数字形式而且满足校验条件,则该组数字就是原 始的账号 2)9位数中最多只有一位在扫描转换中失去正确的数字形式 (3)扫描转换不会引入额外的数位段 当检测到数位段时,扫描转换程序将输出ASCI码的'或'’;当检测到空白区域时,将输出∵’。比如 下面的扫描转换结果:

6 编写程序，判断某个逻辑表达式的可满足性。 输入：每一行都是一个逻辑表达式（整个表达式最多 10 个原子式，且不超过 150 个字符） 输出：每行包含一个字符，’y’表示输入文件对应行中的逻辑表达式是可满足的，或者’n’表示输入文件 对应行中的逻辑表达式是不可满足的； 示例 输入： q (a|(b&c)) ((a&~a)->z) (q&~q) (((a|~b)&(~a|b))&(a&~b)) 输出： y y y n n 试题 7 一家银行希望采用光学字符识别系统自动读出支票中的账号，组成账号的每个数字都是 7 段数 位体。一种图象处理软件可以将组成数字的横段和竖段分别转换成 ASCII 码中的竖线‘|’和下划线 ‘_’。如果显示正常，则 10 个数字的序列应该具有如下形态： 支票中的账号有 9 位数字，但由于光学扫描装置可能会漏检某些数位段，所以 9 位数字未必都能正确 地被扫描转换成对应的 ’|’ ’_’字符形式。为了容错和纠错，对于一个 9 位账号 d9d8…d1，设定其校 验条件为： (d1+2d2+3d3+…+9d9) mod 11 = 0 你需要设计一个程序，从扫描转换的结果推测原始的账号，假定： (1) 若经扫描转换的某组数字全部保存了正确的数字形式而且满足校验条件，则该组数字就是原 始的账号； (2) 9 位数中最多只有一位在扫描转换中失去正确的数字形式； (3) 扫描转换不会引入额外的数位段。 当检测到数位段时，扫描转换程序将输出 ASCII 码的’|’或’_’；当检测到空白区域时，将输出’.’。比如 下面的扫描转换结果：

正确的推测值是123456789,其中的第2位经扫描转换后失去正确的数字形式,既像2又像3,如果令 其为3则与校验条件冲突;其中的第5位虽然保存了正确的数字形式,但既可能是5也可能是6,但 如果令其为6,则与上面的假定2冲突。 输入:输入文件中包含一组用ASCI字符表示的账号。每个账号占3行,每位数字占3列,每行27 个字符。没有空行,也没有空格。 输岀:每行代表一个账号的推测值。账号的顺序和数目与输入文件一致。如果没有找到合理值,则输 出 failure';如果找到多个合理的推测,则输出' ambiguous' 示例 输入 ·|·l ·|_|l|.∴· ll_|_l_|l_|_| _1.__1 _…|LlL_||l_|Ll 输出 123456789 ambiguous failure 878888888 试题8我军特工探知了敌军的信息加密方式,但尚未获得密钥。已知敌军所有的信息都是码值在1 127之内的ASCI字符。敌军以5个字符为单位加密信息。设 pOple2p3p4是5个待加密的字符,敌军 将这5个字符与另外9个密钥k0.k8混合起来产生对应的5个整数型密文e0,,e4。已知这9个密 钥也是码值在1-127间的ASCI字符。其混合原则如下 e=p·k+p1·k+1+p·k+2+·k+3+p4·k+4 我军特工以生命为代价换来了一小串明文和对应的密文。你的任务是找到密钥,并破解另一组被我军 截获的敌军密文

7 正确的推测值是 123456789，其中的第 2 位经扫描转换后失去正确的数字形式，既像 2 又像 3，如果令 其为 3 则与校验条件冲突；其中的第 5 位虽然保存了正确的数字形式，但既可能是 5 也可能是 6，但 如果令其为 6，则与上面的假定 2 冲突。 输入：输入文件中包含一组用 ASCII 字符表示的账号。每个账号占 3 行，每位数字占 3 列，每行 27 个字符。没有空行，也没有空格。 输出：每行代表一个账号的推测值。账号的顺序和数目与输入文件一致。如果没有找到合理值，则输 出’failure’；如果找到多个合理的推测，则输出’ambiguous’。 示例 输入: 输出: 123456789 ambiguous failure 878888888 试题 8 我军特工探知了敌军的信息加密方式，但尚未获得密钥。已知敌军所有的信息都是码值在 1－ 127 之内的 ASCII 字符。敌军以 5 个字符为单位加密信息。设 p0p1p2p3p4 是 5 个待加密的字符，敌军 将这 5 个字符与另外 9 个密钥 k0,…,k8 混合起来产生对应的 5 个整数型密文 e0,…,e4。已知这 9 个密 钥也是码值在 1－127 间的 ASCII 字符。其混合原则如下： 我军特工以生命为代价换来了一小串明文和对应的密文。你的任务是找到密钥，并破解另一组被我军 截获的敌军密文

输入:第一行是一串大于10个字符的明文。第二行是明文中前5个字符对应的密文,分别是用空格分 开的5个整数;第三行是明文中第6个到第10个字符对应的密文,分别是用空格分开的5个整数。然 后是一个空行。后续的每一行都是用空格分开的5个整数,代表需要你破解的5个密文字符。 输出:按顺序给出输入文件中需要你破解的密文对应的明文。 备注:已知10个明文字符和对应的密文就足以找到密钥。 示例 输入 John Q. Crackjack 3009628880326623421736518 2242623187289342787729942 3439135683399564065745237 3304430700349233713338330 3720037645430554369847491 3257430389352253697838050 输出 Squeamish ossifrage

8 输入：第一行是一串大于 10 个字符的明文。第二行是明文中前 5 个字符对应的密文，分别是用空格分 开的 5 个整数；第三行是明文中第 6 个到第 10 个字符对应的密文，分别是用空格分开的 5 个整数。然 后是一个空行。后续的每一行都是用空格分开的 5 个整数，代表需要你破解的 5 个密文字符。 输出：按顺序给出输入文件中需要你破解的密文对应的明文。 备注：已知 10 个明文字符和对应的密文就足以找到密钥。 示例 输入: John Q. Crackjack 30096 28880 32662 34217 36518 22426 23187 28934 27877 29942 34391 35683 39956 40657 45237 33044 30700 34923 37133 38330 37200 37645 43055 43698 47491 32574 30389 35225 36978 38050 输出: Squeamish ossifrage