论文部分内容阅读
全国青少年信息学奥林匹克竞赛（简称信息学竞赛）是培养高质量人才的重要途径，但目前绝大多数教师在带领学生准备参赛的过程中只关注知识、解题方法技巧的传授，忽视了学生思维及探究能力的培养与拓展。因此，本研究以数论函数中莫比乌斯反演问题的教学实施为例，探讨如何在信息学课程中通过引导学生分析问题、发现问题、猜想假设、探究验证、归纳运用，进而改进算法和程序以解决问题这一教学模式，开展科学探究教育，深化学生计算思维等科学思维，同时形成科学稳定的知识逻辑结构。
本次专题课的学生为高一年级的信息学竞赛生，他们从小学五年级开始学习信息学，对编写程序解决具体问题表现出浓厚的兴趣，具有相当强的逻辑推理思维能力，能够摆脱具体事物的限制，运用概念，提出假设，并检验假设来进行抽象逻辑思维。主要教学目标为：在科学探究的过程中发现并证明莫比乌斯反演定理，进而基于实际问题需求对莫比乌斯反演进行灵活应用，最终确定解题步骤，并独立编写程序以解决问题，深化科学思维。
● 呈现题目，引导学生分析发现问题
课前呈现题目的描述、输入输出格式要求、输入输出样例及数据范围如下。
数据范围：
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
本次专题课的学生为高一年级的信息学竞赛生，他们从小学五年级开始学习信息学，对编写程序解决具体问题表现出浓厚的兴趣，具有相当强的逻辑推理思维能力，能够摆脱具体事物的限制，运用概念，提出假设，并检验假设来进行抽象逻辑思维。主要教学目标为：在科学探究的过程中发现并证明莫比乌斯反演定理，进而基于实际问题需求对莫比乌斯反演进行灵活应用，最终确定解题步骤，并独立编写程序以解决问题，深化科学思维。
● 呈现题目，引导学生分析发现问题
课前呈现题目的描述、输入输出格式要求、输入输出样例及数据范围如下。
数据范围：
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