软件大赛集训练习题

做每一道题之前，请在心里“大声”默念：我用什么态度编程序，就在用什么方式走人生！软件大赛集训练习题参加北京决赛的同学重点做以下题目：2,4,9,14,16,18,19,20,22,23,24,26,28,29,31,32,34,36,37,42,43,46,47同学们做过的每一道题的程序最好都保留起来：一则你做的不一定对，以后可能发现其中有错误；二则可以作为“成长日记”，一两年之后你会发现，“咦，我当年写的程序这么好笑！”1、一个字符串中，哪个子串（长度要求大于等于2）重复出现次数最多，如果有多个子串重复次数相同，取长度最大的子串。例如：“abcfabcdabce”中“abc”出现3次，而且最长。2、字符串排序。字符串存放在二维字符数组中，按字典顺序排序。例如：chara[][10]={“bacd”,“bad”，“bacde”,“abc”}排序后成为{“abc”，“bad”，“bacd”,“bacde”}3、输出字符串中不重复的子串。例如：“aaab”中,不重复的子串有“a”“aa”“aaa”“aaab”“aab”“ab”“b”。4、输出两个字符串中的最长公共子串。例如：“abcfabcd”和“abcdabce”中最长公共子串为“abcd”。5、输出1到n之间，两个数相加可到的“各位相同的数（一定是大于10）”的所有情况。例如：设n取20，则输出：1+10=112+9=113+8=11……2+20=223+19=224+18=22……13+20=3314+19=3315+18=33……6、求100！这个数的末尾有多少个零。7、求n个数（每个数小于100，n小于20）的最小公倍数。8、富老师统计缺考人数问题：学生考试结束之后，富老师将所有交卷的人（多个班在一起）的学号已经排好序放在数组中，请统计有几人缺考。chara[][5]={“0101”，“0103”，“0104”，“0106”，……,“0201”，“0202”，“0205”，“0206”，……}学号“0103”表示1班3号，[“0202”，“0205”]表示2班3、4号缺考。有几个班级不一定，每班的第1号和最后一号（不一定是几号）一定不会缺考。一个班最多30人，不可能整个班一起缺考。9、富老师的选择题答案问题：富老师考试的时候仅出单项选择题，答案在A~D之间，学生的答案存在二维数组中。chara[][11]={“ABCDCBCDAA”,“BBCDABCDCA”,“ACCDABCDAC”,“CBCDDBBDDB”}富老师出题太难，学生的成绩不理想，富老师决定修改“标准答案”，使得所有学生都能及格并且平均分尽量高，请问是否存在这样的“标准答案”，如果存在多个，请输出平均分最高的“标准答案”。10、一维数组中存有奇数和偶数，将奇数在奇数的位置上从大到小排序，将偶数在偶数的位置上“前后翻转”。例如：处理前chara[10]={1，8，12，2，5，6，7，10，9，4}，处理后chara[10]={9，4，10，6，7，2，5，12，1，8}11、n*n二维数组，按对角线从小到大排序。12、二维数组中，哪一行或哪一列的连续存放的0的个数最多，是几个0。注意，是“连续”。13、二维数组中，有些矩形区域中存放的都是0，输出其中最大的矩形区域的“面积”。14、上一题中，如果区域不要求是矩形，可以是不规则的区域（上下左右相连都为0即算在一个区域中）。计算其中最大的区域的“面积”。例如：二维数组包含如下数据：01011000011000101001000101010010则区域的“面积”为12。15、富老师的集训时间问题：富老师又要集训了！（咦，我为什么要说“又”？）现在给出富老师的课表（3行7列的二维数组，代表一周的上午下午晚上，0表示没课，1表示有课）和15个学生的课表（3行7列*15的三维数组），选出富老师有时间（学生的课表差异很大，有些学生可能没时间）且有课学生数量最少的k个时间点。k个时间点按有课学生数量从少到多排序，并且在有课学生数量相同的情况下，上午时间点排在晚上的前面，晚上时间点排在下午的前面。16、模拟排队问题：放假了要买火车票回家，有三个售票窗口，人很多，要排队。每个人买票都要3分钟完成，每个人自动会选择“最优”的队来排，给定n个人到来的时间，放在数组a中，问最后一个人买完票的时刻。例如：inta[7]={2，3，4，4，4，5，6}则最后一个人买完票的时刻为11。17、黑白棋哪个位置翻子最多判定。18、国际象棋棋盘上放了n个后，一个车想从x1y1位置走到x2y2位置，怎样走不会被后攻击。19、二维数组中的最大“相似三角形”问题。例如：11711231421306006910其中的123和369就形成相似三角形（即其中元素等比例）。输出最大的相似三角形包含的元素个数。上例中输出3。20、在上题中，假设三角形要考虑可以旋转的情况。例如其中的123和426就形成“旋转相似三角形”（即其中元素旋转90度、180度、270度后形成“相似三角形”）。输出最大的“旋转相似三角形”包含的元素个数。21、“点阵”三维数组中存放0~9数字的“点阵”，例如：数字1的点阵为6*3的数字010110010010010111依据此“点阵”，在屏幕上输出“2010”的字样。22、公共汽车载人问题：公共汽车全程一费，车的载客量不超过n，汽车途中共有1~k个站，共有m个乘客要在不同的站上车下车，问设计一个载客方案，保证收入最高（就是在不超载的情况下，为了多赚钱，选择一下拒载那些人）。m个乘客的上车站和下车站在二维数组中存放。例如：inta[][2]={{1，3}，{3，4}，{4，8}，{5，6}}表示第1个乘客在第1站上车，在第3站下车；第2个乘客在第3站上车，在第4站下车。23、背包问题：有一个背包，可装重量为w的物品；有n个物品，每个物品重量不同，存在数组a[n]中。问选择那些物品，可以将背包装的尽量满（不能超过w的最大装载方案。）24、富老师折腾水：富老师有两个桶，可以装3升、5升水，水有无限多，问怎样折腾出4升水，输出折腾过程。25、富老师跳格游戏：富老师玩跳格游戏，规则如下：从起点开始，每次可以向前跳最多k个格，每个格子中有0到n的数字，如果富老师所在的格子中有数字i,则下一次富老师最多跳k+i个格，问富老师最少几次可以跳到终点。例如：下图所示的情况，k=3时，富老师最少4次跳到终点。S0021003010000E26、富老师乱跳格游戏：富老师玩乱跳格游戏，规则如下：格子是二维的，起点在左上角，终点在右下角，每次只能向右或向下跳，其他和上面一样，问富老师最少几次可以跳到终点。27、富老师做水槽：富老师想做一个容积为C的长方体水槽，水槽没有盖，有五块铁板焊接而成，要求每块铁板的长宽都必须为整数，问如何设计水槽的长宽高使得富老师最省钱。28、富老师的水槽“套娃”：富老师作了一堆具有各种长宽高的水槽，为了节省空间，富老师想到了“套娃”，富老师让你帮忙算一下，这些水槽最多能套几层。水槽的长宽高存在数组中，例如：inta[][2]={{5，6，5},{5，3，3},{3，2，2},{1，1，4},{7,8,9}}这些水槽最多能套3层。29、填字游戏：给定一些单词，例如:eat,each,every,apply,apple,pop,good……每个单词长度都大于等于2，是将上述单词填入下面的格中，确定有问号的格子应该填那些字母。注意格子中的单词之间没有任何空格或标点符号。e???ap?p?e??od例如：上述的格子中应该填eachapplegood。30、富老师儿子的玩具问题：富老师的儿子有超多的玩具，玩具分为n类，每类最多m个，每个玩具被编上号（1号到k号），那个玩具属于哪一类由数组a[n][m]来确定，例如：数组a[3][3]={{1,3,6},{2,4,0},{5,7,0}}表示1、3、6号玩具属于第一类，第二类玩具包括2和4号玩具，第三类玩具包括5和7号玩具。还有一个数组b[n]记录每类玩具玩过之后几天之内不会再玩，例如：数组b[3]={3，2，2}表示玩过第一类玩具之后，3天之内不会再玩第一类了；玩过第二类玩具之后，2天之内不会再玩第二类了……富老师的儿子每天只玩一个玩具，而且每个玩具玩过之后7天内绝不再玩。现在给定一个几天内各计划玩那个玩具的序列，判定其是否“合法”。例如：序列7，2，3，5，4是个“合法”序列。序列1，2，5，3，4是个“非法”序列。更进一步，如果某个序列是“合法”的，试给出下一天可以玩几号玩具。31、又一个富老师儿子的玩具问题：由于富老师不能给出一个“合法”玩具序列，所以不得不给儿子买了一个新玩具：“22世纪高科技新产品”—“积木”。每个积木的平面形状由一个4*4的数组描述（高度忽略），如下所示：1110/*B*/011000100010所有n个积木的平面形状由一个n*4*4的三维数组描述。“22世纪高科技新产品”有新的游戏规则：A积木块如果要放在B积木块的上面，则要求A积木块的每个组成部分（4*4数组中的1）必须放在B积木块的某个组成部分之上，不许悬空。例如上述数组是B积木块,而A积木的数组如下：1111/*A*/001000100010则A积木块无法放在B积木块的上边。最后的问题是，给定n个积木块的形状，问最多可以搭几层？注意：为了搭的更高，每个积木块都可以进行旋转、平移、翻转等操作。例如:C积木块如下：1100110010000000经过翻转、平移之后，C积木块可以放在B积木块之上。/*富老师提示：为了降低难度，可先完成平移功能，成功之后，再增加旋转、翻转等操作。*/32、富老师教儿子认星座：一般的玩具已经搞不定富老师的儿子了，这次他要天上的星星！？富老师这样教育儿子：“哪可不行！因为……天上的星星……不单卖！！,必须成套卖，一次卖一个‘星座’，我先教你认识这些星座吧……”天上所有星星（n个）的坐标（二维的，用（x,y）方式表示）存在a[n][2]数组中，给定一个星座图上的“三角星座”坐标（由三个点组成（x1,y1），（x2,y2），（x3,y3）），问天上的哪三颗星星组成了“三角星座”。/*富老师提示：问题简单点说，其实是要从ｎ个点中找出三个点，它们组成的三角型与星座图上给出的三角型是“相似三角形”就OK。要注意旋转带来的问题*/如果是“四边星座”，问题要怎样解？33、人机猜数游戏由计算机“想”一个四位数，请人猜这个四位数是多少。人输入四位数字后，计算机首先判断这四位数字中有几位是猜对了，并且在对的数字中又有几位位置也是对的，将结果显示出来，给人以提示，请人再猜，直到人猜出计算机所想的四位数是多少为止。例如：计算机“想”了一个“1234”请人猜，可能的提示如下：人猜的整数计算机判断有几个数字正确有几个位置正确112221334421331230412340124342123444游戏结束请编程实现该游戏。游戏结束时，显示人猜一个数用了几次。34、人机猜数游戏(2)将以上游戏（33、人机猜数游戏）双方倒一下，请人想一个四位的整数，计算机来猜，人给计算机提示信息，最终看计算机最少用几次猜出一个人“想”的数。请编程实现。35、兔子产子从前有一对长寿兔子，它们每一个月生一对兔子，新生的小兔子两个月就长大了，在第二个月的月底开始生它们的下一代小兔子，这样一代一代生下去，求解兔子增长数量的数列。如果每对兔子仅会产4对兔子，然后就不再生产，求解兔子增长数量的数列。如果再加上“每对兔子仅能活12个月”这个条件，求解兔子增长数量的数列。36、选美比赛在选美大奖赛的决赛现场，有一批选手参加比赛，比赛的规则是最后得分越高，名次越低。当决赛结束时，要在现场按照选手的出场顺序宣布最后得分和最后名次，获得相同分数的选手具有相同的名次，名次连续编号，不用考虑同名次的选手人数。例如：选手序号：1，2，3，4，5，6，7选手得分：5，3，4，7，3，5，6则输出名次为：3，1，2，5，1，3，4请编程帮助大奖赛组委会完成决赛的排名工作。37、满足特异条件的数列输入m和n(20