This is the 30th day of my participation in the Wenwen Challenge

There may be times when problems cannot be solved using any known algorithm. Try to find a solution using the various problem solving methods you have mastered. Divide and conquer (D&C), a famous recursive problem solving method, is a general problem solving method. This article will delve into the heart of the algorithm. Algorithms that can only solve one problem are of limited use after all, and D&C is another tool that can be used to provide ideas for solving problems.

Suppose a farmer owns a small piece of land (1680m by 640m). You need to divide the land into squares evenly and as large as possible.

How do you divide a field evenly into squares and make sure the squares are the largest? Use the D&C strategy! The D&C algorithm is recursive.

The problem solving process with D&C consists of two steps.

(1) Find the baseline condition, which is as simple as possible.

(2) Break the problem down (or scale it down) until it fits the baseline.

First, find the baseline conditions. The easiest case to deal with is when the length of one edge is the integer value of the other. If one side is 25m long and the other side is 50m long, the maximum square that can be used is 25m by 25m. In other words, you can divide the field into two squares like this.

By D&C’s definition, each recursive call reduces the size of the problem. We start by finding the largest square that can fit into the field. You can draw two blocks of 640m by 640m from this plot, leaving a small plot of land. Do the same for the remaining piece.

The original land size to be divided was 1680m * 640m, but now the land to be divided is smaller, 640m * 400m. The biggest square that works for this plot is also the biggest square that works for the whole plot. In other words, the problem of evenly dividing 1680m * 640m land will be solved. This simplifies to a uniform partition of 640m by 400m.

Let’s use the same algorithm again. For an area of 640m by 400m, the largest square that can be drawn from it is 400m by 400m. That would leave a smaller piece of land, measuring 400m by 240m. Mark out the largest square, leaving a smaller area of 240m by 160m. Then mark out the largest square, the remaining size is 80m by 160m. Because 160 is an integer multiple of 80, the rest of the land meets the baseline condition. Divide an 80m by 160m plot into two squares and there will be no land left.

Therefore, for the original 1680m by 640m piece of land, the maximum square applicable is 80m by 80m.

D&C is not an algorithm that can be used to solve problems, but a way of thinking about solving problems.