配套作业——分治策略

需求

• 解释分治策略的基本思想，并用它分析大整数相乘问题

• 选做：编程实现大整数相乘问题（选做）

• 编程实现二分搜索，快速排序，棋盘覆盖问题

• 编程实现归并排序，并简述其中的分治策略体现在哪里（选做）

实现

大整数相乘

• 解释与分析
• 代码实现
• 测试运行

• 分治策略思想：
  • 分：把问题分解成两个或者更小规模的子问题
  • 治：利用递归解决子问题
  • 合：归并子问题的解得到原问题的解
• 如果用分治策略解大整数相乘问题：
  • 把两个整数拆分成四个小整数相乘
  • 利用·AD+BC）=（A+B）*（C+D）-AC-BD替换，将4次乘法运算降低到3次

• 这里的大整数相乘只是着重于降低算法的时间复杂度，并不能真正做到大整数相乘（溢出）
• 要写出真正的大整数相乘，应该用一个字符数组来输入输出数组
• 感兴趣的读者可以参考基础算法二 | Gallifrey’s Blog中高精度乘法，编写真正的两个大整数相乘代码

#include <iostream>
using namespace std;
int n=1;//位数
int n2=1;
long long multiply(long long x, long long y) {
	long long a, b,c,d,res;

	a = x;
	b = 0;
	c = y;
	d = 0;
	//处理得到 a,b,c,d
	for(int i=0;i<n/2;i++)	a = a / 10;
	for (int i = 0; i < n / 2; i++)	c = c / 10;
	b = x - a * pow(10, n / 2);
	d = y - c * pow(10, n / 2);
	//计算过程
	//res = a * c * pow(10, n) + (a * d + b * c) * pow(10, n / 2)+b*d;
	//其中 a*d+b*c= (a+b)*(c+d)-b*d-a*c ;将4次乘法将为3次
	res = a * c * pow(10, n) + ((a + b) * (c + d) - b * d - a * c) * pow(10, n / 2) + b * d;

	return res;
}


int main() {
	long long  x, y,tempx,tempy;
	cin >> x >> y;
	tempx = x;
	tempy = y;
	//得到位数
	while (tempx /= 10) { n++; }
	while (tempy /= 10) { n2++; }


	cout << multiply(x, y);
	return 0;
}

二分搜索

• 代码实现
• 测试运行

#include<iostream>
using namespace std;

int binarySearch(int arr[], int len, int target) {
	int low = 0, high = len - 1,mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (arr[mid] == target) return mid;
		else if (arr[mid] < target) low = mid + 1;
		else if (arr[mid] > target)  high = mid - 1;
	}
	return -1;
}


int main() {
	int arr[11] = { 1,3,5,7,9,11,22,41,53,77,214 };
	
	cout << "int arr[11] = { 1,3,5,7,9,11,22,41,53,77,214 };" << endl;
	cout << "binarySearch(arr, 11, 77);" << endl;
	cout << "index: " <<binarySearch(arr, 11, 77) << endl;
	return 0;
}

快速排序

• 代码实现
• 测试运行

#include<iostream>
using namespace std;

void quicksort(int arr[], int low, int high) {
	if (low >= high) return;//没有数返回
	int l = low, h = high;
	int x = arr[low];
	while (low < high) {
		while ((low < high) && (arr[high] >= x)) high--;
		swap(arr[low], arr[high]);
		while ((low < high) && (arr[low] <=x))low++;
		swap(arr[low], arr[high]);
	}
	quicksort(arr, l, high - 1);
	quicksort(arr, high +1 ,h);
}



int main() {

	int arr2[9] = { 24,528,46,235,623,9,58,32,3 };
	quicksort(arr2, 0, 8);
	cout << "int arr2[9] = { 24,528,46,235,623,9,58,32,3 };" << endl;
	cout << "quicksort(arr2, 0, 8); " << endl;
	for (int temp : arr2) {
		cout << temp << " ";
	}

	return 0;

}

归并排序

• 代码实现
• 测试运行

#include<iostream>
using namespace std;
const int N = 100000;
int tmp[N];

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];
}



int main() {
	//int arr[11] = { 1,3,5,7,9,11,22,41,53,77,214 };
	
	//cout << "int arr[11] = { 1,3,5,7,9,11,22,41,53,77,214 };" << endl;
	//cout << "binarySearch(arr, 11, 77);" << endl;
	//cout << "index: " <<binarySearch(arr, 11, 77) << endl;

	int arr2[9] = { 24,528,46,235,623,9,58,32,3 };
	//quicksort(arr2, 0, 8);
	cout << "int arr2[9] = { 24,528,46,235,623,9,58,32,3 };" << endl;
	//cout << "quicksort(arr2, 0, 8); " << endl;
	cout << "merge_sort(arr2, 0, 8); " << endl;

	merge_sort(arr2, 0, 8);
	for (int temp : arr2) {
		cout << temp << " ";
	}
	return 0;

}

棋盘覆盖问题

• 代码实现
• 测试运行

• 这里的java代码是直接沿用了这篇文章(18条消息) 算法：棋盘覆盖问题怎么取名啊的博客-CSDN博客棋盘覆盖问题，文章里对解题过程做了很详细的解释，感兴趣的读者也可以看一下
• 其实棋盘覆盖问题，如果手写一下过程去解题是很容易理解的，只是代码规模比较大
• 读者可以尝试手画一个8*8的棋盘，手动模拟一下解题是过程，感受分治策略在其中的应用
• 代码中变量解释：
  • BOARD_SIZE：方格大小
  • board：用于表示棋盘
  • title：表示每个L型骨牌的颜色（用数字表示）
  • tr：棋盘的行
  • tc：棋盘的列
  • （tr,tc）始终表示每一个区域的左上角，用于区域划分
  • dr：特殊方格所在的行
  • dc：特殊方格所在的列
  • size：棋盘的边长

public class ChessBoardCoverage {
    public static void main(String[] args) {
        chessBoard(0, 0, 2, 2, BOARD_SIZE);
        display();
    }

    private static int BOARD_SIZE = 16 ;  //棋盘大小 记得是2的整数次方
    private static int[][] board = new int[BOARD_SIZE][BOARD_SIZE];    //棋盘
    //用数字表示填充颜色
    private static int title = 0;

    //在以tr,tc为左上角，宽高为size，特殊点在dr,dc位置上的矩阵内进行分割划分
    public static void chessBoard(int tr, int tc, int dr, int dc, int size) {
        //如果切割出来的矩阵宽高为一，则不能继续分割，结束递归
        if (size == 1) {
            return;
        }
        //每次递归矩阵边长除2（划分区域）
        int s = size / 2;
        //在该层级内划分出来的四个区域肯定有三个区域要填特殊方格，那么这三个特殊区域的方格数字是一样的
        int num = ++title;
        //特殊方格在左上区域
        if (dr < tr + s && dc < tc + s) {
            chessBoard(tr, tc, dr, dc, s);
        }
        else {
            //如果不在左上区域，就把右下角格子设置为特殊方格
            board[tr + s - 1][tc + s - 1] = num;
            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] = num;
            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 {
            //如果不在左下区域，就把右上角格子设置为特殊方格
            board[tr + s][tc + s - 1] = num;
            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 {
            //如果不在右下区域，把左上角格子设置为特殊方格
            board[tr + s][tc + s] = num;
            chessBoard(tr + s, tc + s, tr + s, tc + s, s);
        }
    }

    //输出棋盘
    public static void display() {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                System.out.printf("%4d", board[i][j]);
            }
            System.out.println("");
        }
    }
}

• 当然只要轻微修改一下，你就可以获得一份C++的代码

#include <iostream>
using namespace std;
const int BOARD_SIZE = 16;  //棋盘大小
int board[BOARD_SIZE][BOARD_SIZE] ;   //棋盘
 //用数字表示填充颜色
int title = 0;


void chessBoard(int tr, int tc, int dr, int dc, int size) {
	//如果切割出来的矩阵宽高为一，则不能继续分割，结束递归
	if (size == 1) {
		return;
	}
	//每次递归矩阵边长除2（划分区域）
	int s = size / 2;
	//在该层级内划分出来的四个区域肯定有三个区域要填特殊方格，那么这三个特殊区域的方格数字是一样的
	int num = ++title;
	//特殊方格在左上区域
	if (dr < tr + s && dc < tc + s) {
		chessBoard(tr, tc, dr, dc, s);
	}
	else {
		//如果不在左上区域，就把右下角格子设置为特殊方格
		board[tr + s - 1][tc + s - 1] = num;
		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] = num;
		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 {
		//如果不在左下区域，就把右上角格子设置为特殊方格
		board[tr + s][tc + s - 1] = num;
		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 {
		//如果不在右下区域，把左上角格子设置为特殊方格
		board[tr + s][tc + s] = num;
		chessBoard(tr + s, tc + s, tr + s, tc + s, s);
	}
}
//输出棋盘
void display() {
	for (int i = 0; i < BOARD_SIZE; i++) {
		for (int j = 0; j < BOARD_SIZE; j++) {
			printf("%4d", board[i][j]);
		}
		printf("\n");
	}
}

int main() {
	chessBoard(0, 0, 2, 2, BOARD_SIZE);
	display();
}

• 从数字的大小能看出棋盘覆盖实现的过程