使用局部到整體的思維方式求解數(shù)組最大值、次大值算法示例的教學(xué)初探

覃煒達(dá)

(河池學(xué)院數(shù)理學(xué)院 廣西·河池 546300)

0 引言

常規(guī)的教學(xué)方法就是直接對(duì)程序進(jìn)行分析，講解算法的執(zhí)行步驟和原理，但是一些算法示例所涉及的函數(shù)結(jié)構(gòu)比較復(fù)雜，并且在程序執(zhí)行時(shí)需要多次重復(fù)調(diào)用函數(shù)。對(duì)于這樣的示例，使用常規(guī)的教學(xué)方法，學(xué)生較難理解。因此，為提高該門課程的教學(xué)質(zhì)量，王彥群、劉少兵、范昊等[1-3]針對(duì)該門課程的相應(yīng)知識(shí)點(diǎn)分享了有關(guān)的教學(xué)方法，例如啟發(fā)式實(shí)驗(yàn)教學(xué)方法、互動(dòng)式教學(xué)等。

朱坤燕、謝劍峰、譚安軍等使用局部到整體的思維方式對(duì)初中數(shù)學(xué)課程、初中Scratch、高中生物課程進(jìn)行探討，旨在讓復(fù)雜的問題簡單化，學(xué)生更易理解。本文使用局部到整體的思維方式對(duì)《算法設(shè)計(jì)與分析》中的求解數(shù)組最大值、次大值算法示例進(jìn)行教學(xué)初步探究，并在實(shí)踐教學(xué)中取得了一定的效果。

1 問題描述

問題描述：對(duì)于給定的含有n元素的無序序列，求這個(gè)序列中最大和次大的兩個(gè)不同的元素，具體參見文獻(xiàn)[7]。

程序代碼如下：

2 算法結(jié)構(gòu)分析及使用局部到整體的思維方式分析算法示例

算法結(jié)構(gòu)分析：

程序需要調(diào)用函數(shù)，且函數(shù)中有if…elseif…else語句，else語句有內(nèi)嵌if…else，并且else語句還有兩次重復(fù)調(diào)用遞歸函數(shù)。

由于算法結(jié)構(gòu)復(fù)雜，主函數(shù)中數(shù)組元素個(gè)數(shù)較多，則函數(shù)重復(fù)調(diào)用次數(shù)就變多，導(dǎo)致學(xué)生不易理解算法的原理。如果數(shù)組元素減少，重復(fù)調(diào)用函數(shù)的次數(shù)就減少了，復(fù)雜的問題就變?yōu)楹唵瘟恕榱俗寣W(xué)生便于理解，教師在授課中可以把主函數(shù)中的數(shù)組元素個(gè)數(shù)取前面2個(gè)來分析算法原理（根據(jù)題意要找到數(shù)組中的最大值、次大值，所以數(shù)組的元素至少有2個(gè)）。隨后，讓元素個(gè)數(shù)逐個(gè)增加，按照局部到整體的思維方式再次分析算法，每次分析算法之后的當(dāng)場調(diào)試程序得到運(yùn)行結(jié)果驗(yàn)證分析過程是否正確，具體的教學(xué)過程如下：

第一次改進(jìn)算法：在主函數(shù)設(shè)置數(shù)組改為a[]={5,2}其它語句不變。

算法的執(zhí)行步驟如下：

1-1 solve(a,0,n-1,max1,max2)傳遞給函數(shù)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執(zhí)行if…else if…else中的else if語句，其中l(wèi)ow==high-1為真，其中max1被賦值為5,max2被賦值為2。

1-3返回主函數(shù)，max1為5，max2為2，輸出max1,max2的值。

第二次改進(jìn)算法如下：在主函數(shù)設(shè)置數(shù)組為a[]={5,2,1}。

算法的執(zhí)行過程如下：

2-1 solve(a,0,n-1,max1,max2)傳遞給函數(shù)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執(zhí)行if…else if…else語句中的else語句。2-2有四個(gè)小步驟，分別為 2-2.1、2-2.2、2-2.3、2-2.4。

2-2.1 mid被賦值為1。

2-2.2 通過調(diào)用函數(shù)solve(a,low,mid,lmax1,lmax2)，使lmax1被賦值為5,lmax2被賦值為2。

2-2.3 通過調(diào)用函數(shù)solve(a,mid+1,high,rmax1,rmax2)，使rmax1被賦值為1,rmax2被賦值為-INF。

2-2.4 執(zhí)行if…else語句，使max1被賦值為5,max2被賦值為2。

2-3返回主函數(shù)，輸出max1,max2的值。

第三次改進(jìn)算法如下：主函數(shù)設(shè)置數(shù)組為a[]={5,2,1,4}。

算法的執(zhí)行過程如下：

3-1 solve(a,0,n-1,max1,max2)傳遞給函數(shù)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執(zhí)行if…else if…else語句中的else語句。3-2有四個(gè)小步驟，分別為 3-2.1、3-2.2、3-2.3、3-2.4。

3-2.1 mid被賦值為1。

3-2.2 通過調(diào)用函數(shù)solve(a,low,mid,lmax1,lmax2)，使lmax1被賦值為5,lmax2被賦值為2。此步的數(shù)組有兩個(gè)元素與第一次改進(jìn)算法的執(zhí)行步驟一樣，這時(shí)，學(xué)生對(duì)此類問題已是第2次接觸了，學(xué)生更容易理解執(zhí)行過程，體現(xiàn)了由局部到整體的思維方式分析此類算法的一種優(yōu)勢(shì)。

3-2.3 通過調(diào)用函數(shù)solve(a,mid+1,high,rmax1,rmax2)，使rmax1被賦值為4,rmax2被賦值為1。此步的數(shù)組有兩個(gè)元素與第一次改進(jìn)算法的執(zhí)行步驟一樣，這時(shí)，學(xué)生對(duì)此類問題已是第3次接觸了，學(xué)生更容易明白執(zhí)行過程。

3-2.4 執(zhí)行if…else語句，使max1被賦值為5,max2被賦值為4。

3-3返回主函數(shù)，輸出max1,max2的值。

第四次改進(jìn)算法：剛開始在主函數(shù)設(shè)置數(shù)組為 a[]={5,2,1,4,3}。

改進(jìn)后的算法執(zhí)行如下：

4-1 solve(a,0,n-1,max1,max2)傳遞給函數(shù)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執(zhí)行if…elseif…else語句中的else語句。4-2有三個(gè)小步驟，分別為 4-2.1、4-4.2、4-4.3。

4-2.1 mid被賦值為2。

4-2.2 通過調(diào)用函數(shù)solve(a,low,mid,lmax1,lmax2)，此步使lmax1被賦值為5,lmax2被賦值為2。此步的數(shù)組有三個(gè)元素，第二次改進(jìn)算法數(shù)組元素個(gè)數(shù)也是三個(gè)，則此步執(zhí)行步驟與第三次改進(jìn)算法的執(zhí)行步驟一樣，這時(shí)，學(xué)生對(duì)此類問題的教學(xué)思路已是第2次接觸了，此類問題更易讓學(xué)生理解，這再次體現(xiàn)了由局部到整體的思維方式分析此類算法的一種優(yōu)勢(shì)。

4-2.3 通過調(diào)用函數(shù)solve(a,mid+1,high,rmax1,rmax2)，此步使rmax1被賦值為4,rmax2被賦值為3。此步的數(shù)組有兩個(gè)元素與第一次改進(jìn)算法的執(zhí)行步驟一樣，這時(shí)，學(xué)生對(duì)此類問題已是第4次接觸了。

4-2.4 執(zhí)行if…else語句，使max1被賦值為5,max2被賦值為4。

4-3返回主函數(shù)，輸出max1,max2的值。

3總結(jié)

該示例難點(diǎn)在于函數(shù)結(jié)構(gòu)復(fù)雜，數(shù)組元素較多，使用局部到整體的思維方式對(duì)算法示例進(jìn)行分析，把復(fù)雜的問題簡單化，加深學(xué)生對(duì)算法原理的理解，從而提高《算法設(shè)計(jì)與分析》的教學(xué)質(zhì)量。