2012年上機題
題目
??從服務(wù)器上下載數(shù)據(jù)文件org.dat文件以二進(jìn)制方式存放一系列整數(shù)阳啥，每個整數(shù)占4個字節(jié)。從第一個整數(shù)開始，第一個整數(shù)和第二個整數(shù)構(gòu)成一個坐標(biāo)點兜喻，依次類推泡仗，數(shù)據(jù)文件中保存了許多坐標(biāo)點數(shù)據(jù)埋虹。
??問題1：
??規(guī)定處于第一象限的坐標(biāo)點為有效點，請問數(shù)據(jù)文件中所有點的個數(shù)n為多少娩怎？有效點的個數(shù)k為多少搔课？
??問題2：
??每個有效點與坐標(biāo)原點構(gòu)成一個的矩形，請問k個有效點與坐標(biāo)原點構(gòu)成的k個矩形的最小公共區(qū)域面積為多少截亦？
??問題3：
??尋找有效點中符合下列條件的點：以該點為坐標(biāo)原點爬泥，其他有效點仍然是有效點即處于第一象限（不包括坐標(biāo)軸上的點）柬讨。輸出這些點。
??問題4：
??對所有有效點進(jìn)行分組袍啡，每個有效點有且只能屬于一個分組踩官，分組內(nèi)的點符合下列規(guī)則：若對組內(nèi)所有點的x坐標(biāo)進(jìn)行排序，點p1（x1境输，y1）在點p2（x2蔗牡，y2）后面，即x1>x2那么y1>y2.請輸出所有的分組嗅剖。
分析
??我看到有的代碼是分題做的辩越，這樣更好給分，但是我就混在一起了窗悯，因為有些功能可以同時完成区匣。
??我大概分成下面幾個部分：
??（1）讀文件，求出n和k蒋院，保存有效點亏钩。
??（2）以x的的大小由小到大進(jìn)行排序。經(jīng)過簡單處理欺旧」贸螅可以得到最小公共面積和問題三所求的點。
??（3）分組辞友。我就遍歷了栅哀，對每個點給了一個符號位。時間復(fù)雜度比較高称龙。
代碼
#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);
}
// 造數(shù)據(jù)文件留拾，coor.txt中已經(jīng)存放了一些數(shù)據(jù)
//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("所有點的個數(shù)為：%d\n", n);
printf("支配點的個數(shù)為：%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("符合要求的點的坐標(biāo)為：(%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("符合要求的點的坐標(biāo)為：(%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("沒有符合要求的點的坐標(biāo)鲫尊。\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年上機題
題目
??二進(jìn)制數(shù)據(jù)文件1.bin中存放了100000個樣本點痴柔，每個樣本點由4個屬性構(gòu)成，屬性均為整型疫向。
??定義： 如a點的k個屬性不比b點的對應(yīng)屬性差（屬性值越小越好）咳蔚，
??且a點至少有一個屬性比b點的對應(yīng)屬性好，則稱a點k-支配b點搔驼。
??要求： 求出不被任何點k-支配的樣本點的個數(shù)谈火。
??在試卷上填寫求出的樣本點個數(shù)和所用時間（Elapsed Time）。
分析
??這道題看上去不難舌涨，但是倒是花費了我不少的時間糯耍，其中有許多大大小小的bug。先簡單介紹一下程序的幾個部分：
??（1）計時（這個已經(jīng)寫好了）
??（2）讀取文件中的數(shù)據(jù)并保存。
??（3）遍歷數(shù)組谍肤，尋找不被控制的數(shù)據(jù)啦租。
??我原來打算直接開一個$100000*4$的數(shù)組來保存數(shù)據(jù)，但是報了stack overflow的錯荒揣，我查了下，說是棧的默認(rèn)大小是1M焊刹，這明顯超過了系任。我就決定用結(jié)構(gòu)體+手動分配內(nèi)存，但是沒想到保存結(jié)構(gòu)體指針的數(shù)組也超過了內(nèi)存限制（原諒我沒算）虐块。后來發(fā)現(xiàn)只要開成全局變量就好了俩滥。
??考慮到數(shù)據(jù)有100000個，昨天丁大佬說10000個數(shù)據(jù)的話復(fù)雜度為$n2$就有些大了贺奠，我就考慮到能不能減少時間復(fù)雜度霜旧。著就想到了鏈表。最開始的構(gòu)想是兩層遍歷儡率，去掉被控制的點挂据。后來想到為了減少比較的次數(shù)，可以設(shè)置標(biāo)志位儿普。既然說到了標(biāo)志位崎逃，就想到不如直接用鏈表刪掉被控制的點就好了。這個算法的時間復(fù)雜度我沒有求眉孩，但是最好情況是$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組數(shù)據(jù)浪汪，每組數(shù)據(jù)有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)}$;現(xiàn)定義k=10广恢，d=7500，顯示出符合點的編號及其各個屬性殃姓。
分析
??這道題就是兩次循環(huán)求解袁波，不難，但是數(shù)據(jù)量比較大蜗侈，時間比較長篷牌。
代碼
#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");
}
}
