当前位置：网站首页>Yyds dry goods inventory C language recursive implementation of Hanoi Tower

Yyds dry goods inventory C language recursive implementation of Hanoi Tower

2022-07-06 21:51:00 【ZS_ Jie】

The tower of Hanoi problem refers to ： There are three needles on one board A、B、C.A The needle is covered with a needle 64 A disc of different sizes , According to the big one 、 The small ones are arranged in the order of , I want to put this 64 A disk from A The needle moves to C On the needle , Only one disc can be moved at a time , The movement process can be done with the help of B The needle . But at any time , Any disc on the needle must keep the big one down , Small in . Enter the number of disks to be moved from the keyboard , Give the process of moving .

Ideas ：

n==1 when , When only one disc is moved , Direct the disc from A The needle moves to C The needle
n>1 when ,
hold (n-1) A disk from A The needle moves to B The needle （ With the help of C The needle ）;
A The last disc on the needle moves to C The needle ;
B On the needle (n-1) A disk moves to C The needle （ With the help of A The needle ）.
Every time I do it , One less moving disc , Gradually decreasing , Finally, when n by 1 when , Complete the entire movement

Algorithm implementation

long count=0;
void han(int n,char a,char b,char c)
{
    if(n==1)  //n==1, Direct the disc from A The needle moves to C The needle , As the end condition of recursion 
    {
        count++;
        printf("%d,%c->%c\n",count,a,c);
    }
    else
    {
     han(n-1,a,c,b);
     ++count;
     printf("%d,%c->%c\n",count,a,c);
     han(n-1,b,a,c);
    }
}
int main()
{


    int n;
    scanf("%d",&n);
    han(n,'A','B','C');
    return 0;

}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.