C++递归经典问题——汉诺塔

C++递归经典问题——汉诺塔

引用

CSDN

1.

https://m.blog.csdn.net/2301_80309996/article/details/142303802

汉诺塔问题是一个经典的递归问题，源自印度的一个古老传说。相传在世界中心贝拿勒斯的圣庙里，一块黄铜板上插着三根宝石针，第一根针上套着64个金盘，金盘大小不一，大的在下，小的在上。当这64个金盘按规则全部移到最后一根针上时，世界末日就会到来。这个问题不仅富有传奇色彩，更是计算机科学中递归算法的经典案例。

问题描述

一块板上有三根杆子，A，B，C。A杆上套有64个大小不等的圆盘，大的在下，小的在上。要把这64个圆盘从A杆移到C杆上，每次只能移动一个圆盘，移动可以借助B杆进行。但在任何时候，任何杆上的圆盘都必须保持大盘在下，小盘在上。求移动的步骤。

以下是n=3的情况：

目标：

思路解析

汉诺塔问题的核心在于递归思想的应用。具体来说，可以将n个圆盘的移动过程分解为以下三个步骤：

1. 将A杆上的n-1个圆盘借助C杆移动到B杆上
2. 将A杆上剩下的一个圆盘直接移动到C杆上
3. 将B杆上的n-1个圆盘借助A杆移动到C杆上

通过递归地执行上述步骤，最终可以将所有圆盘从A杆移动到C杆。

代码实现

下面是用C++实现的汉诺塔问题代码：

//汉诺塔
#include<iostream>
using namespace std;
void hanoi(int n,char x,char y,char z) {
    if(n==1) {
        cout<<x<<"->"<<z<<endl;
    }
    else {
        hanoi(n-1,x,z,y);
        cout<<x<<"->"<<z<<endl;
        hanoi(n-1,y,x,z);
    }
}
int main() {
    int n;
    cin>>n;
    cout<<"The step to moving "<<n<<" disks:\n";
    hanoi(n,'A','B','C');
    return 0;
}  

学习方法

1. 明确递归简化思想：将n个托盘看作是两部分上面的n-1个和第n个，并不断对其进行递归划分直至n=1,直接输出。
2. 模型意识：即推广意识。一上来不要把问题细化考虑，先明确每一步的目标是什么（即划分），并逐步执行；如果想不明白的小伙伴可以象我一样，以n = 3为例，将具体步骤按照模型逐步拆解，看看结果是否和答案一样，进一步论证自己的模型是正确的。