#800. 【经典】汉诺塔问题

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cookiebus

题目描述

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

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

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

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

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

输入格式

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

输出格式

第一行, 输出最少移动的次数. 以下每行分别打印一次移动 (例如, 移动A杆最上面的圆盘到C杆, 则输出"Move A to C").

样例

样例输入 1

3

样例输出 1

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

分类标签