文档介绍：Computer Knowledge and Technology电脑知识与技术第10卷第7期(2014年3月)本栏目责任编辑:谢媛媛软件设计开发图解方式解析汉诺塔递归算法的教学实践周鑫(山东省泰安第一中学,山东泰安 271000)摘要:该文对递归算法的实质进行了探讨。以汉诺塔问题为例,提出一种图解的方式,直观地展示了递归算法的具体执行过程,有助于初学者对递归思想的深入理解。关键词:递归;图解;汉诺塔中图分类号:TP312 文献标识码:A 文章编号:1009-3044(2014)07-1444-02递归是一种有效的算法设计方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。递归是高中信息学奥赛必须掌握的基本算法思想,但在实际教学中却发现,初学者对程序执行的具体过程和参数传递过程难以理解,无法领会递归的实质。为此,笔者根据自己多年的教学实践,以汉诺塔——递归的典型例题为例,提出一种图解的方式,展开递归算法的具体执行过程。1 汉诺塔问题描述汉诺塔是一个经典的数学问题,其具体描述如下:有三根相邻的柱子,标号为A,B,C,A 柱上从下到上按金字塔状叠放着n 个不同大小的圆盘,现在把所有盘子借助于A,B,C 三个柱子一个一个移动到C柱上,并且每次移动在同一根柱子上都不能出现大盘在小盘上方的现象。根据问题描述得到以下规则:1)圆盘必须一个一个的移动;2)大的圆盘必须在小圆盘的下方或单一圆盘;3)满足规则2)的序列可以出现在A,B,C 任意一根塔上。传说布拉马圣2 汉诺塔问题的算法分析汉诺塔问题中盘子的移动过程虽然繁琐,却有规律性可循。要想将A柱上的N个盘子移动至C柱,可以通过以下三个步骤实现:1)以C柱为过渡柱,从A柱将1至N- 1号盘移至B柱。2)将A柱中剩下的第N号盘移至C柱。3) 以A柱为过渡柱,从B柱将1至N- 1号盘移至C柱。这明显是一个递归的过程,不断深入,不断细小化,最终,将到达仅有一个盘的情形,这时, 递归也就终止了,问题也得到了解决。我们看到,整个递归过程可分解为两个问题,即最小子问题和汉诺塔问题。其中,步骤2是递归的终止条件,是一个能直接求解的最小子问题,只需移动一个盘子就完成任务。步骤1、3均是n-1阶的汉诺塔问题,不同阶的区别在于各柱的作用不同。这样,原问题被转换为与原问题性质相同、规模变小的子问题。即:将Hanoi(N,A,B,C)转化为Hanoi(N- 1,A,C,B)与Hanoi(N- 1,B,A,C)。其中Hanoi()中的参数分别表示需移动的盘子数、起始柱、过渡柱与目标柱。把步骤1、3进一步分解下去,每一次分解,都使得规模减少1,最后n阶汉诺塔问题可以被分解成若干个只需要移动一个盘子的能直接求解的子问题,使得整个问题得到解决。3 汉诺塔问题的C语言代码汉诺塔问题的C语言代码为:#include<>⑴ void Hanoi(int n, char a, char b, char c)⑵{⑶ if(n==1) //只有一个盘子,直接移动⑷ pri