分治算法

棋盘覆盖问题

/*
(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;
}

n = 4^k
需(n-1)/3个L型骨牌填满
算法的时间复杂度: t(n)=4t(n/4)+c
Master Method求解得到: t(n)=Theta(n)

分治算法

归并排序

source

// 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

快速排序

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 小的元素

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

#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) 次加法。