使用局部到整体的思维方式求解数组最大值、次大值算法示例的教学初探

覃炜达

(河池学院数理学院 广西·河池 546300)

0 引言

常规的教学方法就是直接对程序进行分析，讲解算法的执行步骤和原理，但是一些算法示例所涉及的函数结构比较复杂，并且在程序执行时需要多次重复调用函数。对于这样的示例，使用常规的教学方法，学生较难理解。因此，为提高该门课程的教学质量，王彦群、刘少兵、范昊等[1-3]针对该门课程的相应知识点分享了有关的教学方法，例如启发式实验教学方法、互动式教学等。

朱坤燕、谢剑峰、谭安军等使用局部到整体的思维方式对初中数学课程、初中Scratch、高中生物课程进行探讨，旨在让复杂的问题简单化，学生更易理解。本文使用局部到整体的思维方式对《算法设计与分析》中的求解数组最大值、次大值算法示例进行教学初步探究，并在实践教学中取得了一定的效果。

1 问题描述

问题描述：对于给定的含有n元素的无序序列，求这个序列中最大和次大的两个不同的元素，具体参见文献[7]。

程序代码如下：

2 算法结构分析及使用局部到整体的思维方式分析算法示例

算法结构分析：

程序需要调用函数，且函数中有if…elseif…else语句，else语句有内嵌if…else，并且else语句还有两次重复调用递归函数。

由于算法结构复杂，主函数中数组元素个数较多，则函数重复调用次数就变多，导致学生不易理解算法的原理。如果数组元素减少，重复调用函数的次数就减少了，复杂的问题就变为简单了。为了让学生便于理解，教师在授课中可以把主函数中的数组元素个数取前面2个来分析算法原理（根据题意要找到数组中的最大值、次大值，所以数组的元素至少有2个）。随后，让元素个数逐个增加，按照局部到整体的思维方式再次分析算法，每次分析算法之后的当场调试程序得到运行结果验证分析过程是否正确，具体的教学过程如下：

第一次改进算法：在主函数设置数组改为a[]={5,2}其它语句不变。

算法的执行步骤如下：

1-1 solve(a,0,n-1,max1,max2)传递给函数void solve(int a[],intlow,inthigh,int&max1,int&max2)；传递之后，在 void solve(int a[],int low,int high,int&max1,int&max2)中，a[]={5,2}，low=0，high=1。

1-2执行if…else if…else中的else if语句，其中low==high-1为真，其中max1被赋值为5,max2被赋值为2。

1-3返回主函数，max1为5，max2为2，输出max1,max2的值。

第二次改进算法如下：在主函数设置数组为a[]={5,2,1}。

算法的执行过程如下：

2-1 solve(a,0,n-1,max1,max2)传递给函数void solve(int a[],intlow,inthigh,int&max1,int&max2)，传递之后，在 void solve(int a[],int low,int high,int&max1,int&max2)中，a[]={5,2,1}，low=0，high=2。

2-2执行if…else if…else语句中的else语句。2-2有四个小步骤，分别为 2-2.1、2-2.2、2-2.3、2-2.4。

2-2.1 mid被赋值为1。

2-2.2 通过调用函数solve(a,low,mid,lmax1,lmax2)，使lmax1被赋值为5,lmax2被赋值为2。

2-2.3 通过调用函数solve(a,mid+1,high,rmax1,rmax2)，使rmax1被赋值为1,rmax2被赋值为-INF。

2-2.4 执行if…else语句，使max1被赋值为5,max2被赋值为2。

2-3返回主函数，输出max1,max2的值。

第三次改进算法如下：主函数设置数组为a[]={5,2,1,4}。

算法的执行过程如下：

3-1 solve(a,0,n-1,max1,max2)传递给函数void solve(int a[],intlow,inthigh,int&max1,int&max2)，传递之后，在 void solve(int a[],int low,int high,int&max1,int&max2)中，a[]={5,2,1,4}，low=0，high=3。

3-2执行if…else if…else语句中的else语句。3-2有四个小步骤，分别为 3-2.1、3-2.2、3-2.3、3-2.4。

3-2.1 mid被赋值为1。

3-2.2 通过调用函数solve(a,low,mid,lmax1,lmax2)，使lmax1被赋值为5,lmax2被赋值为2。此步的数组有两个元素与第一次改进算法的执行步骤一样，这时，学生对此类问题已是第2次接触了，学生更容易理解执行过程，体现了由局部到整体的思维方式分析此类算法的一种优势。

3-2.3 通过调用函数solve(a,mid+1,high,rmax1,rmax2)，使rmax1被赋值为4,rmax2被赋值为1。此步的数组有两个元素与第一次改进算法的执行步骤一样，这时，学生对此类问题已是第3次接触了，学生更容易明白执行过程。

3-2.4 执行if…else语句，使max1被赋值为5,max2被赋值为4。

3-3返回主函数，输出max1,max2的值。

第四次改进算法：刚开始在主函数设置数组为 a[]={5,2,1,4,3}。

改进后的算法执行如下：

4-1 solve(a,0,n-1,max1,max2)传递给函数void solve(int a[],intlow,inthigh,int&max1,int&max2)，传递之后，在 void solve(int a[],int low,int high,int&max1,int&max2)中，a[]={5,2,1,4,3}，low=0，high=4。

4-2执行if…elseif…else语句中的else语句。4-2有三个小步骤，分别为 4-2.1、4-4.2、4-4.3。

4-2.1 mid被赋值为2。

4-2.2 通过调用函数solve(a,low,mid,lmax1,lmax2)，此步使lmax1被赋值为5,lmax2被赋值为2。此步的数组有三个元素，第二次改进算法数组元素个数也是三个，则此步执行步骤与第三次改进算法的执行步骤一样，这时，学生对此类问题的教学思路已是第2次接触了，此类问题更易让学生理解，这再次体现了由局部到整体的思维方式分析此类算法的一种优势。

4-2.3 通过调用函数solve(a,mid+1,high,rmax1,rmax2)，此步使rmax1被赋值为4,rmax2被赋值为3。此步的数组有两个元素与第一次改进算法的执行步骤一样，这时，学生对此类问题已是第4次接触了。

4-2.4 执行if…else语句，使max1被赋值为5,max2被赋值为4。

4-3返回主函数，输出max1,max2的值。

3总结

该示例难点在于函数结构复杂，数组元素较多，使用局部到整体的思维方式对算法示例进行分析，把复杂的问题简单化，加深学生对算法原理的理解，从而提高《算法设计与分析》的教学质量。