欢迎光临散文网会员登陆 & 注册

由汉诺塔所引出的

2022-08-21 14:10 作者:-王-小-明- 0人读过 | 我要投稿

最近在学C嘛，在递归这一节，老师举到了汉诺塔作例子。在目瞪口呆于居然用这么少的代码便能实现以至于感叹递归是神的同时，我在代码里加了一个统计次数的功能。

（代码写得比较烂不要在意）

运行程序，随便输几个数，然后……我好像发现了什么奇奇怪怪的东西。

有没有发现什么奇奇怪怪的东西（为了能放下，我把移动过程去掉了）

应该能发现，如果将 $n$ 层汉诺塔的移动次数记为 $a_%7Bn%7D%20$ ，那么应该有 $a_%7Bn%7D%20%3D2%5En-1%20$

结论有了，接下来该写证明过程了，当然其实也不是很难。

不妨将汉诺塔的三根轴记为 $x%2Cy%2Cz$

记 $n$ 层汉诺塔移动次数为 $a_%7Bn%7D%20$ ，易见 $a_%7B1%7D%3D1%20$ ，

注意到， $n$ 层汉诺塔的解法可拆解为三步：

①将上面的 $n-1$ 层汉诺塔从 $x$ 轴移动到 $y$ 轴

②将最下面的 $1$ 片从 $x$ 轴移动到 $z$ 轴

③将 $n-1$ 层汉诺塔从 $y$ 轴移动到 $z$ 轴

易见①③需要的步骤均为 $a_%7Bn-1%7D%20$ 次，而②需要 $1$ 次

故而 $a_%7Bn%7D%3D2a_%7Bn-1%7D%2B1%20$

可以通过凑系数得解

让我想起了高中的数学题（

两边同时加 $1$ ，有 $a_%7Bn%7D%2B1%3D2(a_%7Bn-1%7D%2B1)$ ，

由此可见 $%5Cleft%5C%7B%20%20a_%7Bn%7D%2B1%20%5Cright%5C%7D$ 是以 $a_%7B1%7D%2B1%3D2$ 为首项， $2$ 为公比的等比数列。

$a_%7Bn%7D%2B1%3D2%5En$ ， $a_%7Bn%7D%3D2%5En-1$

证明完毕。

标签：

由汉诺塔所引出的的评论 (共条)