软件大赛集训练习题-修订版

做每一道题之前，请在心里“大声”默念：
我用什么态度编程序，就在用什么方式走人生路！
同学们根据自己的实际情况量力而行，选择相应的题目来练习，不能因为题目较多就想一口吃成富老师那样（啊，我是说编程能力，不是体重），特别是低年级同学，编程熟练程度是逐步训练出来的，不是一两个月就能搞定的，欲速则不达，短学期做不完，放假回家接着做，开学后接着做，毕了业接着做（题海无涯苦作舟）。

同学们之间要多交流，“这个题目我是这样做的，你是怎样做的……我的方法有漏洞没有，你的方法有错误没有……”
参加北京决赛的同学重点做以下题目：
1,2,4,14,16,18,19,20,22,23,24,26,28,29,31,32,34,36,37,42,43 ,46,47,49
刚入门的同学先做以下题目：
10、6、8、12、13、21、30、5、11、25、35、36、40、41
同学们做过的每一道题的程序最好都保留起来：一则你做的不一定对，以后可能发现其中有错误；二则可以作为“成长日记”，一两年之后你会发现，“咦，我当年写的程序这么好笑！”；三则可以计算自己累积的编码量，记住：一个优秀的计算机专业本科生大学四年的编码要求是-—4万行！
/* ACM竞赛的题目算法都比较难，所以代码量可以按3到5倍放大，那也意味着８千行的竞赛代码，大约是100至200道ACM竞赛题，大家可以用做题量作为尺子衡量一下自己。

*/
软件大赛集训练习题
1、一个字符串中，哪个子串（长度要求大于等于2）重复出现次数最多，如果有多个子串重复次数相同，取长度最大的子串。

例如：“abcfabcdabce”中“abc”出现3次，而且最长。

2、字符串排序。

字符串存放在二维字符数组中，按字典顺序排序。

例如：char a[][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=11 2+9=11 3+8=11 ……
2+20=22 3+19=22 4+18=22 ……
13+20=33 14+19=33 15+18=33 ……
6、求100！这个数的末尾有多少个零。

7、求n个数（每个数小于100，n小于20）的最小公倍数。

8、富老师统计缺考人数问题：
学生考试结束之后，富老师将所有交卷的人（多个班在一起）的学号已经排好序放在数组中，请统计有几人缺考。

char a[][5]={“0101”，“0103”，“0104”，“0106”，……,“0201”，“0202”，“0205”，“0206”，……}
学号“0103”表示1班3号，[“0202”，“0205”]表示2班3、4号缺考。

有几个班级不一定，每班的第1号和最后一号（不一定是几号）一定不会缺考。

一个班最多30人，不可能整个班一起缺考。

9、富老师的选择题答案问题：
富老师考试的时候仅出单项选择题，答案在A~D之间，学生的答案存在二维数组中。

char a[][11]={“ABCDCBCDAA”,“BBCDABCDCA” ,“ACCDABCDAC” ,“CBCDDBBDDB”}
富老师出题太难，学生的成绩不理想，富老师决定修改“标准答案”，使得所有学生都能及格并且平均分尽量高，请问是否存在这样的“标准答案”，如果存在多个，请输出平均分最高的“标准答案”。

10、一维数组中存有奇数和偶数，将奇数在奇数的位置上从大到小排序，将偶数在偶数的位置上“前后翻转”。

例如：处理前char a[10]={1，8，12，2，5，6，7，10，9，4}，
处理后char a[10]={9，4，10，6，7，2，5，12，1，8}
11、n*n二维数组，按对角线从小到大排序。

12、二维数组中，哪一行或哪一列的连续存放的0的个数最多，是几个0。

注意，是“连续”。

13、二维数组中，有些矩形区域中存放的都是0，输出其中最大的矩形区域的“面积”。

14、二维数组中，有些矩形区域中存放的都是0，输出其中最大的区域的“面积”,区域不要求是矩形，可以是不规则的区域（上下左右相连都为0即算在一个区域中）。

计算其中最大的区域的“面积”。

例如：二维数组包含如下数据：
0 1 0 1 1 0 0 0
0 1 1 0 0 0 1 0
1 0 0 1 0 0 0 1
0 1 0 1 0 0 1 0
则区域的“面积”为12。

15、富老师的集训时间问题：
富老师又要集训了！（咦，我为什么要说“又”？）
现在给出富老师的课表（3行7列的二维数组，代表一周的上午下午晚上，0表示没课，1表示有课）和15个学生的课表（3行7列*15的三维数组），选出富老师有时间（学生的课表差异很大，有些学生可能没时间）且有课学生数量最少的k个时间点。

k个时间点按有课学生数量从少到多排序，并且在有课学生数量相同的情况下，上午时间点排在晚上的前面，晚上时间点排在下午的前面。

16、模拟排队问题：
放假了要买火车票回家，有三个售票窗口，人很多，要排队。

每个人买票都要3分钟完成，每个人自动会选择“最优”的队来排，给定n个人到来的时间，放在数组a中，问最后一个人买完票的时刻。

例如：int a[7]={2，3，4，4，4，5，6} 则最后一个人买完票的时刻为11。

17、黑白棋哪个位置翻子最多判定。

18、国际象棋棋盘上放了n个后，一个车想从x1y1位置走到x2y2位置，怎样走不会被后攻击。

19、二维数组中的最大“相似三角形”问题。

例如：1 1 7 1 1
2 3 1 4 2
6 0
其中的123和369就形成相似三角形（即其中元素等比例）。

输出最大的相似三角形包含的元素个数。

上例中输出3。

20、在上题中，假设三角形要考虑可以旋转的情况。

例如其中的123和426就形成“旋转相似三角形”（即其中元素旋转90度、180度、270度后形成“相似三角形”）。

输出最大的“旋转相似三角形”包含的元素个数。

21、“点阵”
三维数组中存放0~9数字的“点阵”，
例如：数字1的点阵为6*3的数字
0 1 0
1 1 0
0 1 0
0 1 0
0 1 0
1 1 1
依据此“点阵”，在屏幕上输出“2010”的字样。

22、公共汽车载人问题：
公共汽车全程一费，车的载客量不超过n，汽车途中共有1~k个站，共有m个乘客要在不同的站上车下车，问设计一个载客方案，保证收入最高（就是在不超载的情况下，为了多赚钱，选择一下拒载哪些人）。

m个乘客的上车站和下车站在二维数组中存放。

例如：int a[][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次跳到终点。

26、富老师乱跳格游戏：
富老师玩乱跳格游戏，规则如下：格子是二维的，起点在左上角，终点在右下角，每次只能向右或向下跳，其他和上面一样，问富老师最少几次可以跳到终点。

27、富老师做水槽：
富老师想做一个容积为C的长方体水槽，水槽没有盖，有五块铁板焊接而成，要求每块铁板的长宽都必须为整数，问如何设计水槽的长宽高使得富老师最省钱。

28、富老师的水槽“套娃”： /* 先做第49题再做这个题 */
富老师作了一堆具有各种长宽高的水槽，为了节省空间，富老师想到了“套娃”，富老师让你帮忙算一下，这些水槽最多能套几层。

水槽的长宽高存在数组中，例如：
int a[][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，是将上述单词填入下面的格中，确定有问号的格子应该填那些字母。

注意格子中的单词之间没有任何空格或标点符号。

例如：上述的格子中应该填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是个“非法”序列。

更进一步，如果某个序列是“合法”的，试给出下一天可以玩几号玩具。

#include <stdio.h>
int a[3][3]={{1,3,6},{2,4,0},{5,7,0}};
int zhaoshu(int x)
{
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(x==a[i][j])
{
return i;
break;
}
}
}
}
main()
{
int n,t;
int d[3]={1,1,1};
int b[3]={3,2,2};
printf("序列长度:\n");
scanf("%d",&n);
int c[n];
printf("序列:\n");
for(int i=0;i<n;i++)
{
scanf("%d",&c[i]);
}
for(int i=0;i<n;i++)
{
t=zhaoshu(c[i]);
if(t<d[t])
switch(t)
{
case 0:;break;
case 1;break;
case 2:;break;
}
}
31、又一个富老师儿子的玩具问题：/* 先做第49题再做这个题 */ 由于富老师不能给出一个“合法”玩具序列，所以不得不给儿子买了一个新玩具：“22世纪高科技新产品”—“积木”。

每个积木的平面形状由一个4*4的数组描述（高度忽略），如下所示： 1 1 1 0 /* B */
0 1 1 0
0 0 1 0
0 0 1 0
所有n个积木的平面形状由一个n*4*4的三维数组描述。

“22世纪高科技新产品”有新的游戏规则：A积木块如果要放在B积木块的上面，则要求A积木块的每个组成部分（4*4数组中的1）必
须放在B积木块的某个组成部分之上，不许悬空。

例如上述数组是B 积木块,而A积木的数组如下：
1 1 1 1 /* A */
0 0 1 0
0 0 1 0
0 0 1 0
则A积木块无法放在B积木块的上边。

最后的问题是，给定n个积木块的形状，问最多可以搭几层？
注意：为了搭的更高，每个积木块都可以进行旋转、平移、翻转等操作。

例如:C积木块如下：
1 1 0 0
1 1 0 0
1 0 0 0
0 0 0 0
经过翻转、平移之后，C积木块可以放在B积木块之上。

/* 富老师提示：为了降低难度，可先完成平移功能，成功之后，再增加旋转、翻转等操作。

*/
32、富老师教儿子认星座：
一般的玩具已经搞不定富老师的儿子了，这次他要天上的星星！？
富老师这样教育儿子：“哪可不行！因为……天上的星星……不单卖！！,
必须成套卖，一次卖一个‘星座’，我先教你认识这些星座吧……”天上所有星星（n个）的坐标（二维的，用（x,y）方式表示）存在a[n][2]数组中，给定一个星座图上的“三角星座”坐标（由三个点组成（x1,y1），（x2,y2），（x3,y3）），问天上的哪三颗星星组成了“三角星座”。

/* 富老师提示：问题简单点说，其实是要从ｎ个点中找出三个点，它们组成的三角型与星座图上给出的三角型是“相似三角形”就OK。

要注意旋转带来的问题 */
如果是“四边星座”，问题要怎样解？
33、人机猜数游戏
由计算机“想”一个四位数，请人猜这个四位数是多少。

人输入四位数字后，计算机首先判断这四位数字中有几位是猜对了，并且在对的数字中又有几位位置也是对的，将结果显示出来，给人以提示，请人再猜，直到人猜出计算机所想的四位数是多少为止。

例如：计算机“想”了一个“1234”请人猜，可能的提示如下：
人猜的整数计算机判断有几个数字正确有几个位置正确
1122 2 1
3344 2 1
3312 3 0
4123 4 0
1243 4 2
1234 4 4
游戏结束
请编程实现该游戏。

游戏结束时，显示人猜一个数用了几次。

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>=m>=n>0)求出满足以下方程的正整数数列i1,i2,…,in，使得：i1+i2+…+in=m，且i1>=i2…>=in。

例如：
当n=4, m=8时，将得到如下5 个数列：
5 1 1 1
4 2 1 1
3 3 1 1
3 2 2 1
2 2 2 2
38、回文数的形成
任取一个十进制整数，将其倒过来后与原来的整数相加，得到一个新的整数后重复以上步聚，则最终可得到一个回文数。

请编程验证。

/*回文数的这一形成规则目前还属于一个猜想，尚未得到数学上的证明。

有些回文数要经历上百个步聚才能获得。

*/
39、黑白子交换
有三个白子和三个黑子如下图布置：
○ ○ ○ . ● ● ●
游戏的目的是用最少的步数将上图中白子和黑子的位置进行交换：● ● ● .○ ○ ○
游戏的规则是：(1)一次只能移动一个棋子； (2)棋子可以向空格中移动，也可以跳过一个对方的棋子进入空格，但不能向后跳，也不能跳过两个子。

请用计算机实现上述游戏。

40、约瑟夫问题
这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。

问怎样排法，才能使每次投入大海的都是非教徒。

/* 为什么不叫加斯帕问题，而叫约瑟夫问题？*/
41、邮票组合
富老师有四张3分的邮票和三张5分的邮票，用这些邮票中的一张或若干张可以得到多少种不同的邮资？
42、可称1~40磅的4块砝码
法国数学家梅齐亚克在他著名的《数字组合游戏》(1962)中提出了一个问题：一位商人有一个重40磅的砝码，一天不小心将砝码摔成了四块。

后来商人称得每块的重量都是整磅数，而且发现这四块碎片可以在天平上称1至40磅之间的任意重量。

请问这四块碎片各重多少？/* 注意：题目中给出的条件是“在天平上”，这意味着：同一砝码既可以放在天平的左侧，也可以放在天平的右侧。

若规定重物只能放在天平的左侧，则当天平平衡时有：
重物重量+左侧砝码重量总和=右侧砝码重量总和
由此可得：
重物重量=右侧砝码重量总和-左侧砝码重量总和 */
43、波松瓦酒的分酒趣题
法国著名数学家波瓦松在少年时代研究过一个有趣的数学问题：某人有12品脱的啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，仅有一个8品脱和5品脱的容器，怎样倒才能将啤酒分为两个6品脱呢？
/* 下面是别人给出的问题分析与算法设计，看看能读懂不。

注意，此题和“24题富老师折腾水”是不一样的。

将12品脱酒 8品脱和5品脱的空瓶平分，可以抽象为解不定方程：8x-5y=6
其意义是：从12品脱的瓶中向8品脱的瓶中倒x次，并且将5品脱瓶中的酒向12品脱的瓶中倒y次，最后在12品脱的瓶中剩余6品脱
的酒。

用a,b,c代表12品脱、8品脱和5品脱的瓶子，求出不定方程的整数解，按照不定方程的意义则倒法为：
a ->
b ->
c ->a
x y
倒酒的规则如下：
1) 按a -> b -> c ->a的顺序；
2) b倒空后才能从a中取
3) c装满后才能向a中倒 */
44、1~9组成三个3位的平方数
将1、2、3、4、5、6、7、8、9九个数字分成三组，每个数字只能用一次，即每组三个数不允许有重复数字，也不许同其它组的三个数字重复，要求每组中的三位数都组成一个平方数。

例如：361,529,784。

45、由8个整数形成奇特的立方体
任意给出8个整数，将这8个整数分别放在一个立方体的八个顶点上，要求每个面上的四个数之和相等。

46、减式还原
编写程序求解下式中各字母所代表的数字，不同的字母代表不同的数字。

PEAR
- ARA
——
PEA
答案是： 1098
- 989
———
109
47、乘式还原
有乘法算式如下：
○○○
×○○
————
○○○○
○○○○
——————
○○○○○
18个○的位置上全部是素数(1、3、5或7)，请还原此算式。

48、魔术师的猜牌术
魔术师利用一副牌中的13张黑桃，预先将它们排好后迭在一起，牌面朝下。

对观众说：我不看牌，只数数就可以猜到每张牌是什么，我大声数数，你们听，不信？你们就看。

魔术师将最上面的那张牌数为
1，把它翻过来正好是黑桃A，将黑桃A放在桌子上，然后按顺序从上到下数手上的余牌，第二次数1、2，将第一张牌放在这迭牌的下面，将第二张牌翻过来，正好是黑桃2，也将它放在桌子上，第三次数1、2、3，将前面两张依次放在这迭牌的下面，再翻第三张牌正好是黑桃3。

这样依次进行将13张牌全翻出来，准确无误。

问魔术师手中的牌原始顺序是怎样安排的？
答案:1 8 2 5 10 3 12 11 9 4 7 6 13
49、求数组中最长单调递增子序列
int a[10]={1,2,9,5,6,7,8,4,3,10}
上述数组中最长单调递增子序列是：1，2，5，6，7，8，10。

50、关于世界杯的题目，球迷专用：
世界杯32个球队共进行48场小组赛、8场1/8决赛、4场1/4决赛、2场半决赛、2场决赛共64场比赛，共有64个比赛结果，存在一个a[32][32]的数组中，如下：
数组中的a[0][1]的值为1.2，表示一号队和二号队的比赛结果是1：2，很明显，a[1][0]的值一定为2.1。

数组中的a[0][2]的值为-1，表示一号队和三号队没比过。

数组中的a[i][j]的值为0表示两个队踢成0：0。

假设，任何两个队都没有在比赛过程中遇到过两次（理论上，两个队在小组赛中比过，到淘汰赛中还可能相遇，我们去掉这种情况，因为数组一个元素没法存两个结果）。

请依据a[32][32]数组的值判断：1）哪个队是冠军、亚军、季军和殿军；2）哪四个队是同一个小组的，共有8个小组呦。

/* 编程的时候，不要真的用32个队，比赛结果不好编。

你可以用16个队分成4个组，每个组出线2个队，再进行淘汰赛…… */。