大学生程序设计大赛试题

1湖南省首届“湘邮科技杯”大学生程序设计大赛试题试题1n个人围成一圈,并依次编号1～n，。从编号为1的人开始，按顺时针方向每隔一人选出一个，剩下的人重新围成一圈，如此循环直到剩下两人，这剩下的两人就是幸运儿。如果你想成为最后两个幸运儿，请问开始时应该站在什么位置？（设3=n=50）输入：开始时的人数n输出：第1行是选出顺序，第2行是两名幸运儿的开始位置（按升序排列），位置编号之间用一个空格分开。示例输入：12应该的输出：246810123711519试题2在二维字符阵列中寻找指定的字符串。输入：前两行分别指示字符矩阵的宽w和高h（1=w=80且1=h=80）。接下来的h行每行w个字符便是字符矩阵的内容，再下面的1行为要寻找的字符串的数目n（n10），其后的n行便是要寻找的字符串，每个字符串不会超过20个字符。输出：n行，每行保存1个字符串的位置。位置的格式形如(1,2)-(2,6)，意为该字符串首字母在字符矩阵中的位置是第1列2行，尾字母在字符矩阵中的位置是第2列6行。备注：如果某个字符串在字符阵列中出现多次，则只记录任意一个出现位置即可。字符串出现的形式可能是水平、竖直、向前、向后和斜向。输出的位置顺序应该与输入中的字符串出现顺序一致。区分字符的大小写。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表示。输出：输出文件的每一行对应输入文件的每一个图案变换对。其中每行开始的整数表示对应图案对在输入文件中出现的序号，紧跟一个空格，然后就是该图案对的最小变换，采用上述记号表示。备注：为了比较不同变换的大小，定义：旋转变换的代价小于映像变换，小角度旋转变换的代价小于大角度旋转变换，保持变换的代价最小。注意：对本题而言，只有上面列出的变换是合法的，如果某个图案对可以由多个变换得到，则应选择代价最小的变换。3示例输入：5booobooooboboooooobooooboobooooobobooboooooobbboob6oooobbbooooboooboobobooobboobooboobooobooooooboboooboooobooooobooboobooo2boboobob4ooboooobbboooooooooobboooooboobo5booooobooooboooooboooboooooboooooboooooboooobboooo4obooooboobobbooooooooobboobooooo2oobbbboo输出：1rot902rot2703idt4vr5imp6vr-rot2707rot1804试题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排序，即左边缘坐标最小的建筑物三元组会出现在输入文件的第一行。输出：输出文件中包含一行描述轮廓线的数值序列，其中偶元素代表轮廓线的延伸高度，奇元素代表轮廓线顶点的水平坐标，如上面的图例所示。示例输入：11152673139127161432519182223132924428输出：11131390127163191822323132905试题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进制数值输出：每行一个与输入文件对应的外星球数值表示示例输入：102-17421024-2147483648输出：1011--1011---0111-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))6编写程序，判断某个逻辑表达式的可满足性。输入：每一行都是一个逻辑表达式（整个表达式最多10个原子式，且不超过150个字符）输出：每行包含一个字符，’y’表示输入文件对应行中的逻辑表达式是可满足的，或者’n’表示输入文件对应行中的逻辑表达式是不可满足的；示例输入：q(a|(b&c))((a&~a)-z)(q&~q)(((a|~b)&(~a|b))&(a&~b))输出：yyynn试题7一家银行希望采用光学字符识别系统自动读出支票中的账号，组成账号的每个数字都是7段数位体。一种图象处理软件可以将组成数字的横段和竖段分别转换成ASCII码中的竖线‘|’和下划线‘_’。如果显示正常，则10个数字的序列应该具有如下形态：支票中的账号有9位数字，但由于光学扫描装置可能会漏检某些数位段，所以9位数字未必都能正确地被扫描转换成对应的’|’’_’字符形式。为了容错和纠错，对于一个9位账号d9d8…d1，设定其校验条件为：(d1+2d2+3d3+…+9d9)mod11=0你需要设计一个程序，从扫描转换的结果推测原始的账号，假定：(1)若经扫描转换的某组数字全部保存了正确的数字形式而且满足校验条件，则该组数字就是原始的账号；(2)9位数中最多只有一位在扫描转换中失去正确的数字形式；(3)扫描转换不会引入额外的数位段。当检测到数位段时，扫描转换程序将输出ASCII码的’|’或’_’；当检测到空白区域时，将输出’.’。比如下面的扫描转换结果：7正确的推测值是123456789，其中的第2位经扫描转换后失去正确的数字形式，既像2又像3，如果令其为3则与校验条件冲突；其中的第5位虽然保存了正确的数字形式，但既可能是5也可能是6，但如果令其为6，则与上面的假定2冲突。输入：输入文件中包含一组用ASCII字符表示的账号。每个账号占3行，每位数字占3列，每行27个字符。没有空行，也没有空格。输出：每行代表一个账号的推测值。账号的顺序和数目与输入文件一致。如果没有找到合理值，则输出’failure’；如果找到多个合理的推测，则输出’ambiguous’。示例输入:输出:123456789ambiguousfailure878888888试题8我军特工探知了敌军的信息加密方式，但尚未获得密钥。已知敌军所有的信息都是码值在1－127之内的ASCII字符。敌军以5个字符为单位加密信息。设p0p1p2p3p4是5个待加密的字符，敌军将这5个字符与另外9个密钥k0,…,k8混合起来产生对应的5个整数型密文e0,…,e4。已知这9个密钥也是码值在1－127间的ASCII字符。其混合原则如下：我军特工以生命为代价换来了一小串明文和对应的密文。你的任务是找到密钥，并破解另一组被我军截获的敌军密文。8输入：第一行是一串大于10个字符的明文。第二行是明文中前5个字符对应的密文，分别是用空格分开的5个整数；第三行是明文中第6个到第10个字符对应的密文，分别是用空格分开的5个整数。然后是一个空行。后续的每一行都是用空格分开的5个整数，代表需要你破解的5个密文字符。输出：按顺序给出输入文件中需要你破解的密文对应的明文。备注：已知10个明文字符和对应的密文就足以找到密钥。示例输入:JohnQ.Crackjack300962888032662342173651822426231872893427877299423439135683399564065745237330443070034923371333833037200376454305543698474913257430389352253697838050输出:Squeamishossifrage.湖南省第二届“软考杯”大学生程序设计大赛试题试题1人类的大脑是按功能分区的。正常人的大脑分区都是活跃的，分区之间有着广泛的神经连接；而脑病患者的某些大脑分区则是不活跃的，处于“睡眠”状态。最近的研究发现：如果某个“睡眠”分区X与其它至少3个活跃分区保持连接1年时间，则分区X会“苏醒”过来，恢复成活跃状态。“苏醒”后的分区不会再转入“睡眠”状态。有位病人的大脑分区都处于“睡眠状态”。经用一种新方法治疗后，其中3个分区同时“苏醒”过来。根据上文的结论，若不再进行治疗则其它分区经过多少年也能全部“苏醒”过来？输入：输入文件的第1行仅包含1个整数M，取值范围是[3,26]，它表示病人大脑的分区数。第2行也只包含1个非负整数N，它表示分区之间的连接数（如果分区A与分区B相连，则分区B也与分区A相连。由于这样的连接是等价的，所以只计数1次）。第3行包含3个相邻的英文字母，分别代表刚刚同时“苏醒”的3个分区。第4行中包含N个用空格分割的字符串，每个字符串包含2个英文字母，分别代表2个相连接的分区。输出：如果该病人的大脑分区经过若干年后能够全部“苏醒”，请在输出文件中按格式输出一行：“WAKEUPINnYEARS”（其中n指分区全部“苏醒”需要的年数）如果该病人的大脑分区无法全部“苏醒”，请在输出文件中按格式输出一行：“THISBRAINNEVERWAKESUP”示例输入：611HABABACAHBDBCBFCDCFCHDFFH输出：WAKEUPIN3YEARS试题2测绘人员将卫星拍摄的地面遥感图像转换成了数值方阵。方阵中的每个元素都是正整数，代表某单位面积土地上的植物类型。元素为质