将数学归纳法的思想引入算法与程序设计的教学中

余克非

《算法与程序设计》的课程标准强调了学生能从简单问题出发,设计算法解决问题,并能初步使用某种程序语言解决问题;强调的是实际问题的解决方法。

将数学归纳法的思想引入算法与程序设计的教学中可以结合数学和信息技术两门课程优势,使学生利用已有的知识和技能去设计正确的算法,达到培养信息素养的目的。同时,可以开辟新的教学方法,从有别于传统程序设计教学的角度,快速高效地在中学生中普及算法知识。

以下是数学归纳法教学思路与传统程序设计思路的对比。

数学归纳法是一种数学证明方法,典型地用于确定一个表达式在所有自然数范围内是成立的或者用于确定一个其他的形式在一个无穷序列是成立的。

用数学归纳法进行证明的步骤:

1.(归纳奠基)证明当取第一个值时命题成立;证明了第一步,就获得了递推的基础

2.(归纳递推)假设当前命题成立,证明后续命题也成立;证明了第二步,就获得了递推的依据,但没有第一步就失去了递推的基础。只有把第一步和第二步结合在一起,才能获得普遍性的结论;

3.下结论:从第一个值开始的所有后续命题都成立

数学归纳法的第二种形式:第二数学归纳法原理是设有一个与自然数n有关的命题,如果:

(1)当n=1回时,命题成立;

(2)假设当n≤k时命题成立,则当n=k+1时,命题也成立。

从上可以看出数学归纳法有着很强的递推关系,而计算机的很多算法都具备递推关系。由此,我们可以考虑,在中学NOIP的教学过程中,可以利用数学归纳法来进行教学。

一、用于递归的教学

程序调用自身的编程技巧称为递归。这种编程技巧可以解决很多算法问题。它也是算法的核心思想和描述方法。

一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

对比数学归纳法,我们可以这样理解:递归的边界条件即为数学归纳法的第一步,也就是当取第一个值时命题成立。递归的过程就是归纳递推的方法。即假设当前命题成立,证明后续命题也成立。

例如:阶乘计算

递归的思考方式:

1.边界条件n=1时:n!=1。

2.递归过程n!=n*(n-1)!

数学归纳法的思考方式:

1.n=1时,1!=1成立

2.假设(n-1)!可以求出,则n!=

n*(n-1)!必定可以求出。

我们可以看出,递归的思考方式和数学归纳法是有一定相似之处的。

使用数学归纳法,除了可以引入解题的方法之外,还可以同时在数学上证明该思路是正确的。可以加深初学者对递归的认识并降低难度。

又例如汉诺塔问题的思考:

递归的思考方式:

1.边界条件

只有一个盘子时,盘子从A柱移到C柱

2.递归过程

n-1个盘子从A柱移到B柱,剩下的盘子从A柱移到C柱,n-1个盘子从B柱移到C柱

数学归纳法的思考方式:

1.n=1时盘子可移,盘子从A柱移到C柱

2.假设n-1个盘子可以从一个柱子移动到另一个柱子,寻找n个盘子从一个柱子移动到另一个柱子的方法。

在初学递归的同学中,汉诺塔问题是学习的难点和重点。我们需要从栈、函数的调用原理、题目的思考方法来讲述。从数学归纳法的思考方式来看,我们可以更好的加深学生对递归的理解。同时引入数学归纳法的思考方式可以更容易的证明解题的正确性。

二、用于分治的教学

一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这是分治算法的核心思想。

我们也可以看到:“最后子问题可以简单的直接求解”即为数学归纳法中命题n=1时的阶段,“问题的解的合并”即为数学归纳法中当n≤k时命题成立推n=k+1时命题成立的阶段。

例如:二分排序算法利用数学归纳法的讲解思路

1.n=20=1时,1个数据自然排序成功。

2.假设n=2k-1时,2组2k-1个数据分别有序,则n=2k时,可将两组分别有序的数据通过归并排序合并,使之有序。

可以看到,数学归纳法的讲解思路不同于普通的分治排序的思考方式。但这可以激发学生从多方面思考算法的求解思路。

(3)用于动态规划的教学

动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础。

动态规划思想中“将原问题分解为相似的子问题,在求解过程中通过子问题的解求出原问题的解”所具备的递推性质,决定了动态规划的问题思考中也可以使用数学归纳法的思想。其中的状态转移方程,便是第二数学归纳法中当n≤k时命题成立,推n=k+1时,命题成立的步骤。这里的性质决定了使用数学归纳法来思考,可以解决子结构和多阶段规划(无后效性)问题。

如题:

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

请编一个程序计算从顶至底的某处的一条路径,使该路径所经过的数字的总和最大。规定:

●每一步可沿直线向下或右斜线向下走;

●1<三角形行数≤100;

●三角形中的数字为整数0,1,…,99;

在动态规划的题目中,数学归纳法的归纳奠基思想起到了寻找边界条件的作用;其递推思想则起到了划分阶段,定决策并写出状态转移方程的作用。

从这里可以想到,当三角形只有一个结点时,问题自然解决。需要解决的命题是从已知1个结点的三角形结果推出具有3个结点的三角形的结果。从已知3个结点的三角形结果推出具有6个结点的三角形的结果,以此类推;即由n=k-1时命题成立推出n=k时命题成立。这样,我们就可以引入顺推和逆推的方法。最终得到该题的状态转移方程。

在整个的教学过程中,学生所学的知识始终由原有的知识进行迁移转化,利于学生的理解和接受。可以大大简化动态规划的教学难度,加快学生入门的速度。

从这里可以看到,凡是具备分层和递推形式的问题都可以使用数学归纳法的思想。所以在进行算法教学中,可以将数学归纳法思想作为主线,贯穿于递归、分治和动态规划的教学中。使学生从纵向上加深对算法的理解。学生在学习过程中,整合了数学和程序设计。

作者单位:深圳中学