汉诺塔问题递归算法与非递归算法比较
|
摘要
汉诺塔问题是一个古典数学问题,对于给定的盘子数量及每步移动盘子次序是确定的。因此,只要能够确定盘子移动的规则,就可以通过计算机程序加以实现。递归算法虽然代码简单,但对于初学者而言,理解其内涵存在困难,且算法执行效率不高。提出一种基于非递归思想的移动方向判断算法解决汉诺塔问题,通过与递归算法执行时间比较,提出的判断移动方向算法执行效率更高,且算法思想相对更简单、更容易理解。
The Hanoi tower problem is a classical mathematical problem.Since the order of moving plate at each step is fixed for agiven number of plates,the rules for moving plate can be readily determined by computer program.Although the code of recursive algorithm is simple,but for beginners,its meaning is not easy to understand,and the efficiency of its execution is not high.In this paper,we propose algorithm which is based on the non-recursive thinking and used to jude moving directions to solve the problem of the Hanoi tower.By comparing with the execution time of the recursive algorithm,we can draw a conclusion that judge the algorithm proposed in this paper is more efficient,and its algorithmic thinking is relatively simple,easier to understand.
The Hanoi tower problem is a classical mathematical problem.Since the order of moving plate at each step is fixed for agiven number of plates,the rules for moving plate can be readily determined by computer program.Although the code of recursive algorithm is simple,but for beginners,its meaning is not easy to understand,and the efficiency of its execution is not high.In this paper,we propose algorithm which is based on the non-recursive thinking and used to jude moving directions to solve the problem of the Hanoi tower.By comparing with the execution time of the recursive algorithm,we can draw a conclusion that judge the algorithm proposed in this paper is more efficient,and its algorithmic thinking is relatively simple,easier to understand.
引文
[1]谭浩强.C程序设计(第四版)[M].北京:清华大学出版社,2010.
[2]吴晓晨.递归程序设计教学方法的研究[J].天津科技,2017,44(1):69-73.
[3]姚云霞.对汉诺塔(Hanoi)问题的算法探索与研究[J].物联网技术,2013(7):48-49.
[4]王明.梵塔问题的两个定理[J].应用数学,1999(2):112-114.
[5]严蔚敏,陈文博.数据结构及应用算法教程[M].北京:清华大学出版社,2011.
[6]戴莉萍,黄龙军,刘清华.自底向上记录式Hanoi塔非递归算法[J].实验科学与技术,2016,14(1):51-54.
[7]张建波.一种将递归过程转换为非递归过程的方法研究[J].计算机教育,2017(8):139-142.
[8]李玉华,崔凤云,刘晓庆.汉诺塔问题的层次迭代算法[J].计算机工程与应用,2008,44(35):73-75.
[9]卢芳芳,孙燮华,仇苏恺,等.Hanoi塔问题非递归的新算法[J].计算机工程与应用,2006,42(17):108-110.
[10]赵东跃.汉诺塔非递归算法研究[J].计算机应用与软件,2008,25(5):241-243.
[11]戴莉萍,黄龙军,刘清华,等.记录式Hanoi塔非递归算法及快速仿真[J].电气电子教学学报,2015,37(6):112-116.
[12]李健.汉诺塔算法演示系统的设计与实现[J].现代计算机:专业版,2011(24):76-80.
[13]卫洪春.图形环境下的汉诺塔演示[J].电子设计工程,2014(15):8-10.
[14]李兆歆,张大坤.基于VSL语言的三维动态交互移动实现及其应用[J].计算机工程与设计,2010,31(2):455-458.
[15]曾夏玲.基于计算思维能力培养的“轻游戏”教学模式初探[J].职教论坛,2015(11):79-82.
[16]李清霞,孙欣.益智课堂,数学核心素养践行之地——以“汉诺塔”活动课为例[J].中国教师,2017(10).
[2]吴晓晨.递归程序设计教学方法的研究[J].天津科技,2017,44(1):69-73.
[3]姚云霞.对汉诺塔(Hanoi)问题的算法探索与研究[J].物联网技术,2013(7):48-49.
[4]王明.梵塔问题的两个定理[J].应用数学,1999(2):112-114.
[5]严蔚敏,陈文博.数据结构及应用算法教程[M].北京:清华大学出版社,2011.
[6]戴莉萍,黄龙军,刘清华.自底向上记录式Hanoi塔非递归算法[J].实验科学与技术,2016,14(1):51-54.
[7]张建波.一种将递归过程转换为非递归过程的方法研究[J].计算机教育,2017(8):139-142.
[8]李玉华,崔凤云,刘晓庆.汉诺塔问题的层次迭代算法[J].计算机工程与应用,2008,44(35):73-75.
[9]卢芳芳,孙燮华,仇苏恺,等.Hanoi塔问题非递归的新算法[J].计算机工程与应用,2006,42(17):108-110.
[10]赵东跃.汉诺塔非递归算法研究[J].计算机应用与软件,2008,25(5):241-243.
[11]戴莉萍,黄龙军,刘清华,等.记录式Hanoi塔非递归算法及快速仿真[J].电气电子教学学报,2015,37(6):112-116.
[12]李健.汉诺塔算法演示系统的设计与实现[J].现代计算机:专业版,2011(24):76-80.
[13]卫洪春.图形环境下的汉诺塔演示[J].电子设计工程,2014(15):8-10.
[14]李兆歆,张大坤.基于VSL语言的三维动态交互移动实现及其应用[J].计算机工程与设计,2010,31(2):455-458.
[15]曾夏玲.基于计算思维能力培养的“轻游戏”教学模式初探[J].职教论坛,2015(11):79-82.
[16]李清霞,孙欣.益智课堂,数学核心素养践行之地——以“汉诺塔”活动课为例[J].中国教师,2017(10).