2025年汉诺塔(梵塔)问题递归解决

大家好，我是讯享网，很高兴认识大家。

汉诺塔(梵塔)问题描述：来自于百度百科

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
在这里插入图片描述

输入：输入汉诺塔(梵塔)的铜板个数

输出：要求输出每一步移动的操作，并输出最终步数

示例如下:
在这里插入图片描述

简要分析：

对于梵塔问题，递归解决是比较容易想到的。我们以三个铜板的梵塔问题为例来进行讲解。

在这里插入图片描述

我们要将A柱上的三个铜板移到C上，并且不破坏规则(小的铜板不能在大的铜板下)。在保证规则不被破坏的前提下，我们有这样一个策略来移动铜板: 每次都将最大的铜板移到C上。

为了达到上面的策略，我们要有一下两个步骤:

将除去最大的铜板的所有铜板(1、2号铜板)移到B上
将最大的铜板(3号铜板)移到C上(达到目的)

在完成以上两步后，我们实现了将现在最大的铜板(3号铜板)移到目标C上。下一步需要将次小的铜板(2号铜板)从当前的位置B上移动到C上。这相当于重复了上面的步骤，只不过此时要移动的铜板是次小的铜板(2号铜板)，移动的起始位置也从A换到了B，但是目标位置不变，依然为C。

如此执行下去，最终我们将所有铜板从A移动到C，而且我们每次移动的都是依次变小的铜板，符合规则。

那么现在就只剩下一个问题: 上述步骤中的步骤一将除去最大的铜板外的所有铜板(1、2号铜板)移到B上如何实现呢? 我们来分析初始问题与当前问题:

初始的问题: 将所有的铜板(1、2、3)从A移动到C(不破坏规则)
现在的问题: 将除去最大的铜板(1、2)从A移动到B(不破坏规则)

很容易发现，这与初始问题描述一样，只不过更换了铜板数量和目标位置。相当于减小了问题规模，我们依然可以采取上述两个步骤的策略来解决子问题，而子问题又有自己的子问题…

这一特性十分适合我们采用递归的方式来解决这一问题。

也许你还不太清除如何代码实现，但递归问题解决这一问题的思想大概如此(我们语言能力有限，可能你对于思想也不太清除，下面给一份C++编辑的代码，帮助你理解汉诺塔问题)。

代码如下：

#include<iostream> using namespace std; /* 我们分别以 -1(A) , 0(B) , 1(C) 代表梵塔问题的三个柱. 起始时默认所有的盘均在 -1 号柱上. 当然我们在输出时依然按照A、B、C来表示铜板号， 这样更加直观。 */ void Just_do_it(int num,int goal,int position); //含义: 将1-num的所有铜板从position移到goal void Move(int moveNum,int goal,int position); //含义: 将moveNum号的铜板从position移到goal int GetGoal(int goal,int position); //含义: 根据目标(goal)和当前位置(position)获取接下来要去哪里 char* GetPrint(int n); //含义: 格式化输出 int step = 0; //步数 int main() { 
    int panNum; //铜板的数量,默认铜板的编号从1到panNum。 且编号越大,铜板的大小也越大。 cout<<"请输入铜板的数量: "; cin>>panNum; Just_do_it(panNum,1,-1); //将所有的铜板从-1柱移到1号柱。 cout<<"step: "<<step<<endl; return 0; } void Just_do_it(int num,int goal,int position) { 
    for(int i=num; i>0; i--){ 
    Move(i,goal,position); if(goal + position == 0){ 
    position = 0; } else if(goal + position == -1){ 
    position = 1 ;} else{ 
    position = -1; } } } void Move(int moveNum,int goal,int position) { 
    if(moveNum == 1){ 
    step++; cout<<"move 1 from "<<GetPrint(position)<<" to "<<GetPrint(goal)<<endl; }else{ 
    Just_do_it(moveNum-1,GetGoal(goal,position),position); step++; cout<<"move "<<moveNum<<" from "<<GetPrint(position)<<" to "<<GetPrint(goal)<<endl; } } int GetGoal(int goal,int position) { 
    if(goal + position == 0){ 
    return 0; } else if(goal + position == -1) { 
    return 1;} else { 
    return -1; } return -9; //随便返回一个，因为走不到这一步 } char* GetPrint(int n){ 
    if( n == -1){ 
    return "A"; } else if( n == 0) { 
    return "B"; } else { 
    return "C"; } return "error!"; //随便返回一个，因为走不到这一步 }

讯享网