奇怪的汉诺塔

  • 2019-06-29
  • 88
  • 0

奇怪的汉诺塔

题目描述:

汉诺塔问题,条件如下:

1、这里有A、B、C和D四座塔。

2、这里有n个圆盘,n的数量是恒定的。

3、每个圆盘的尺寸都不相同。

4、所有的圆盘在开始时都堆叠在塔A上,且圆盘尺寸从塔顶到塔底逐渐增大。

5、我们需要将所有的圆盘都从塔A转移到塔D上。

6、每次可以移动一个圆盘,当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时,可将圆盘移至这座塔上。

请你求出将所有圆盘从塔A移动到塔D,所需的最小移动次数是多少。

河内塔.jpg
汉诺塔塔参考模型

输入格式:

没有输入。

输出格式:

对于每一个整数n(1≤n≤12),输出一个满足条件的最小移动次数,每个结果占一行。

输入样例:

没有输入。

输出样例:

参考输出格式。

假设当前 A 柱上有 n 个圆盘,并且当圆柱上有 1 ~ n – 1 个圆盘时所需要移动的最小次数已知。

那么,对于 n 个圆盘,枚举 i 从 1 到 n – 1,现将 i 个圆盘利用四根柱子移动到非目标柱子的任意一根柱子上,再将 n – i 个圆盘,利用三根柱子移动到目标柱子上,最后将 i 个圆盘利用四根柱子移动到目标柱子上,取最小值即为移动 n 个圆盘所需要的最小移动次数。

显然,完成上述操作还需要有一个只利用三根柱子移动 1 ~ n 个圆盘的最小次数。

对于三根柱子的情况,仍然假设当前 A 柱上有 n 个圆盘,并且当圆柱上有 n – 1 个圆盘时只利用三根柱子所需要的移动的最小次数已知。

那么,对于 n 个圆盘,先将 n – 1 个圆盘利用三根柱子移动到非目标柱子上,再将最后一个圆盘移动到目标柱子上,最后将 n – 1 个圆盘利用三根柱子移动到目标柱子上,得到的答案即为结果。

PS:对于三根柱子为什么不需要像四根柱子那样枚举从 1 ~ n – 1 这个问题就留给读者自行思考。(因为显然不需要~~)


评论

还没有任何评论,你来说两句吧

浙ICP备19014917号

浙公网安备 33068302000569号