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