2009程序设计竞赛试题

《2009程序设计竞赛试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机信息工程学院2009编程竞赛试题第一部分、基础题（计算机信息工程学院参赛学生只能任选3题，其他专业学生可任选。每题20分）1．根据以下问题描述编写程序，实现求在环上哪个位置剪开，按下述规则可取走的珠子粒数最多。设一个环上有编号为0～n-1的n粒不同颜色的珠子(每粒珠子颜色用字母表示，n粒珠子的颜色由输入的字符串表示)。将环中某两粒珠子间剪开，环上珠子形成一个序列，然后按以下规则从序列中取走珠子：首先从序列左端取走所有连续同色珠子；然后从序列右端在剩下珠子中取走所有连续同色珠子，两者之和为该剪开处可取走珠子的粒数。在不同位置剪开，能取走的珠子数不尽相同。例如，10粒珠子颜色对应字符串为

2、“aaabbbadcc”，从0号珠子前剪开，序列为aaabbbadcc，从左端取走3粒a色珠子，从右端取走2粒c色珠子，共取走5珠子。若在3号珠子前剪开，即bbbadccaaa共可取走6粒珠子。2．根据以下描述，编制程序解决问题。五只猴子一起摘了一堆桃子，因为太累，五只猴子决定先睡一觉再分。不久，其中一只猴子醒来了，它见别的猴子没有醒来，便将一堆桃子平均分成5份，结果多了一个，就将多的这个吃了，拿走其中的一份并离开。又不久，第二只猴子醒来了，它不知道有一个同伴已经拿走过桃子，便又将剩下的桃子平均分成5份，发现也多了一个，同样吃了这一个，拿走其中的一份。如此类推第3只，第4只，第5只猴子都是

3、这样分、吃、拿走。问这5只猴子至少摘了多少个桃子？3．根据以下描述，编制程序解决问题。在一个n英寸深的井里，有一条身长1英寸的小虫，它想尽力爬出井外。可是小虫的力气太小了，每分钟只能爬u英寸，然后就得休息1分钟。在这1分钟里，它又会滑下去d英寸。这个向上爬和休息的过程不断的进行着。这条小虫要用多久才能爬到井外呢？小于1分钟的时间以1分钟计算。如果小虫在向上爬而即将休息的那一刻到达了井口，我们就认为它已经成功了，而不再计算接下来的休息时间。输入三个整数n,u和d,且d

4、mpleInput2:2031SampleOutput2:194．根据以下描述，编制程序解决问题。网上流传一句话:"常在网上飘啊，哪能不挨刀啊～"。其实要想能安安心心地上网其实也不难，学点安全知识就可以。首先，我们就要设置一个安全的密码。那什么样的密码才叫安全的呢？一般来说一个比较安全的密码至少应该满足下面两个条件：(1)密码长度大于等于8，且不要超过16。(2)密码中的字符应该来自下面“字符类别”中四组中的至少三组。这四个字符类别分别为：1）大写字母：A,B,C...Z2）小写字母：a,b,c...z3）数字：0,1,2...94）特殊符号：~,!,@,#,$,%,^给你一个密码，你的任

5、务就是判断它是不是一个安全的密码。Input:输入一行密码（长度最大可能为50），密码仅包括上面的四类字符。Ouput:判断这个密码是不是一个安全的密码，是的话输出YES，否则输出NO。5．矩阵中填数问题。给出N*N的矩阵，要求编程分别实现倒填、蛇形填数和回转填数。SampleInput:5SampleOutput:（倒填）25242322212019181716151413121110987654321（蛇形填数）13410112591219681318207141721241516222325（回转填数）11615141321724231231825221141920211056789

6、6．编程将一个正整数（小于1000）表示成1和质因子的连乘积。SampleInput:45SampleOutput:45=1*3*3*5第二部分、提高题（每题30分）1．根据以下描述，编制程序解决问题。我们都知道，素数是只能被1和它本身整除的自然数，比如2，3，5…。在这个问题中，我们将请你编写一个程序，要求如下：给定一个自然数N，我们可以得到一个小于等于N的素数数列。例如，N＝21时，我们得到了如下的数列：2，　3，　5，　7，　11，　13，　17，　19在上述数列中加入整数1，得到如下数列：1，　2，　3，　5，　7，　11，　13，　17，　19将这个数列记作Q(N)。我们的问题是

7、，给定整数N和C，如果Q（N）的长度是奇数，则找出Q（N）中间的2*C-1个数，如果Q（N）的长度是偶数，则找出Q（N）中间的2*C个数。此外，如果Q（N）的长度小于2*C-1(C是奇数的情况下)或2*C(C是偶数的情况下)，则输出整个Q（N）数列。输入第一行包括两个整数，以空格分开，分别代表N和C，(1<=N<=1000,1<=C<=N)。结果输出从Q（N）中取得的数列，每两个数之间用空格分开。SampleInput1