[Algorithm Design and Analysis]–Divide and Conquer Algorithm

Personal column:

Algorithm design and analysis: Algorithm design and analysis_IT Yan’s blog-CSDN blog

Java Basics: Java Basics_IT Yan’s Blog-CSDN Blog

C language: c language_IT Yan’s blog-CSDN blog

MySQL: Data Structure_IT Yan’s Blog-CSDN Blog

Data structure: Data structure_IT Yan’s blog-CSDN blog

C++: C++_IT Yan’s Blog-CSDN Blog

C51 MCU: C51 MCU (STC89C516)_IT Yan’s Blog-CSDN Blog

Webpage design and application based on HTML5: Webpage design and application based on HTML5_IT Yan’s Blog-CSDN Blog

python: python_IT Yan’s blog-CSDN blog

Welcome to watch, I hope it is useful to everyone!

Table of Contents

Purpose:

Problems and code analysis:

1) Implementation of binary search:

Code and analysis:

Import necessary classes:

Create the One class:

Perform a binary search in the main method:

The binarySearchHelper method implements binary search:

2) Minimum value problem: Find the minimum value of n elements:

Code and analysis:

Import necessary classes:

Create the One class:

Perform the search for the minimum value in the main method:

The findMinmumHelper method implements recursive search for the minimum value:

3) Power multiplication problem: Given a real number a and a natural number n, find a^n:

Code and analysis:

Imported the Scanner class:

main function:

power method:

Implementation of quick sort:

Code and analysis:

Imported the java.util.Arrays class:

main method:

Quick sort algorithm:

Split the array:

Swap the positions of two elements in an array:

Summary the characteristics of the divide-and-conquer algorithm:

Note: All complete codes:

Purpose:

1) Understand the algorithmic ideas and basic principles of the divide-and-conquer strategy;

2) Master the general characteristics of using the divide-and-conquer algorithm to solve problems;

3) Master the methods of decomposition and management;

4) Be able to correctly decompose, manage, and design divide-and-conquer algorithms for practical problems;

5) Be able to correctly analyze the time complexity and space complexity of the algorithm.

Problems and code analysis:

1) Implementation of binary search:

Code and analysis:

Import necessary classes:

Analysis: This line of code imports the java.util.Scanner class, which is used to read user input from the console.

import java.util.Scanner;
Create One class:

Analysis: This code defines a public class named One and contains the main method and the binarySearchHelper method.

public class One {
    public static void main(String[] args) {
        // ...
    }

    public static int binarySearchHelper(int[] arr, int target, int low, int high) {
        // ...
    }
}
Perform binary search in the main method:

analyze:

This code first creates a Scanner object scan for reading user input. Then, an ordered array of integers arr is defined, which contains the numbers 1, 3, 4, 7, 8, and 10.

Next, use System.out.println to print a prompt message asking the user to enter a number within 10. Then, use scan.nextInt() to read the user-entered target number from the console and store it in the variable target.

Finally, call the binarySearchHelper method to perform a binary search, passing in the array arr, the target number target, and the starting index of the array 0 and end index arr.length - 1. Based on the returned index value, print the corresponding result.

Scanner scan = new Scanner(System.in);
int[] arr = {1, 3, 4, 7, 8, 10};
System.out.println("Please enter the number within 10 you are looking for:");
int target = scan.nextInt();
int index = binarySearchHelper(arr, target, 0, arr.length - 1);
if (index < 0) {
    System.out.println("The number you entered cannot be found!");
} else {
    System.out.println("The input number corresponds to the index:" + index);
}
binarySearchHelper method implements binary search:

analyze:

This code defines a recursive method binarySearchHelper that searches for a target number target in a given ordered array of integers arr. The method accepts four parameters: array arr, target number target, starting index low and ending index high of the array >.

In the method, first check whether the starting index is greater than the ending index, if so, it means that the target number is not in the array, and -1 is returned.

Otherwise, calculate the middle index mid and check whether the middle element is equal to the target number. If so, return the mid index mid.

If the middle element is greater than the target number, the binarySearchHelper method is called recursively to continue searching for the target number in the left half of the array.

If the middle element is smaller than the target number, the binarySearchHelper method is called recursively to continue searching for the target number in the right half of the array.

In this way, through the recursive call, the index value of the target number will eventually be found or -1 will be returned, indicating that the target number does not exist in the array.

public static int binarySearchHelper(int[] arr, int target, int low, int high) {
    if (low > high) {
        return -1;
    }
    int mid = (low + high) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearchHelper(arr, target, low, mid - 1);
    } else {
        return binarySearchHelper(arr, target, mid + 1, high);
    }
}

2) Minimum value problem: Find the minimum value of n elements:

Code and analysis:

Import necessary classes:

Analysis: This line of code imports the java.util.Arrays class, which is used to print the contents of the array.

import java.util.Arrays;
Create One class:

Analysis: This code defines a public class named One and contains the main method and the findMinmumHelper method.

public class One {
    public static void main(String[] args) {
        // ...
    }

    public static int findMinmumHelper(int[] arr, int low, int high) {
        // ...
    }
}
Perform the search for the minimum value in the main method:

analyze:

This code first defines an integer array arr, which contains some integers.

Next, call the findMinmumHelper method to find the minimum value, passing in the array arr, starting index 0 and ending index arr .length - 1. Store the returned minimum value in the variable x.

Finally, use System.out.println to print the contents and minimum value of the array.

int[] arr = {90, 40, 50, 10, 99, 20};
int x = findMinmumHelper(arr, 0, arr.length - 1);
System.out.println("in array" + Arrays.toString(arr));
System.out.println("The minimum value is:" + x);
findMinmumHelper method implements recursive search for the minimum value:

analyze:

This code defines a recursive method findMinmumHelper that finds the minimum value in a given array arr. The method accepts three parameters: array arr, starting index low and ending index high.

In the method, first check whether the starting index and the ending index are equal. If they are equal, it means there is only one element, and the element is returned directly as the minimum value.

Otherwise, calculate the intermediate index mid and call the findMinmumHelper method recursively to find the minimum value in the left half array and right half array respectively.

Finally, use the Math.min method to compare the minimum value of the left half of the array leftMin with the minimum value of the right half of the array rightMin and return the smaller The value is used as the minimum value of the entire array.

public static int findMinmumHelper(int[] arr, int low, int high) {
    if (low == high) {
        return arr[low];
    }
    int mid = (low + high) / 2;
    int leftMin = findMinmumHelper(arr, low, mid);
    int rightMin = findMinmumHelper(arr, mid + 1, high);
    return Math.min(leftMin, rightMin);
}

3) Power multiplication problem: Given a real number a and a natural number n, find a^n:

Code and analysis:

Imported the Scanner class:
import java.util.Scanner;
main function:

analyze:

In the main method, obtain the values of a and n input by the user through the Scanner class, and call the power method to calculate the nth power of a.

 public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
System.out.println("Please enter the value of a:");
int a=scan.nextInt();
System.out.println("Please enter the value of number n");
int n=scan.nextInt();
int x=power(a,n);
System.out.println(a + "The" + n + "th power is: " + x);
}
power method:

analyze:

  1. The power method is a recursive method whose parameters are the base a and the exponent n. If n is equal to 0, then 1 is returned, because any number raised to the power 0 is equal to 1.

  2. If n is not equal to 0, continue to recursively calculate the value of power(a,n/2), that is, divide the index by 2 to reduce the number of recursions.

  3. If n is an even number, the value of temp*temp is returned directly, which is to calculate the square of the result.

  4. If n is an odd number, it needs to be multiplied by a to return the value of atemptemp.

  5. Finally, the calculation results are output in the main method.

 public static int power(int a,int n)
{
if(n==0) {
return 1;
}
int temp=power(a,n/2);
if(n%2==0) {
return temp*temp;
}
else {
return a*temp*temp;
}
\t\t
}
}

implementation of quick sort:

Code and analysis:

Imported the java.util.Arrays class:
import java.util.Arrays;
main method:

analyze:

  1. A Java class named One is defined and the main() method is implemented in it.

  2. An integer array arr is defined and initialized to {9,10,44,33,4,15}.

  3. Use the Arrays.toString() method to convert the array to a string and output the sequence before sorting.

  4. Call the quickSort() method to sort the array.

  5. Use the Arrays.toString() method to convert the array to a string and output the sorted sequence

 public static void main(String[] args) {
        int [] arr= {9,10,44,33,4,15};
        System.out.println("The sequence before sorting is:" + Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println("The sorted sequence is:" + Arrays.toString(arr));
    }
Quick sort algorithm:

analyze:

  1. A method named quickSort() is defined to implement the quick sort algorithm. The parameters of this method are the array to be sorted, the starting position and the ending position. If the starting position is smaller than the ending position, it means that sorting needs to continue.

  2. Call the partition() method to divide the array into two parts and return the index pivotIndex of the pivot element.

  3. Recursively call the quickSort() method to sort the sub-array on the left, that is, from low to pivotIndex-1.

  4. Recursively call the quickSort() method to sort the sub-array on the right, that is, from pivotIndex to high.

 public static void quickSort(int [] arr,int low,int high) {
        if(low <high) {
            int pivotIndex=partition(arr,low,high);
            quickSort(arr, low,pivotIndex-1);
            quickSort(arr, pivotIndex, high);
        }
    }
Split array:

analyze:

  1. A method named partition() is defined, which is used to divide the array into two parts, the left part is smaller than the pivot element, and the right part is greater than or equal to the pivot element. The parameters of this method are the array to be sorted, the starting position and the ending position.

  2. Sets the pivot element to the last element of the array arr[high].

  3. Define a pointer i, pointing to the starting position of the array low-1.

  4. Use a for loop to iterate through all elements arr[j] in the array from low to high-1.

  5. If arr[j] is less than the pivot element pivot, move the i pointer one position to the right and swap arr[i ] and arr[j] to ensure that the left part is smaller than the pivot element.

  6. Swap the pivot element pivot with arr[i + 1] and return i + 1 as the new pivot element index.

 public static int partition(int [] arr,int low,int high) {
        int pivot=arr[high];
        int i=low -1;
        for(int j=low;j<high;j + + ) {
            if(arr[j]<pivot) {
                i + + ;
                swap(arr,i,j);
            }
        }
        swap(arr,i + 1,high);
        return i + 1;
    }
Swap the positions of two elements in the array:

analyze:

A method named swap() is defined to swap the positions of two elements in the array. The parameters of this method are the array to be exchanged and the subscripts of the two elements.

 public static void swap(int [] arr,int i,int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

Summary the characteristics of the divide-and-conquer algorithm:

The divide-and-conquer algorithm is a commonly used problem-solving method with the following characteristics:

  1. Divide: Divide the original problem into several sub-problems, each of which is smaller in size and similar in structure to the original problem.

  2. Conquer: Solve each subproblem recursively. If the subproblem is small enough, it can be solved directly.

  3. Combine: Combine the solutions of sub-problems into the solution of the original problem.

The characteristics of the divide-and-conquer algorithm include the following aspects:

  1. Wide applicability: The divide-and-conquer algorithm is suitable for solving various types of problems, including sorting, search, graph algorithms, etc. The divide-and-conquer algorithm can be used whenever the problem can be divided into several smaller sub-problems and the solutions to these sub-problems can be combined into a solution to the original problem.

  2. Improving efficiency: By dividing the problem into multiple sub-problems and processing them in parallel, the divide-and-conquer algorithm can significantly improve the efficiency of problem solving. The sub-problems are independent of each other and can be calculated at the same time, thereby making full use of computing resources.

  3. Recursive idea: Divide and conquer algorithms usually use recursion to solve sub-problems. Recursive calls gradually reduce the size of the problem until the base case is reached, and then the solutions to the sub-problems are gradually merged to obtain the solution to the original problem.

  4. Overhead of splitting and merging:The efficiency of the divide-and-conquer algorithm is also affected by splitting and merging operations. If the decomposition and merging operations are expensive, the efficiency of the algorithm may decrease.

  5. Space complexity: Divide-and-conquer algorithms usually require additional space to store solutions to sub-problems, so there may be a certain overhead in space complexity.

In general, the divide-and-conquer algorithm solves complex problems efficiently by dividing the problem into multiple sub-problems, solving these sub-problems recursively, and then merging the solutions of the sub-problems into the solution of the original problem. It is an important algorithmic idea that is widely used in various fields.

Note: All complete codes:

You can follow private message bloggers, and bloggers can send them to their friends!