题解 | #循环汉诺塔#

/*

写了半天没看到要取模.....

用大数加法输出的原始数据，但是核心思路是没错的

和普通的汉诺塔一样，无非就是加了方向，推导迭代表达即可

*/

#include <iostream>

#include <vector>

using namespace std;

int num;

//大数加法

//大端序存储

vector<int> sum(vector<int> added, vector<int> add){

    //保证长度一致

    if(add.size()>added.size()){

        while(add.size()!=added.size()){

            added.push_back(0);

        }

    }else{

        while(add.size()!=added.size()){

            add.push_back(0);      

        }

    }

    int temp=0;//进位

    int sum=0;

    for(int i=0;i<add.size();++i){

        sum = add[i] + added[i] + temp;

        if(sum>=10){

            sum = sum-10;

            temp = 1;

        }else{

            temp = 0;

        }

        added[i] = sum;

    }

    if(temp!=0){

        added.push_back(1);

    }

    return added;

}

//递归

void find(vector<int>& Dp_A_B,vector<int>& Dp_A_C,int id){

    if(id==num){

        return;

    }

    vector<int> Dp_A_B_next = sum(sum(Dp_A_C, Dp_A_C),{1});

    //cout<<Dp_A_B_next[0]<<endl;

    vector<int> Dp_A_C_next = sum(sum(sum(Dp_A_C, Dp_A_C),{2}),Dp_A_B);

    //cout<<Dp_A_C_next[0]<<endl;

    find(Dp_A_B_next,Dp_A_C_next,id+1);

    Dp_A_B = Dp_A_B_next;

    Dp_A_C = Dp_A_C_next;

}

int main() {

    int n;

    cin>>n;

    num = n;

    vector<int> Dp_A_B = {0};

    vector<int> Dp_A_C = {0};

    find(Dp_A_B, Dp_A_C, 0);

    for(int i=1;i<=Dp_A_B.size();++i){

        cout<<Dp_A_B[Dp_A_B.size()-i];

    }

    cout<<" ";

    for(int j=1;j<=Dp_A_C.size();++j){

       cout<<Dp_A_C[Dp_A_C.size()-j];

    }

    return 0;

}

// 64 位输出请用 printf("%lld")