题解 | #循环汉诺塔#

#include<iostream>
#include<vector>

using namespace std;
// 以下是@Muuuuuuu的解题思想，仅做借鉴学习*****************
//根据题目规定，易知该情况下，只有底部，没有顶部，从A移动到B需要1次操作（A→B），从A移动到C需要2次操作（A→B，B→C）。

//设函数AB（N）为把N个盘从A移动到B需要操作的次数，函数AC（N）为把N个盘从A移动到C需要操作的次数。

// 因此我们可以记为当N=1时，AB（1）=1，AC（1）=2。
//A移动到B时
/*首先需要把顶部从A移到C，再把底部从A移到B，最后把顶部从C移到B。

一共会有5次操作，即1、A→B，2、B→C，3、A→B，4、C→A，5、A→B。

实际上，AB（N）可以视为是由3个子问题组成的，即1、顶部移动两次，2、底部移动一次，3、顶部移动两次；

子问题1实际上是AC（N-1）的问题；

子问题2由于底部只有一个盘，所以子问题2的值恒等于AB（1），即值为1；

子问题3实际上也是AC（N-1）的问题；

所以AB（N）=AC（N-1）+1+AC（N-1）

简化一下，AB（N）=2AC（N-1）+1*/

/*A移动到C时：
首先将顶部从A移到C，再将底部从A移到B，再将顶部从C移到A，再将底部从B移到C，最后将顶部从A移到C。

一共有7次操作，即：1、A→B，2、B→C，3、A→B，4、C→A，5、B→C，6、A→B，7、B→C。

同样的，AC（N）也可以视为由5个子问题组成，即：1、顶部移动两次，2、底部移动一次，3、顶部移动一次，

4、底部移动一次，5、顶部移动两次；

子问题1实际上是AC（N-1）的问题；

子问题2由于底部只有一个盘，所以子问题2的值恒等于AB（1），即值为1；

子问题3实际上是AB（N-1）的问题；

子问题4也是值恒为1；

子问题5实际上也是AC（N-1）的问题；

所以AC（N）=AC（N-1）+1+AB（N-1）+1+AC（N-1）

简化一下，AC（N）=2AC（N-1）+AB（N-1）+2*/

void RecurHanoi(int index, int n, vector<long long int> &AB, vector<long long int> &AC){
    //index = 2 初始化使用该函数
    // AB[1] = 1, AC[1] = 2;
    if(index > n){
        return;
    }
    // AB[n] = 2*AC[n-1] + 1
    // AC[n] = 2*AC[n-1] + AB[n-1] + 2
    // 这里注意要先取模，要不会数据太大，会出现负数
    AB[index] = (2*AC[index-1] + 1)%1000000007;
    AC[index] = (2*AC[index-1] + AB[index-1]  + 2)%1000000007;
    index++;
    RecurHanoi(index, n, AB, AC);
}

int main(){
    int n = 0;
    cin >> n;
    int id = 2;
    vector<long long int> AB(n+1, 1);
    vector<long long int> AC(n+1, 2);
    RecurHanoi(id, n, AB, AC);
    cout << AB[n] << ' ' << AC[n] << endl;
    return 0;
}