2050 - 汉诺塔
汉诺塔是根据一个印度传说形成的数学问题:有三根杆子A, B, C， A杆上有n个穿孔圆盘, 盘的尺寸由下到上依次变小. 要求按照下列规则将所有圆盘移至C杆:
1. 每次只能移动一个圆盘
2. 大盘不能叠在小盘上面
找出最少需要移动多少次, 并打印移动的方案。
输入
一个整数n(1<=n<=15), 表示A杆最初有多少个圆盘。
输出
第一行, 输出最少移动的次数.
以下每行分别打印一次移动(例如, 移动A杆最上面的圆盘到C杆, 则输出"Move A to C")。
样例
输入
3
输出
7 Move A to C Move A to B Move C to B Move A to C Move B to A Move B to C Move A to C
提示
【样例解释】
【数据规模】
50% 的数据，满足 1≤n≤5；
100%的数据，满足 1≤n≤15。