算法與程序設(shè)計(jì)——選擇排序

1、精品文檔 算法與程序設(shè)計(jì)選擇排序 算法與程序設(shè)計(jì)選擇排序 一、學(xué)情分析 通過(guò)上學(xué)期算法與編程部分的學(xué)習(xí)，學(xué)生初步了解算法及其表示、比較熟悉流程圖設(shè)計(jì)； 本學(xué)期課程為算法與程序設(shè)計(jì)，對(duì)算法的理解更加深入，要求能通過(guò)VisualBasic實(shí)現(xiàn)簡(jiǎn)單算法； 在本課之前，學(xué)生應(yīng)了解了流程圖的應(yīng)用，熟悉在一組數(shù)中求極值算法，對(duì)于排序及冒泡排序，學(xué)生比較熟練。 對(duì)于本部分，學(xué)生可能會(huì)對(duì)選擇排序算法的原理理解較為困難，需要教師的引導(dǎo)學(xué)習(xí)。學(xué)生應(yīng)當(dāng)在學(xué)習(xí)過(guò)程中認(rèn)真聽(tīng)取教師對(duì)于算法的分析，在教師指導(dǎo)下能解釋該算法的流程圖，進(jìn)而實(shí)現(xiàn)程序。 二、教學(xué)目標(biāo) 知識(shí)性目標(biāo)： 了解排序的概念、能在現(xiàn)實(shí)生活中列舉出關(guān)于排序的實(shí)

2、例 能對(duì)照冒泡排序，解釋選擇排序的優(yōu)勢(shì)，指出選擇排序的策略，找出數(shù)字之間的邏輯聯(lián)系 有遷移應(yīng)用能力，能由此及彼，歸納排序中的數(shù)字規(guī)律，探索更有效率的排序算法 技能性目標(biāo)： 具有模仿水平，在教師指導(dǎo)下可以表達(dá)出選擇排序的思想，能對(duì)流程圖作出解釋 能獨(dú)立完成流程圖的繪制，對(duì)選擇排序的各個(gè)環(huán)節(jié)比較熟練，并能在VisualBasic環(huán)境中規(guī)范地編寫(xiě)程序 情感、態(tài)度、價(jià)值觀(guān)目標(biāo)： 學(xué)生在學(xué)習(xí)過(guò)程中，通過(guò)親身經(jīng)歷體驗(yàn)選擇排序的實(shí)現(xiàn)過(guò)程，獲得對(duì)此算法的感性認(rèn)識(shí) 利用信息技術(shù)手段，開(kāi)展交流合作，把自己對(duì)此算法的心得與他人交流，培養(yǎng)良好的信息素養(yǎng)，提升熱愛(ài)科學(xué)的理念 三、重點(diǎn)難點(diǎn) 重點(diǎn)：對(duì)選擇排序原理的理解，繪

3、制流程圖，數(shù)據(jù)交換，調(diào)試程序 難點(diǎn)：分析流程圖 四、教學(xué)策略與手段 把握重點(diǎn)，先導(dǎo)入問(wèn)題，復(fù)習(xí)排序定義，分析冒泡中數(shù)據(jù)交換次數(shù)多的問(wèn)題，指出冒泡排序法效率不高，從而引出數(shù)據(jù)交換次數(shù)較少的選擇排序算法 在教學(xué)過(guò)程中，可通過(guò)Flash演示材料，比較直觀(guān)地把抽象的問(wèn)題簡(jiǎn)單化，由“流程圖雛形繪制”-“逐步完善流程圖”-“程序?qū)崿F(xiàn)”-“調(diào)試”的過(guò)程，讓學(xué)生熟練此算法與程序?qū)崿F(xiàn)。 在教學(xué)中可靈活運(yùn)用小組合作、分組討論、小組間競(jìng)賽等手段進(jìn)行教學(xué)，通過(guò)發(fā)散性思維的培養(yǎng)，增強(qiáng)學(xué)生對(duì)知識(shí)的探索能力。 五、課前準(zhǔn)備 1學(xué)生的學(xué)習(xí)準(zhǔn)備：對(duì)流程圖的繪制方法、VB語(yǔ)法作鞏固，對(duì)選擇排序算法作預(yù)習(xí)；學(xué)生分組：4人一組 2教

4、師的教學(xué)準(zhǔn)備：準(zhǔn)備充分的演示材料、相關(guān)數(shù)據(jù)、相關(guān)軟件安裝。 3教學(xué)環(huán)境的設(shè)計(jì)與布置：計(jì)算機(jī)教室 六、教學(xué)過(guò)程 簡(jiǎn)要點(diǎn)撥排序的概念。 演示已經(jīng)學(xué)習(xí)過(guò)的冒泡排序Flash動(dòng)畫(huà)。 小組討論在冒泡排序算法中，我們知道冒泡排序是依次把數(shù)組中相鄰兩個(gè)數(shù)據(jù)進(jìn)行比較，通過(guò)交換數(shù)據(jù)，把較小的數(shù)據(jù)逐次向上移動(dòng)的算法。由于數(shù)據(jù)的移動(dòng)是逐次進(jìn)行的，數(shù)據(jù)交換的次數(shù)相當(dāng)多。大家想想它的實(shí)質(zhì)既然是將一堆數(shù)據(jù)中的最小數(shù)據(jù)移動(dòng)到某個(gè)位置，有沒(méi)有必要讓這個(gè)數(shù)字逐個(gè)移動(dòng)？比如，對(duì)于數(shù)組：4、8、3、9、6、5、11、10、2、9，如果要用冒泡法實(shí)現(xiàn)排序，第一遍冒泡其實(shí)是把這組數(shù)據(jù)中最小數(shù)“2”移動(dòng)到最前邊，第二遍冒泡把“3”逐次移

5、到第二個(gè)位置，其它類(lèi)推。它們的過(guò)程是逐次向前的，這樣做很多無(wú)謂的交換。為了達(dá)到移動(dòng)2到最前邊的目的我們可以怎么簡(jiǎn)化這個(gè)過(guò)程？ 學(xué)生直接把2最前面的數(shù)4交換，再把3與第二個(gè)位置的數(shù)8交換，其它類(lèi)推 教師這個(gè)思想就是今天我們要學(xué)習(xí)的選擇排序算法 小組討論選擇排序的實(shí)質(zhì)是每次把一堆數(shù)據(jù)中的最小數(shù)移到某個(gè)位置，那么這樣的操作在規(guī)模為N的數(shù)組中會(huì)做多少次？ N-1次，因?yàn)榻?jīng)過(guò)N-1次操作已經(jīng)確定了第1到N-1個(gè)位置的次序，第N個(gè)位置也自然可以確定。 小組討論找出數(shù)組中的最小數(shù)用什么策略? 復(fù)習(xí)鞏固可以借助一個(gè)自定義的Integer型變量in，用它記錄最小的一個(gè)數(shù)據(jù)的下標(biāo)。 首先，不管實(shí)際情況如何，我們先

6、假設(shè)數(shù)組中第1個(gè)元素為最小，于是有in=1，再把這個(gè)元素與從第2個(gè)元素開(kāi)始的所有元素作比較，一旦有比d(in)更小的元素存在，則修改in變量值為新的較小元素下標(biāo)。這樣，在d(in)經(jīng)過(guò)了從第2個(gè)元素到最后一個(gè)元素的一一比較后，所得到in應(yīng)該就是第1到N個(gè)元素中的選舉出來(lái)的最小元素下標(biāo)了。 然后用類(lèi)似的方法，把第2到N個(gè)元素中最小數(shù)選舉出來(lái)；把第3到N個(gè)元素中最小數(shù)選舉出來(lái) I1:in1:j2 開(kāi)始 j d(j) inj y y N j=j+1 最后把每次選舉出來(lái)的結(jié)果依次輸出即可實(shí)現(xiàn)升序排列。 學(xué)生完成第1遍處理過(guò)程的流程圖片斷 依據(jù)流程圖寫(xiě)出代碼 DiinAsInteger DijAsInt

7、eger in=1 Forj=2ToN Ifd(j) Nextj 小組討論 在遍歷了一遍后如果發(fā)現(xiàn)第1-N個(gè)數(shù)中的最小數(shù)d(in)，根據(jù)選擇排序的思想，需要把它與第1個(gè)數(shù)字進(jìn)行交換。如何進(jìn)行？ 請(qǐng)同學(xué)發(fā)言打個(gè)比方，在廚房里有一瓶醬油、一瓶醋和一個(gè)空瓶，如何利用這個(gè)空瓶實(shí)現(xiàn)醬油與醋？ 可先把醬油倒到空瓶中，再把醋倒到原來(lái)裝醬油的瓶中，然后從原來(lái)的空瓶中把醬油倒到原來(lái)裝醋現(xiàn)在已經(jīng)空的瓶中，即可實(shí)現(xiàn)換位。 教師大家動(dòng)動(dòng)腦筋，用這種思想，試試把d(1)與d(in)換位，并寫(xiě)出相應(yīng)的代碼。 DiTepAsInteger Tep=d(I):d(I)=d(in):d(in)=Tep關(guān)鍵在于引入“空瓶”變量T

8、ep 思考是不是每遍歷一遍后必須做這樣的一次交換？ 不是必須的，只有當(dāng)確實(shí)發(fā)現(xiàn)有比d(1)小的數(shù)后才交換 教師那怎么知道有沒(méi)有發(fā)現(xiàn)比d(1)更小的數(shù)呢？ I1:in1:j2 開(kāi)始 j d(j) inj y N N in1? Tep=d(1) d(1)=d(in) d(in)=Tep y j=j+1 其實(shí)在遍歷之前我們已經(jīng)假設(shè)第1個(gè)元素最小，即in=1，所以在遍歷一遍后我們只需要驗(yàn)證一下in=1是否還成立。成立則表明沒(méi)有比第1個(gè)元素小的數(shù)，不成立則表明有比第1個(gè)元素小的數(shù)，且它的下標(biāo)為in，此時(shí)要交換d(1)與d(in)。 學(xué)生完善流程圖及代碼 Ifin1then Tep=d(1):d(1)=d

9、(in):d(in)=Tep EndIf 教師我們先前說(shuō)過(guò)，對(duì)于規(guī)模為N的數(shù)組，需要遍歷處理次數(shù)為N-1次，以上的流程就是這N-1次中需要重復(fù)做的事，對(duì)于重復(fù)處理的事，可以用什么結(jié)構(gòu)？ 循環(huán)，以上的比較、交換即為循環(huán)體 教師大家試著把這個(gè)循環(huán)結(jié)構(gòu)流程圖畫(huà)出來(lái) 學(xué)生完善流程圖及代碼 開(kāi)始 j d(j) inj y N 輸出排序結(jié)果 N inI? Tep=d(I) d(I)=d(in) d(in)=Tep y I I1 y N 結(jié)束 I=I+1 j=j+1 in=I:j=I+1 ForI=1ToN-1 in=I Forj=I+1ToN Ifd(j) Nextj IfinIThen Tep=d(I)

10、:d(I)=d(in):d(in)=Tep EndIf NextI For=1ToN Print(Str(d() Next 調(diào)試程序 擴(kuò)展提高 我們知道，冒泡排序的效率比較低，主要因?yàn)閿?shù)據(jù)交換的次數(shù)多，那我們?nèi)绾沃肋x擇排序中數(shù)據(jù)交換的次數(shù)？ 學(xué)生帶著問(wèn)題思考并實(shí)踐 可利用一個(gè)自定義Integer型變量，初值0，記錄數(shù)據(jù)交換次數(shù)，在程序交換數(shù)據(jù)部分令其自加1，程序結(jié)束時(shí)輸出結(jié)果。 完整的程序?yàn)?DiI,j,in,cishuAsInteger cishu=0 ForI=1ToN-1 in=I Forj=I+1ToN Ifd(j) Nextj IfinIThen Tep=d(I):d(I)=d(in):d(in)=Tep:cishu=cishu+1 EndIf Next