分析:

我们把汉诺塔变换看为是路径的变换，这样我们只要能把路径的变换调整就能知道总步骤
eg:
a->c步数 我们用数组hnt[1][3]表示
a->b步数 我们用数组hnt[1][2]表示
b->a步数 我们用数组hnt[2][1]表示
b->c步数 我们用数组hnt[2][3]表示
c->a步数 我们用数组hnt[3][1]表示
c->b步数 我们用数组hnt[3][2]表示
如果 我现在要调整将位置b,与位置c进行交换(a,b,c)->(a,c,b)
那么我们只需调整他们之间的位置
f(a,b,c):
swap(hnt[a][c],hnt[a][b]);
swap(hnt[b][a],hnt[c][a]);
swap(hnt[b][c],hnt[c][b]);
这样所有的步数就都调整过来了
同理 现在要调整将位置a,与位置c进行交换(a,b,c)->(b,a,c)
将f(a,b,c) 换成f(c,a,b)就行了

减少复杂度

我们用递归会超时，复杂度太大O(2^N)
所以我们转变思路，将递归变为递推，
通过位置关系，
我们可以知道下一层就是本层位置变换2次步数之和(一个是位置a,与位置c进行交换,一个是位置b,与位置c进行交换)+a->c这一步
这样我们的复杂度就会变为O(N)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define ll long long
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
const int maxx=1e6;
ll hnt[5][5],bb[5][5];//hnt汉诺塔数组，bb是保留上一次的汉诺塔数组
ll n,m;
void nf(ll (&p)[5][5],ll a,ll b,ll c)
{
    swap(p[a][c],p[a][b]);
    swap(p[b][a],p[c][a]);
    swap(p[b][c],p[c][b]);
}//交换p[][]中的b<->c      原本a,b,c 交换后a,c,b

void nnf(ll a,ll b,ll c)//让上一次(n-1)层汉诺塔数组  进行交换
{
    for(ll i=1;i<=3;i++)
    {
        for(ll j=1;j<=3;j++)
        {
            bb[i][j]=hnt[i][j];//让bb数组看为是原数组(n-1,a,b,c)
        }
    }
    nf(hnt,a,b,c);//hnt 交换b<->c 即步数(n-1,a,c,b)
    nf(bb,c,a,b);//bb 交换a<->b 即步数(n-1,b,a,c)
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            hnt[i][j]+=bb[i][j];//步数(n-1,a,c,b)(n-1,b,a,c)二者相加
        }
    }
}
void ff(ll n,ll a,ll b,ll c)//递推实现汉诺塔 步数统计
{
    for(ll i=1;i<=n;i++)
    {
        nnf(a,b,c);
        hnt[1][3]++;//最后加上a->c 这一步
    }
}
ll poww(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
            if(y&1)
        {
            ans*=x;
        }
        x*=x;
        y>>=1;
    }
    return ans;
}//快速幂算总步数
int main(int argc, char** argv) 
{
    cin >> n;
    ff(n,1,2,3);
    ll sum=poww(2,n)-1;
    printf("A->B:%lld\n",hnt[1][2]);
    printf("A->C:%lld\n",hnt[1][3]);
    printf("B->A:%lld\n",hnt[2][1]);
    printf("B->C:%lld\n",hnt[2][3]);
    printf("C->A:%lld\n",hnt[3][1]);
    printf("C->B:%lld\n",hnt[3][2]);
    printf("SUM:%lld\n",sum);
    return 0;
}