新解法在教學中的應用

李素萍

（山西工程技術學院信息系，陽泉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 要求用遞歸方法實現，如果沒有遞歸知識做基礎，那這種解法就無從談起，但如果學了一堆知識不去整合，不聯系實際解決問題的話，即知識感知階段不轉換為知識應用階段就無法證明知識的正確性，無法評價優劣，實踐是認識的來源，也是檢驗真理的標準，經過實踐檢驗發現紕漏提出新的解決問題的方法即知識創新，然后再應用于實踐檢驗，再創新，循環往復推動社會發展。這種“實踐、認識、再實踐、再認識”的無限發展過程，在形式上是循環往復，在實質上是前進上升，是由低級階段向高級階段不斷推移的永無止境的前進運動。只有這樣，才有可能實現科學研究、人才培養、社會服務等功能。