#1234. 汉诺塔问题

汉诺塔问题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

汉诺塔是根据一个印度传说形成的数学问题:

有三根杆子A\red{A}, B\red{B}, C\red{C}. A\red{A}杆上有n\red{n}个穿孔圆盘, 盘的尺寸由下到上依次变小.

要求按照下列规则将所有圆盘移至C\red{C}杆:

  • 1. 每次只能移动一个圆盘
  • 2. 大盘不能叠在小盘上面

找出最少需要移动多少次, 并打印移动的方案.

输入格式

一个整数n\red{n}(1<=n<=15\red{1<=n<=15}), 表示A\red{A}杆最初有多少个圆盘.

输出格式

第一行, 输出最少移动的次数. 以下每行分别打印一次移动 (例如, 移动A杆最上面的圆盘到C\red{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

省实越秀的作业

未参加
状态
已结束
规则
ACM/ICPC
题目
8
开始于
2022-6-6 14:30
结束于
2022-6-6 20:30
持续时间
6 小时
主持人
参赛人数
21