一个盘子的情况

根据题目规定，易知该情况下，只有底部，没有顶部，从A移动到B需要1次操作（A→B），从A移动到C需要2次操作（A→B，B→C）。

设函数AB（N）为把N个盘从A移动到B需要操作的次数，函数AC（N）为把N个盘从A移动到C需要操作的次数。

因此我们可以记为当N=1时，AB（1）=1，AC（1）=2。

两个或两个以上盘子的情况

A移动到B时

首先需要把顶部从A移到C，再把底部从A移到B，最后把顶部从C移到B。

一共会有5次操作，即1、A→B，2、B→C，3、A→B，4、C→A，5、A→B。

实际上，AB（N）可以视为是由3个子问题组成的，即1、顶部移动两次，2、底部移动一次，3、顶部移动两次；

子问题1实际上是AC（N-1）的问题；

子问题2由于底部只有一个盘，所以子问题2的值恒等于AB（1），即值为1；

子问题3实际上也是AC（N-1）的问题；

所以AB（N）=AC（N-1）+1+AC（N-1）

简化一下，AB（N）=2AC（N-1）+1

可结合下图理解,其中绿色部分为顶部，橙色部分为底部：

A移动到C时

首先将顶部从A移到C，再将底部从A移到B，再将顶部从C移到A，再将底部从B移到C，最后将顶部从A移到C。

一共有7次操作，即：1、A→B，2、B→C，3、A→B，4、C→A，5、B→C，6、A→B，7、B→C。

同样的，AC（N）也可以视为由5个子问题组成，即：1、顶部移动两次，2、底部移动一次，3、顶部移动一次，

4、底部移动一次，5、顶部移动两次；

子问题1实际上是AC（N-1）的问题；

子问题2由于底部只有一个盘，所以子问题2的值恒等于AB（1），即值为1；

子问题3实际上是AB（N-1）的问题；

子问题4也是值恒为1；

子问题5实际上也是AC（N-1）的问题；

所以AC（N）=AC（N-1）+1+AB（N-1）+1+AC（N-1）

简化一下，AC（N）=2AC（N-1）+AB（N-1）+2

可结合下图理解：

总结

综上所述，我们可以获得AB（1）=1，AC（1）=2，AB（N）=2AC（N-1）+1，AC（N）=2AC（N-1）+AB（N-1）+2进行运算。

输入N时，可通过上述条件求出AB（N）的值和AC（N）的值。

golang实现方式可参考下面代码片段：

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scanf("%d", &n)
	AB := 1
	AC := 2
	for i := 2; i <= n; i++ {
		ab := AB
		ac := AC
		AB = (2*ac + 1) % 1000000007
		AC = (2*ac + ab + 2) % 1000000007
	}
	fmt.Print(AB, " ", AC)
}

题解 | #循环汉诺塔#

一个盘子的情况

两个或两个以上盘子的情况

A移动到B时

A移动到C时

总结