Shulou(Shulou.com)06/03 Report--

Java programming in the divide and conquer algorithm how to use, for this problem, this article details the corresponding analysis and solution, hoping to help more want to solve this problem of small partners to find a simpler and easier way.

Divide and conquer is a very important algorithm. The literal interpretation is "divide and conquer," which is to divide a complex problem into two or more identical or similar sub-problems, and then divide the sub-problems into smaller sub-problems…until the sub-problems can be solved simply and directly, and the original solution is the combination of the solutions of the sub-problems. This technique is the basis of many efficient algorithms, such as sorting algorithms (fast sort, merge sort), Fourier transforms (fast Fourier transforms)...

Branching algorithm can solve some classic text graph: binary search, large integer multiplication, chessboard covering, merge sort, quick sort, linear time selection, closest point pair problem, round-robin schedule, hanoi tower.

Basic steps of divide and conquer algorithm

Divide and conquer has three steps at each level of recursion:

Decomposition: Decomposition of an original problem into several smaller, independent subproblems of the same form as the original problem

Solve: several subproblems are small and easy to solve, solve them directly, otherwise solve each subproblem recursively.

Merging: combining solutions of subproblems into solutions of the original problem

Divide and conquer algorithm design pattern

Divide-and-Conquer(P) algorithm mode as shown below,

wherein| P| Denotes the size of the problem P, n0 is a threshold value, indicating that when the size of the problem P does not exceed n0, the problem is easily solved directly and does not need to be decomposed further. ADHOC(P) is the basic subalgorithm of the divide-and-conquer algorithm, which is used to directly solve small-scale problems P. Therefore, ADHOC(P) is used to solve directly when the size of P does not exceed n0. The algorithm MERGE(y1,y2,…yk) is a merging sub-algorithm of the divide-and-conquer method, which is used to merge the corresponding solutions y1,y2,…yk of the sub-problems P1,P2,…Pk of P into the solution of P.

Divide and conquer algorithm practice-Tower of Hanoi

On one pillar were placed sixty-four gold disks in order of size from bottom to top, and the disks were rearranged in order of size from bottom to top on the other pillar, with the stipulation that no disk could be enlarged on the small disk, and that only one disk could be moved at a time between the three pillars.

Thinking analysis:

If there is one disk, A->C

if n>=2 tray, we can always think of two tray, one for that bottom tray and one for all the trays above: first move all the topmost trays from A to B, move the bottom tray from A to C, and move all the trays in tower B from B to C.

package com.xie.algorithm; public class Hanoitower { public static void main(String[] args) { hanoiTower(3, 'A', 'B', 'C'); /** * 1st plate from A->C * 2nd plate from A->B * 1st plate from C->B * 3rd plate from A->C * 1st plate from B->A * 2nd plate from B->C * 1st plate from A->C */ } public static void hanoiTower(int num, char a, char b, char c) { //if there is only one disk if (num == 1) { System.out.println("1st disk from" + a + "->" + c); } else { //If n>=2 disks, we can always see two disks, one is the bottom disk, and one is all the disks above. //1. First move the topmost disk from A to B, and the movement process will use C. hanoiTower(num - 1, a, c, b); //2. Move the bottom disk from A to C System.out.println(" + num + " th disk from " + a + "->" + c); //3. Move all trays of Tower B from B to C, using the movement process to Tower A hanoiTower(num - 1, b, a, c); } } } About Java programming divide and conquer algorithm how to use the answer to the problem to share here, I hope the above content can have some help for everyone, if you still have a lot of doubts not solved, you can pay attention to the industry information channel to learn more related knowledge.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.