汉诺塔变形

野性酷女 2022-05-29 00:20 144阅读 0赞

# **题目描述：**  #

约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。Daisy已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有N个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？  
输入：  
包含多组数据，每次输入一个N值(1<=N=35)。  
输出：  
对于每组数据，输出移动最小的次数。  
样例输入：  
1 3 12  
样例输出：  
2 26 531440

# **题目分析:** #

**我们首先对汉诺塔的原型进行分析，然耨再去考虑变种的问题**  
原先三步走过程：A,B,C  
1.将A中的n-1块儿进行移动，移动到b上。  
2.将A中的最大块儿进行移动，移动到C上。  
3.将B中的n-1块儿进行移动，移动到C上。  
n=1时，A->B,B->C; 由此我们得到1块儿盘从A移动到C所需要的全部步骤。  
n=2时，A->B,B-C,A->B,C->B,B->A,B->C,A->B,B->C  
规模为n时，我们不去具体考虑n-1块是怎么移动的，只需要考虑当下。我们把最大块儿以上的看做一个块儿。  
整个过程分为以下几个步骤：

*  将N-1块儿移动到C.A->C(这是个递归过程，求解此过程需要继续求解n-2的移动状态)
 *  将第N块儿移动到B.A->B
 *  将N-1块儿移动到A.C->A(这是个递归过程，求解此过程需要继续求解n-2的移动状态)
 *  将第N块儿移动到C.B->C
 *  将N-1块儿移动到C.A->C(这是个递归过程，求解此过程需要继续求解n-2的移动状态)

代码实现：  
**注意，题目上要求的是次数，而我求得是递归的过程**

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    void dfs(int n,char src,char dst ,char temp){
        if(n==1){
            cout<<src<<"->"<<temp<<endl;
            cout<<temp<<"->"<<dst<<endl;
            return ;
        }
        dfs(n-1,src,dst,temp);
        cout<<src<<"->"<<temp<<endl;
        dfs(n-1,dst,src,temp);
        cout<<temp<<"->"<<dst<<endl;
        dfs(n-1,src,dst,temp);
    }
    int main(){
        int num;//输入要移动盘片儿的个数 
        cin>>num;
        dfs(num,'A','C','B');
        return 0;
    }