2012年上机题
题目
从服务器上下载数据文件org.dat文件以二进制方式存放一系列整数，每个整数占4个字节。从第一个整数开始，第一个整数和第二个整数构成一个坐标点，依次类推，数据文件中保存了许多坐标点数据。
问题1：
规定处于第一象限的坐标点为有效点，请问数据文件中所有点的个数n为多少？有效点的个数k为多少？
问题2：
每个有效点与坐标原点构成一个的矩形，请问k个有效点与坐标原点构成的k个矩形的最小公共区域面积为多少？
问题3：
寻找有效点中符合下列条件的点：以该点为坐标原点，其他有效点仍然是有效点即处于第一象限（不包括坐标轴上的点）。输出这些点。
问题4：
对所有有效点进行分组，每个有效点有且只能属于一个分组，分组内的点符合下列规则：若对组内所有点的x坐标进行排序，点p1（x1，y1）在点p2（x2，y2）后面，即x1>x2那么y1>y2.请输出所有的分组。
分析
我看到有的代码是分题做的，这样更好给分，但是我就混在一起了，因为有些功能可以同时完成。
我大概分成下面几个部分：
（1）读文件，求出n和k，保存有效点。
（2）以x的的大小由小到大进行排序。经过简单处理。可以得到最小公共面积和问题三所求的点。
（3）分组。我就遍历了，对每个点给了一个符号位。时间复杂度比较高。
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void fileRead(FILE * fp, int num[][2], int *k, int * n);
int cmp(const void* a, const void *b);
void findMinSquare(int num[][2], int k);
int divideGroup(int num[][2], int k, int group[]);
void main()
{
FILE * fp = fopen("org.dat", "rb");
if (fp == NULL) {
printf("FILE OPEN ERROR!\n");
exit(1);
}
// 造数据文件，coor.txt中已经存放了一些数据
//FILE * fp = fopen("org.dat", "wb");
//FILE * f2 = fopen("coor.txt","r");
//if (fp == NULL || f2==NULL) {
// printf("FILE OPEN ERROR!\n");
// exit(1);
//}
//int t;
//while (fscanf(f2, "%d", &t) != EOF) {
// fwrite(&t, sizeof(int), 1, fp);
//}
//fclose(f2);
int num[1000][2], k = 0, n = 0, groupnum;
int group[100];
fileRead(fp, num, &k, &n);
printf("所有点的个数为：%d\n", n);
printf("支配点的个数为：%d\n", k);
qsort(num, k, sizeof(num[0]), cmp);
findMinSquare(num, k);
memset(group, -1, sizeof(group));
groupnum = divideGroup(num, k, group);
printf("共分为%d组，具体如下：\n", groupnum);
for (int i = 0; i < groupnum; i++) {
printf("第%d组点为：", groupnum);
for (int j = 0; j < k; j++) {
if (group[j] == i) {
printf(" (%d, %d)", num[j][0], num[j][1]);
}
}
printf("\n");
}
fclose(fp);
}
void fileRead(FILE * fp, int num[][2], int *k, int * n)
{
int x, y;
while (fread(&x, sizeof(int), 1, fp) && fread(&y, sizeof(int), 1, fp)) {
*n = *n + 1;
if (x > 0 && y > 0) {
num[*k][0] = x;
num[*k][1] = y;
*k = *k + 1;
}
}
}
int cmp(const void* a, const void *b)
{
return ((int *)a)[0] - ((int *)b)[0];
}
void findMinSquare(int num[][2], int k)
{
int minx, miny;
if (k == 1) {
printf("最小公共面积是：%d\n", num[0][0] * num[0][1]);
printf("符合要求的点的坐标为：(%d, %d)", num[0][0], num[0][1]);
}
else {
if (num[0][0] < num[1][0] && num[0][1] < num[1][1]) {
printf("最小公共面积是：%d\n", num[0][0] * num[0][1]);
printf("符合要求的点的坐标为：(%d, %d)\n", num[0][0], num[0][1]);
}
else {
minx = num[0][0];
miny = num[0][1];
for (int i = 1; i < k; i++) {
if (minx > num[i][0]) {
minx = num[i][0];
}
if (miny > num[i][1]) {
minx = num[i][1];
}
}
printf("最小公共面积是：%d\n", minx * miny);
printf("没有符合要求的点的坐标。\n");
}
}
}
int divideGroup(int num[][2], int k, int group[])
{
int groupnum = 0;
int tx, ty;
for (int i = 0; i < k; i++)
{
if (group[i] == -1) {
group[i] = groupnum;
tx = num[i][0];
ty = num[i][1];
for (int j = i + 1; j < k; j++) {
if (group[j] == -1 && num[j][0] > tx && num[j][1] > ty) {
group[j] = groupnum;
tx = num[j][0];
ty = num[j][1];
}
}
groupnum++;;
}
}
return groupnum;
}
2013年上机题
题目
二进制数据文件1.bin中存放了100000个样本点，每个样本点由4个属性构成，属性均为整型。
定义： 如a点的k个属性不比b点的对应属性差（属性值越小越好），
且a点至少有一个属性比b点的对应属性好，则称a点k-支配b点。
要求： 求出不被任何点k-支配的样本点的个数。
在试卷上填写求出的样本点个数和所用时间（Elapsed Time）。
分析
这道题看上去不难，但是倒是花费了我不少的时间，其中有许多大大小小的bug。先简单介绍一下程序的几个部分：
（1）计时（这个已经写好了）
（2）读取文件中的数据并保存。
（3）遍历数组，寻找不被控制的数据。
我原来打算直接开一个$100000*4$的数组来保存数据，但是报了stack overflow的错，我查了下，说是栈的默认大小是1M，这明显超过了。我就决定用结构体+手动分配内存，但是没想到保存结构体指针的数组也超过了内存限制（原谅我没算）。后来发现只要开成全局变量就好了。
考虑到数据有100000个，昨天丁大佬说10000个数据的话复杂度为$n2$就有些大了，我就考虑到能不能减少时间复杂度。着就想到了链表。最开始的构想是两层遍历，去掉被控制的点。后来想到为了减少比较的次数，可以设置标志位。既然说到了标志位，就想到不如直接用链表删掉被控制的点就好了。这个算法的时间复杂度我没有求，但是最好情况是$O(n)$，最坏情况是$O(n2)$。
代码
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define MAXSIZE 100000
void run(void);
int main()
{
LARGE_INTEGER m_nFreq;
LARGE_INTEGER m_nBeginTime;
LARGE_INTEGER m_nEndTime;
QueryPerformanceFrequency(&m_nFreq);
QueryPerformanceCounter(&m_nBeginTime);
run();
QueryPerformanceCounter(&m_nEndTime);
printf("\nElapsed Time = %lf sec\n",(double)(m_nEndTime.QuadPart-m_nBeginTime.QuadPart)/m_nFreq.QuadPart);
return 0;
}
struct Dot
{
int pos[4];
Dot * next;
};
int dataRead(FILE * fp, Dot * head);
void eraseControlDot(Dot * head, int * count);
void freeSpace(Dot * head);
void run(void)
{
FILE * fp = fopen("1.bin", "rb");
if (fp == NULL) {
printf("FILE OPEN ERROR!\n");
exit(0);
}
Dot * head = (Dot *)malloc(sizeof(Dot));
head->next = NULL;
int count = dataRead(fp, head);
eraseControlDot(head, &count);
printf("%d", count);
freeSpace(head);
fclose(fp);
}
int dataRead(FILE * fp, Dot * head)
{
int count = 0;
int a, b, c, d;
Dot * node, *p = head;
while (fread(&a, sizeof(int), 1, fp) && fread(&b, sizeof(int), 1, fp) && fread(&c, sizeof(int), 1, fp) &&
fread(&d, sizeof(int), 1, fp ) && count < MAXSIZE) {
node = (Dot *)malloc(sizeof(Dot));
node->pos[0] = a;
node->pos[1] = b;
node->pos[2] = c;
node->pos[3] = d;
node->next = NULL;
p->next = node;
p = node;
count++;
}
return count;
}
void eraseControlDot(Dot * head, int * count)
{
Dot *p, *q, *current;
if (*count > 0) {
current = head->next;
while(current != NULL) {
q = head;
p = head->next;
while (p != NULL) {
if (p->pos[0] >= current->pos[0] && p->pos[1] >= current->pos[1] &&
p->pos[2] >= current->pos[2]&& p->pos[3] >= current->pos[3]
&&(p->pos[0] > current->pos[0] || p->pos[1] > current->pos[1]
|| p->pos[2] > current->pos[2] || p->pos[3] > current->pos[3])) {
q->next = p->next;
free(p);
p = q->next;
*count = *count - 1;
}
else {
p = p->next;
q = q->next;
}
}
current = current->next;
}
}
}
void freeSpace(Dot * head)
{
Dot *p, *q;
p = head->next;
q = head;
while (p != NULL) {
free(q);
q = p;
p = p->next;
}
free(p);
}
2014年上机题
题目
input.bin中有10000组数据，每组数据有4个属性，都为整型。定义邻近点为拥有k个距离小于等于d的点的点，$d=\sqrt{(b_1-a_1)*(b_1-a_1)+(b_2-a_2)*(b_2-a_2)+(b_3-a_3)*(b_3-a_3)+(b_4-a_4)*(b_4-a_4)}$;现定义k=10，d=7500，显示出符合点的编号及其各个属性。
分析
这道题就是两次循环求解，不难，但是数据量比较大，时间比较长。
代码
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <windows.h>
#define ARRAYSIZE 10000
#define _CRT_SECURE_NO_WARNINGS
struct Dot {
int pos[4];
int ngb;
void initDot() {
ngb = 0;
}
}points[ARRAYSIZE];
int fileRead(FILE *fp);
void countNeighbour(int count, double distance);
void showResult(int count, int k);
void main()
{
LARGE_INTEGER m_nFreq;
LARGE_INTEGER m_nBeginTime;
LARGE_INTEGER m_nEndTime;
QueryPerformanceFrequency(&m_nFreq);
QueryPerformanceCounter(&m_nBeginTime);
FILE * fp = fopen("1.bin", "rb");
if (fp == NULL) {
printf("FILE OPEN ERROR!\n");
exit(1);
}
int k=10;
double distance=7500;
//printf("请输入k和距离：");
//scanf("%d%lf", &k, &distance);
int count = fileRead(fp);
countNeighbour(count, distance);
showResult(count, k);
fclose(fp);
QueryPerformanceCounter(&m_nEndTime);
printf("\nElapsed Time=%lf sec\n",(double)(m_nEndTime.QuadPart-m_nBeginTime.QuadPart)/m_nFreq.QuadPart);
}
int fileRead(FILE *fp)
{
int num[4];
int count = 0;
while (fread(num, sizeof(int), 4, fp) && count < ARRAYSIZE) {
points[count].initDot();
for (int i = 0; i < 4; i++) {
points[count].pos[i] = num[i];
}
count++;
}
return count;
}
void countNeighbour(int count, double distance)
{
for (int i = 0; i < count - 1; i++) {
for (int j = i + 1; j < count; j++) {
if (sqrt((double)((points[i].pos[0]-points[j].pos[0])*(points[i].pos[0]-points[j].pos[0])
+(points[i].pos[1] - points[j].pos[1])*(points[i].pos[1] - points[j].pos[1])
+(points[i].pos[2] - points[j].pos[2])*(points[i].pos[2] - points[j].pos[2]) +
(points[i].pos[3] - points[j].pos[3])*(points[i].pos[3] - points[j].pos[3]))) < distance)
{
points[i].ngb++;
points[j].ngb++;
}
}
}
}
void showResult(int count, int k)
{
bool flag = true;
for (int i = 0; i < count; i++) {
if (points[i].ngb == k) {
printf("第%d个点:(%d,%d,%d,%d)\n",i,points[i].pos[0], points[i].pos[1], points[i].pos[2],
points[i].pos[3]);
flag = false;
}
}
if (flag) {
printf("没有符合要求的点。\n");
}
}
