新解法在教学中的应用

李素萍

（山西工程技术学院信息系，阳泉045000）

1 问题

给出一个整形数组，要求找出元素之和最大的子数组。

为了更精确地描述问题，定义数组元素A[0]=0，并用A[j:k]表示A 中从下标j 到下标k 的元素构成的子数组（0<=j<=k<=n）。最大子数组的问题是，求使得sj，k达到最大的子序列A[j:k]（0<=j<=k<=n），sj，k表示该段元素的和，这个最大和称为A 的最大子数组和。为了简单起见，该问题只限于求出最大子数组和（算法表示），这里不需求最大子数组A[j:k]的下标j 和k。

2 已有解法

算法1：

MaxsubSlow（A）:

输入：n 个数的数组A，下标1 到n

输出：A 的最大子数组和

m←A[1]//目前找到的最大和

for j←1 to n do

for k←j to n do

s←0//将要计算的下一部分和

for i←j to k do

s←s+A[i]

if s>m then

m←s

return m

算法2：

MaxsubFaster（A）:

输入：n 个数的数组A，下标1 到n

输出：A 的最大子数组和

S0←0//初始前缀和

for i←1 to n do

si←si-1+A[i]

m←A[1]//目前找到的最大和

for j←1 to n do

for k←j to n do

s←sk-sj-1

if s>m then

m←s

return m

算法3：

MaxsubFastest（A）:

输入：n 个数的数组A，下标1 到n

输出：A 的最大子数组和

m←A[1]

S←0

for i←1 to n do

If（s<0）s←0;

s←s+A[i]

If s>m then

m←s

return m

3 新解法

算法4：

Maxsubnew（A）:

输入：n 个数的数组A，下标1 到n

输出：A 的最大子数组和

A[0]←0

m←A[1]

for j←1 to n do

for i←j to n do

s←sum（i，A）-sum（j-1，A）

if（m

return m

用递归法求和算法：

int sum（int i，int A[n]）

{if（i==0）return 0;

if（i==1）return A[1];

else

return sum（（i-1），A）+A[i];

}

4 学习三阶段

以上展示了从问题提出到各种解法的过程，下面还将对各种解法比较分析，目的是想证明学习三阶段循环往复无限发展。

学习第一阶段——知识认知阶段：上面问题提到要求求出元素之和最大的子数组，学过计算机语言的人都知道这个问题需要用到数组知识解决，涉及到数组自然会用到循环结构，这就是解决这个问题用到的主要知识点，也就是说在学习计算机语言时会讲到数据类型运算符表达式，顺序结构分支结构循环结构、数组、函数等这些基本内容，在学习这门课程的过程中如果不做太多练习或即使做了练习问题应用性不强又没有对同一问题提出各种解法，对各种解法进行比较，对各种解法进行性能分析的话，对知识的认识基本还停留在认知阶段，知道如何定义数组使用数组，以及使用数组的注意事项、技巧，等等，无法对知识认知深化，再认识，这样学习就很枯燥，这样的学习处于机械记忆被动接受阶段，于是，遇到困难就可能选择逃避甚至放弃。如果做练习时联系实际，提出一题多解，要求对各种解法比较并分析性能的话，学习的过程就有了趣味性，由被动变主动，由要我做变为我要做，从而使学习的效率大大提高，学习的效果也非常好，这就是学习过程从知识认知阶段转化为知识应用阶段的必然结果，对知识的认知由感性认识上升到了理性认识，由理解上升到了掌握进而能熟练应用。

学习第二阶段——知识应用阶段：如果我们告诉学生该问题可以用于数字化图像模式识别，在运行时间和存储空间等性能方面有具体要求的话，学生感觉知识有着落了，即使有困难也会尝试挑战自己解决问题的能力，于是就会找资料，复习旧知识，巩固新知识，优化解法，证明自己。学习过程从知识认知阶段转化到知识应用阶段，实质上是对知识的认识到知识的使用的转变，是从理论到实践的转变，是将知识转化为产品的过程，这个过程既要对知识进行整合，又要对知识进行应用，这样才能实现问题满足用户需求。例如算法1 使用了累加器设计模式，运行时间为O（n3），算法二引入了前缀和，即前t 个整数和st=a1+a2+...+an（t=1，2，...n.），就可以用该公式sj，k=sk-sj-1。在常数时间计算该任何子数组的和sj，k，从而使总运行时间变为O（n2），比算法一改进了一个线性因子。算法三从实际输入数据角度考虑，当数据序列中有负数的话，加入了s<0，则清零，从下一个数开始求和找出最大值，从而使总运行时间变为O（n）。可见学习阶段转换的必要性。既锻炼了学生解决问题的能力，又给社会带来了实际效益。“认识，实践，再认识，再实践”，学习过程形成良性循环，知识积累构成庞大体系，全方位发展，实现个人价值社会价值相统一。

这里，笔者再换一种思维方式求解，用递归法求和完成该问题，从而得到新的解法算法4。可以看到，这种解法在时间空间性能上并没有优化，但我提出用递归方法解决此问题并成功实现了这种思想，这就是求异思维。

求异思维是在思维中自觉地打破已有的思维定式、思维习惯或以往的思维成果，在事物各种巨大差异之间建立“中介”，突破经验思维束缚的思维方法。

求异思维重在开阔学生思路，启发学生联想，从各方面、各角度、各层次思考问题，并在各种结构的比较中，选择富有创造性的异乎寻常的新构思。具有广博的开拓创新性和迁延性，冲破陈旧的思维模式，把思维从狭窄、封闭、陈旧体系中解放出来，进而使学习过程上升为知识创新阶段。

学习第三阶段——知识创新阶段：知识是人们在改造世界的实践中所获得的认识和经验的总和。知识创新包括科学知识创新、技术知识特别是高技术创新和科技知识系统集成创新等。知识创新的目的是追求新发现、探索新规律、创立新学说、创造新方法、积累新知识。有的时候灵感真的是瞬间的，就像牛顿在苹果树下被那个灵感苹果所砸中，于是牛顿的大脑当中产生了这样的火花，为什么苹果会落地下呢，就这一碰撞，碰撞出了万有引力这个基础的新的知识点，如果牛顿当时没有立即记下这个灵感或者说没有将这个灵感付诸于实践，那么这个知识是否会被世人发现呢？勤于思考，勇于实践，敢于创新，善于开拓，由深到广推动科技发展构建和谐社会，为实现“人类命运共同体”这一全球价值观做出贡献。

学习三阶段缺一不可，构成相互依赖的统一体。知识感知阶段是其他阶段的基础，正如本文算法4 要求用递归方法实现，如果没有递归知识做基础，那这种解法就无从谈起，但如果学了一堆知识不去整合，不联系实际解决问题的话，即知识感知阶段不转换为知识应用阶段就无法证明知识的正确性，无法评价优劣，实践是认识的来源，也是检验真理的标准，经过实践检验发现纰漏提出新的解决问题的方法即知识创新，然后再应用于实践检验，再创新，循环往复推动社会发展。这种“实践、认识、再实践、再认识”的无限发展过程，在形式上是循环往复，在实质上是前进上升，是由低级阶段向高级阶段不断推移的永无止境的前进运动。只有这样，才有可能实现科学研究、人才培养、社会服务等功能。