龙源期刊网 https://www.doczj.com/doc/ef4649199.html,
四柱汉诺塔非递归研究与实现
作者:姜华林李立新陈强
来源:《计算机时代》2013年第05期
摘要:对“经典三柱汉诺塔”的递归求解算法及其他非递归算法问题进行了详细的分析和研究,给出了一种新的简单且高效的非递归算法。在“经典三柱汉诺塔”的非递归算法研究基础上对“四柱汉诺塔”问题的四柱汉诺塔Frame算法进行了深入的研究,实现了一种高效的四柱汉诺塔非递归算法,并用C#语言进行了验证。通过该问题的C#实现,可使学习者清晰地观测到解决四柱汉诺塔非递归算法的全过程。
关键词:三柱汉诺塔;四柱汉诺塔; Frame算法;非递归算法
中图分类号:TP302 文献标志码:A 文章编号:1006-8228(2013)05-45-03
Research on non-recursive algorithm of 4-peg hanoi tower
Jiang Hualin1, Li Lixin2, Chen Qiang2
(1. Department of Computer Science, Zunyi Vocational and Technical College, Zunyi,Guizhou 563000, China;
2. School of computer and Information Science, Southwest University)
Abstract: Detailed analysis about hanoi issue is carried out and one easy and efficient realization of non-recursive algorithm in program C# is given.Frame algorithm of 4-peg hanoi tower is analyzed and researched based on the classic 3-peg hanoi tower program and a non-recursive and efficient algorithm of 4-peg hanoi tower is proposed. Realization of 4-peg hanoi tower algorithm though program C# can make learners observe clearly the whole process which solves this issue.
Key words: 3-peg hanoi tower; 4-peg hanoi tower; frame algorithm; non-recursive algorithm
0 引言
汉诺塔问题是一个古老的数学问题。经典汉诺塔问题是三柱的,即:有三个柱(分别为A、B和C)。开始时,有n个碟子按从下到上、从大到小的次序叠置在A柱上。现要将A柱上的所有碟子,借助B柱,全部移动到C柱上,且仍按照原来的次序叠置。三柱汉诺塔经典
算法为:首先用三柱汉诺塔经典算法把A柱上面的n-1个碟子通过C柱移到B柱上,然后把
A柱剩下的一个碟子移到C柱上,最后用三柱汉诺塔经典算法把B柱上所有的碟子通过A柱移到C柱上[1]。