Divide and treat and some interesting problems

Tram Ho

1) What is division and rule?

Divide and Conquer is an important method in designing algorithms. The idea of ​​this method is quite simple and easy to understand: When we need to solve a problem, we will proceed to divide it into smaller subproblems. Continue to divide until these small problems cannot be further divided, then we will solve these smallest problems and finally combine the solutions of all small problems to find the solution of the problem. initial math.

In general, you can understand the Divide and Conquer algorithm through the following 3 steps:

– Step 1: Divide (Divide)

In this step, we divide the initial problem into subproblems. Each subproblem should be part of the original problem. In general, this step uses a recursive approach to break the problem down until it cannot be further divided. Then, the subproblems were called “atomic”, but they still represent some part of the original problem.

– Step 2: Solve the subproblem (Conquer)

Solve the subproblems discussed above

– Step 3: Combine subproblems to give the answer of the original problem

2) A few examples apply

a) Binary search

  • A relatively familiar problem when learning about algorithms: Given a sorted array, find the position of the number k in the array.

ex: Array 1, 2, 4, 7, 9

Find position of number 4 => position 3

Input:

– The first line contains 2 natural numbers n (the number of elements of the array) and k (the position to find)

Line 2 contains n increasing natural numbers

Output: the kth number in the sequence

Solution: We can go from the beginning of the array to the end of the array, if an element is equal to its value, it will be returned. But this way has complexity O (n) => should only be used when the quantity is small

What if we apply division to rule?

The special point here is that the array has been sorted so we can do the following:

Thus, the complexity will be reduced to O (log (n)).

b) Fibonaci strings

  • Still the familiar Fibonaci problem, but slightly modified:

The fibonaci strings are defined as follows:

Finds the kth character of the nth fibonaci string

Input: 2 natural numbers n (fibonaci order by definition) and k (position to find)

Output: Print out the kth character of the nth fibonaci sequence

More details on the problem can be found here

Method 1: Solve in the way that each gene makes sequences to the desired sequence and get the kth position

But for the above problem with the condition n <93. that is, in the 92th string the length of the string will ~ 7 500 000 000 000 000 000 (read 7.5 billion billion: v) and the storage of such a string, the compiler will respond to that

Method 2: Apply division to rule

Parse: call length[] an array containing lengths of words first > n 1 -> n 1 > n

To find the kth position in th fibonaci sequence n n n . Let’s go find the location k k k is in the range n – 2 if k < = l e n g t H [ n 2 ] k <= length [n-2] k < = l e n g t h [ n 2 ] and location k l e n g t H [ n 2 ] k – length [n – 2] k l e n g t h [ n 2 ] otherwise. Repeat until k = first k = 1 k = 1 then return “A” and k = 2 then return “B”

c) Double the sequence

A sequence of natural numbers starts with the number 1 and is performed N-1 transforms “double” the sequence as follows: With the current sequence A, the new number has the form A, x, A where x is the smallest natural number that does not appear in A. Example with 2 steps of transformation.

We have [ first ] > [ 121 ] > [ 1213121 ] [1] -> [1 2 1] -> [1 2 1 3 1 2 1] [ 1 ] > [ 1 2 1 ] > [ 1 2 1 3 1 2 1 ] . What is the number K in the last sequence of numbers?

Input: 2 natural numbers n (fibonaci order by definition) and k (position to find)

Output: Print out the kth character of the sequence after n – 1 transformation

Analysis: Following n first n – 1 n For a transformation, the length of the number will be 2 n first 2 ^ n – 1 2 n 1 .

To find the kth position in the n sequence. We will find the kth element in the sequence n first n – 1 n 1 if k is less than the position of the middle element of the sequence and the position k n first k – n – 1 k n 1 if k is greater than the middle position of the sequence

repeat until k is the center element of the current sequence then the result will be n

3) Disadvantages of divide and conquer

It looks dangerous, but everything has its disadvantages and so does the division and treatment algorithm.

The biggest problem is how to divide the big problem into small problems and small problems must have the same solution, otherwise the complexity will multiply.

This article I introduced you to the division and value algorithm and an example. Hope you can use people at the right time “okay: v

Share the news now

Source : Viblo