[学习笔记]差分方程模型——汉诺塔问题

题目：
（汉诺塔问题）n 个大小不同的圆盘依其半径大小依次套在桩 A 上，大的在下，小的在上。现要将此 n 个盘移到空桩 B 或C 上，但要求一次只能移动一个盘且移动过程中，始终保持大盘在下，小盘在上。移动过程中桩 A 也可利用。设移动 n 个盘的次数为an ，试建立关于 an 的差分方程，并求an 的通项公式。

首先我们从两个盘子的情况开始探索：
由图片我们可以显而易见的看出移动两个盘子所需要的次数是3次，在此我们将移动两个盘子的过程打包，将这两个盘子看成一个特殊的盘子，只是移动这个盘子需要花费掉三次移动次数。

现在我们以移动三个盘子为目标，将两个盘子看成特殊盘子之后，这个汉诺塔相当于只有两个盘子——一个普通盘子，一个特色盘子。特殊盘子移动了两次，而普通盘子移动了一次，一共移动了3*2+1次。我们又可以将移动三次盘子的过程打包，求出四次、五次、乃至n次。
对于移动n次，将上面的n-1个盘子看成一个特殊盘子，记录移动次数为an-1，于是根据规律推出了差分公式an=2 * an-1 + 1。（也是一个递归公式）

解方程
在c语言中，可以衍化成套娃（雾，递归）
在这里当作常系数线性差分方程进行求解。