h089 - 疊披薩
題目描述
題目描述了將 N 片由上往下尺寸遞增的披薩從 A 盒子移動到 C 盒子，過程中只能一次移動最上面的披薩，且避免披薩互相碰撞或打翻。要求輸出移動披薩的步驟，以最少步數完成移動。
解題思路
這道題是經典的漢諾塔問題。漢諾塔問題的解法是遞迴的。將 N 片披薩從 A 移動到 C，可以分解為以下三個步驟：
- 將 N-1 片披薩從 A 移動到 B (借助 C)。
- 將第 N 片披薩從 A 移動到 C。
- 將 N-1 片披薩從 B 移動到 C (借助 A)。
遞迴的終止條件是當 N 等於 1 時，直接將披薩從 A 移動到 C。
複雜度分析
- 時間複雜度: O(2^N)
- 空間複雜度: O(N)
程式碼
#include <iostream>
using namespace std;
void Towers(int n,char a,char b,char c){
if(n==1){
cout<<"from "<<a<<" to "<<c<<'\n';
}
else{
Towers(n-1,a,c,b);
cout<<"from "<<a<<" to "<<c<<'\n';
Towers(n-1,b,a,c);
}
}
int main() {
cin.tie(0);cout.tie(0); ios::sync_with_stdio(false);
int n;
cin>>n;
Towers(n,'A','B','C');
}