This is the 21st day of my participation in the August Text Challenge.More challenges in August
Divide and conquer
The overall thought
- The larger problem to be solved is divided into k smaller sub-problems
- Let’s solve each of these k subproblems. If the size of the subproblem is still not small enough, it is further divided into k as a subproblem, and the recursion continues until the problem is small enough to be easily solved
- Combine the solution of the small scale problem into the solution of a larger scale problem, and work out the solution of the original problem step by step from bottom up
Conditions of use
- The problem can be easily solved if it is scaled down to a certain extent
- The problem can be decomposed into several similar problems of smaller scale, that is, the problem has the property of optimal substructure
- The solution of the subproblem decomposed by this problem can be combined into the solution of this problem
- The subproblems decomposed by this problem are independent of each other, that is, there is no common subproblem among the subproblems
Whether the divide-and-conquer method can be used depends entirely on whether the subproblem has this feature. If it has the first two features but does not have the third feature, greedy algorithms or dynamic programming can be considered
Basic steps
divide-and-conquer(P) { if (|P| <= n0) abhoc(P); Divide P into smaller subinstances P1, P2,... For (I = 1; i <= k; i++) { yi = divide-and-conquer(Pi); // Return merge(y1,... ,yk) // Merge the solutions of each sub-problem into the original problem}}Copy the codecase
Overlays the incomplete checkerboard
- In a checkerboard consisting of 2k×2k squares, exactly one square is called a special checkerboard, which is different from the others.
- Place (n2) / 3 triples on an n × n defective chessboard and cover all the squares exactly
- Divided into four small chessboards
- One of them is a 4 × 4 defective chessboard
-
Put a three-grid board on the corner where the other three 4-by-4 boards are all adjacent to each other, making them defective boards as well
-
Recursively overwrites four 4×4 defective checkerboards
-
Place a three-grid board on the corner adjacent to the other three 4-by-4 checkerboards, making them defective checkerboards too.
Java code implementation
package Chess;
public class Chess {
// represents the checkerboard
private int[][] board;
// The size of the chessboard is raised to the power of 2
private int boardSize;
// The position of the special square in the board (row number, column number)
private int dr, dc;
private int tile = 1;
public Chess(a) {
board = new int[1] [1];
dr = 0;
dc = 0;
boardSize = 0;
}
public Chess(int r, int c, int s) {
int n;
n = (int) Math.pow(2, s);
if (n <= r || n <= c)
System.out.println("Initialization parameter error!");
else {
board = new int[n][n]; dr = r; dc = c; boardSize = s; }}public void Print(a) {
for (int i = 0; i < Math.pow(2.this.boardSize); i++) {
for (int j = 0; j < Math.pow(2.this.boardSize); j++) {
System.out.printf("%3d|".this.board[i][j]); } System.out.println(); }}public static void main(String[] args) {
// 2^2*2^2 checkerboard, assuming the special grid position is (3, 3)
Chess c1 = new Chess(3.3.2);
c1.chessBoard(0.0, c1.dr, c1.dc, (int)Math.pow(2, c1.boardSize));
c1.Print();
}
/ * * *@paramTr: Line number * in the upper left square of the board@paramTc: column number * in the upper-left square of the board@paramDr: the line number of the special box *@paramDc: indicates the column number * of the special board@paramSize: 2^k, 2^k*2^k **/
public void chessBoard(int tr, int tc, int dr, int dc, int size) {
if (size == 1) return;
// t: L dominoes, s split board
int t = tile++;
int s = size / 2;
// overrides the upper-left checkerboard
if (dr < tr + s && dc < tc + s) {
// Special squares are in this board
chessBoard(tr, tc, dr, dc, s);
} else {
// If there are no special squares in this checkerboard, cover the bottom right corner with t and L dominoes
board[tr + s - 1][tc + s - 1] = t;
// Overwrite the remaining squares
chessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
}
// Overwrite the upper right subcheckerboard
if (dr < tr + s && dc >= tc + s) {
// Special squares are in this board
chessBoard(tr, tc + s, dr, dc, s);
} else {
// No special squares, cover the lower left corner with t dominoes
board[tr + s - 1][tc + s] = t;
chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
}
// overwrite the bottom left checkerboard
if (dr >= tr + s && dc < tc + s) {
chessBoard(tr + s, tc, dr, dc, s);
} else {
// No special squares, cover the upper right corner with t dominoes
board[tr + s][tc + s - 1] = t;
chessBoard(tr + s, tc, tr + s, tc + s - 1, s);
}
// Overwrite the lower-right checkerboard
if (dr >= tr + s && dc >= tc + s) {
// Special squares are in this board
chessBoard(tr + s, tc + s, dr, dc, s);
} else {
// No special squares, cover upper left corner with t dominoesboard[tr + s][tc + s] = t; chessBoard(tr + s, tc + s, tr + s, tc + s, s); }}}Copy the code2 | 2 | 3 | 3 | 2 | 3 | 1 | 1 | | 1 | 4 5 5 4 4 | | | | | | 0Copy the codeMultiplication of large integers
- Primary school method: Inefficient O(n2)
- Divide and conquer method:
It is possible to get a better algorithm if you divide large integers into more segments and combine them in a more complex way
Strassen matrix multiplication
- Divide each matrix in matrices A, B and C into four equally sized sub-matrices, then C = AB can be written as:
- To reduce the time complexity, reduce the number of multiplications
