題目描述

如下圖所示，設有?nn?個大小不等的中空圓盤，按照從小到大的順序疊套在立柱?A?上，另有兩根立柱?B?和?C?。

現在要求把全部圓盤從?A?柱（稱為源柱）移到?C?柱（稱為目標柱），移動過程中可借助?B?柱（稱為中間柱）。

移動時有如下要求：

1. 一次只許移動一個盤。
2. 任何時候、任何柱子上不允許把大盤放在小盤上邊。
3. 可使用任意一根立柱暫存圓盤。

問：如何用最少步數實現?nn?個盤子的移動？請打印出具體移動方案。

輸入格式

一行一個正整數?n(1≤n≤18)n(1≤n≤18)?。

輸出格式

輸出若干行，第?ii?行表示第?ii?步的移動方案。

具體格式參見輸出樣例。

樣例 #1

樣例輸入 #1

3

樣例輸出 #1

A->C
A->B
C->B
A->C
B->A
B->C
A->C

#include<bits/stdc++.h>
using namespace std;  
void hanio(int n,char a,char b,char c)
{if(n==0){return ;}hanio(n-1,a,c,b);cout<<a<<"->"<<c<<endl; hanio(n-1,b,a,c);
}
int main(){int n;cin>>n;hanio(n,'A','B','C');return 0;
}