基于栈结构的孔明棋算法研究

Research of Kongming Chess Algorithm Based on Stack-Structure

孔明棋是一种玩法简单,但其中变化无数的益智游戏。对孔明棋求解问题进行分析,提出了基于回溯思想的递归和非递归算法,运行结果表明了算法的有效性。文章还围绕栈在存储数据、消解递归等方面的应用对两个算法的优缺点进行了比较分析,递归算法结构清晰,但递归调用次数多;而非递归算法借助程序栈,将程序向循环转化,降低了时间复杂度,但算法难以分析和理解。因此在求解实际问题时可以采用递归思想来分析,然后借助栈用非递归来实现算法。

Kongming chess is an intellective game with simple rules but changeable playing measures. Backtracking is an important and efficient solution for many issues. On the analysis of Kongming chess, proposes recursion and non- recursion algorithms based on backtrack for the issue, which works effectively. At the same time, advantages and disadvantages of the two algorithms are compared in the stack - based applications for data storage, backtracking problem, and recursion. Recursion has a vivid algorithm structure,hut it has to make use of recurring for many times; While non - recursion circulates the program with the help of a program stack. Thus it lowers the complexity of time but it has a complicated algorithm which is hard to analyse and understand. It comes to a conclusion that recursion is suitable for analysis, while non - recursion is for algorithm in solving practical problems.