C语言递归实现汉诺塔

水深无声 2023-02-19 14:27 14阅读 0赞

# 汉诺塔 #

汉诺塔问题是指：一块板上有三根针 A、B、C。A 针上套有 64 个大小不等的圆盘，按照大的在下、小的在上的顺序排列，要把这 64 个圆盘从 A 针移动到 C 针上，每次只能移动一个圆盘，移动过程可以借助 B 针。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。从键盘输入需移动的圆盘个数，给出移动的过程。

#### 思路： ####

1.  n==1时，只移动一个圆盘时，直接将圆盘从 A 针移动到 C 针
2.  n>1时，  
    把 (n-1) 个圆盘从 A 针移动到 B 针（借助 C 针）；  
    A 针上的最后一个圆盘移动到 C 针；  
    B 针上的 (n-1) 个圆盘移动到 C 针（借助 A 针）。  
    每做一遍，移动的圆盘少一个，逐次递减，最后当 n 为 1 时，完成整个移动过程

#### 算法实现 ####

long count=0;
    void han(int n,char a,char b,char c)
    { 
        if(n==1)  //n==1，直接将圆盘从A针移动到C针，作为递归结束条件
        { 
            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;
    
    }

#### 实例 ####

当有3个盘子时  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMTg1NzM3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMTg1NzM3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020062109350790.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMTg1NzM3,size_16,color_FFFFFF,t_70