分治算法

棋盘覆盖问题

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
/*
(tr,tc)是棋盘左上角的方格坐标
(dr,dc)是特殊方格所在坐标
size是棋盘的行数和列数
*/
#include <iostream>
using namespace std;
#define N 1025
int board[N][N];
static int tile = 1;

void ChessBoard(int tr, int tc, int dr, int dc, int size) {
if(size == 1) return; //递归边界
int t = tile++; //L型骨牌号
int s = size/2; //分割棋盘
//覆盖左上角子棋盘
if(dr < tr + s && dc < tc + s)
ChessBoard(tr, tc, dr, dc, s);
else { //此棋盘中无特殊方格,用t号L型骨牌覆盖右下角
board[tr + s - 1][tc + s - 1] = t;
//覆盖其余方格
ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
}
//覆盖右上角子棋盘
if(dr < tr + s && dc >= tc + s)
Chessboard(tr, tc + s, dr, dc, s);
else {
board[tr + s - 1][tc + s] = t;
ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
}
//覆盖左下角子棋盘
if(dr >= tr + s && dc < tc + s) //特殊方格在此棋盘中
ChessBoard(tr + s, tc, dr, dc, s);
else { //此棋盘中无特殊方格,用t号L型骨牌覆盖右上角
board[tr + s][tc + s - 1] = t;
//覆盖其余方格
ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
}
//覆盖右下角子棋盘
if(dr >= tr + s && dc >= t c+ s) //特殊方格在此棋盘中
ChessBoard(tr + s, tc + s, dr, dc, s);
else { //此棋盘中无特殊方格,用t号L型骨牌覆盖左上角
board[tr + s][tc + s] = t;
//覆盖其余方格
ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
}
}

int main() {
int i, j, k, x, y;
while(cin >> k) { //k cases
int size = 1 << k;
cin >> x >> y;
board[x][y] = 0;
ChessBoard(0, 0, x, y, size);
for(i = 0; i < size; i++) {
for(j = 0; j < size; j++)
cout << board[i][j] << '\t';
cout << '\n';
}
}
return 0;
}
1
2
3
4
n = 4^k
需(n-1)/3个L型骨牌填满
算法的时间复杂度: t(n)=4t(n/4)+c
Master Method求解得到: t(n)=Theta(n)

分治算法

归并排序

source

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
// C++ program for Merge Sort
#include <iostream>
using namespace std;

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;

// Create temp arrays
int L[n1], R[n2];

// Copy data to temp arrays L[] and R[]
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

// Merge the temp arrays back into arr[l..r]

// Initial index of first subarray
int i = 0;

// Initial index of second subarray
int j = 0;

// Initial index of merged subarray
int k = l;

while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

// Copy the remaining elements of
// L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

// Copy the remaining elements of
// R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int arr[],int l,int r){
if(l>=r){
return;//returns recursively
}
int m = (l+r-1)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}

// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
}

// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

cout << "Given array is \n";
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}

// This code is contributed by Mayank Tyagi

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
void QuickSort(T a[], int l, int r) {
if(l >= r) return;
int i = l, j = r + 1;
T pivot = a[l];
while(true) {
do { i++; } while(a[i] < pivot);
do { j--; } while(a[j] > pivot);
if(i >= j) break;
swap(a[i], a[j]);
}
a[l] = a[j];
a[j] = pivot;
QuickSort(a, l, j - 1);
QuickSort(a, j + 1, r);
}

寻找第 k 小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class T>
T select(T a[], int l, int r, int k) {
if(l >= r) return a[l];
int i = l, j = r + 1;
T pivot = a[l];
while(true) {
do { i++; } while(a[i] < pivot);
do { j--; } while(a[j] > pivot);
if(i >= j) break;
swap(a[i], a[j]);
}
if(j - i + 1 == k) return pivot;
a[l] = a[j];
a[j] = pivot;
if(j - i + 1 < k)
select(a, j + 1, r, k - j + l - 1);
else select(a, l, j - 1, k);
}

距离最接近的点对

source

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
#include <bits/stdc++.h>
using namespace std;

struct point {
double x;
double y;
point(double x, double y) : x(x), y(y) {}
point() { return; }
};

bool cmp_x(const point& A, const point& B) {
return A.x < B.x;
}

bool cmp_y(const point& A, const point& B) {
return A.y < B.y;
}

double distance(const point& A, const point& B) {
return sqrt(pow(A.x - B.x, 2) + pow(A.y - B.y, 2));
}

/*
* function: 合并,同第三区域最近点距离比较
* param: points 点的集合
* dis 左右两边集合的最近点距离
* mid x坐标排序后,点集合中中间点的索引值
*/
double merge(vector<point>& points, double dis, int mid) {
vector<point> left, right;
for(int i = 0; i < points.size(); i++) {
if(points[i].x - points[mid].x <= 0 && points[i].x - points[mid].x > -dis)
left.push_back(points[i]);
else if(points[i].x - points[mid].x > 0 && points[i].x - points[mid].x < dis)
right.push_back(points[i]);
}
sort(right.begin(), right.end(), cmp_y);
for(int i = 0, index; i < left.size(); i++) {
for(index = 0; index < right.size() && left[i].y < right[index].y; index++);
for(int j = 0; j < 7 && index + j < right.size(); j++) {
if(distance(left[i], right[j + index]) < dis)
dis = distance(left[i], right[j + index]);
}
}
return dis;
}

double closest(vector<point>& points) {
if(points.size() == 2) return distance(points[0], points[1]);
if(points.size() == 3) return min(distance(points[0], points[1]), min(distance(points[0], points[2]), distance(points[1], points[2])));
int mid = (points.size() >> 1) - 1;
double d1, d2, d;
vector<point> left(mid + 1), right(points.size() - mid - 1);
copy(points.begin(), points.begin() + mid + 1, left.begin()); //左边区域点集合
copy(points.begin() + mid + 1, points.end(), right.begin()); //右边区域点集合
d1 = closest(left);
d2 = closest(right);
d = min(d1, d2);
return merge(points, d, mid);
}

int main() {
int cnt;
printf("点个数:");
scanf("%d", &cnt);
vector<point> points;
double x, y;
for(int i = 0; i < cnt; i++) {
printf("第%d个点", i);
scanf("%lf%lf", &x, &y);
point p(x, y);
points.push_back(p);
}
sort(points.begin(), points.end(), cmp_x);
printf("最近点对值:%lf", closest(points));
return 0;
}

两个 n*n 的矩阵 A 与 B 的乘积是另一个 n*n 的矩阵 C,则:进行了 n^3 次乘法和 n^2(n-1) 次加法。