汉诺塔问题
山西省临汾市临汾三中学校高370班冀超指导老师：李艳芳
摘要：通过对汉诺塔问题中盘子数与移动次数的关系，探寻其中的规律，并建立数学模型，达到用最小的开支，取得最大的效果。

关键词：汉诺塔问题数学模型
如图，汉诺塔问题是指有三根杆子A,B,C。

C杆上有若干碟子，把所有碟子从C杆上移到B杆上，每次只能移动一个碟子，大的碟子不能叠在小的碟子上面。

求最少要移动多少次。

一. 发现并提出问题
如上图，汉诺塔问题是指有三根杆子A,B,C。

C杆上有若干碟子，把所有碟子从C杆上移到B杆上，每次只能移动一个碟子，大的碟子不能叠在小的碟子上面。

现在C杆上有四个碟子求最少要移动多少次。

我问我周围的同学，发现有算出15步的、16步的、还有17步，
还有20多步的。

当我一遍一遍地在脑子里模拟，在纸上画图，最后得出的结果是15.
这就是这道题的最后答案
我想，当时数出20多步的同学一定有一些步骤重复了。

最近要写论文，在课间做眼保健操时，我就很容易地想到了这个问题。

它能不能被深入地推广一下呢？
于是我就开始了对这个论文题目的思考与研究。

二. 建立数学模型
我列出了C杆上碟子的数量与移动次数的关系
注意观察移动次数的增加量之间的关系：
1+2=3 = （22-1-1）+22-1
3+4=7 = (23-1-1)+23-1
7+8=15 = (24-1-1)+24-1
15+16=31 = （25-1-1）+25-1
由此猜想：当C杆上有n个碟子时，那么总移动次数为：
（2n-1-1）+2n-1=2*2n-1-1=2n-1
但这只是不完全归纳，如何从正面直接推导呢？
三.数学模型的分析与问题的解决
经过对刚才移动过程的回忆，我又发现，当C杆上有4个盘子时，可以先将最上边的3个碟子移动到A杆上，共七次；然后将第四个也就是最大的那个碟子移到B杆上，共一次；最后再将三个盘子移回B 杆，共七次。

一共是7+1+7=8次。

那么我们可以得到：
当C杆上有n-1个碟子时，设总移动次数为a n-1次
当C杆上有n个碟子时，设总移动次数为a n次
那么
a n=a n-1+1+a n-1
a n=2a n-1+1
a n+1=2(a n-1+1)
即：数列{a n+1}是等比数列，首项是a1+1=2，公比是2
∴：a n+1=2*2n-1
可得到：a n=2n-1
四.数学模型的进一步推广
如下图，汉诺塔问题是指有三根杆子A,B,C。

C杆上有若干碟子，把所有碟子从C杆上移到B杆上，每次只能移动一个碟子，大的碟子不能叠在小的碟子上面。

现在C杆上有n个碟子求最少要移动多少次。

由上文的推导过程来看，总共需要：（2n-1）步
五.论文总结：
问题：如下图，汉诺塔问题是指有三根杆子A,B,C。

C杆上有若干碟子，把所有碟子从C杆上移到B杆上，每次只能移动一个碟子，大的碟子不能叠在小的碟子上面。

现在C杆上有n个碟子求最少要移动多少次。

答：最少要移动2n-1次
附. 论文写作后记：
这个问题是在眼保健操时脑子放松偶然想到的。

在百无聊赖的时候，一个偶然提出的问题，却引发了我们长时间的思考。

这种题目类型不止用于汉诺塔问题当中生活中的这类问题并不少见。

而细致地进行处理，周密地进行思考，就可以从容地应对那些看似复杂的问题。

这个问题的解决，对于我们在日常生活中“用最小的开支，取得最大的效果”，也是有指导意义的。

参考文献：《高中数学A版必修5》人民教育出版社 2007 主编：李建华。