- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： 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