# 递归

下面是几个比较基本的题目。

# HANOI 塔问题

假设有三个分别命名为 $A, B, C$ 的塔座，在塔座 $A$ 上插有 $n(n<20)$ 个直径大小各不相同、依小到大编号为 $1, 2, \dots, n$ 的圆盘。现要求将 $A$ 轴上的 $n$ 个圆盘移至塔座 $C$ 上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则：

1. 每次只能移动一个圆盘
2. 圆盘可以插在 &A, B, C$ 中的任一塔座上
3. 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。

请通过编程来打印出移动的步骤。

输入样例：

5

输出样例：

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

代码如下：

#include <iostream>

using namespace std;

const char all = ('A'^'B'^'C');

void hanoi(int n, char begin, char end) {

    if (n==1) {

        printf("%c-->%c ", begin, end);

        return;

    }

    else {

        char oth = begin^end^all;

        hanoi(n-1, begin, oth);

        printf("%c-->%c ", begin, end);

        hanoi(n-1, oth, end);

    }

}

int main() {

    int n;

    cin>>n;

    hanoi(n, 'A', 'C');

    return 0;

}