preface

I believe that students who have learned the course “Data Structures and Algorithms” have heard of the Hannotta problem, but may not have studied in college, or did not understand when learning, resulting in no good understanding of the classical solution of Hannotta, let me give you to analyze.

background

The problem with the Tower of Hannot (also known as the Tower of Hanoi) is a puzzle toy from an old Indian legend. Maharma made three diamond towers when he created the world, and on one tower were stacked 64 gold disks in ascending order of size. Mahama ordered the Brahmin to rearrange the disks on the last tower, starting from the bottom, in order of size. It is also stipulated that the disk cannot be enlarged on the small disk and that only one disk can be moved at a time between the three towers.

Analysis of the

For disks numbered 1 to n, the disk with a large number is larger than the disk with a small number. In addition, the concepts of starting tower, transit tower and target tower are introduced. When the algorithm is running, the identities of these three towers may change with each other.

  1. If there is now only one disk above tower A, move the disk directly to tower C;
  2. If there are now two disks above tower A, move disk 1 from tower A to tower B, then move disk 2 from tower A to tower C, and finally move disk 1 from tower B to tower C;
  3. ….
  4. If tower A has N disks, move the disks before disk N from tower A to tower B, then move the disks before disk N from tower A to tower C, and finally move the disks before disk N from tower B to tower C.

As you can see, the above solution is a typical divide-and-conquer algorithm idea.

Because Hanover tower requires that only one disk can be moved at a time, and the disk cannot be enlarged on the small disk, it is necessary to remove the disk on the large disk at the bottom of the same tower. To move disk N, first move (disk N-1 ~ disk 1) to the transfer tower, to move (disk N-1 ~ disk 1) in the disk N-1, then move (disk N-2 ~ disk 1) to the transfer tower, and so on…… Until there’s only one disk 1, and then you just move it. At the same time, because our goal is to move all disks to the target tower, after moving disk N to the target tower, we need to move (disk N-1 ~ disk 1) previously placed on the transfer tower to the target tower.

Maybe you can say that, but how do you write code? In fact, this is also the more time-consuming part of the algorithm learning, with computer programming language algorithm representation (write) out. Here is a classic implementation, an analysis of why it is written this way, and a way of thinking that I use to understand recursion.

Java version algorithm implementation

In general, divide-and-conquer is implemented in conjunction with recursion, which is used in the following example code.

When writing recursive structures, you can start from the semantic level. The thinking process is as shown in the above analysis: We need to write a function that moves the disk N ~ disk 1 from a starting tower to the target tower. Since it is required to move the disk on disk N before moving the disk N, a transfer tower is needed. Void Hanoi (int n, String sourceTower, String tempTower, String targetTower) void Hanoi (int n, String sourceTower, String tempTower, String targetTower)

According to the algorithm, the inside of the function body can be written like this:

Move (n, sourceTower, targetTower);

Otherwise, move disks N-1 ~ disk 1 to the transfer tower Hanoi (N-1, sourceTower, targetTower, tempTower) Move (n, sourceTower, targetTower) Then move disks n-1~ disk 1 on the transfer tower to the targetTower Hanoi (n-1, tempTower, sourceTower, targetTower).

public class Hanoi {
    public static void hanoi(int n, String sourceTower, String tempTower, String targetTower) {
        if (n == 1) {
            // If there is only one dish 1, move it directly from sourceTower to targetTower
            move(n, sourceTower, targetTower);
        } else {
            // Move (plates n-1~ plates 1) from sourceTower past targetTower to tempTower
            hanoi(n - 1, sourceTower, targetTower, tempTower);
            // Move the tray n from sourceTower to targetTower
            move(n, sourceTower, targetTower);
            // Move the tempTower (plates n-1~ plates 1) from tempTower to targetTower via sourceTower
            hanoi(n - 1, tempTower, sourceTower, targetTower); }}// Move plate n from sourceTower->targetTower
    private static void move(int n, String sourceTower, String targetTower) {
        System.out.println("The first" + n + "Plate number move:" + sourceTower + "- >" + targetTower);
    }

    public static void main(String[] args) {
        System.out.println("Steps to move Hanover Tower:");
        hanoi(3."a"."b"."c"); }}Copy the code

Running results:

Steps to move Hanover Tower: Plates move no. 1: a - > c plates move no. 2: a - > b plates move no. 1: c - > no. 3 b plates move: a - > c plates move no. 1: b - > no. 2 plates move: no. 1 b - > c plate move:a--->cCopy the code

It can be found that for a call Hanoi (N, sourceTower, tempTower, targetTower), the transfer tower is for disk N-1 ~ disk 1. – Hanoi (n, sourceTower, tempTower, targetTower) – Hanoi (N, sourceTower, tempTower, targetTower) – Hanoi (N, sourceTower, tempTower, targetTower

For those of you who still don’t understand why you can’t enlarge a disk on a small disk, it’s very simple, because every time we want to move the disk N, we’ve already removed the disk on top of the disk N, and after we move the disk N, we move the other disks onto the tower where the disk N is, So of course it satisfies the requirement that you can’t enlarge a disk on a small disk. If you still don’t understand it, you can simulate it with two disks and three disks.

Attached is an analysis diagram of algorithm calls:

conclusion

Usually in the use of divide-and-conquer to solve the problem, first according to the principle of divide-and-conquer gradually split the problem. While divide-and-conquer often needs to be combined with recursion to write code, reading or designing recursion structures can be carried out from the semantic level.

Like divide-and-conquer, backtracking can be combined with recursion. But there are a few differences.

Divide-and-conquer uses recursion to solve problems that usually have solutions. Like Hanover tower, list inversion.

Backtracking, which uses recursive heuristics to solve a problem, may result in no solution. Such as maze problems, depth traversal.

conclusion

In fact, studying algorithms is really quite brain-burning, and need to invest more time. A lot of people think they’re better off looking at other frameworks when they have the time. In fact, algorithmic knowledge is essential if you want to become a computer giant. I like to see animation “a fist superman”, there is a line “interest”. Indeed, I think algorithms are the most fascinating thing about computer science, so it’s not boring to study algorithms because it’s “fun”.

— Written in 2018 Mid-Autumn Festival.