Divide and Conquer Algorithm in Python

• Typical of Divide and Conquer Algorithm

There is a pile of coins, containing one counterfeit coin. The counterfeit coin is lighter than the genuine coins. How can we quickly find the counterfeit coin using a balance?

By comparing them two by two until a lighter coin is found?

Divide into two piles, find the lighter pile, then divide it into two piles… divide into three piles…

• Concept of Divide and Conquer Algorithm

Divide and conquer means to divide and conquer, which can be understood in three parts:

(1) Divide: Split a complex problem into two or more similar subproblems, and then further divide the subproblems into smaller subproblems.

(2) Conquer: Finally, the subproblems can be solved easily and directly.

(3) Combine: The solutions of all subproblems combined together yield the solution to the original problem.

• Characteristics of Divide and Conquer Algorithm

(1) If the problem size is small enough, it can be easily solved. Most problems are like this.

(2) The problem can be decomposed into several smaller subproblems (i.e., it has optimal substructure properties) and follows a recursive approach.

(3) The solutions of the subproblems can be combined to obtain the solution to the problem. This follows a recursive thought process.

(4) The subproblems are independent of each other, and there are no common subproblems among them.

If these conditions are not met, although divide and conquer can solve the problem, its efficiency may not be better than other methods.

• Examples of Divide and Conquer Algorithm

(1) Permutation Problem

Classic problem example:

How many different arrangements can be made with the numbers 1, 2, 3, and 4?

This can be divided into arrangements starting with 1, 2, 3, and 4. Then continue to break down the problem.

(2) Integer Partition Problem

Classic problem example:

In how many ways can the number 4 be expressed as a sum of positive integers?

4 = 3 + 1

4 = 2 + 2

4 = 2 + 1 + 1

4 = 1 + 1 + 1 + 1

(3) Binary Search

Classic problem example:

A thinks of a number between 1 and 100.

B tries to guess it.

A tells B whether the guess is too high, too low, or correct.

We look at how many guesses B needs to make.

Binary search is commonly used to find counterfeit coins, guess numbers, and search for numbers in a sorted sequence.

• Divide and Conquer Algorithm Exercises

(1) (True/False) The general steps to solve a problem using the divide and conquer algorithm are decomposition, solving, and merging.

Correct Incorrect

Answer: Correct.

(2) (Multiple Choice) Which of the following is NOT a characteristic of the divide and conquer algorithm?

A. The problem can be easily solved when its size is reduced to a certain extent.

B. The solutions of the subproblems can be combined to form the solution to the original problem.

C. Each subproblem must be decomposed until it cannot be decomposed further.

D. The problem has optimal substructure properties.

Answer: C.

(3) (Multiple Choice) The problems that can be solved by the divide and conquer algorithm generally have the following characteristics. Which of the following descriptions is incorrect?

A. The problem can be easily solved when its size is reduced to a certain extent.

B. The problem can be decomposed into several smaller identical problems, i.e., it has optimal substructure properties.

C. The solutions of the subproblems can be combined to form the solution to the original problem.

D. The subproblems contain common subproblems.

Answer: D. There should not be common subproblems.

• Application of Divide and Conquer Algorithm 1

  Problem Description:

  Using binary search to find the square root of n or its approximate value.

  Program Implementation:

def sqrt(n):
  left=0
  right=n
  for i in range(30):
    mid=(left+right)/2
    if mid*mid>n:
      right=mid
    elif mid*mid<n:
      left=mid
    else:
      return mid
  return mid
print(sqrt(2))

• Application of Divide and Conquer Algorithm 2

  Problem Description:

  Given a list n containing a sequence of increasing positive integers, input x, and search for x in n. If found, output its index; otherwise, output -1. (Binary Search).

  Program Implementation:

  def  f(n, l, r, x):
    if r >= l:
      mid =int(l +(r-l)/2)
      if n[mid] == x:
        print(mid)
        return
      elif n[mid]> x:
        return f(n,l, mid-1,x)
      else:
        return f(n, mid+l, r, x)
  else:
      print(-1)
      return
  n=[2,3, 4, 10,40]
  x=10
  f(n, 0, len(n)-1,x)

• Application of Divide and Conquer Algorithm 3

  Problem Description:

  Given a list [5,3,7,6,4,1,0,2,9,10,8], implement a sorting algorithm using divide and conquer.

• Program Implementation:

  def fen(ls):
      mid = ls[0]
      left=[]
      right=[]
      for i in ls[1:]:
        if i<mid:
          left.append(i)
        else:
          right.append(i)
      return left,mid,right
  
  def paixu(ls):
      # If the decomposed ls is less than 1, it is solved
      if len(nums) <= 1:
          return nums
      else:
        # Decompose    
        leftls,mid,rightls = fen(ls)
        # Recursion (tree), divide and conquer, merge
        return paixu(leftls)+[mid]+paixu(rightls)
      
  ls =[7,5,0,6,3,4,1,9,8,2]
  print(paixu(ls)

Follow me to stay updated ⬇️⬇️⬇️