Divide and conquer method

The divide-and-conquer method is an algorithm that decomposes a larger problem into smaller sub-problems, solves the sub-problems first, and then combines the solutions of the sub-problems to obtain the solution of the original problem

recursive

Recursion is a natural way of thinking, clear thinking, easy to implement, but the specific implementation steps of the recursive algorithm is difficult to understand, bad recursion will greatly improve the complexity of the algorithm, so it should be careful to use recursion.

Hannotta problem

Existing in three pillars highly as, respectively, the starting column A, auxiliary column B, C target column, column with A number of initial from down to up in turn reduce disk, can only move one disk at A time, and all the disc from the starting column of A transfer to the target column C the required minimum number of times, for disk can only put in rather than on disk or big empty post.

Their thinking

Don’t think about the next step, just think about the current step, okay

First of all, we would have thought that to A minimum on A moving onto A C, but the disc only upon is larger than the disk or empty column, C as the ultimate goal, if the minimum disk move directly to the C, so the rest of A is bigger than the first one want to move to the disk C, must be taking out already on disk C, can increase the unnecessary steps, This is not the right way to think about it, either by moving the smallest to C first or by moving the smallest to C first, so to move all disks from A to C we should move the largest disks to C first:

    1. You put n minus 1 disks on A onto B
    1. Take the maximum from A and put it on C
    1. I’m going to put n minus 1 disks on B on C

The second step can be completed in one step, but 1 and 3 need to further subdivide their tasks, so the solution of the problem can be easily abstracted into recursive functions:

  • Input: number of disks to be transferred n, start disk X, secondary disk Y, target disk Z
  • Logic:
    • If the number of disks to be transferred is 1, the disks are directly transferred to the target disk
    • If the number of disks to be transferred is multiple, there should be 3 steps:
      • Move n – 1 on X to Y, where X is the starting drive, Z is the secondary drive, and Y is the target drive. Move N – 1
      • Move 1 disk on X to Z, X is the starting disk, Y is the auxiliary disk, Z is the target disk, move 1 disk (1 step does not need auxiliary)
      • Move n – 1 disks on Y to Z, Y as the starting disk, X as the secondary disk, and Z as the target disk, and move N – 1 disks

Whether the rules were followed

In the process of moving, we will pay more attention to whether we violate the rule that only small disks can be placed on top of large disks. We can consider the following:

  • Each of the three steps in the same recursion completes the previous step
  • The actual movement is only done when it needs to move one, moving one directly from the starting pillar to the target pillar without the aid of the auxiliary cylinder

Feeling explains loneliness. When you move one, you will find that you can either move to the empty column or move to the larger column of the lower disk. You can try it yourself with 3 disks

Time complexity

Let me draw it a little bit in Xmind

The recursive function is called 1 + 2^0 * 3 + 2^1 * 3 +… + 2^(n – 2) * 3

The sum of the geometric sequence plus 1 becomes 1 plus 2 to the n minus 1 times 3

So the time is order 2 to the n.

JAVA code

The code will output the details of each cylinder for each movement

  • The test class
import java.util.ArrayList; public class HanoiTest { public static void main(String[] args) { ArrayList<Integer> A_nums = new ArrayList<>(); A_nums.add(5); A_nums.add(4); A_nums.add(3); A_nums.add(2); A_nums.add(1); Tower A = new Tower("A", A_nums); Tower B = new Tower("B"); Tower C = new Tower("C"); Hanoi.move(A, B, C); }}Copy the code
  • Hanoi class
import java.util.ArrayList; public class Tower{ String name; ArrayList<Integer> nums; public Tower(String name) { this.name = name; this.nums = new ArrayList<Integer>(); } public Tower(String name, ArrayList<Integer> nums) { this.name = name; this.nums = new ArrayList<Integer>(); for(int num : nums) { this.nums.add(num); } } public String toString() { return " " + name + ": " + nums.toString(); } public boolean add(int num) { return this.nums.add(num); } public int remove() { return this.nums.remove(nums.size()-1); } public int size() { return nums.size(); }}Copy the code
  • Answer key classes
public class Hanoi { private static int step; private static Tower first; private static Tower second; private static Tower third; public static void move(Tower a, Tower b, Tower c) { step = 0; first = a; second = b; third = c; System.out.println(first.toString() + second.toString() + third.toString()); moveSomeFromByTo(a.size(),a,b,c); step = 0; } public static void moveSomeFromByTo(int n,Tower org,Tower support, Tower destination) {if(n == 1) {step++; System.out.println("step: "+ step + " move " + org.nums.get(org.nums.size()-1) + " from " + org.name +" to " + destination.name); destination.add(org.remove()); System.out.println(first.toString() + second.toString() + third.toString()); }else { moveSomeFromByTo(n-1,org,destination,support); moveSomeFromByTo(1,org,support,destination); / / can be directly operation step moveSomeFromByTo (n - 1, support, org, destination); }}}Copy the code

LeetCode antithesis

class Solution { public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) { traceback(A.size(),A,B,C); } public void traceback(Integer num, List<Integer> A,List<Integer> B, List<Integer> C){ if(num == 1){ int tmp = A.remove(A.size() - 1); C.add(tmp); }else{ traceback(num - 1,A,C,B); traceback(1,A,B,C); traceback(num-1,B,A,C); }}}Copy the code