0 #1234. 汉诺塔问题
汉诺塔问题
题目描述
汉诺塔是根据一个印度传说形成的数学问题:
有三根杆子, , . 杆上有个穿孔圆盘, 盘的尺寸由下到上依次变小.
要求按照下列规则将所有圆盘移至杆:
1.
每次只能移动一个圆盘2.
大盘不能叠在小盘上面
找出最少需要移动多少次, 并打印移动的方案.
输入格式
一个整数(), 表示杆最初有多少个圆盘.
输出格式
第一行
, 输出最少移动的次数. 以下每行分别打印一次移动 (例如, 移动A杆最上面的圆盘到杆, 则输出"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