2022年编程竞赛试题 .pdf
《2022年编程竞赛试题 .pdf》由会员分享,可在线阅读,更多相关《2022年编程竞赛试题 .pdf(5页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第二届富藤杯编程大赛试题一、基础题。 (选做,最多选做三道,可不做。 )1、 (20 分)按递增顺序产生序列M 中最小的n 个数(自然数n 由键盘输入)。序列M 的定义如下:1)数 1 属于 M;2)如果 k 属于 M,则 2k+1 ,3k+1 也属于 M;3)除 1)、 2)之外,再无数属于M。2、( 20 分)分数变小数:写出一个程序,接受一个以N/D 的形式输入的分数,其中N 为分子, D 为分母,输出它的小数形式。如果它的小数形式存在循环节,要将其用括号括起来。例如: 1/3=.00000.表示为 .(3) ,又如 41/333=.123123123.表示为 .(123) 。一些转化的
2、例子:1/3=.(3) 22/5=4.4 1/7=.(142857) 3/8=.375 45/46=.803(571428) 用上面的分数和11/59 来测试你的程序。运行举例:ENTER N,D:17 1/7=.(142857) 本题中, 0=N=65535,0=D1 的反正切函数值(精确到0.001) 。要求:从键盘输入一个大于1 的数,在屏幕上输出其对应的反正切函数值。2、 ( 30 分)问题描述:一个二维数组共有M 行和 N 列,每行元素按从小到大的顺序排列,每列元素也按从小到大的顺序排列。输出要求:请设计一个有效的算法,输入一个数据X,能够判断X 是否在二维数组中,如果在,则输出它的
3、行列号,否则,输出“没有找到!” 。附加条件:在完成算法的同时,请给出算法的复杂度,如果算法复杂度为N x M, 则得 30分,如果算法复杂度为M*LOG2N,则得 70分,如果算法复杂度为MAX(N,M),则得 100,如果没有指出算法复杂度,则不得分。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 5 页 - - - - - - - - - 3、 ( 30 分)问题描述:假设有 n 个任务由k 个可并行工作的机器完成。完成任务i 需要的时间为 ti。试设计一个算法找出
4、完成这n 个任务的最佳调度,使得完成全部任务的时间最早。输出要求:对任意给定的整数n 和 k,以及完成任务i 需要的时间为ti,i=1n。编程计算完成这n 个任务的最佳调度。附加条件:由文件 input.txt 给出输入数据。第一行有2 个正整数n 和 k。第 2 行的 n 个正整数是完成n 个任务需要的时间。将计算出的完成全部任务的最早时间输出到文件output.txt 。 input.txt 7 3 2 14 4 16 6 5 3 output.txt 17 4、 ( 30 分)问题描述:海明码是一种多重(复式 )奇偶检错系统。它将信息用逻辑形式编码,以便能够检错和纠错。 用在海明码中的全
5、部传输码字是由原来的信息和附加的奇偶校验位组成的。 每一个这种奇偶位被编在传输码字的特定位置上。实现得合适时, 这个系统对于错误的数位无论是原有信息位中的,还是附加校验位中的都能把它分离出来。推导并使用长度为m 位的码字的海明码,所需步骤如下:1)确定最小的校验位数k,将它们记成D1、 D2、 , 、 Dk,每个校验位符合不同的奇偶测试规定。2)原有信息和k 个校验位一起编成长为m+k 位的新码字。选择k 校验位( 0 或 1)以满足必要的奇偶条件。3)对所接收的信息作所需的k 个奇偶检查。4)如果所有的奇偶检查结果均为正确的,则认为信息无错误。如果发现有一个或多个错了,则错误的位由这些检查的
6、结果来唯一地确定。输出要求:请根据上述描述,编写海明码编码和解码的程序,并求解信息码 “1 1 0 0 1 1 0 0(K=8) ”的海明码是多少(1 0 1 1 1 0 0 0 1 1 0 0)?海明码“1 0 0 1 1 0 0 0 1 1 0 0(K=8) ”的原信息码是多少(1 1 0 0 1 1 0 0)?5、 ( 30 分)现在有N 辆车要按顺序通过一个单向的小桥,由于小桥太窄,不能有两辆车并排通过,所以在桥上不能超车。另外,由于小桥建造的时间已经很久,所以小桥只能承受有限的重量,记为Max (吨) 。所以,车辆在过桥的时候必须要有管理员控制,将这N 辆车按初始顺序分组, 每次让一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年编程竞赛试题 2022 编程 竞赛 试题
限制150内