计算机程序算法试题.docx
- 文档编号:13133868
- 上传时间:2023-06-11
- 格式:DOCX
- 页数:18
- 大小:66.76KB
计算机程序算法试题.docx
《计算机程序算法试题.docx》由会员分享,可在线阅读,更多相关《计算机程序算法试题.docx(18页珍藏版)》请在冰点文库上搜索。
计算机程序算法试题
1.数字分解
Timelimit:
1Seconds Memorylimit:
32768K
描述Description
今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。
在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ也有幸得以参加。
活动中,主持人给所有参加活动的选手出了这样一道题目:
设有一个长度N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。
同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子:
有一个数字串:
312,当N=3,K=1时会有以下两种分法:
1)3*12=36
2)31*2=62
这时,符合题目要求的结果是:
31*2=62
现在,请你帮助你的好朋友XZ设计一个程序,求得正确的答案。
输入格式InputFormat
程序的输入共有两行:
第一行共有2个自然数N,K(6<=N<=40,1<=K<=6)
第二行是一个K度为N的数字串。
输出格式OutputFormat
屏幕输出(结果显示在屏幕上),相对于输入,应输出所求得的最大乘积(一个自然数)。
样例输入SampleInput
42
1231
样例输出SampleOutput
62
时间限制TimeLimitation
1second
来源Source
NOIP2000年
2.回文
TimeLimit:
1SecondMemoryLimit:
32768KB
描述Description
回文词是一种对称的字符串——也就是说,一个回文词,从左到右读和从右到左读得到的结果是一样的。
任意给定一个字符串,通过插入若干字符,都可以变成一个回文词。
你的任务是写一个程序,求出将给定字符串变成回文词所需插入的最少字符数。
比如字符串“Ab3bd”,在插入两个字符后可以变成一个回文词(“dAb3bAd”或“Adb3bdA”)。
然而,插入两个以下的字符无法使它变成一个回文词。
输入格式InputFormat
第一行包含一个整数N,表示给定字符串的长度,3<=N<=5000
第二行是一个长度为N的字符串,字符串由大小写字母和数字构成。
输出格式OutputFormat
一个整数,表示需要插入的最少字符数。
样例输入SampleInput
5
Ab3bd
样例输出SampleOutput
2
时间限制TimeLimitation
各个测试点1s
来源Source
IOI2000
byZossin
3.看球的巴士
描述Description
两个球队的支持者要一起坐车去看球,他们已经排成了一列。
我们要让他们分乘若干辆巴士,同一辆巴士上的人必须在队伍中是连续的。
为了在车上不起冲突,希望两队的支持者人数尽量相等,差至多是D。
有一个例外,就是一辆车上的人全部都是一个球队的支持者。
问要将这N个人全部送至球场,至少要几辆巴士。
输入格式InputFormat
第一行是整数N和D,1<=N<=2500,1<=D<=N。
接下来的N行,按排队的顺序,描述每个人支持的球队,用H或J表示。
输出格式OutputFormat
至少要几辆巴士。
样例输入SampleInput
143
H
J
H
H
H
J
H
J
H
H
H
H
H
H
样例输出SampleOutput
2
时间限制TimeLimitation
1second
注释Hint
有多种方案,例如让前9人做一辆车,差正好是3;后5人做一辆车,因为只有一对的支持者。
4.伪随机数
TimeLimit:
1SecondMemoryLimit:
32768KB
计算机通常不能产生真正的随机数,但是经常使用计算机来产生伪随机数。
由于实际应用,通过算法使得伪随机数成为真随机数。
随机数应用广泛,包括在仿真领域。
伪随机数生成时用的最普遍的是线性同余法。
如果上一次生成的伪随机数是L,那么接下来的伪随机数通过(z*L+I)modM产生,这里的Z是一个常数乘法器,I是常数增量,M是常量模数。
例如,假设Z=7,I=5,M=12,第一个随机数(通常叫做种子)是4,那么我们可以得到后续的伪随机数,如下表所示:
通过上表我们可以看出,通过这个方法产生的随机数序列在6个数字以后会重复。
显然,由于模数M,用这个方法能产生的最长序列是有限的。
通过给出的Z,I,M,和种子L,(Z,I,M,L<10000),我们确定产生的伪随机数序列的重复周期。
注意重复周期不一定从种子L开始。
Input
每行有四个数字,依次是Z,I,M,和L,其中L Output 对于输入的每行,输出伪随机数序列的重复周期 SampleInput 75124 5173384932791511 9111530960001234 1079213699991237 0000 SampleOutput Case1: 6 Case2: 546 Case3: 500 Case4: 220 5.机器人规划 Timelimit: 5SecondsMemorylimit: 32768K 在一个方格地图上放机器人。 有三种方格: 墙、草地、空地。 机器人只能放在空地上,不断向四个方向发射激光。 激光可以穿过草地,但不能穿墙。 机器人不能移动。 问在使机器人不能互相攻击的情况下,最多可以放多少个机器人。 输入: 第一行T(<=11)代表有T组测试数据; 每组测试数据第一行为m,n(1<=m,n<=50)代表地图的大小; 下面有m行,每行n个字符'#','*'或'o',分别代表墙,草地,空地. 输出: 对于第T组数据,首先输出"Case: T"; 提行输出最多可以放置的机器人数. SampleInput 2 44 o*** *### oo#o ***o 44 #ooo o#oo oo#o ***# SampleOutput Case: 1 3 Case: 2 5 6.游戏 Timelimit: 10Seconds Memorylimit: 32768K 最近Hart迷上了一种游戏: GnomeTetravex。 游戏开始给出玩家n*n个正方形,每个正方形分成四个三角形,并且分别标号(0到9)。 在每个正方形里,三角形分成左三角形,上三角形,右三角形和下三角形。 例如,图1显示了游戏的初始状态: 2*2个正方形 图.1初始状态: 2*2个正方形 玩家需要移动这些正方形到最终状态。 所谓的最终状态就是: 任意两个相邻正方形的相邻三角形的编号要是同一个数字。 图2就是上面例子的一种最终状态。 图.2最终状态 看起来这个游戏不难,实际上,Hart对这个游戏并不熟,他只能完成最简单的。 如果游戏复杂一点,他就完成不了。 请编程判断游戏是否能够完成。 Input 输入文件包含了几个游戏用例。 每个游戏用例的第一行包含一个整数(0<=n<=5),表示游戏的正方形个数n*n。 随后的n*n行表示每一个正方形内的三角形编号。 每一行有四个整数,编号顺序按从上,右,下,左。 以0表示输入文件结束。 Output 判断每一个游戏用例是否能够完成,打印"Possible"或者"Impossible"。 以空行隔开每个游戏用例的判断结果。 SampleInput 2 5914 4456 6854 0443 2 1111 2222 3333 4444 0 OutputfortheSampleInput Game1: Possible Game2: Impossible 7.欧几里得游戏 TimeLimit: 1SecondMemoryLimit: 32768KB Stan和Ollie两个人用两个自然数做游戏。 首先Stan用大数减去小数的正倍数,假设所得的差是非负的。 然后,Ollie对差和小数进行同样的操作,然后是Stan,依次交替。 直到有人得到差的结果是0,就是这个人赢了。 例如,他们从(25,7)开始: 257 117 47 43 13 10 这个例子是Stan赢了. Input 每行包含游戏开始的两个正整数,测试用例以“00”结束。 Stan总是先开始游戏。 Output 对每个测试用例,输出哪个赢的判断结果。 输入的最后一行“00”不需要处理。 SampleInput 3412 1524 00 SampleOutput Stanwins Olliewins 8.PrimeRingProblem1 TimeLimit: 10SecondsMemoryLimit: 32768KB Aringiscomposeofncirclesasshownindiagram.Putnaturalnumber1,2,...,nintoeachcircleseparately,andthesumofnumbersintwoadjacentcirclesshouldbeaprime. Note: thenumberoffirstcircleshouldalwaysbe1. Input n(0 Output Theoutputformatisshownassamplebelow.Eachrowrepresentsaseriesofcirclenumbersintheringbeginningfrom1clockwiselyandanticlockwisely.Theorderofnumbersmustsatisfytheaboverequirements.Printsolutionsinlexicographicalorder. Youaretowriteaprogramthatcompletesaboveprocess. Printablanklineaftereachcase. SampleInput 6 8 SampleOutput Case1: 143256 165234 Case2: 12385674 12583476 14765832 16743852 9.迷宫 TimeLimit: 10SecondsMemoryLimit: 32768KB 金字塔的北边有个很大的迷宫。 迷宫由很多四方块组成,这些四方块中有的是岩石,有的是空的。 在每个空的四方块中央的地上有些小钩子。 分析发现每两个钩子可以通过一根绳子连接起来,而这根绳子穿过路径(由互相连起来的四方块组成)上的所有方块。 当绳子拉紧的时候,一个隐藏的门就会打开。 问题是我们并不知道要连接哪个钩子,因此所需要绳子的最大长度也是未知的。 任务: 给出一个迷宫,请确定绳子的最大长度。 Input 输入有几个测试用例。 第一行的数字T表示测试用例的数目。 每个测试用例的第一行是两个整数C,R(2<=C,R<=1000),分别表示行列数。 接下来有R行,每行有C个字符。 字符是“#”或者“.”,表示迷宫的内部分布。 “#”代表岩石四方块,“.”代表空的四方块。 当相邻块紧挨在一起,只能在相邻四方块间行走,不能按对角线行走也不能走出迷宫。 迷宫的设计方法是: 任意两个空四方块之间只有一条路径。 因此,如果我们可以找到合适的钩子来连接,也就找到了相应的路径。 SampleOutput 对于每个测试用例,请输出任意两个空四方块间的路径中的最大长度(长度单位是块)。 SampleInput 2 33 ### #.# ### 76 ####### #.#.### #.#.### #.#.#.# #.....# ####### SampleOutput Maximumropelengthis0. Maximumropelengthis8. 10.抄书 TimeLimit: 1SecondMemoryLimit: 32768KB m本书分给k个抄书员,书的页数为分别为p1,p2...pm,每个抄书员速度相同,而且只能分得连续的若干本书。 求一种分配方案使得抄书的所用总时间最少。 每个抄书员分配至少一本书。 Input 输入的第一行只包含一个整数N,表示有N个测试用例。 接下来是测试用例。 每个测试用例包含两行。 每个测试用例的第一行有两个整数: m和k,1<=k<=m<=500。 第二行有整数p1,p2,...pm,以空格隔开。 所有的数字小于10000000。 Output 对于每个用例的分配结果输出一行。 分配的方案以斜线('/')表示。 如果不止一种分配方案,输出能够使第一个抄书员的工作量最少的方案。 SampleInput 2 93 100200300400500600700800900 54 100100100100100 SampleOutput 100200300400500/600700/800900 100/100/100/100100 11.ExchangeRates TimeLimit: 1SecondMemoryLimit: 32768KB Usingmoneytopayforgoodsandservicesusuallymakeslifeeasier,butsometimespeopleprefertotradeitemsdirectlywithoutanymoneychanginghands.Inordertoensureaconsistent"price",traderssetanexchangeratebetweenitems.TheexchangeratebetweentwoitemsAandBisexpressedastwopositiveintegersmandn,andsaysthatmofitemAisworthnofitemB.Forexample,2stovesmightbeworth3refrigerators.(Mathematically,1stoveisworth1.5refrigerators,butsinceit'shardtofindhalfarefrigerator,exchangeratesarealwaysexpressedusingintegers.) Yourjobistowriteaprogramthat,givenalistofexchangerates,calculatestheexchangeratebetweenanytwoitems. Input Theinputfilecontainsoneormorecommands,followedbyalinebeginningwithaperiodthatsignalstheendofthefile.Eachcommandisonalinebyitselfandiseitheranassertionoraquery.Anassertionbeginswithanexclamationpointandhastheformat ! mitema=nitemb whereitemaanditembaredistinctitemnamesandmandnarebothpositiveintegerslessthan100.Thiscommandsaysthatmofitemaareworthnofitemb.Aquerybeginswithaquestionmark,isoftheform ? itema=itemb andasksfortheexchangeratebetweenitemaanditemb,whereitemaanditembaredistinctitemsthathavebothappearedinpreviousassertions(althoughnotnecessarilythesameassertion). Output Foreachquery,outputtheexchangeratebetweenitemaanditembbasedonalltheassertionsmadeuptothatpoint.Exchangeratesmustbeinintegersandmustbereducedtolowestterms.Ifnoexchangeratecanbedeterminedatthatpoint,usequestionmarksinsteadofintegers.Formatalloutputexactlyasshownintheexample. Note: >Itemnameswillhavelengthatmost20andwillcontainonlylowercaseletters. >Onlythesingularformofanitemnamewillbeused(noplurals). >Therewillbeatmost60distinctitems. >Therewillbeatmostoneassertionforanypairofdistinctitems. >Therewillbenocontradictoryassertions.Forexample,"2pig=1cow","2cow=1horse",and"2horse=3pig"arecontradictory. >Assertionsarenotnecessarilyinlowestterms,butoutputmustbe. >Althoughassertionsusenumberslessthan100,queriesmayresultinlargernumbersthatwillnotexceed10000whenreducedtolowestterms. SampleInput ! 6shirt=15sock ! 47underwear=9pant ? sock=shirt ? shirt=pant ! 2sock=1underwear ? pant=shirt . SampleOutput 5sock=2shirt ? shirt=? pant 45pant=188shirt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 程序 算法 试题