信息学竞赛视角下培养计算思维的策略研究

丁双林 广东省中山市中山纪念中学

●计算思维及其特征

1.计算思维

随着科学技术的发展，以计算机技术为基础所形成的信息技术不断融入人类的生活，在解决人类问题的过程中扮演着越来越重要的角色。在此背景下，计算机科学家周以真教授于2006年首次提出计算思维的概念，她认为计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。目前，越来越多的专家学者认识到计算思维的重要性，将计算思维同理论思维、实验思维并列为科学研究及解决问题的三大思维。

为适应时代的发展，《普通高中信息技术课程标准（2017年版）》及《义务教育信息科技课程标准（2022年版）》均将计算思维作为学科重要的核心素养之一，也就是说计算思维是中小学阶段学生必备的核心素养。

2.计算思维的特征

计算思维的两大核心特征是抽象建模和自动化。这两大核心特征概括了计算机解决问题过程中的核心步骤。抽象建模特征是指在利用计算思维解决问题过程中需要将问题进行归纳、总结，发现其中的规律，然后基于规律建立问题模型，这是利用计算思维解决问题的基础步骤。自动化特征是指将问题模型转化为计算机自动执行的程序指令，程序指令是计算思维解决问题的关键步骤。

3.学科视角与竞赛视角计算思维的异同

信息技术学科是中学生必须学习的学科之一，主要涉及包括信息技术的获取、表示、传输、存储、加工在内的各种技术及在信息技术基础上所形成的信息社会、信息系统、信息安全等相关的内容。信息学竞赛是信息技术学科内容的补充，竞赛以设计算法、编写程序为主要学习内容，重在培养学生分析问题、逻辑推理、抽象建模以及利用算法、程序解决问题的能力。信息学竞赛和信息技术学科既有区别也有联系。具体如下：

第一，教学内容的侧重点不同。信息技术学科是从学科的视角培养学生计算思维的意识和能力，着重培养学生在解决问题过程中将问题进分析、抽象、建模、设计算法的能力，强调的是学生具备利用计算机解决问题所需要的思维能力。信息学竞赛偏重于计算思维的算法设计和程序实现模块，强调学生不仅要具备利用计算机解决问题的思维能力，还要具备将算法转化为程序的能力，且所设计的程序可以在时间以及空间的限制下通过所有的测试数据。

第二，面向的教学对象不同。信息技术学科面向所有学生，计算思维是学生必须具备的核心素养之一，是面向所有学生开展的普适教育。信息学竞赛主要面向学有余力且对该竞赛感兴趣的部分学生。

第三，教学时空不同。信息技术是每个学生必须学习的内容之一，学科核心素养—计算思维的培养主要依靠课堂教学。信息学竞赛是一种课外活动，主要依靠课外时间学习相关的知识。

●信息学竞赛培养学生计算思维的策略

信息学竞赛的解题过程可以分为四步：分析问题、理解题意；梳理问题、建立数学模型；设计算法、时空复杂度分析；实现程序、调试程序。计算思维体现在以上各个方面，尤其在算法设计上，可以从以下三个方面提升学生计算思维的能力。

1.强化信息学和数学的融合

（1）强化数学知识的学习

信息学竞赛解题过程中常用的数学知识主要分布于高等数学、离散数学、概率论。高等数学常用对数函数、指数函数中的知识，如利用对数函数对算法的时间复杂度进行分析。离散数学知识在信息学竞赛中应用更为普遍，主要分布于数论、计数模块，如数论中的素数、丑数、最大公约数、最小公倍数，计数模块主要分布于排列组合、二项式定理、加法原理、减法原理、鸽巢原理等。

（2）强化数学方法的学习

数学方法、思想的学习对于信息学竞赛同等重要，数学归纳、递推是信息学竞赛中常用的方法，也是发现问题中隐藏规律的重要方法。如数学中的递推方法是理解递归程序的基础，递推是由已知推向未知的过程，是正向求解问题，递归是借助计算机函数调用的原理，由未知推向已知的过程，是逆向求解问题。

2.强化数据结构和算法知识学习

数据结构与算法是计算机学科的核心内容，是计算机解决问题过程中的必备知识。数据结构主要研究数据的组织、存储的方式，也就是数据运算过程中逻辑主旨结构和物理存储结构。任何一种算法都有对应的数据结构，算法本质上反映了对数据的操作，而数据又是通过某种数据结构进行存储。例如，二分查找算法是一种效率较高的查找元素的方法，其要求线性表必须采用顺序存储结构，表中元素按关键字有序排列，数组数据结构恰好满足二分查找的所有要求。信息学竞赛常用的数据结构有数组、链表、堆栈、队列、哈希表、堆、树、图表、线段树等，常用算法有排序、查找、分治、贪心、递归、动态规划、深度优先搜索、宽度优先搜索、拓扑排序。学生需要知道每种数据结构和算法的作用、特征，在解决问题的过程中根据实际需要选择合适的数据结构和算法。

3.深化原理认知并重视思维发展

信息学竞赛的知识既与数学有关，又有自己的特征。教师在教学过程中不仅要传授知识，更要注重知识的传递方式。教学过程围绕理解概念、认识原理、证明过程、应用练习、创新应用5个步骤展开，让学生知道每一个算法设计的理论依据，加深学生对经典算法的理解，同时，还要通过学练结合、巩固应用等环节，强化知识。

4.一题多解、多题一解

一题多解就是从不同的视角分析问题，从不同的层次理解问题，进而用不同的知识解决问题，加深学生对知识的理解。一题多解需要学生具有较强的知识整合能力，将已有的知识和方法灵活运用。通过一题多解可以有效培养学生的创造性思维、发散思维。多题一解就是看似不同的题目可以用同一种方法进行问题求解。信息学竞赛的题目是无限的，方法、思路是有限的。多题一解是对知识总结反思的过程，通过多题一解将问题的类型进行归纳总结。

信息学教学过程中通过“一题多解和多题一解”的教学策略可提升学生学习的效率，拓宽学生的解题思路，培养学生自主探究的学习意识和能力。

PCR产物用1%的琼脂糖凝胶电泳检测判断是否为阳性扩增。样品和Marker的上样量为4 μL。设定电压为150 V，电泳时间15 min。接通电极，PCR产物由阴极向阳极移动。电泳结束后紫外成像观察，结果见图1。

●计算思维导向下的信息学教学实践

信息学竞赛中解决问题的过程为分析问题、抽象建模、设计算法、编写程序和调试程序。下面以集合的划分习题为例，探究该问题的解决过程。

问题描述：

设S是一个具有n个元素的集合，S={a1,a2,……,an}，现将S划分成k个满足下列条件的子集合S1，S2，……，Sk，且满足：

①Si≠∅

②Si∩Sj=∅

③S1∪S2∪S3……∪Sk=S，则称S1，S2，……，Sk是集合S的一个划分。求满足条件的划分数。

1.分析问题

样例在信息学解题过程中具有重要的作用，信息学问题的描述一般比较抽象，样例是将抽象描述具体化的过程。从小样例出发，分析问题，发现样例中隐藏的一般规律是解决信息学竞赛习题常用的方法。设集合S有4个元素分别为1，2，3，4，划分为3个子集合的个数。也就是集合S={1，2，3，4}，k＝3，不难得出S有6种不同的划分方案。具体方案为：

{1，2}∪{3}∪{4}，{1，3}∪{2}∪{4}，{1，4}∪{2}∪{3}，

{2，3}∪{1}∪{4}，{2，4}∪{1}∪{3}，{3，4}∪{1}∪{2}

当S的元素个数较少的时候，通过人工枚举可以发现S的子集合个数。当S较大时，显然无法直接枚举S的子集合的个数，需利用数学归纳的方法发现该问题的本质，建构模型，设计算法，充分利用计算机运算快速的特征达到利用计算机解决问题的目标。

2.抽象建模

集合的划分问题，可以转化为集合之间的映射问题，该问题满足第二类斯特林模型。假设原集合为A，元素个数为n，划分之后的集合为B，元素个数为m，集合B中的元素均被集合A中的元素所指向，求集合A到集合B的满射的个数。通过强化信息学和数学的融合促进计算思维的培养。

第二类斯特林数的递推式为：s(n，m)=s(n-1，m-1)＋m*s(n-1，m)，1≤m≤n。

3.设计算法

基于第二类斯特林数学模型，设计算法如下：

①A集合中的元素单独构成一个子集合{an}，那么剩下的n-1的元素构成m-1个子集合，即共有子集合个数f(n-1，m-1)。

②第n个元素和别的元素一起构成子集合，即剩下的n-1个元素构成m个子集合，共有子集合个数f(n-1，m)，然后再将第n个元素放到m个子集合中，则有m种选择，最终共有子集合个数m*f(n-1，m)。由离散数学的加法原理得知最终的子集合个数为f(n，m)=f(n-1，m-1)＋m*f(n-1，m)。其中，当n＜m时或者m=0时，显然没有答案。当m=1或者m=n时，显然只有一个答案。

划分之后的情况依然满足原问题的规律，仅仅是减少了问题的规模，并且找到了算法结束的条件，从而将该问题转化为计算机递归模型，当然也可以从递推的视角解决问题，一题多解。

4.编写程序、调试程序

下图为算法的核心模块。其中n表示原来集合的个数，m表示划分的子集合的个数。

●结语

本研究以具体实践为例，从强化信息学和数学的融合、强化数据结构和算法知识学习、深化原理认知并重视思维发展、一题多解等维度，探讨如何通过信息学竞赛培养学生的计算思维，提升学生核心素养。