另辟蹊径：在创编程序中培育计算思维

李友兴

摘要：程序设计题库平台里的题目从何而来？它是如何被创造出来的？出题者是以怎样的方式构建问题来考察解题者的算法能力？这一系列的思考让作者审视目前程序设计教学方法，将创新引入到程序设计教学的领域中，探索程序设计教学的另一条路径——创编程序题。对于创编程序题的教学探索，本文提出了规范框架、确定算法、辨识情境、试用反馈等方法。创编程序题不仅可以发展学生的计算思维力，而且还可以激发学生的创造潜能，提升学生的技术学习成就感。

关键词：程序设计;计算思维;教学策略;创新实践

中图分类号：G434  文献标识码：A  论文编号：1674-2117（2019）10-0034-04

在程序设计教学中，通常以程序题的求解为载体，来培养学生的算法构建能力，发展学生的计算思维。而教师通常会在程序题的OI平台中“上下翻腾”，通过“以身探题”来了解题目中所蕴含的算法，为学生构建拾阶而上的算法构建能力培育的程序题序列。随着教师和学生对题目求解的不断深入，师生都会自然地萌发一种想法：这些程序题从何而来？出题者有怎样的算法理解力？他（她）以怎样的方式构建问题来考察解题者的算法能力？这一系列的思考，让笔者审视目前程序设计的教学方法是不是该走出传统的靠刷题的唯一路径，向出题者致敬，从解题到创题，寻找一条新的程序设计教学路径。

创编程序题是学生基于一个或若干个算法，借助特定的生活情境，通过改编或创造，编制程序题源的一种行为。在创编程序题的过程中，学生基于算法，从一道最简单的“裸题”出发，通过逐步构造、转化、深化、增加、整合等过程，完成对问题的构思，体验程序创编的快乐，同时发展与提升计算思维。

规范框架——从了解到理解

程序题有一些基本的格式和规范，其表述的文本是与解题者的一种对话。以NOIP试题为参照，其组成要素有题目名称、问题描述、输入文件、输出文件、样例数据和数据规模，每种要素都有各自的价值，用于向解题者提供明确的信息。

以学生创编的“课间游戏”程序题为例，“课间游戏（kjyx.cpp/c/pas）”是程序题的“题目名称”，它是对具体问题情境的一种提炼与浓缩，同时明确了源程序的文件主名与扩展名。“问题描述”是提供已知条件，抛出一个具体索求的问题，本程序题的“问题描述”提出的是“在地图中棋子经历多次前进与后退行动后的最终状态”。“输入文件”是根据题目中的描述，提供一种一定规格的数据，第一行有三个数字，分别表示棋子移动的次数为N次，最多前进格数为M格，后退格数为K格。第二行数据表示每次移动的格数，数据之间有空格分隔。输入文件对应的是“kjyx.in”。“输出文件”是求解后输出的结果，文件名对应的是 “kjyx.out”。“样例数据”分别对应输入输出格式具体的数据说明。“数据规模”是超越样例的数据规模说明，在构造程序时要考虑极大、极小、特殊等一些数据，使得数据规模能够区分解题者的算法能力水平。

在程序题创编辅导中，教师不要急着让学生死记硬背其组成要素，而要与学生讨论与交流，使其理解这几大基本要素。通过暂时性隐藏某些元素与内容，让学生感受到这几个元素的不可或缺性，如缺失了数据规模，就无法考虑时间复杂度与空间复杂度，缺失了样例说明，就难以确定输入与输出的数据具体含义，进而也就难以理解题目。

确定算法——从简单到复杂

一般情况下，学生创编程序题初始阶段构造的题目是比较朴素的，能被“一眼看穿”，其算法暴露在题目的描述中，即所谓的“裸题”。此时，教师要顺势引导，让学生通过转化、增加、整合等方法，实现题目的难度升级。其目的在于，构造的程序题不仅能考验解题者对问题的理解力和抽象能力，还能考查解题者灵活应用算法的能力。

以基于小数的计数算法创编为例，程序社团小江同学打算创编计数算法的程序题，她一开始确定的思路如上页图1所示——一组N个整数，要求若干个整数个数并按照整数的大小进行排序，这样的问题设计对于学过计数的解题者来说不需要任何思考。于是，笔者引导学生在原题的基础上增加“关卡”，将计数算法作一定的隐藏。通过启发，她开始想“怎样的数据是不能直接用来计数的，但是通过转化仍可计数”？最后，她想出输入的数据是小数，每个小数的位数又是不同的，那就要寻找到最大的小数位数n，再把所有的小数乘以10^n，将所有原来的小数数据转换为整数形式。这样，就可以应用计数排序，只需要将排序后再还原为小数，就完成了问题的求解。

当学生将修改后的创编题提交时，笔者发现其最大数据规模为2<=N<=10^8，虽说计数排序的数据规模理论上是可以开到N（按照一秒的有限时间），但还要考虑数组存储空间大小（参照128MB的内存空间），最终将数据规模定在N<=10^7。同时，笔者进一步引导学生考虑分层，让普通的计数排序算法也能获得一些分值，这样就构造出30%的数据规模为1<=N<=1000，ai是一位小数。最终版的程序题既有区分度，又有灵活性。

编织情境——从良构到劣构

学生在确定了算法的考量，明确了算法，也确定了数据规模之后所构造出来的题目虽然有深度有区分度，但“嚼之无味”“读之无趣”。这种没有生活情境的题目缺少了现实意义的支撑，学生在分析问题过程中感受不到其意义与价值，在一定程度上会降低解题者的探索兴趣。此时，教师就需要引导学生联系现实，走向真实世界，创设有“时代感”“生活味”的情境，将程序设计的问题求解回归现实的意义，如上页图2所示。

当前的新课程理念提倡的是一種在复杂问题情境中的求解，在程序创编中教师除了可以编织生活情境以外，还可以将良构的问题描述改编成劣构的问题情境。通常的做法是，在良构的问题描述上再加上一些冗余的信息，让学生在生活情境、冗余的信息中去提炼信息，确定问题，构建算法。这样，不仅有利于发展解题者的算法构建力，而且也有利于提升创编者的计算思维，如图3所示。

试用反馈——从薄弱到增强

程序题的创编是一个不断地迭代与优化的过程，就如同用程序设计一样，它的改进需要从创编的反方向去思考——解题者的反馈。其反馈主要有三种信息：兴趣度、题目难度和数据漏洞。第一种是“趣味度”，表明了题目是否足够引起解题者的兴趣;第二种是“题目难度”，其指标在于区分一个群体的程序算法的能力水平;第三种是“数据漏洞”，指的是数据构造中的漏洞，具体表现为解题者不需要正确的算法也能“踩”到分值。根据反馈的不同，需要不断地改进。比如难度太简单，那就要对照前面的算法构造进行一定的转化与隐藏，或者提高数据规模来增加难度。再如数据构造上有漏洞，那就要对数据构造方面进行修正补全。

以上页图4“找数字朋友”为例，小黄同学第一次把题目提交给笔者时，数据规模为：“100%的数据 1<=n<=200，m<=200， 0<=ai<=100”。为了检测该题的难易程度，笔者将此题发给社团学员进行现场测试，并由小黄同学亲自监考与cena评测。结果发现每位同学都得满分，因为只需要利用双重循环模拟扫一遍就可以求解出答案，难度不大。为了加大难度，小黄修改了数据规模为：“100%的数据 1<=n<=100000，0<=m<=2000，0<=ai<=1000”。通过再试做，发现10位同学有8位得满分，那是因为“n数据规模到达10万”，采用双重循环的解题者必然超时，而采用计数算法的解题者能够将时间复杂度降低到O（maxai），是为正解。为再次加大难度，小黄直接将数据规模调整为：“100%数据 1<=n<=

100000000<=m<=20000000，0<=ai<=10000000”，结果只有3位同学100%通过。由于ai到了10000000数据量，利用原先的计数算法加双重循环已经没法实现，这就要解题者改为O（n）或者O（ai）的算法，利用read（x）;ans=ans+a[m-x];inc（a[x]）;外套一个循环语句扫一遍完成，只有灵活应用计数算法，才能100%顺利通过。

创编程序的关键在于学生对程序算法的深刻理解，在理解的基础上才能联系生活情境，做到算法与情境的深度融合。同时，创编程序题使学生在不断地创编改良中进一步地深刻理解算法，甚至对各类相类似的算法融会贯通。创编程序是一种以创促学的算法学习、算法研习方式，它使学生从一个学习者跃升为一个有着计算思维驾驭力和个性思考力的构造者和创造者，这就极大地激发了学生的算法学习潜能，让他们获得技术学习的成就感。

参考文献：

[1]中华人民共和国教育部.普通高中信息技术课程標准[M].北京：人民教育出版社，2018.

[2]费海明.中小学生计算思维培育的路径与策略[J].中小学信息技术教育，2017（10）.