《普及组试题和解答》由会员分享,可在线阅读,更多相关《普及组试题和解答(14页珍藏版)》请在金锄头文库上搜索。
1、普及组试题和解答 付浩 目录目录 A. 矩阵乘法. 2 B. GPA. 4 C. GAP. 7 D. 材质贴图. 9 E. 货币兑换. 11 F. 网页浏览器 . 13 A. 矩阵乘法矩阵乘法 题目描述 矩阵乘法是线性代数中最基本的运算之一。 给定三个矩阵(),(),()ijp qijr sijn mAaBbCc,请编写程序判断A BC是否成立。 输入格式 输入包含多组数据。每组数据的格式如下: 第一行包括两个整数 p 和 q,表示矩阵 A 的大小。后继 p 行,每行有 q 个整数,表示矩阵 A的元素内容。 紧接着用相同的格式给出矩阵 B 和矩阵 C。 输入数据的最后一行是两个 0,你的程序
2、处理到这里时就应该退出了。 输入数据中所有的整数绝对值都不超过 100。 输出格式 对每一组输入数据,你的程序都要输出单独一行字符。 如果A BC成立则输出”Yes” 如果 A 和 B 根本不能相乘,或A BC不成立,则输出”No”。注意大小写。 输入样例 2 3 1 2 3 4 5 6 3 2 1 2 3 4 5 6 2 2 22 28 49 64 1 2 1 2 2 1 2 1 2 2 2 4 1 2 1 2 1 2 1 1 1 1 1 1 0 0 输出样例 Yes No No 解答 此题考察线性代数基本概念,请参阅线性代数教材。 B. GPA 题目描述 科大的学生都很重视 GPA,所以我
3、们来编写一个成绩管理系统吧 大多数高校都使用平均成绩绩点(Grade Point Average, 简称 GPA)来评估学生成绩。科大的百分制成绩与绩点的对应关系如下: 百分制 绩点 10095 4.3 9490 4.0 8985 3.7 8482 3.3 8178 3.0 7775 2.7 7472 2.3 7168 2.0 6765 1.7 64 1.5 6361 1.3 60 1.0 590 0.0 一个学生的平均分为各门课程百分制成绩的加权平均值: 课程成绩 课程学分平均分课程学分同样地,平均成绩绩点为各门课程绩点的加权平均值: GPA 课程绩点 课程学分课程学分请编写一个成绩管理系统
4、处理成绩的录入、计算和查询等操作。 输入格式 输入数据只有一组。 第一行包括三个整数:学生总数 n (1n500),课程总数 m (1m500),操作总数 q (1q100000) 接下来的 n 行每行为一个仅包含字母和数字的字符串,表示各个学生的学号。 接下来的 m 行每行为一个仅包含字母和数字的字符串,表示各个课程的编号;以及一个正整数,表示该课程的学分。 最后 q 行每行描述一次操作。各操作的格式和功能如下: 操作 功能 score a b s 学号为a的学生的课程 b 的百分制成绩为s, 把该成绩登记录入系统。 成绩不会重复录入。 student a 根据当前系统中的数据,输出学号为
5、a 的学生百分制平均成绩和 GPA,用单个空格隔开,四舍五入到小数点后两位 course b 根据当前系统中的数据, 输出课程 b 的百分制平均成绩, 四舍五入到 小数点后两位 query a b 输出学号为a的学生的课程b的百分制成绩和绩点, 用单个空格隔开。 该成绩一定已经录入到系统中。 学号和课程编号长度不超过 10 个字符。 输出格式 对于操作 student, course 和 query,按照上述描述输出。输入输出具体格式请参阅输入输出样例。 输入样例 5 3 10 PB09123456 PB09654321 SA09123456 SA09654321 PB07010101 ABC
6、DEFGHIJ 1 0123456789 2 0101010101 2 score PB09123456 0101010101 64 score PB09123456 0123456789 100 query PB09123456 0101010101 score SA09654321 0101010101 90 student PB09123456 course 0101010101 student PB07010101 course ABCDEFGHIJ score PB09654321 0101010101 85 course 0101010101 输出样例 64 1.50 82.00
7、2.90 77.00 0.00 0.00 0.00 79.67 提示 请尽可能地优化你的程序,否则难以在规定时间内完成所有操作。 C 语言可以用 printf(“%.2lfn”,s);四舍五入到小数点后两位输出 double 类型。 解答 首先, 需要给各个学号和课程号分配一个整数的编号以方便操作。 按照输入数据中的顺序来编号其实就可以了,如果事先对输入进行排序,每次使用二分查找来确定编号会更快。 为了快速地完成各项查询操作,每次录入成绩时我们需要保存如下信息: 一个二维数组储存每个学生对应课程的成绩。 三个一维数组储存每个学生获得的总学分、百分制成绩加权和、绩点加权和。 两个一维数组储存每门
8、课程已有成绩的学生人数、百分制成绩总和。 C. GAP 题目描述 最近经常下雨,泥泞的道路已经让人不爽,如果不小心踩到水沟(gap)里就相当刺激了。 某位热爱科学的无聊闷骚科大猥琐男想到了这样一个问题:水沟里有多少水? 为了简化问题,我们只需求出给定的一个纵切面上雨水所占的面积即可。 如图所示,假设在这个纵切面上,水沟的轮廓可以用一条抛物线描述: 2(0)yaxbxc a 水平面位于 y=0。换言之,由 y=0 和2(0)yaxbxc a两条曲线围成的区域就是雨水所在的区域。 输入格式 输入包括多组数据。 每组数据仅占一行,包括三个浮点数 a, b, c (a0)。当输入的 a 小于 0 时则
9、表示输入结束,你的程序应该到此结束,并且不要处理这组数据。 输出格式 对于每组数据,输出一行包括所求的面积,四舍五入到小数点后四位。 -15-10-505101520-6-4-20246轮廓水平面输入样例 0.5 4.0 6.0 1.0 1.0 1.0 1.0 0.0 -2.5 1.0 2.0 1.0 -1.0 0.0 0.0 输出样例 5.3333 0.0000 5.2705 0.0000 提示 C 语言可以用 printf(“%.4lfn”,s);四舍五入到小数点后四位输出 double 类型。 解答 解答此题需分两步: 首先,求解两曲线的交点,易见这是一个简单地一元二次方程,如果方程无实
10、数解那么面积为零。 最后,由积分 1223322 121212()()()()32xxabSaxbxc dxxxxxc xx求得面积。 D. 材质贴图材质贴图 题目描述 3D 游戏中的场景经常用材质贴图来表现,例如石头、水面等。 通常,材质贴图是一张正方形的位图,上下边界的像素对应相同,左右边界的像素也对应相同。例如下图中,左边是一张材质贴图,而右边的不是(左右边界不同)。 255 192 120 255 255 192 120 255 31 119 3 31 31 119 3 31 76 214 0 76 77 214 0 76 255 192 120 255 255 192 120 255
11、 给定一张 nn 的位图,请在这张位图中寻找一块材质贴图,使得材质贴图尺寸最大。下图中黄色区域就是最大的材质贴图,虽然黄色区域左上角 22 的位图也是材质贴图,但不是最大的。 5 251 127 11 195 23 13 0 13 23 211 0 13 0 67 211 13 0 13 23 1 251 127 11 47 输入格式 输入包含多组数据。 每组数据第一行是一个整数 n (1n50),表示位图的大小。 然后 n 行每行 n 个在 0 到 255 之间的整数,描述位图的内容。 输入数据以 n=0 结束,不要处理这组数据。 输出格式 对每组数据输出最大的材质贴图的边长。请注意,11
12、的位图也是材质贴图。 输入样例 2 255 0 0 127 5 5 251 127 11 195 23 13 0 13 23 211 0 13 0 67 211 13 0 13 23 1 251 127 11 47 0 输出样例 1 3 解答 一重循环按从大到小的顺序枚举材质贴图的大小,再两重循环枚举材质贴图左上角的坐标,最后一重循环判断是否是材质贴图。首次发现的材质贴图就是最大的。 E. 货币兑换货币兑换 题目描述 招商银行遇到一位很奇怪的顾客。 这位顾客起初用一些人民兑换了另一种货币, 然后不断地用一种货币兑换另一种货币,最后又换回人民币。令人惊奇的是,最后换回的人民币居然比他最初带来的多
13、了一些。 例如这样一个兑换过程: 假设 1 单位人民币兑换 6.89 单位火星币,1 单位火星币兑换 0.18 单位水星币,1 单位水星币兑换 0.81 单位人民币。 我们用 1.20 单位人民兑换得 8.27 单位火星币,然后用这 8.27 单位火星币兑换得 1.49 单位水星币,最后用 1.49 单位水星币兑换到 1.21 单位人民币。 奇迹就这样发生了。聪明的你一定已经发现了,这都是四舍五入的功劳。 当然这种事情在现实中是不可能的,但我们还是来研究一下这个问题。 假设共有 n 种货币,编号从 1 到 n。我们最初持有 m 单位的货币 1。已知各种货币之间兑换比率,每次兑换后都四舍五入到小数点后两位。请问兑换 k 次且换回到货币 1 后,最多能让我们持有的货币增加多少单位? 输入格式 输入包含多组数据。 每组数据第一行包含两个整数:n (1n100), k (0k100),第二行为一个实数 m (0m100),精确到小数点后两位。这三个数的含义如上所述。 然后是 n 行, 每行 n 个数, 第 i 行的第 j 个数 aij表示可以用单位货币 i 兑换 aij单位的货币 j,注意,不一定能反向兑换。若 aij=0,则表示不能直接用货币 i 兑换货币 j。显