h664 - 河內塔 (Hanoi)
題目描述
題目要求在河內塔遊戲中，給定圓盤數量 N 和步數 S，輸出第 S 步移動的圓盤編號。梅林會以最佳方式移動圓盤，直到詢問提示。
解題思路
這題的核心在於理解河內塔移動的模式。在最佳策略下，河內塔的移動步驟可以被編號。題目給定的步數 S 實際上是按照最佳策略移動的第 S 步。程式碼利用了位運算和遞迴來計算在第 S 步應該移動哪個圓盤。fd(x, y) 函數的作用是找到在 x 個圓盤的河內塔中，第 y 步移動的圓盤編號。它通過遞迴地將步數 y 分解為更小的子問題來實現。a[i] 陣列預先計算了 2 的冪，用於快速計算步數範圍。
複雜度分析
- 時間複雜度: O(N)
- 空間複雜度: O(N)
程式碼
#include <iostream>
using namespace std;
int a[16]={0,1},t,n,m;
int fd(int x,int y){
if(x==1)return 1;
int x2=(1<<(x-1));
if(y==x2)return x;
else if(y>x2){
return fd(x-1,y-x2);
}
else{
return fd(x-1,y);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
for(int i=2;i<=15;++i)
a[i]=a[i-1]*2+1;
cin >> t;
while(t--){
cin >> n >> m;
cout << fd(n,m) << "\n";
}
}