跳至正文
题库4249
#4249

Hanoi问题

查看题目操作

Hanoi问题

题目描述

给定 N 个大小不同的盘子和三根柱子。初始时全部盘子从小到大叠在第一根柱子上,目标是把全部盘子移到第三根柱子上。

每次可以从一根柱子的顶部取走连续叠放的 1 至 M 个盘子,保持它们的顺序,并作为一个整体放到另一根柱子的顶部。任何时候都不能把大盘子放在小盘子上。

求最少移动次数。例如 N = 5、M = 2 时,可以把最小的两个盘子、中间两个盘子和最大的一个盘子分别看作一个整体,共需要移动 7 次。

输入格式

一行两个整数 N 和 M。当 N > 0 时,满足 1 ≤ M ≤ N ≤ 8;另外允许 N = M = 0,表示没有盘子。

输出格式

输出一个整数,表示最少移动次数。没有盘子时输出 0。

样例

5 2
7
0 0
0

来源

蓝桥杯 算法训练