# Hanoi Tower problem is a common and classic problem solved by recursion.

## What is the Hanoi Tower?

### Generally speaking, there are three columns A, B and C. begin to stack 64 plates on column A from top to bottom in the order of small to large. Put all plates on column A on column C in the order of small to large, and at any time, the disk cannot be enlarged on the small disk, and only one disk can be moved between the three columns at A time.

---------------------------------

# Be careful:

### Let's analyze:

First of all, we need to have a concept that when we start moving, we think of the bottom plate as a whole, and the rest of the top plate as a whole.

##### Realize A to C from the three plates in the figure below. First, consider the two plates above as A whole to enable them to reach B (original to step 1, note: since only one can be moved at A time, and the small ones are on the top, the two plates above first arrive at C and then arrive at B to realize the two plates above as A whole to B pillar). Then, let the largest plate go from A to C, and then let the plates on B as A whole realize all plates from B to A and then to C Move (internal move from step 2 to step 3). So according to the figure above, we can summarize the rules

A to C

A to B
A to C
B to C

#### When A column is placed with three plates, the movement rule is as follows:

A to B

{the above two are regarded as A whole, from the purple box above: the above two go through A to C and then C to B}

**A to C

{step 1 to step 2}

B to C

{the steps in the green box above go through B to A and then to C}**

----------

## For the n-1 plate, first move the n-1 plate from A to B through some operations, then move the n-1 plate from B to C through some operations

----------—
Code diagram above!  Code:

```import java.util.Scanner;
public class hanoiTower {
public static void main(String[] args) {
System.out.println("Enter the number of plates to move:");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char A = 'A';
char B = 'B';
char C = 'C';
System.out.println("The steps required are:");
hanoi(n,A,B,C);
}
public static void move(char A , char C){
System.out.println(A+"->"+C);
}
public static void hanoi(int n , char A , char B , char C){
if (n==1){
move(A , C);
}else{
hanoi(n-1 , A , C , B);
move(A , C);
hanoi(n-1 , B , A , C);
}
}
}

```

Test: # Frog jumps on the steps

#### It can be compared with peibonaceh sequence: sum=f(n-1)+f(n-2) Up code!!!

## Recursion:

```import java.util.Scanner;
public class frogSeat {
public static void main(String[] args) {
System.out.println("Enter the number of steps for the frog to jump:");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = jump(n);
System.out.println("Frog has"+sum+"Seed jump method!");
}
public static int jump(int n){
int sum = 0 ;
if(n==1){
return n ;
}else if(n==2){
return n ;
}else{
sum = jump(n-1)+jump(n-2);
}
return sum ;
}
}
//Test:
//Enter the number of steps for the frog to jump:
10
//Frog has89Seed jump method!

```

## Non recursive:

### 1. Using variables

```import java.util.Scanner;
public class frogSeat {
public static void main(String[] args) {
System.out.println("Enter the number of steps for the frog to jump:");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = jump(n);
System.out.println("Frog has"+sum+"Seed jump method!");
}
public  static int jump(int n){
int i = 1 ;
int j = 2 ;
int k = 0 ;
if (n==1){
return n ;
}else if(n==2) {
return n ;
} else{
for (int a = 3 ; a<=n ; a++){
k = i+j ;
i=j;
j=k;
}
return k ;
}
}
}
//Test:
//Enter the number of steps for the frog to jump:
6
//Frog has13Seed jump method!

```

### 2. Using arrays

```import java.util.Scanner;
public class frogSeat {
public static void main(String[] args) {
System.out.println("Enter the number of steps for the frog to jump:");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
jump(n);
}
public  static void jump(int n) {
int []funArrays = new int;
funArrays = 1;
funArrays = 2;
int j = 0 ;
if (n == 1) {
System.out.println("Method has"+ funArrays+"Kind!");
}
if (n == 2) {
System.out.println("Method has"+ funArrays+"Kind!");
}else {
for (j = 2; j <= n-1; j++) {
funArrays[j]=funArrays[j-1]+funArrays[j-2];

}
System.out.println("Method has"+ funArrays[n-1]+"Kind!");
}
}
}

```   Published 12 original articles, won praise 3, visited 149

Keywords: Java REST

Added by mizkit73 on Fri, 13 Mar 2020 08:55:14 +0200