墙画图片-电子商务网站推广

标题：浅谈用组合数学解决汉诺塔问题—暨对组合数
学的认识
汉诺塔问题来自 一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A），其上有
64个金碟。所有碟子按从大 到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石
宝塔（塔B和塔C）。从世界创始之日起， 婆罗门的牧师们就一直在试图把塔A上的碟子移
动到塔C上去，其间借助于塔B的帮助。每次只能移动一 个碟子，任何时候都不能把一个
碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。

对于这个问题，我们先来考虑盘子数为2的情形：此时，只需将上面的一个盘子从A搬到B< br>上，再将A柱的最下面的盘子从A搬到C柱上，最后把B上面的盘子搬到C柱上即可。整
个过程搬 运次数为3次；同理，我们考虑盘子数为3，可推得搬运次数为7次；
将问题一般化，假定盘子数为n ，我们现在把A上面的n-1个盘子看成一个整体，并设把A
柱上的n-1个盘子搬到B上，设需要的搬 运次数为H(n-1)，则n个盘子的搬运过程类似于2
个盘子，即把A柱上的n-1个盘子从A搬到B 柱上，搬运次数为H(n-1)，再把A柱的最下面
的盘子从A搬到C柱上，搬运次数为1次，最后把B 上的盘子搬到搬到C柱上，搬运次数
同样也为H(n-1)，总共的搬运次数为H(n)=2*H(n- 1)+1；
对于上述问题，可能以前会无从下手。但学过组合数学以后，我们知道，这是一个递推关系
的求解过程；对于此类递推关系可有两种求解思路，下面我来一一讲述：
思路1：上式递推关系可用数列的相关思想来进行解答；
H(n)=2*H(n-1)+1；
H(n)+1=2（H(n-1)+1）；
故{H(n)-1}为以2为公比的等比数列，首项为H(2)=3；
所以H(n)+1=2*2
n-1
，故H(n)=2
n
-1；
这是用数列的思想，构造一个等比数列继而求得该递推关系。
思路2：利用组合数学中生成函 数的有关内容，求出该递推关系H(n)的生成函数A(x)，进而
容易得到H(n)的表达式： 其中，我们定义，对于H(n)构成的序列，H(0)，H(1)，（假设存在，此处不考虑其实际意义），
H(2)，H(3)，……H(n)……，则生成函数A(x)定义如下
A(x)=H(0)+H(1)*X
1
+H(2)*X
2
+……H(n)*X
n
+……
那么，容易看出，只需求出A(x)这一生成函数，那么根据X
n
项系数即可得到递推关系H(n)
的式子；
接下来就是需要重点解决A(x)函数的求法；
我们不妨H(n)+1=2*2两边同乘X，并求和H(X)-X=2*X*H(X)+X(1-X)
化简 X+X^2(1-X)=(1-2X)H(X)
X(1-X)(1-2X)=H(X)
H(x)=a(1-2x)+b(-x);
再由待定系数法得 a=1,b=-1；
n-1k2

所以 H(X)=（1+2X+2X+…）-（1+X+X+…）
所以H(n)=2-1；
OK,这就是著名的汉诺塔问题以及利用组合数学的思想解决该问题的方法；
那么，组合数学是一门什 么学科呢？下面我结合这半个学期学习组合数学的感觉谈谈对这门
学科的简单认识。
组合数学 ，首先，顾名思义，组合，即一些离散数据的相互组合关系；我们利用数学上的符
号甚至公式，将现实问 题具体数学化；以方便人们的研究及应用。这是在网上找到的关于组
合数学的一般描述：组合数学是研究 离散结构的存在，计数，分析，和优化等问题的一门学
科。拿上面所述汉诺塔问题来说，这样的一个实际 问题，对于盘子数很大的情况，我们是无
法用类似盘子数为2,3时的枚举法得出结果的，而这时研究此 问题中这些数据间的离散关系
就显得尤为重要了。而组合数学正是研究离散数据关系的强有力工具！正如 上述组合法解答
过程，我们可以看到，组合可以给我们提供一个简单的看问题的角度，而我们正可以通过 这
一简单的角度窥视到深层，进而通过某种相对简单的方法得到我们想要的解答！
现今一种说 法，组合数学是也将持续是未来计算机领域发展的重要依托。细想下，的
确！现今数学可以主要分为两大 类，一类是一类是研究连续对象的，如分析、方程等，另一
类就是研究离散对象的组合数学。计算机程序 是计算机的大脑思维，而程序的本质就是算法，
在绝大多数情况下，计算机的算法是针对离散的对象，而 不是在作数值计算。组合数学的产
生恰好满足了编写计算机程序的需求。所以，身为计算机专业的学生， 组合数学的重要性就
不言而喻了！而许多组合问题的解决常常需要某些特别的例证，而且有时需要结合使 用一般
的理论。我们必须学会建立数学模型，研究模型，抓住问题的要害，灵活的应用智慧来解决
问题。我们必须把组合数学的学习放在一个重要的位置上来，掌握基本的组合数学原理，培
养专业的数 学思维，这样才能在以后的工作学习中掌握主动和先机。才能在将来为中国的计
算机软件事业做出自己的 贡献。
以上即通过利用组合数学解决汉诺塔问题，浅谈对于组合数学的认识全文。
2011.11.27


参考文献
维普《利用组合数学化简汉诺塔问题》、《组合数学》等。

n
^2*22