汉诺塔问题（小杨）

༺དༀ༒PHKLSA༒ༀཌ༻

2026-10-04 10:36:03

发布于：浙江

0阅读

0回复

0点赞

题目：

有三个可以放圆盘的柱子，编号为A、B和C。开始时柱子A上套着n个圆盘，它们从上到下按照从小到大的顺序排列。我们的任务是要把这n个圆盘移到柱子C上，并保持它们的原有顺序不变。

在移动圆盘的过程中，需要遵守以下规则：

每次只能移动一个圆盘。

小圆盘必须时刻位于大圆盘之上。

每一次移动，圆盘只能从A移动到B，从B移动到C，或者从C移动到A；其它移动是不允许的。

在新规则下，给定圆盘数量n，求将n个圆盘从A移动到C所需的最少移动步数。

输入格式：输入一个正整数n，表示圆盘的数量。

输出格式：输出一个整数，表示新规则下的最少移动步数。

样例：

输入为2时，输出为7。

题解（代码）：

#include<bits/stdc++.h>
using namespace std;
int n,a[1009],b[1009];
long long ans=3;
int main(){
    cin>>n;
    a[1]=7;
    b[1]=5;
    for(int i=2;i<=n;++i){
        b[i]=a[i-1]*2+1;
        a[i]=2*a[i-1]+b[i-1]+2;
    }
    
    cout<<a[n-1];
    return 0;
}