2.6 using recursion and stack - [tower of Hanoi problem]

Title Description

The tower of Hanoi is an ancient mathematical problem

There are three poles A,B,C.A There's... On the pole n individual (n>1) Perforated disc , The size of the disc decreases from bottom to top .

All discs are required to be moved to C rod ：

• Only one disc can be moved at a time ;
• The big plate can't be stacked on the small one .

Tips ：
The disc can be temporarily placed in B rod , You can also start from A The disc from which the rod is removed moves back A rod , But both must follow the above two rules .
ask ： How to move ？ At least how many times to move ？

Input description

a line , contain 2 A positive integer , One is N, Indicates the number of disks to be moved ; One is M, Represents the number of the least moving steps M Step .

Output description

common 2 That's ok .
 
The output format of the first line is ：#No：a->b, It means the first one M Step specific moving method , among No It means the first one M The number of the moving plate （N The plates are numbered from top to bottom 1 To n）, It means the first one M The next step is to No Plate from a The rod moves to b rod （a and b All values are （A,B、C]）.
 
The first 2 Line outputs an integer , Represents the minimum number of moving steps .

I/o sample

Input ：

3 2

Output ：

#2: A->B
7

---

The final code

1. c/c++ 【 recursive 】

#include<bits/stdc++.h>
using namespace std;
int sum = 0, m;

void hanoi(char x,char y,char z,int n)
{
    
    //m It's the first step ,n It's the number of plates 
    if(n==1) 
    {
    
        sum++;
        if(sum==m) cout<<"#"<<n<<": "<<x<<"->"<<z<<endl;
    }
    else 
    {
    
        hanoi(x,z,y,n-1);
        sum++;
        if(sum==m) cout<<"#"<<n<<": "<<x<<"->"<<z<<endl;
        hanoi(y,x,z,n-1);
    }
}

int main()
{
    
    int n;    
    cin>>n>>m;
    hanoi('A','B','C',n);
    cout<<sum<<endl;
    return 0;
}

---

1. c/c++ 【 Stack , Not recommended 】

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int sum = 0, m;
struct mystack{
    
    int a[N];                           // Store stack elements 
    int t = -1;                         // The top of the stack 
    void push(int x){
     a[++t] = x; }     // hold x Feed stack 
    int top()      {
     return a[t]; }    // Back to top of stack element 
    void pop()     {
     t--;        }    // Pop up the top of the stack 
    int empty()    {
     return t==0?1:0;} // return 1 Said empty 
}st[4];   // Define three columns , no need st[0]

void move(int x, int y,int n){
     // Moving disc 
        int element = st[x].top(); // Slave pole x Take out the top disc and put it on the pole y On 
        st[x].pop();
        st[y].push(element);
        sum++;

        char a,b; // For printing 
        if(x==1) a='A'; if(x==2) a='B'; if(x==3) a='C';
        if(y==1) b='A'; if(y==2) b='B';        if(y==3) b='C';
        if(sum == m) cout<<"#"<<n<<": "<<a<<"->"<<b<<endl;
}
void hanoi(int n, int x, int y, int z){
    
        if(n==1) move(x,z,n);
        else{
    
                hanoi(n-1, x, z, y);
                move(x,z,n);
                hanoi(n-1, y, x, z);
        }
}
int main(){
    
        int n;   cin>>n>>m;
        for(int i=n;i>=1;i--) // The initial state ： In the 1 Add n Disc 
                st[1].push(i);
        hanoi(n,1,2,3);
    cout<<sum<<endl;
        return 0;
}

---

2. java

---

3. python

---

Process understanding