分治法

算法设计与分析
Word count: 1.4k   |   Reading time≈ 7 min

1.ChessCovering 问题（棋盘覆盖）

易知，覆盖任意一个2^k×2^k的特殊棋盘，用到的骨牌数恰好为(4^K-1)/3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <stdlib.h>
#define N 8 //2^k×2^k
int Board[N][N];//定义一个棋盘
int tile = 1; //表示骨牌的型号
void ChessBoard(int r, int c, int fr, int fc, int size);
//r表示棋盘左上角行号，c表示棋盘左上角列号，fr表示特殊方格所在行号，fc表示特殊方格所在列号，size棋盘规格

/*原理：为无特殊方格的小棋盘（分之后的）添加特殊方格*/

int main() {
	//将棋盘各方格初始化为0
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			Board[i][j] = 0;

	ChessBoard(0, 0, 2, 2, N);

	//输出棋盘
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			printf("%d\t", Board[i][j]);
		printf("\n");
	}
	system("PAUSE"); //因编译器原因，防止运行结果闪退
}

void ChessBoard(int r, int c, int fr, int fc, int size) {
	if (size == 1)
		return;
	int t = tile++; 								//本列用相同数字表示骨牌
	int s = size / 2;

	if (fr < r + s && fc < c + s) 					//特殊方格在此小棋盘内
		ChessBoard(r, c, fr, fc, s);
	else { 											//特殊方格不在此棋盘
		Board[r + s - 1][c + s - 1] = t; 			//用t号骨牌覆盖右下角
		ChessBoard(r, c, r + s - 1, c + s - 1, s); 	//继续覆盖其余方格
	}
	//后面三个if-else类似于第一个
	if (fr >= r + s && fc < c + s) 					//特殊方格在此小棋盘内（第三象限），人为选定默认认为在
		ChessBoard(r + s, c, fr, fc, s); 			//棋盘左上角坐标为(r+s,c)
	else { 											//特殊方格不在此小棋盘内
		Board[r + s][c + s - 1] = t; 				//选定(r+s,c+s-1)为特殊方块，用t号骨牌覆盖右上角
		ChessBoard(r + s, c, r + s, c + s - 1, s); 	//继续覆盖其余方格
	}

	if (fr < r + s && fc >= c + s) 					//特殊方格在此小棋盘内（第一象限），人为选定默认认为在
		ChessBoard(r, c + s, fr, fc, s);
	else { 											//特殊方格不在此小棋盘内
		Board[r + s - 1][c + s] = t; 				//用t号骨牌覆盖左下角
		ChessBoard(r, c + s, r + s - 1, c + s, s);
	}

	if (fr >= r + s && fc >= c + s) 				//特殊方格在此小棋盘内（第四象限），人为选定默认认为在
		ChessBoard(r + s, c + s, fr, fc, s);
	else { 											//特殊方格不在此小棋盘内
		Board[r + s][c + s] = t; 					//用t号骨牌覆盖左上角
		ChessBoard(r + s, c + s, r + s, c + s, s);
	}

}

2.最接近点对问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>

// 定义一个二维点的结构体
struct Point {
	int x, y;
};

// 比较函数，用于根据x坐标对点进行排序
int compareX(const void* a, const void* b) {
	return ((struct Point*)a)->x - ((struct Point*)b)->x;
}

// 比较函数，用于根据y坐标对点进行排序
int compareY(const void* a, const void* b) {
	return ((struct Point*)a)->y - ((struct Point*)b)->y;
}

// 计算两点之间的距离
float dist(struct Point p1, struct Point p2) {
	return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

// 计算最小距离的函数
float min(float x, float y) {
	return (x < y) ? x : y;
}

// 在给定点集中找到最小距离的函数,左右区计算最近距离
float bruteForce(struct Point P[], int n) {
	float min_distance = FLT_MAX;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (dist(P[i], P[j]) < min_distance) {
				min_distance = dist(P[i], P[j]);
			}
		}
	}
	return min_distance;
}

// 使用分治法找到最小距离的函数
float closestUtil(struct Point Px[], struct Point Py[], int n) {
	if (n <= 3) { //分为每个区3个，再BF算最小距离
		return bruteForce(Px, n);
	}

	// 找到中间点
	int mid = n / 2;
	struct Point midPoint = Px[mid];

	// 分别在左右子集中递归查找最小距离
	float dl = closestUtil(Px, Py, mid);
	float dr = closestUtil(Px + mid, Py + mid, n - mid);

	// 取两个子集中的最小距离
	float d = min(dl, dr);

	// 构建y坐标在(d - 2d, d + 2d)范围内的点集
	struct Point strip[n];
	int j = 0;
	for (int i = 0; i < n; i++) {
		if (abs(Py[i].x - midPoint.x) < d) {
			strip[j] = Py[i];
			j++;
		}
	}

	// 找到strip中的最小距离
	float minStrip = bruteForce(strip, j);

	// 返回最小距离
	return min(d, minStrip);
}



// 主函数，计算最小距离
float closest(struct Point P[], int n) {
	struct Point Px[n];
	struct Point Py[n];
	for (int i = 0; i < n; i++) {
		Px[i] = P[i];
		Py[i] = P[i];
	}

	// 按x坐标排序
	qsort(Px, n, sizeof(struct Point), compareX);

	// 按y坐标排序
	qsort(Py, n, sizeof(struct Point), compareY);

	// 使用分治法计算最小距离
	return closestUtil(Px, Py, n);
}

// 示例用法
int main() {
	struct Point P[] = {
		{8,-15},{9,-29},{29,-28},{-30,-13},{-3,45},{-33,-12},{-7,35},{47,-45},{43,-10},{24,-6},
		{47,23},{18,-23},{-37,16},{-45,-1},{1,-43},{-42,16},{-16,-50},{-39,35},{-48,38},{-26,-28},
		{49,31},{42,-36},{-50,-33},{41,36},{-13,14},{4,5},{32,-19},{0,17},{-35,15},{18,-5},
		{14,46},{0,23},{-7,28},{-45,-28},{46,10},{5,-31},{42,5},{-28,-22},{36,-13},{-24,-39},
		{-12,-8},{42,-47},{29,6},{30,26},{30,6},{-14,-39},{-49,16},{39,-20},{-35,28},{-33,13}
	};

	int n = sizeof(P) / sizeof(P[0]);

	printf("最接近点的距离是 %f\n", closest(P, n));

	return 0;

}
Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2022-2024 CoffeeLin
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信