递归解决汉诺塔问题

凤年徐

发布于 2025-08-28 13:16:29

2070

文章被收录于专栏：代码飞升代码飞升

用递归思想解决汉诺塔问题

1.什么是汉诺塔

汉诺塔问题源自印度一个古老的传说，印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱，其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上，移动过程中必须遵守以下规则：

每次只能移动柱子最顶端的一个圆盘；
每个柱子上，小圆盘永远要位于大圆盘之上；

2.问题分析

下面以两个圆盘为例做一个分析

从左到右不妨依次称为A B C柱子，要从A柱移动到C柱，有以下步骤

A->B

A->C

B->A

如果是n个呢？

过程可以理解为，先把上边n-1个看作一个整体移动到辅助轴（B轴），再把第n个移动到目标轴

3.代码实现

共两个函数

#include<stdio.h>
void move(char pos1, char pos2)
{
    printf("%c->%c\n", pos1, pos2);
}
void hanoi(int n,char pos1, char pos2, char pos3)
{
    if (n == 1)
        move(pos1, pos3);//n为1时直接移动过去
    else 
    {
        hanoi(n - 1, pos1, pos3, pos2);//对于上边n-1个圆盘，以A为起始轴，C为辅助轴，全部移动到目标轴B轴
        move(pos1, pos3);
        hanoi(n - 1, pos2, pos3, pos1);//以B为起始轴，C为辅助轴，把剩下的n-1个移动回A轴
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

对参数的解释：

n为圆盘个数，pos1为起始轴，pos2为辅助轴，pos3为目标轴

移动哪个轴就把哪个轴当起始轴