算术谜题与程序设计（2）

昨天写了一个例子，推荐作为第一门程序设计课的作业。（其实这样的例子通过变化可作为一系列作业，并非只能是一题）。每当讨论类似问题，总有老师跟我说：你们不知道我们这些应用型地方院校，学生不爱学习，...。我并不相信现在的学生如何如何...。但作为第一门程序设计课，开始确实总得弄点不需要动太多脑筋的问题（但总得有点趣），别把还不太习惯所谓智力题的同学吓跑了。为此，我们可以找比昨天那个恢复长除算式更容易的问题（从编程角度看）。下面是个示例：F G R J C PE M C P G L E—————————————————F R R J J E E E这是一个加法算式。每个字母代表一个10进制数字，式子中字母与数字的对应是固定不变的。要求将式子还原成符合加法法则的算式。这个例子中出现的字母有9个，它们与9个十进数字的对应可以表示成含9！个元素的集合。采用简单穷尽方法，首先生成9个元素的全部排列，9！，不到40万，在现在的笔记本电脑上还能处理。对初学者，编一下这个程序也不错，生成所有排列并非对每个初学程序设计的同学都觉得信手拈来。可以要求循环和递归两种方法。不过换个输入，10个数字都用上，那排列数就有360万了，穷尽算法就会遇到效率瓶颈。这时我们就需要通过分析缩小搜索空间。上面这个例子尤其简单，算式的形式表明F一定是1，E一定是9，R一定是0。搜索空间下降到6!=720。当然不能只生成排列，还得通过验证判断正确结果。这一般比长除问题简单很多。只需要对字母与数字的每种对应，计算相应的两个加数与和就可以了。当然也可以通过变化使难度有所变化。总之，这类问题用于第一门程序设计课通常具备的优点，这个更简单的例子几乎都有。那些对自己的学生信心不那么足的老师可能会觉得更适用一些。