汉诺塔问题(C语言递归实现)

一、问题分析

1.要用递归实现汉诺塔问题得先了解递归的两个必要条件

(1)存在限制条件,当满足这个条件的时候,递归将不再继续

(2)每次调用递归之后会越来越接近这个限制条件

2.汉诺塔问题用递归解决的思路

(1)假设有n个大小不一样的盘子且大盘子下面不能有小盘子,三根柱子A,B,C

(2)找到限制条件:当只需要移动的盘子只有一个时直接移动该盘子

有n个盘子在A柱,将n-1个盘子移动到B柱,将A柱上剩余的1个盘子移动到C柱

有n-1个盘子在B柱,将n-2个盘子移动到A柱,将B柱上剩余的1个盘子移动到C柱

有n-2个盘子在A柱,将n-3个盘子移动到B柱,将A柱上剩余的1个盘子移动到C柱

......

有2个盘子在A或B柱上,将1个盘子移动到B或A柱上,将A或B柱上剩余的1个盘子移动到C柱

将A或B柱上的1个盘子移动到C柱上,完成了移动

 

二、具体代码

#include <stdio.h>
void move(char ch1, char ch2)
{
    //把一根柱子的最上面的一个盘子移到另外一根柱子的最上面
    printf("%c->%c\n", ch1, ch2);
}
void Hanoi(char a, char b, char c, int n)
{
    if (n == 1)
    {
        //当移动的盘子数量只有一个的时候直接使用move函数
        move(a, c);
    }
    else
    {
        Hanoi(a, c, b, n - 1);//A柱借助C柱将n-1个盘子移动到B柱       
        move(a, c);//将A柱剩余的一个盘子移动到C柱                    
        Hanoi(b, a, c, n - 1);//将B柱的n-1个盘子借助A柱移动到C柱     
    }
}
int main()
{
    int n;//要移动的盘子的总数
    scanf("%d", &n);
    Hanoi('A', 'B', 'C', n);//A柱借助B柱将n个盘子移到C柱上
    return 0;
}

三、运行结果

 

 

四、总结

一开始打算用数组内移动元素的方式来写,但觉得编译后的结果很难看到具体的移动过程,于是借鉴了CSDN上一位老铁的打印移动柱子的方法,并配上了汉诺塔递归最底层的逻辑思维写出来的,并且补全了具体的递归步骤

 

热门相关:重生之女将星   我成了暴戾帝君的小娇包   名门盛婚:首席,别来无恙!   重生成偏执霍少的小仙女   上将大叔,狼来了!