Scilab案例 汉诺塔问题

案例 汉诺塔问题

学习目标

1．熟悉递归算法的设计要求；

2．提高算法设计能力；

3．理解数学归纳法与递归算法原理之间的关系.

学习内容

问题 汉诺塔问题即梵塔问题，自上而下从小到大64片圆片依次叠在长针a上，借助长针c，通过多少次移动将此64片圆片移到长针b上，每次只能移动一片圆片，且小片必须在大片上方.

解：设an表示n个圆片从长针a移到长针b的次数；

如图分析，由递推方法可知，a1 1，an 2an 1 1， 所以 an 2n 1. 如果有64个圆片，那么移动次数是a64 264 1，这是一个可怕的天文数字！ 如果圆片的个数小点，如n 4,5,6,

它的移动次数分别是15,31,63,. ，那么上述是如何移动的呢？尽管我们已知道了长针b 长针a 长针b

长针c

an 1③ an 1

现在我们利用递归算法来求解上述问题，其思想与上述分析类似.

Scilab案例 汉诺塔问题

我们把n阶的汉诺塔问题记作：hannuo(n,a,b,c)，表示n个圆片，从长针a借助长针c移到长针b.

由上述分析可以知道，n个圆片移动情况由递归方法可转化为：

第一步 hannuo(n-1,a,c,b) 表示n 1个圆片，从长针a借助长针b移到长针c. 第二步 把最下面的一个圆片n，从长针a移到长针b.

第三步 hannuo(n-1,c,b,a) 表示n 1个圆片，从长针c借助长针a移到长针b. 如此不停地递归转化为n更小的情况，当n 0时，则不移动结束.