信息学课程教学中如何开展科学探究教育

宋新波　陈智敏　黄细光

全国青少年信息学奥林匹克竞赛（简称信息学竞赛）是培养高质量人才的重要途径，但目前绝大多数教师在带领学生准备参赛的过程中只关注知识、解题方法技巧的传授，忽视了学生思维及探究能力的培养与拓展。因此，本研究以数论函数中莫比乌斯反演问题的教学实施为例，探讨如何在信息学课程中通过引导学生分析问题、发现问题、猜想假设、探究验证、归纳运用，进而改进算法和程序以解决问题这一教学模式，开展科学探究教育，深化学生计算思维等科学思维，同时形成科学稳定的知识逻辑结构。

本次专题课的学生为高一年级的信息学竞赛生，他们从小学五年级开始学习信息学，对编写程序解决具体问题表现出浓厚的兴趣，具有相当强的逻辑推理思维能力，能够摆脱具体事物的限制，运用概念，提出假设，并检验假设来进行抽象逻辑思维。主要教学目标为：在科学探究的过程中发现并证明莫比乌斯反演定理，进而基于实际问题需求对莫比乌斯反演进行灵活应用，最终确定解题步骤，并独立编写程序以解决问题，深化科学思维。

● 呈现题目，引导学生分析发现问题

课前呈现题目的描述、输入输出格式要求、输入输出样例及数据范围如下。

数据范围：

20%的数据满足：1≤T≤100，1≤n≤100，1≤m≤100，1≤k≤100

50%的数据满足：1≤T≤1000，1≤n≤1000，1≤m≤1000，1≤k≤1000

70%的数据满足：1≤T≤1000，1≤n≤10000，1≤m≤10000，1≤k≤10000

100%的数据满足：1≤T≤50000，1≤n≤50000，1≤m≤50000，1≤k≤50000

时间限制：1秒。

信息学课程中经常需要学生针对问题寻找数理规律，摆脱思维惯性，尝试各种组合，创新算法去求解。通过对问题的需求情况及已知条件进行详细分析，学生们很快都提出了方法1：枚举1到n中的每一个数x，再枚举1到m中的每一个数y，判断x和y的最大公约数是不是等于k。教师引导学生计算出该算法的时间复杂度为，其中lgn是用辗转相除法计算gcd（x，y）的时间复杂度，方法1可以在1秒时间限制内通过20%的数据。

而部分学生则对方法1进行了优化得出方法2：因为gcd（x，y）=k，则令x=k*x'，y=k*y'，推出1≤k*x'≤n，1≤k*y'≤m，从而得出1≤x'≤n/k，1≤y'≤m/k进而分别枚举x'和y'，判断x'和y'的最大公约数是否等于1。方法2的时间复杂度为。当k较大时有明显的优化效果，但当k=1时跟方法1在效率上没有任何改进。

怎么改进算法才能在时间限制范围内通过更多的数据？疑问是激发学生思维的源泉，设立数据范围这一障碍激发学生疑问，以疑问引发思考。由于学生的基础较好，教师给予了学生更多自主思考的时间，探讨如何解决原有算法超时的问题。最终，有少数学生能够在上述算法的基础上进一步优化算法，得到方法3：用f（x）表示1到m/k中与x互质的数的个数，则答案为x取1到n/k范围内的f（x）之和，利用容斥原理来计算f（x），时间复杂度为O（2g（x））（其中，g（x）为x质因子的个数），方法3能够通过50%的数据。

● 追问点拨，鼓励学生大胆猜想假设

如何进一步改进算法才能通过更多的数据？追问可以加快思维节奏，促成学习发生。聚焦于问题的解决，通过进一步的讨论与交流，个别学生想出方法4：用f（k）表示1≤x≤n，1≤y≤m且x与y的最大公约数为k的数对（x，y）个数，g（k）表示1≤x≤N，1≤y≤M且k|gcd（x，y）的数对（x，y）个数，其中“|”是整除符号，表示k整除gcd（x，y）。则有，又有g（k）=（n/k）*（m/k），這时，问题转为如何利用递推关系反过来计算出f（k）。

方法4相对方法3虽然效率上没有得到本质的提升，但却成功地把原问题推导出了莫比乌斯反演的原型一，即已知f（n）和g（n）是定义在正整数集合上的两个函数，并满足，且g（k）容易求解，要求利用g函数来计算f（k）的值。

现在要解决的问题是：输入n，输出f（1），f（2），...，f（n）用g函数表示的形式。教师鼓励学生学以致用，用编写程序来解决。首先，不难发现表示f（k）的g函数的参数都是k的倍数，这个可以用数学归纳法来证明。

证明过程具体如下：

（1）当k=n时，f（n）=g（n）成立。

（2）设当k>X时都成立，则观察，根据假设可知f（X*d）用g函数表示形式中的每一个g函数的参数都是X*d的倍数，那固然也是X的倍数。因此，f（X）的g函数表示形式中每一个g函数的参数也是X的倍数，即k=X也成立。

（3）综上，结论得证。

引导学生利用此性质编写程序。有学生不到二十分钟编写出以下程序（具体程序代码略）。

该程序可以测试较大数据，观察较大数据时的规律。教师引导学生以输入n=10为例，程序输出结果如下：

f（1）=g（1）-g（2）-g（3）-g（5）+g（6）-g（7）+g（10）

f（2）=g（2）-g（4）-g（6）-g（10）

f（3）=g（3）-g（6）-g（9）

f（4）=g（4）-g（8）

f（5）=g（5）-g（10）

f（6）=g（6）

f（7）=g（7）

f（8）=g（8）

f（9）=g（9）

f（10）=g（10）

教师引导学生测试较大数据并对输出结果进行观察、讨论及分析，鼓励学生大胆猜想f（k）的计算公式。这种猜想既调动了学生的学习兴趣，又培养了学生的逻辑思维、发散思维和创新思维。学生基本都能够发现，f（k）也是用k在不超过n范围内的所有倍数作为参数所对应的g的函数值进行计算，而且还发现有的g函数值的系数是1，有的为-1，有的则为0。学生初步作出猜想假设： 。

在学生提出的猜想不完整时，教师适时点拨学生，学生认识到“？”部分不是一个定值，而是一个函数，应该跟这里的k和d有关，对输出结果进行再次观察和对比分析，最终学生发现“？”部分与k没有关系，而是跟d有关的某个函数值。因此对结论进行二次猜想：，其中是跟d有关的函数。

通过测试大数据发现的值只有1、-1、0三种，接下来，教师引导学生编写程序把取这三种值对应的d列举出来观察规律。有学生在此前猜想程序的基础上稍作改动。

学生在教师的引导下发现了不少关于的规律，现仅归纳跟取值有关的规律：

（1）当d=1的时候，=1;

（2）当d=p1*p2*...pk，其中pi（1≤i≤k）为互异素数，则=（-1）k;

（3）其余情况则=0。

至此，猜想完成。即根据，猜想出，其中定义如上。

● 基于猜想，要求学生严谨探究验证

编程教育需要引导学生经历探求真理、发现奥秘的过程。通过分析、抽象、概括、猜想出f（k）的计算公式后，接下来需要进一步证明猜想的正确性，这才是完整的科学探究过程。

已知，证明成立。

教师引导学生注意等式右边的g（k*d）可以根据已知表示成f的形式，左右两边就都是f的形式，以此为突破口进行证明。

把已知的结论带入等式右边得：

上面式子的写法可以看出是以为主体的，如n=6，k=1时，上面的式子展开后如图1所示。

这样的写法很难跟左边f（k）去进行比较，需要进行更换f（）为主体，把上式等价转换为如图2所示的样子。

这样，就可以很方便地去比较左右两边对于f（）的系数是否相等。接下来教师引导学生对右式进行主体外移的等价变换处理。

令T=d*d1，則有，对于同样的T，观察f（k*T）的系数，只要满足d|T，都要累加进f（k*T）的系数中。有学生在教师的启发下，写出如图3所示的等价形式。

要证明就转化为证明：

当T=1时，，成立。

当T>1时，设，因为，另外，不需要考虑=0的情况，所以只需要考虑yi=0或1的情况。设d的质因子分解中含有r个质因子，T共有t个质因子，则这样的d有个，，含r个质因子的d的之和等于，r可以从0取到k，累积即可。所以T>1时，，利用二项式定理，则有。得证！

以上结论就是著名的莫比乌斯反演。整个过程各环节环环相扣，周密严谨，展现了完整的从大胆猜想到严谨证明的科学探究全过程。信息学竞赛的研究性学习课程阶段经常会出现花大量时间解决问题的情况，而让学生经历猜想验证的过程，不仅可以解决他们在学习中所产生的困惑，更有利于他们克服困难的意志以及对新知识点迎难而上，的科学品质的养成，使其树立学好信息学的信心。

● 归纳运用，引导学生编程解决问题

教师引导学生回到最初所提出的问题：，g（k）=，如何利用g（k）反过来计算出f（k）。基于莫比乌斯反演公式，学生就g（k）进行式子变形，得到。

针对这一结果，部分学生最终利用线性筛法在O（n）时间复杂度内初始化出所有的u（d），再从1到n/k范围内枚举d计算f（k），单次询问的时间复杂度为O（n/k），可以得到70分。少数学生则是进一步对（n/（k*d））*（m/（k*d））进行分块处理，这样单次询问的时间复杂度则降低为，能够得到100分。

上述过程中，每位学生最终设计出的算法都集中体现了各自特有的思维方式，但是有的学生采用的算法处理效率高、速度快。为了让每位学生都能够恰当地利用所学的算法进行程序设计，快速高效地解决实际问题，教师需要组织学生进行讨论和交流，让每位学生都发表自己的看法和建议，让每位学生在互相讨论和交流的过程中学习到别人的长处，发现自己的不足。最终，学生形成了清晰的问题解决思路，经过思考、改进算法和编写、调试程序，结合相互之间的交流与教师的个别指导，绝大多数学生都能够编写出完整的程序以解决课前所提出的问题。

“教”只是实现“学”的一种服务手段，学生的“学”才是教学的出发点和归宿。整个教学实施的过程，没有滔滔不绝的教师讲解，也没有气氛热烈的小组活动，更多的是教师严密理性的引导，以及对学生的思考和实践的激活，最终帮助学生深化科学思维，培养科学探究能力。