我对汉诺塔的理解

最近在复习C++相关的算法，而这之中就有汉诺塔，网上也看了很多信息，代码很简单，但是感觉原理没有讲透。我就想着我来分享我对汉诺塔的看法。

一、汉诺塔问题
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。该问题的百度百度百科链接：点击打开链接
二、代码思路

汉诺塔问题，简单来说就是有A,B,C三个柱子，然后将A中的盘子移动到C中的盘子，但是每次移动的时候必须保证小盘子在大盘子上面。B 作为一个辅助盘子。

首先当只有1个盘子在A上的时候，就移动1次，从A 移动C。

那有两个盘子在A上的时候，肯定先将小盘子移动到B，然后大盘子由A移动到C。小盘子由 B移动到C。

分析两个盘子的情况，两个盘子比1个盘子的情况多了一步，把小盘子移动到B的过程，另外两步的本质都可以看出由A移动到C。

那么当有N个盘子在A上的时候，我们是怎么样来做的？我们的解决办法是否可以理解成有两个盘子的状态。

N个盘子， A,B,C 三个柱子

第一步， 将n-1个盘子移动到B，即 f(n-1, A,C,B) 这里的意思是 N-1的盘子，通过C为中间，移动到B盘

第二步， 将最底下的大盘子， 由 A移动C move(A,C)

第三步， 此时经过前两步骤，A：0个盘子 ， B：N-1个盘子， C：1个最大的盘子

那么接下来，就是将B 移动到 C ， 即 f(n-1,B,A,C) 这里的意思是 n-1的盘子，通过A为中间，移动到C盘

关于递归来讲，就两个，第一个，明白循环结束条件， 第二个，循环体。

那么循环结束条件就是，n<1，即没有盘子的情况

#include <iostream>

class han{
public:
    int num;
    han(int a):num(a){}

    void move(char m, char n){
        static int numb = 0;
        numb++;
        std::cout << "第" << numb << "次" << std::endl;
        std::cout << m << "-> " << n << std::endl;
    }
    void pai(int num, char a, char b, char c){
        if (num < 1){
            return;
        }
        else{
            pai(num - 1, a, c, b);
            move(a,c);
            pai(num-1,b,a,c);
        }
    }
    void solve(){
        char A = 'A';
        char B = 'B';
        char C = 'C';
        pai(this->num, A, B, C);


    }
};



int main(){

        int n = 0;
        std::cout << "请输入你想放的盘子:    ";
        std::cin >> n;
        han han1(n);
        han1.solve();
        std::cout << std::endl;






    std::cin.get();
    std::cin.get();
    return 0;
}

原文链接: https://www.cnblogs.com/zhurun/p/4590755.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍