李晓明教授
0 引 言
计算思维谈了十多年了。如果于概念辨析的层面探讨,似乎还没有形成共识的“定义”。事实上,并非任何事情都要先搞清楚定义才能展开内涵研究和实践,许多方向性的话题,本就不好下定义。然而,十多年没搞清楚定义,却还有人愿意继续谈,一定是这个词语后面蕴涵着某种比较广阔的人们觉得有价值的东西。于是,可以重点讨论或者展示些具体的做法和例子。是否属于计算思维的范畴,有些不同的看法也正常,重点是事情具体了,价值就容易判断。
本文提出一种教学思路,面向非计算机专业的学生(这里不一定只是在校生),不追求让他们系统掌握什么,只是希望通过一种过程,让他们感受到“计算思维”的魅力。
这个过程应该是轻松愉快的,否则感受到的就不是“魅力”了;这个过程也应该是有挑战性的,否则感受到的就不是“计算思维的魅力”了。我们姑且把这个过程称为“从趣味数学到趣味算法到趣味编程”,或者短一些,就叫“趣味数算程”。
1 从趣味数学说起
为什么起点是“趣味数学问题”而不是什么“生活中的真实问题”?这是另外一个话题了。用生活中的真实问题作为引导,当然也是有价值的。这里可以说的是,用已经抽象好的趣味数学问题作为引导,不仅有价值,而且对初学者来说会相对容易些。
这里,可能有敏感的读者会提问题:“等等,计算思维不是强调抽象吗?用已经抽象好的问题作为出发点,不就丧失了体会‘抽象’的机会?”
我的回答是:“这里只是完成了‘ 数学抽象’的问题,计算抽象还在后面呢!”
这样一种说法,得益于最近这两年参与讲授一门北大社会学系的课程,对于我讲的那些内容的风格,学生给了一个概括:概念抽象→数学抽象→计算抽象。可以说,这真是教学相长了。我自己先前就没总结出这么漂亮(而且贴切)的说法,只是朴素地凭感觉铺陈那些内容。
为什么以趣味数学为起点?还有一个个人的原因。记得大约是上小学三四年级的时候,不知从哪弄来一本书,叫《趣味数学》,上面有许多有趣的小题目,不是都看得懂,但其中一些内容已足以让人很有兴致,有些题目直到现在都还记得,偶尔会在脑海中蹦出来。当然,那本书后来就不知去向了。
前年某个时候,不知怎么又想起了它,抱着试一试的心态,到一个旧书网,居然淘到了这本 1961年少年儿童出版社出的书(如图 1 所示)。翻一翻,非常亲切。结合最近这几年参与编写基于高中信息技术新课标的教材《算法初步》,意识到许多趣味数学问题(或者说数学游戏)的解,都是一个过程描述(即先做什么,再做什么,然后做什么等),也就是一个“算法”了。不过从讨论“计算机算法”的角度,那些问题有局限性,即它们都很具体,相当于计算机科学中某问题的一个“实例”。
图 1 1961 年少年儿童出版社出版的《趣味数学》
于是,一个思路自然浮现出来:从《趣味数学》中的问题出发,将它们一般化,讨论在一般化情形下的解,即计算机算法,最后用程序予以表达,从而形成一条从趣味数学到趣味算法到趣味编程的途径。
2 从趣味算法到趣味编程
《趣味数学》中适合的问题有很多,由于篇幅原因,本文仅通过下面这样一个例子展现这条途径的风格,也相信读者能有更多、更好的例子。
《趣味数学》中的一个问题:移棋子。将黑白 6 只棋子在桌上黑白相间地排成一排——黑白黑白黑白,左边留出够放 4 只子的空位,现在要把这 6 只子移成 3 只白子在左边、3 只黑子紧接在右边的样子(如图 2 所示)。要求是必须一次并列移两子,把它们移到空位上,不能更改子的顺序,只可移 3 次解决问题。
三年级以上小学生能理解这个问题。想一想,试一试,10 分钟内通常就能解决,也就是给出了一个三步骤算法。这里留给读者来做。
但我们不能就此满足。现在 3 对黑白相间棋子的问题会求解了,那么如果是任意 n(n > 3)对,是不是也会求解呢?我们需要有一个以 n 为参数的计算机算法!
怎么做?对熟悉计算机科学的人来说,马上能想到的可以试一试的思路就是“约简”。希望求解关于 n 的问题,就看能否先解决 n-1 的问题,然后在那基础上做些“增量性”工作,得到关于 n 的解。这种思路递归下去,到了 n=3,就可用前面提到的办法了。于是,重点就在于“增量性”工作该怎么做。图 3(a)展示了一个方案:以 3 对棋子已经移好了作为初始状态,经过靠拢、交界、到位、凑整、回填 5 个步骤,完成 4 对棋子的移动任务。
审视这 5 个步骤,我们能体会到这种增量性操作具有一般性,也就是在 4 对已经完成的基础上再用类似的5 步,就能完成 5 对棋子的移动任务等。至此,作为算法描述和理解也就透彻了,的确看到了一个对所有 n >3 的解决方案。我们实现了一个从特殊(n=3)到一般的升华,从趣味数学到了趣味算法。
那么,若编出程序来,还能带来什么新的价值吗?是的,如果我们心目中的程序是要基于输入 n,一步步输出展示一个类似于图 3(a)所示的过程(当然还要加上最初 3对是怎么完成的),就会有至少两条很有价值的考虑:
首先,信息的表示,即如何在程序中用数据表示棋子局面的状态和变化过程。简单起见,只考虑字符方式。程序的执行,就可能想象输出如图 3(b)所示的结果。从学理的角度讲,就是要体现信息和数据的关系,利用编程语言提供的能力,做一个从信息到数据的映射。
再者,这样一个针对 n 的过程,显然有递归的味道,当然可用递归实现,同时也很容易用迭代来实现,也就促进了对这两种基本方式的理解和运用。图 4 就是一个完整的程序(迭代方式),图 3(b)则是它的一次执行结果。
有些编程基础的读者会看到这程序真的很简单,几乎不需要数据结构,也没有复杂的过程控制,其中有点挑战的细节,就是让图 3(a)所示的 5 个步骤“参数化”,每次移动的具体位置与已经完成的状态相关,程序中就是通过 p 实现的。这样的程序,从对编程能力的要求来看,初级水平就可以胜任,所需要的,是清晰的逻辑思维和算法思维能力。
这种程序本身并不复杂,可一旦实现,带来的却是惊喜,因为它意味着走完了一条有点曲折,但每个弯都能过去且引人入胜的途径。《趣味数学》中的许多例子,都有类似的样式:从算法的角度分析清楚后,最后落实到程序都不需要专业的编程能力。
3 结 语
如果有进一步的追求,马上可以问的问题是:前面说的这个算法在效率上是最优的吗?如果有 n对棋子,现在的做法是需要 3 5×(n-3)次操作。还能否再改进?结论是可以的,但如何能简单描述,则是另一个层面的挑战了。
经常会听到这样的纠结:非计算机专业的学生该不该学编程?如果该学,该如何学?当然,非计算机专业也有不同的情况,这里主要谈传统上认为离得比较远的,如社会科学专业的学生。
我现在认为,他们应该编程,但没必要“学”编程。这里给“学”打上引号,是指那种很正式地选一门计算机语言编程课的方式。那么,不学怎么会呢?答案是“在用中学”!就像一些应用软件,人们都没有“学”,但都在不同程度(不同水平)上用一样。类似于 Python 这种层次的解释型语言,是可以高效“嵌入到”一些问题求解过程中的。这种过程可能需要抽象、分析、推理,也可能需要写些文字,还可能需要算出几个数,对某些现象进行简单模拟,于是需要写几行代码等。这就是“面向问题求解”,而不是为了编程而编程。本文以数学游戏问题为例,展示了一条途径。不同专业学科自然可以选择各自的问题作为出发点,培养训练这种“融会贯通”的能力。
引文格式:李晓明.从趣味数学到趣味算法到趣味编程——非专业学习者体会计算思维的一条途径?[J].计算机教育,2020(11):优先出版.
李晓明教授其他文章:
在计算机专业教育中引入跨学科元素——“网络”课教学的初步实践与体会
(微信编辑:史志伟)
联系客服