《另辟蹊径在创编程序中培育计算思维.docx》由会员分享，可在线阅读，更多相关《另辟蹊径在创编程序中培育计算思维.docx（7页珍藏版）》请在三一办公上搜索。
1、另辟蹊径：在创编程序中培育计算思维宁波市江北区育才实验学校李友兴【摘要】程序设计题库平台里的题目从何而来？它是如何被创造出来的？出题者是以怎样的方式构建问题来考察解题者的算法能力？这一系列的思考让笔者审视目前程序设计教学方法，将创新引入到程序设计教学的领域中，探索程序设计教学的另一条路径创编程序题。对于创编程序题的教学探索上，本文提出了在规范框架、确定算法、辨识情境、试用反馈等一条明朗的路径与方法。创编程序题不仅可以发展学生的计算思维力，而且还可以激发学生的创造潜能，提升学生的技术学习成就感。【关键词】程序设计；计算思维；教学策略；创新实践程序设计教学中，通常以程序题的求解为载体,来培养学生的
2、算法构建能力，发展学生的计算思维。而教师通常会在程序题的Oi平台中“上下翻腾”，通过“以身探题”来了解题目中所蕴含的算法，为学生构建拾阶而上的算法构建能力培育的程序题序列。随着教师和学生对题目求解的不断深入，师生都会自然地萌发一种想法一一这些程序题从何而来？出题者有怎样的算法理解力？他（她）以怎样的方式构建问题来考察解题者的算法能力？这一系列的思考，让笔者审视目前程序设计的教学方法，是不是该走出传统的靠刷题的唯一一条路径，向着出题者致敬，从解题到创题，寻找一条新的程序设计教学路径。创编程序题是学生基于一个或若干个算法，借助特定的生活情境，通过改编或创造，编制程序题源的一种行为。在创编程序题的过
3、程中，学生基于算法，从一个最简单的“裸题”出发，通过逐步构造、转化、深化、增加、整合等过程,完成对问题的构思，体验程序创编的快乐，同时发展与提升学生的计算思维。一、规范框架从了解到理解程序题是有一些基本的格式和规范，其表述的文本是与解题者的一种对话。以NolP试题为参照，其组成要素由：题目名称、问题描述、输入文件、输出文件、样例数据和数据规模，每种要素都有各自的价值，用于向解题者提供明确的信息。以学生创编的“课间游戏”程序题为例，“课间游戏（/c/pas）”这个是程序题的“题目名称”，它是对具体问题情境的一种提炼与浓缩，同时明确了源程序的文件主名与扩展名。“问题描述”是提供已知条件，抛出一个具
4、体索求的问题，本程序题的“问题描述”提出的是“在地图中棋子经历多次前进与后退行动后的最终状态”。“输入文件”是根据题目中的描述，提供一种一定规格的数据，第一行由三个数字，分别表示棋子移动的次数为N次，最多前进格数为M格，后退格数为K格。第二行数据表示每次移动的格数，数据之间有空格分隔。输入文件对应的是“输出文件”是求解后输出的结果，文件名对应的是”样例数据”分别是对应输入输出格式具体的数据说明。“数据规模”事实上是超越样例的数据规模说明，在构造程序时要考虑极大、极小、特殊等一些数据，使得数据规模能够区分解题者的算法能力水平。在程序题创编辅导中，不应急着让学生死记硬背其组成要素，而是要与学生讨论
5、与交流，理解这几大基本要素。通过暂时性隐藏某些元素与内容，让学生感受到这几个元素的不可或缺性。比如缺失了数据规模，就无法考虑时间复杂度与空间复杂度。又比如缺失了样例说明，就难以确定输入与输出的数据具体含义,进而也就难以理解题目，如图1所示。课间游戏(cpas)【问题描述】终于等到下课了，聪明的小亮随手画了一个棋盘，发明了一个游戏：一枚棋子，每次移动ai步(起始点为第零格)，但当前进了M格的时候，就要后退K格。棋子一共移动N次。看看最后走到哪里。但这个过程实在太漫长了，等做完都快上课了。你能通过程序算出最后在哪里吗？【输入文件】文件名：第一行有三个整数N、M和K,表示棋子移动的次数、最多前进格数
6、和后退格数。第二行有N个整数，表示每次移动的格数。叫修棋Ae文件中只有一个整数，表示最后停在哪儿。【样例输入】【样例输出】5325352101【数据规模】20%的数据:1=N=101=M,K=51=ai=540%的数据：1=N=1000K=M,K=1001=ai=20100%的数据:1=N=1OOOOO1=M,K=1OOOOO1=ai=保证K=M图1课间游戏创编题二、确定算法从简单到复杂一般情况下，学生创编程序题初始阶段构造的题目是比较朴素的，能被“一眼看穿”，其算法暴露在题目的描述中一一即所谓的“裸题”。此时，教师要顺势引导，让学生通过转化、增加、整合等方法，实现题目的难度升级。其目的在于，
7、构造的程序题不仅能考验对问题的理解力和解题者的抽象能力，而且还能考查解题者灵活应用算法的能力。以基于小数的计数算法创编为例，程序社团小江同学打算创编计数算法的程序题，她一开始确定的思路（如图2所示）：一组N个整数，要求若干个整数个数并按照整数的大小进行排序，这样的问题设计对于学过计数的解题者不需要花费任何思考。于是，笔者引导学生在原题的基础上增加“关卡”，将计数算法作一定的隐藏。通过启发，她就开始想“怎样的数据是不能直接用来计数的，但是通过转化仍可计数？”最后，她想出输入的数据是小数，每个小数的位数又是不同的，那就要寻找到最大的小数位数n,再把所有的小数乘以10m，将所有原来的小数数据转换为整
8、数形式。这样，就可以应用计数排序，只需要将排序后再还原为小数，就完成了问题的求解。当学生将修改后的创编题提交时,笔者发现其最大数据规模为2=N=108,虽说计数排序的数据规模理论上是可以开到N（按照一秒的有限时间），但还要考虑数组存储空间大小（参照128MB的内存空间）,最终将数据规模定在NCIO，。同时笔者进一步引导，让学生考虑分层，让普通的计数排序算法也能获得一些分值，这样就构造出30%的数据规模为l=N=1000,ai是一位小数。最终版的程序题既有区分度，又有灵活性。【样例输入】整数计【样例输入】修正数【样例输入】5数转换5据范围5150120120191150为小数1.51.21.21
9、.911.5并增加1.51.21.21.911.5【样例输出】计数【样例输出】区分度【样例输出】1202.1.2021.2021911Z)1.9111.91115021.5021.502【数据范围】【数据范围】【数据范围】100%2=N=108100%2=N=10830%l=N=1000,ai是一位小数100%2=N=107,ai是02位小数图2从整数计数算法转化为小数计数算法三、编织情境一一从良构到劣构学生在确定了算法的考量，明确了算法，也确定了数据规模之后所构造出来的题目虽然有深度有区分度，但“嚼之无味”、“读之无趣”。因为这种没有生活情境的题目缺少了现实意义的支撑，学生在分析问题过中感受
10、不到其意义与价值,在一定程度上会降低解题者的探索兴趣。此时，教师就需要引导学生联结现实,走向真实世界，创设有“时代感”、“生活味”的情境，将程序设计的问题求解回归现实的意义，如图3所示。统计数(cp)定制校服（cppc）【问题描述】一组N个整数，求若干个整数个数并按照整数的大小进行排序。【物入文件】第一行一个整数N,表示有N个小数。第二行是N个小数ai.每个小数之间有一个空格。【步出文件】整数个数并按照整数的大小进行排序【样例输入】51.51.21.21.911.5【样例输出】情境化后的程序创编题【问题描述】某服装公司为同学们量身定制校服，已知有N位同学，每位同学的身高为08m2.0m,公司为
11、了能成少布料成本，想在服装制造前能精准知道同学们的身高尺寸数量（身高按照从大到小），可人数实在太多，公司人员数不过来，你能帮帮他们吗？【输入文件】文件名：第一行一个整数N,表示要做校服的学生的个教。第二行是N个小数ai,每个小数之间有一个空格。（单位：m）【榆出文件】文件名：按照身高从大到小统计对应的人数。（尺寸保留2位小数）1.202【样例输入】【样例幡出】1.9111.502【数据范围】30%1=N=1000,ai是一位小数100%2=N=107,ai是02住小数5L2021.51.21.21.911.51.911【数据范围】20%1=N=1000,ai是一位小数f100$2=N=1(7,
12、ai是02位小图3具有情境化的创编题当前的新课程理念提倡的是一种在复杂问题情境中的求解，在程序创编中教师除了会编织生活情境以外，还能够将良构的问题描述改编成劣构的问题情境。通常的做法是,在良构的问题描述上再加上一些冗余的信息，让学生在生活情境、者的算法构建力，而且也有利于提升创编者的计算思维，如图4所示。从良构到劣构的改在冗余的信息中去提炼信息、确定问题、构建算法。这样，不仅有利于发展解题良构的问题描述（原题）【问题描述】一个整数N怎样拆分为两个不同的 自然数乘积最大构的问题描述（改进题）【问题描述】小亮同学在设计一个比较好玩的游戏，这个游戏是这样子的：有一个装满沙子的大桶N升，现场需要制作一
13、个长方静的小容器（材料有限，周长为M米，长与宽均为自然数，高度为0.4米）将沙子搬运到旁边的一个大桶里，请问最少搬运几次可以完成？图4从良构到劣构的改进题四、试用反馈一从薄弱到增强程序题的创编是一个不断地迭代与优化的过程，就如同用程序设计一样。那么，它的改进需要从创编的反方向去思考一一即解题者的反馈。其反馈主要有三种信息：兴趣度、题目难度和数据漏洞。第一种是“趣味度”，表明了题目是否足够引起解题者的兴趣；第二种是“题目难度”，其指标在于区分一个群体的程序算法的能力水平；第三种是“数据漏洞”，指的就是数据构造中的漏洞，具体表现为解题者不需要正确的算法也能“踩”到分值。根据反馈的不同，需要不断地改
14、进。比如难度太简单，那就要对照前面的算法构造中进行一定的转化与隐藏,或者提高数据规模来增加难度。比如数据构造上有漏洞，那就要对数据构造方面进行修正补全。找数字朋友(cppc)【问题描述】近来，学校程序社团里的黄佳瑞同学创编了名叫“找数字朋友”的游戏。游戏规则是这样的：每个玩家可以得到一个数字号码，每个人的数字只能进行两两“数字配对”即加法运算，若运算的结果恰巧是M,那么游戏就可以累计一个分值，游戏允许再次累计。你是游戏的开发者之一，你需要迅速计算出找伙伴游戏的最终得分。【榆入文件】第一行有二个数字n和m第二行有n个整数ai,每个终数之间有一个空格，表示每个玩家手中的数字号码。【输出文件】只有一
15、行，一个数字s,表示游戏的最终分数。【输入样例】【输出样例】391356【数据规模】30%数据1=n=200,m=200,0=ai=10070用数据1=n=100000,0=m=2000,0=ai=1000100%数据，1=n=,0=m=,0=ai=图5找数字朋友以图5“找数字朋友”为例，小黄同学第一次把题目提交给笔者时，数据规模为：“100%的数据l=n=200,m=200,0=ai=100,o为了检测该题的难易程度，笔者将此题发给社团学员进行现场测试，并由小黄同学亲自监考与cena评测。结果发现每位同学都得满分，因为只需要利用双重循环模拟扫一遍就可以求解出答案，难度不大。为了加大难度，小黄
16、修改了数据规模为：“100%的数据l=n=100000,0=m=2000,0=ai=1000,o通过再试做，结果发现10位同学有8位得满分，那是因为“n数据规模到达10万”，采用双重循环的解题者必然超时，而采用计数算法的解题者能够将时间复杂度降低到O(maxai),是为正解。为再次加大难度，小黄直接将数据规模调整为：“100%数据ICnC,0=m=O=ai=,结果只有3位同学100%通过。由于ai到了数据量，利用原先的计数算法加双重循环已经没法实现，这就要解题者改为。(n)或者O(ai)的算法，利用read(x);ans=ans+am-x;inc(ax);外套一个循环语句扫一遍就可完成，只有灵
17、活应用计数算法，才能100%顺利通过。创编程序的关键在于学生对于程序算法的深刻理解，在理解的基础上才能联结生活情境，做到算法与情境的深度融合。但反过来，创编程序题使学生在不断地创编改良中进一步的深刻理解算法，甚至对各类相类似的算法融会贯通。创编程序是一种以创促学的算法学习、算法研习方式，它将学生从一个学习者跃升为一个有着计算思维驾驭力的构造者和个性思考力的创造者，这就极大地激发学生的算法学习潜能，让他们获得技术学习的成就感。【参考文献】1普通高中信息技术课程标准M.人民教育出版社，中华人民共和国教育部,20182费海明.中小学生计算思维培育的路径与策略J,中小学信息技术教育杂志，2017(10)
