1
2
3
4
5
6
7
8
divide-and-conquer(P)
{
　if ( |P| <= n0) adhoc(P);   //解决小规模的问题
　divide P into smaller subinstances P1,P2,...,Pk；//分解问题
　for (i=1,i<=k,i++)
　yi=divide-and-conquer(Pi);  //递归的解各子问题
　return merge(y1,...,yk);  //将各子问题的解合并为原问题的解
}

1
2
3
4
5
min←a[0];max←a[0];//伪代码
For i←1 to n-1 do
    if a[i]<min 
            min←a[i]
       else if a[i]>max max←a[i]

1
2
3
4
5
6
7
8
9
Max-min(A[0,n-1],max,min)//伪代码
  if n=1 max←min←a[0],return;//解决小规模问题
  if n=2 {
      if a[0]≥a[1] max←a[0],min←a[1] //解决小规模问题
              else max←a[1],min←a[0];
      } else m←n/2 
             Max-min(A[0,m-1],max1,min1),Max-min(A[m,n-1],max2,min2),//递归的解决各类子问题
             max←max(max1,max2), min←min(min1,min2),//将子问题的解合并为原问题的解
             return.

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
//归并排序
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

//快速排序
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/39790/
来源：AcWing

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
void MergeSort(int r[], int low, int high) { // 进行归并排序
	int mid, r1[1000], i;
	if (low == high)
		return;
	else {
		mid = (low + high) / 2; // 划分
        
		MergeSort(r, low, mid); // 递归求左子序列中逆序对
		MergeSort(r, mid + 1, high); // 递归求右子序列中逆序对
        
		Merge(r, r1, low, mid, high); // 合并
		for (i = low; i <= high; i++)
			r[i] = r1[i];
	}
}

void Merge(int r[], int r1[], int low, int mid, int high) { // 合并子序列
	int i = low, j = mid + 1, k = low;
    
	while (i <= mid && j <= high) {
		if (r[i] <= r[j]) {// 取较小者放入r1[k]中
			r1[k++] = r[i++];
		} else {
			count += mid - i + 1;
			// 若左子序列中的数1大于右子序列的数2，则数1后面的数都大于数2
			r1[k++] = r[j++];
		}
	}
	while (i <= mid) r1[k++] = r[i++];
	while (j <= high) r1[k++] = r[j++];
}

1
2
3
4
5
6
7
8
9
10
template<class Type>
int BinarySearch(Type a[],const Type&x,int l,int x)
{
    while(r>=l)
    {
        int m=(l+r)/2;
        if(x==a[m])return m;
        if(x<a[m])r=m-1;else l=m+1;
    }
}

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
void chessBoard(int tr, int tc, int dr, int dc, int size) {
    //dr,dc残缺方块所在行列
    //tr,tc棋盘中左上角方格所在行列
	if (size == 1) return;
	int t = tile++, // L型骨牌个数
	    s = size / 2; // 子棋盘大小
    
	// 覆盖左上角子棋盘
	if (dr < tr + s && dc < tc + s)
		// 特殊方格在此子棋盘中
		chessBoard(tr, tc, dr, dc, s);
	else {// 此子棋盘中无特殊方格
		// 用 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 {// 此子棋盘中无特殊方格
		// 用L型骨牌覆盖左下角
		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 {// 用 L型骨牌覆盖右上角
		board[tr + s][tc + s - 1] = t;
		// 覆盖其余方格
		chessBoard(tr + s, tc, tr + s, tc + s - 1, s);
	}
    
	// 覆盖右下角子棋盘
	if (dr >= tr + s && dc >= tc + s)
		// 特殊方格在此子棋盘中
		chessBoard(tr + s, tc + s, dr, dc, s);
	else {// 用 L型骨牌覆盖左上角
		board[tr + s][tc + s] = t;
		// 覆盖其余方格
		chessBoard(tr + s, tc + s, tr + s, tc + s, s);
	}
}

void OutputBoard(int size) {
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++)
			cout << setw (5) << Board[i][j];
		cout << endl;
	}
}        

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
void gametable(int k) {
	int a[100][100];
	int n, temp, i, j, p, t;
    
	n = 2; //两个参赛选手日程
	a[1][1] = 1;
	a[1][2] = 2;
	a[2][1] = 2;
	a[2][2] = 1;
    
	for (t = 1; t < k; t++)
		//迭代处理，依次处理2 ^ n....2 ^ k个选手的比赛日程
	{
		temp = n;
		n = n * 2; //填左下角元素
		for (i = temp + 1; i <= n; i++)
			for (j = 1; j <= temp; j++)
				a[i][j] = a[i - temp][j] + temp;
        
		//左下角和左上角元素的对应关系
		for (i = 1; i <= temp; i++)
			//将左下角元素抄到右上角
			for (j = temp + 1; j <= n; j++)
				a[i][j] = a[i + temp][(j + temp) % n];
        
		for (i = temp + 1; i <= n; i++)
			//将左上角元素抄到右下角
			for (j = temp + 1; j <= n; j++)
				a[i][j] = a[i - temp][j - temp];
	}
}