游戏算法分析在C语言教学中的应用

刘天时 李皎 陈明晰 西安石油大学计算机学院 710065

1 引言

算法是程序设计和软件开发的基础，也是计算机程序设计语言中一个重点和难点。算法具有不可见性、抽象性、复杂性是影响学生理解算法思想的重要因素[1,2]。由于其逻辑性强、实践性强，对初学者来说具有一定难度。因此，激发学生对算法设计的兴趣尤为重要。本文通过一些游戏案例来讲解算法设计思想，将学生对玩游戏的兴趣往设计算法的方向引导，从而促进学生理解一些典型算法设计思想。游戏算法分析教学方法使得学生从枯燥无味的算法学习中解脱出来，特别是学生一提到游戏，兴趣高涨，产生强烈的求知欲望，从而大大提高学生的学习兴趣，真正使学生爱学、乐学，达到寓教于乐的目的[3]。

下面以游戏案例为切入点，叙述程序设计中一些典型的常用算法，包括递归法、递推法和逆向法。

2 递归法

在算法分析与设计中，常常用到递归法。递归是指在定义自身的同时又出现了对自身的调用。递归方法可以把复杂问题逐层分解，最后将其划分为规模较小的问题进行解决，然后再逐层返回。使用递归方法往往使函数的定义或算法的描述简洁而且易于理解[4,5,6]。

汉诺塔问题是一个用递归思想解题的经典例子。汉诺塔问题可描述为：有3个分别命名为A、B、C的塔座，在塔座A上插有N个大小各不相同、从小到大编号为1，2，…，N的圆盘，且圆盘必须按照自下而上，由大到小叠放（如图1）。要求将塔座A上的N个圆盘借助塔座C移至塔座B上，并仍然按同样顺序叠放，圆盘移动时必须遵循如下规则：每次只能移动一个圆盘；……