Recursion & Towers of Hanoi

发表于 2019-10-21  605 次阅读


文章目录

1.Introduction

In the process of learning java, it is inevitable to meet some challenge , I feel that I still lack the way of thinking in object-oriented. Sometimes I feel like the picture below.

For this reason, I plan to release some notes and my own understanding on the blog. I don't want to waste my moeny on a blank blog.

PS:When I landed on the Linux side, it shows that there were nearly 70,000 failed logins . Which one is so interested in my server?:)

2.What is recursion?

First of all, we have to know what is recursion. Simply, recursion is that I call myself.

The basic idea of recursion is to solve a difficult problem by decomposing a complex problem into many small (sub) problems. The purpose of using recursion is essentially to solve the problem, rather than making the problem more complicated.

In order to better understand recursion, I suggest that we start from God creates the world from a simple sample.I think the Fibonacci sequence is more better for starter.

The Fibonacci sequence is a sequence that each number is the sum of the two preceding ones, starting from 0 and 1. 

That is,

F[n] = F[n-1] + F[n-2] (n>=3 , F[1]=1 , F[2]=1)

From wikipedia

So according to this formula, we can easily express it in the program.

public class fibonacci {
	
	public static void main(String[] args) {
		int counter=0;
		while (counter <= 10){
        	System.out.printf("Fibonacci of %d is: %dn",counter, fibonacci(counter));
        	counter++;
		}
	}	
		
	private static long fibonacci(long number) {
	     if ((number == 0) || (number == 1)) {
	            return number;
	     }
	        else {
	            return fibonacci(number - 1) + fibonacci(number - 2);
	        } 
        }
}

First, the purpose of the main method section is to create a loop and output the values of the sequence at a time.

private static long fibonacci(long number) {
	     if ((number == 0) || (number == 1)) {
	            return number;
	     }
	        else {
	            return fibonacci(number - 1) + fibonacci(number - 2);
	        } 
        }

Next we will discuss the part of the fibonacci method of this program.

We need to know the position of number first, because the first two numbers of the Fibonacci sequence are constants. All we need to do is assign it directly and pass it back to the main function.

As for the rest, it is very important because we need to use recursion to calculate the values of the number (because the sum of previous two numbers are equal to the value we are looking for).

So, let's turn it into java:

fibonacci(number - 1) + fibonacci(number - 2);

So after this example, do you understand the Recursion?

Is this the latest magic show?

3.Towers of Hanoi

Now you have learned how to use recursion, you should be able to solve the problem of the Tower of Hanoi by yourself.

Although it was embarrassing to say it, when I was writing this article, I still felt a bit confused about the issue of the Tower of Hanoi, because I felt that the project code was quite difficult to read or understand.

First of all, we need to know what Hanno is. I believe this small GIF can help you to understand it.

Simply, we have any number of disk, each with its own number, and the small numbered disk is always on the the big value of disk. At the same time we have three columns A, B, C, and any number of disk are placed on the A column one by one. And we need a way to put all the disk from A to C,

I know this may make you confused. This problem is annoying. we not only have to solve this problem, but also write a program to help others solve this problem???

Image result for you serious spiderman gif

However, we can't say anything about it,that's the course requirements.

So let's try to find a way to solve this problem and turn it into a program.

Let us think about it, what is the solution of Hanoi in a small amount?

  • When there is only one disk,n=1
  • disk 1 A-->C
  • It's easy, right?

What if we add a disk?

  • When there are two disks,n=2
  • disk 1 A --> B
  • disk 2 A --> C
  • disk 1 B --> C
  • Looks interesting, right?

What if we add another disk?

  • When there are three disks,n=3
  • disk 1 A --> C
  • disk 2 A --> B
  • disk 1 C --> B
  • disk 3 A --> C
  • disk 1 B --> A
  • disk 2 B --> C
  • disk 1 A --> C
  • Looks a little difficult, but it's not so bad.

What do these three programs have in common?

No! (Very loudly)

We will find that when n=3, the content of the fourth step when moving disk 3(A-->C) is the same as that of the second part when n=2 (A-->C) . The content of the first three steps in n=3 is very similar to the content of the first step in n=2.

Let's keep going, can we divide all the disks into two group, we will regard the 1 to (n-1) plate as a whole, and n as another whole, then solve this problem and it will similar to the situation when n=2, right? In this way, I think of 1 to n-2 as a whole, and n-1 as another whole, then we got the idea.

The simple idea is that we only need to let the hanoi function do its own thing (that is, sort n and 1 to n disk), and if n is not equal to 1, the hanoi function will call itself until When n=1 (no disk can be sorted)

All right, let's try to turn it into program:

public static void towerofHanoi(int n,char from_rod, char to_rod, char aux_rod)
     {
         if(n == 1)
         {
             System.out.println("Now move disk "+n+" from rod "+from_rod+" to rod "+to_rod);
             return;
         }
         towerofHanoi(n-1, from_rod, aux_rod, to_rod);
         System.out.println("Now move disk "+n+" from rod "+from_rod+" to rod "+to_rod);
         towerofHanoi(n-1, aux_rod, to_rod, from_rod);
     }

First, we need to know how many disks need to be moved in total, and which columns are there. Then we need to determine n==1 (whether there is only one plate). When it is confirmed that there are no special situation such as n equal to 1, we can complete the code according to the previous ideas.

4.Conclusion

After writing this blog post, my brain is a bit embarrassing, but I have completed the relevant notes and understanding of recursion and Hanoi. The beauty of recursion is that it can decompose a complex problem and break it down into small ones (but you need know how to make it simple).

That's it, enjoy. I really want to write more about this topics, but I don't want to fail any quiz or test again this week.

本站文章基于国际协议BY-NA-SA 4.0协议共享;
如未特殊说明,本站文章皆为原创文章,请规范转载。

1

I am just a person who lives in my own world~