解题思路

  1. 问题描述：

    • 三个柱子 顺时针排列
    • 只能顺时针移动：
    • 初始所有盘子在 柱
    • 求移动到 和 的最少步数

  2. 限制条件：

    • 大盘不能放在小盘上
    • 一次只能移动一个盘
    • 结果需要对 取模

递推公式推导

  1. 移动到B的情况：

    • 要将 个盘子移到
    • 需要先将 个盘子移到
    • 再移动最大盘到
    • 再将 个盘子从 通过 移到
    • 所以：

  2. 移动到C的情况：

    • 要将 个盘子移到
    • 需要先将 个盘子移到
    • 再移动最大盘经过 到
    • 再将 个盘子从 移到
    • 所以：

  3. 状态定义：

    toB: 将 n 个盘子从 A 移动到 B 的最少步数
toC: 将 n 个盘子从 A 移动到 C 的最少步数

  4. 递推公式：

    toB(n) = 2 * toC(n-1) + 1
toC(n) = 2 * toC(n-1) + toB(n-1) + 2

  5. 初始状态（）：

    toB = 1  (A->B)
toC = 2  (A->B->C)

代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    unsigned toB = 1, toC = 2;  // 初始状态：n=1
    
    for(int i = 1; i < n; i++) {
        // 计算新状态
        unsigned newB = (toC * 2u + 1) % 1000000007u;
        unsigned newC = (toC * 2u + toB + 2) % 1000000007u;
        // 更新状态
        toB = newB;
        toC = newC;
    }
    
    cout << toB << " " << toC;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long toB = 1, toC = 2;  // 初始状态：n=1
        final int MOD = 1000000007;
        
        for(int i = 1; i < n; i++) {
            long newB = (toC * 2 + 1) % MOD;
            long newC = (toC * 2 + toB + 2) % MOD;
            toB = newB;
            toC = newC;
        }
        
        System.out.println(toB + " " + toC);
    }
}

n = int(input())

toB, toC = 1, 2  # 初始状态：n=1
MOD = 1000000007

for i in range(1, n):
    newB = (toC * 2 + 1) % MOD
    newC = (toC * 2 + toB + 2) % MOD
    toB, toC = newB, newC

print(toB, toC)

算法及复杂度分析

算法：动态规划、递归 时间复杂度:

  • 需要进行 次状态转移
  • 每次状态转移是 的操作

空间复杂度:

  • 只使用常数个变量存储状态
  • 不需要额外空间

优化说明

  1. 空间优化：

    • 只保存当前状态
    • 不需要数组存储所有状态

  2. 类型选择：

    • 使用 避免负数
    • 及时取模避免溢出

  3. 计算顺序：

    • 先计算新状态
    • 再更新旧状态
    • 避免中间结果污染

注意事项

  1. 模运算：

    • 每次计算后立即取模
    • 防止中间结果溢出

  2. 初始值：

    • 时的正确初始值很重要
    • 影响后续所有计算

  3. 数据范围：

    • 可达到
    • 需要考虑计算过程中的溢出问题