分类: c/c
2012-06-02 21:50:22
上机直接写代码,时间2小时:
一张纵横交错的平面网格(围棋棋盘),有n*m个交叉点,每个交叉点都有一个权值 (unsigned int类型),定义:
1.连接相邻2个交叉点的线段为边,边的权值是其所连接的交叉点的平均值,共有n*(m- 1)条横边,(n-1)*m条纵边。
2 .由4条边围成的区域为格,格的权值是其4个角上的交叉点的平均值,共有(n-1)*(m-1) 个格。
3.定义一个矩阵变换 n*m to (2n-1)*(2m-1):
将输入的n*m个值看做网格上的交叉点的权值,
在每个格的中心生成一个新的点,该点权值为其所在格的权值;
在每条边的线段中心生成一个新的点,权值为其所在边的权值;
这样算上原有的n*m个点,一共有了排列整齐的(2n-1)*(2m-1)个点,将这些点的权值依
次输出即得到变换后的矩阵。
n和m都不超过10000,所有权值都用unsigned int表示,在内存中以先行后列的一维数组
存储,理论值有小数的需要四舍五入。
编写程序实现这样一个变换。
//src为输入,dst作为输出,已指向足够的内存空间
void func(int n, int m, const unsigned int * src, unsigned int * dst);
基本减分项:
1.语法错误 -100
2.运行时出错 -90 如果只是对部分测试输入出错,可酌情归入4或5。
3.没做完 -80
4.题意理解错误 -50
对于没有考虑四舍五入的,可适当轻判。
对于n、m用反的,可适当轻判。
5.输出结果错误 -40
仅对于部分测试输入,输出错误的,可适当轻判。
如计算两数均值:
c=(a b 1)/2; //可能溢出
额外减分项:
6.不良的代码书写风格 酌情减分
7.时间复杂度o(n*m) 10
8.遵循先行后列的顺序遍历src 10
9.只使用整数类型完成 10
10.用位运算右移代替所有的“/2”、“/4” 10
11.循环终止条件写成与0比较 10
如:for (i = n; i != 0; i--)
12.循环中用指针而不是“[]”读写内存 10
如:*(p 1) //good
p[1] //bad
13.常用的简单函数用宏定义 10
如两数求均值,四数求均值等,宏参数加括号的可以再给分。
14.访问内存的偏移地址尽量减少重复计算 10
如:
unsigned int *p;
p = src;
for (i = n; i != 0; i--)
{
……
……
p = m;
}
当然p在第二重循环中能够“ ”则更好,可以再加分。
15.在第一行和第一列处展开循环,而不是在循环中判断 10
如:
for (i = n; i != 0; i--)
{
if (i == n) //bad!!!
……
else
……
}
好的写法:
……
……
//do i=n
……
for (i = n - 1; i != 0; i--) //start i with n-1
{
//do j=m
……
for (j = m - 1; j != 0; j--) //start j with m-1
{
}
}
16.能主动对高热度临时变量加register关键字 10
额外加分项:
17.能有意识减少连续指令的依赖性 20
如:
x = a b;
x = c;
x = d; //bad
y = e f;
y = g;
y = h; //bad
好的写法:
x = a b;
y = e f; //good,不依赖上一条指令执行结果
x = c d;
y = g h; //good,不依赖上一条指令执行结果
能将2组点如此交叉并行计算的可以得满分( 20),否则酌情加分,但不超过10分。
18.能有意识重复利用运算中间结果 20
如:
考虑简单的n=2,m=3时,6个点
a,b,c,
d,e,f.
2个格的权值:
q1=(a b d e)/4, q2=(b c e f)/4
可见其中有重复的运算:(b e)/4
在编程时,计算q1时保留(b e)/4这一中间结果,在计算q2时先计算(c f)/4,再与前面
中间结果叠加即可得到q2,同时将中间结果更新为(c f)/4,在m很大时,可以减少大约
一半的计算量。
19.写出极高效率的两数求均值代码 25
20.写出极高效率的四数求均值代码 35
必须与第17、18项有机结合才能得满分,否则酌情给分。
第19、20项总分超过50分者,若证实是独立原创,不论之前分数,本次测试破格评定为
a