信息学奥林匹克竞赛对中学生计算思维的培养

梁雪梅

摘  要：中学是培养良好思维的关键时期，但是中学以基础知识教育为主，忽略了学生的思维能力的培养，使得学生缺乏科学素养、工程素养和计算素养。而信息奥赛刚好弥补了这一短板，通过信息奥赛教学，尤其是算法教学来培养学生分析问题和解决问题的能力。因此，该文研究信息学奥林匹克竞赛对中学生计算思维的培养，并以贪心算法教学为例，通过两个具体问题，引导学生分析问题、建立模型并评价算法。以此找出算法的规律和设计算法的步骤，培养学生分析问题和解决问题的能力，培养学生的计算素养。

关键词：信息奥赛  计算思维  贪心算法  建模

中图分类号：G642;R-4    文献标识码：A 文章编号：1672-3791（2019）09（c）-0118-02

美国卡内基·梅隆大学计算机科学系主任周以真（Jeannette M. Wing）教授在美国计算机权威期刊《Communications of the ACM》杂志上首次提出计算思维（Computational Thinking）。计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动[1，2]。即如何将看似困难的问题进行拆析、建模、抽象、转换成计算机能进行信息处理或代码执行的思维方法。这是解决实际问题的一种思维活动过程，也是一种有效解决问题的方法。

中小学阶段是培养学生良好思维的最佳时期，特别是计算思维的培养，但是我国中小学阶段的教育以基础知识教育为主，缺乏对计算思维的培养，使得学生对问题的思考缺乏科学素养、工程素养和计算素养，从而导致学生在思考实际问题的解决方法时不严谨、不科学[3]。

信息学奥林匹克竞赛即NOI竞赛（National Olympiad in Informatics），是全国中学五大竞赛之一。既然基础知识教育缺乏计算思维的培养，那信息奥赛是如何提高学生的计算思维呢？

该文通过设计、实现和评价实际问题的算法来阐明信息学奥林匹克竞赛对中学生计算思维的培养过程。同时还培养了学生分析问题、解决问题的能力，并通过不断地解决问题、开拓创新，提高学生的创新能力[4]。

1  基于信息奥赛的计算思维培养——以贪心算法教学为例

在信息奥赛中包含大量算法方面的考核，尤其是算法在实际问题中的应用。因此，在信息奥赛教学中更加侧重算法教学，主要教学过程分为问题描述、问题分析与建模、算法评价与优化等[5]。通过该过程不断提高学生素质和分析问题、解决问题的能力，培养学生的计算思维。该文以贪心算法为例，探究信息奥赛对中学生计算思维的培养。

1.1 问题描述

有n位同学参加学校文艺汇演，每位同学的表演时间已知。从0时刻开始陆续安排每位同学上场表演，每个表演的完成时间是从0时刻到个人表演结束的时间。请求出所有表演的总完成时间（所有表演完成时间之和）最短的上场顺序。

例如：5位同学，表演时间分别为2min、6min、4min、9min、13min。

1.2 问题分析与建模

【输入】同学集：S={1，2，3，4，5}，第i位同学的表演时间：tj∈Z+，j=1，2，…，n。

【输出】最短总完成时间I，S的排列为i1，i2，…，in。

【问题分析】将表演时间按从小到大排序：2、4、6、9、13。则第一位同学的完成时间为2min，第二位同学的完成时间为（2+4）min，第三位同学的完成时间为（2+4+6）min，第四位同学的完成时间为（2+4+6+9）min，第五位同学的完成时间为（2+4+6+9+13）min。总的完成时间计算如下：

T=2+（2+4）+（2+4+6）+（2+4+6+9）+（2+4+6+9+13）

=2×5+4×4+6×3+9×2+13

=75

通过分析得出，则最短的总完成时间为75min。表演时间短的先上场，根据表演时间按从小到大排序，然后依次上场。因此，抽象出其目标函数和解。

【目标函数】I的总完成时间，。

需要注意的是，在一些更为复杂的问题求解中，目标函数还有一定的约束条件。

【解】I*：使得T（I*）最小，即T（I*）=min{T（I）|I为S的排列}。

1.3 算法评价与优化

对于所有文艺汇演上场顺序的实例，使用该算法都能得到最优解吗？我们用数学思维来验证该算法的正确性。

证：假设上场顺序m第i，j项上场顺序相邻且有逆序，即ti>tj，交换任务i和j得到上场顺序n，其他次序不变，如图1所示。

根据目标函数可知T（n）-T（m）=ti-tj﹤0。所以该算法得到的结果为最优解。

通过学校文艺表演，我们发现每次先让表演时间最短的同学上场便可以得到最短的总完成时间，这就是贪心算法的应用。通过具体的实例，我们可以发现贪心算法总是做出当前最好的选择，即考虑在某种意义上的局部最优解，而不是整体上的最优。因此，贪心算法的关键是贪心策略的选择，没有固定的算法框架。使用贪心算法解决问题的基本步骤是[6]：（1）建立问题的数学模型;（2）将问题分解为若干子问题;（3）求解子问题的局部最优解;（4）合并子问题局部最优解得到原问题的一个解。

那么，所有问题都能通过贪心算法来解决并获得最优解吗？我们再来探讨另一个问题。

圣诞老人给同学们派发新年礼物，但是每位同学的背包只能装6kg礼物，现在有4类礼物，礼物的重量和价值如表1所示。

如何选择礼物，使得不超过背包承重范围且礼物价值达到最大呢？

依旧使用贪心法来解决这个问题，贪心策略是先装单位重量价值大的礼物，总重量不超过6kg。因此，各类礼物按照排序为。按照贪心策略选择了礼物1之后，再礼物2或礼物3均会超出6kg，所以最终的选择结果为礼物1和礼物4，最终的价值为9。但是，很明顯，选择礼物2和礼物4的总重量为6kg且价值为11，显然比价值9更好。

通过这个例子我们可以知道，通过贪心算法得到的解不一定是正解。这就涉及到算法设计的问题。那么，设计算法的步骤为：（1）问题建模;（2）算法选择与描述;（3）证明该方法是否对所有实例都能得到最优解;（4）如果得不到最优解，请给出反例证明。

根据文艺汇演案例，引导学生分析问题并建立模型，找到贪心算法的规律。然后分析具体的贪心算法，让学生明白使用贪心算法解决问题的基本步骤。然后，根据新年礼物选择案例，让学生明白贪心算法得到的解不一定是最优解，引导学生明白设计算法的步骤。使用具体的问题引入，引导学生学会分析问题和解决问题，培养学生的计算思维。

2  结语

该文根据计算思维的概念和信息奥赛培养目标，探究信息学奥林匹克竞赛对中学生计算思维的培养。通过分析中学生基础知识教育，发现中学基础教育缺乏计算思维的培养。因此，以贪心算法教学为例，根据文艺汇演问题，引导学生分析问题、一步步解决问题，得到贪心算法的规律和使用贪心算法解决问题的步骤，然后根据新年礼物选择问题，引导学生发现贪心法得到的解不一定是最优解，引出设计算法的步骤。通过分析和解决具体问题，培养学生分析问题和解决问题的能力，提高学生的数学思维、工程思维和计算思维。

参考文献

[1] Jeannette M.Wing.Computational Thinking[J].Communications of the ACM，2006，3（49）：33-35.

[2] 周以真.计算思维[A].中国科学技术协会学会学术部.新观点新学说学术沙龙文集7：教育创新与创新人才培养[C].中国科学技术协会学会学术部：中国科学技术协会学会学术部，2007：6.

[3] 刘向永，周以真，王荣良，等.计算思维改变信息技术课程[J].中国信息技术教育，2013（6）：5-12.

[4] 刘焱青.App Inventor2在中学生计算思维培养中的应用研究[D].湖南师范大学，2016.

[5] 屈婉玲，刘田，张立昂，等.算法设计与分析[M].北京：清华大学出版社，2011.

[6] 崔萌.遗传算法解决多背包问题[J].计算机与网络，2005（19）：52-54.