第三章算法與程序?qū)崿F(xiàn)3課件-高中信息技術(shù)浙教版必修1

算法與程序設(shè)計(jì)——方衛(wèi)龍八、排序算法

排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素(或記錄)的任意序列，重新排列成一個(gè)關(guān)鍵字有序的序列。排序算法是高考選考的必考內(nèi)容，考試中主要以冒泡排序算法和選擇排序算法為樣本進(jìn)行改編。(1)冒泡排序（升序）Fori=1ton–1Forj=ntoi+1Step-1Ifa(j)<a(j-1)Thent=a(j)a(j)=a(j-1)a(j-1)=tEndifNextjNexti例如：數(shù)組元素a(1)到a(6)的值依次為“26、13、23、18、7、14”，執(zhí)行程序數(shù)組元素的變化：i=1i=2j=626132318714j=672613231418j=526132371814j=572613142318j=426137231814j=472613142318j=326713231814j=371326142318j=272613231814i=3i=4j=671326141823j=671314261823j=571326141823j=571314182623j=471314261823i=5j=671314182328

（一）常見變形代碼舉例aa(1)a(2)a(3)a(4)a(5)a(6)1.VB程序，已知n=6值698351Fori=1ton-1Forj=ntoi+1Step-1Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tEndifNextjNexti1234經(jīng)過____趟后數(shù)組就已經(jīng)有序4169 835136 985135 6981 35689

（一）常見變形代碼舉例八、排序算法aa(1)a(2)a(3)a(4)a(5)a(6)2.VB程序，已知n=6值658139Fori=1ton-1Forj=iton-iIfa(j)<a(j+1)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndifNextjNexti12345經(jīng)過____趟后數(shù)組就已經(jīng)有序56853918659318695318965319865311.有以下VB程序段ForI=1to3Forj=1to5Ifa(j)>a(j+1)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndifNextjList1.AdditemStr(a(i))Nextia(1)到a(6)的初始值依次為“865793”，經(jīng)過該程序“加工”后，列表框List1中顯示器的是（）A.876B.879C.653D.5672.有以下VB程序段Fori=1to2Forj=1to5–iIfa(j+1)<a(j)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndifNextjNextI數(shù)據(jù)“562378118”依次存放在數(shù)組a(1)到a(5)中，執(zhí)行下列VB程序員段后，數(shù)組a(1)至a(5)中的數(shù)組依次為（）A.8,11,23,56,78B.23,11,8,56,78C.11,8,23,56,78D.8,11,56,23,783.有以下VB程序段Fori=1to2Forj=1to5–iIfa(j)>a(j+1)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndifNextjNexti數(shù)組元素a(1)到a(5)值依次為“24,20,45,16,18”,經(jīng)過該程序段“加工”后，數(shù)組元素a(1)到a(5)的依次為（）A.1618202445B.2016182445C.1618242045D.45242018164.有以下VB程序段ForI=6to4step-1j=1DoWhilej<=i-1Ifa(j)>a(j+1)Then

t=a(j):a(j)=a(j+1):a(j+1)=tEndifj=j+1LoopNexti數(shù)組元素a(1)到a(6)的值依次為“26，13，23，18，7，14”，執(zhí)行該程序段后，數(shù)組元素a(1)到a(6)的值依次為（）A.26,13,23,18,7,14B.13,7,14,18,23,26C.7,13,14,18,23,26D.26,23,18,14,13,7八、排序算法之冒泡CBBB5.冒泡排序在某一遍加工過程中沒有數(shù)據(jù)交換時(shí)，說明數(shù)據(jù)已經(jīng)有序，優(yōu)化程序段如下I=1:flag=TrueDoWhilei<=4andflag=Trueflag=FalseForj=5toI+1Step-1Ifa(j)>a(j-1)Then

t=a(j):a(j)=a(j-1):a(j-1)=tflag=TrueEndifNextji=i+1Loop數(shù)組元素a(1)到a(5)的值依次為“48,36,24,97,77”,經(jīng)過該程序段“加工”后，變量i的值是（）1B.2C.3D.46.有以下VB程序段i=1DoWhilei<=4andflag(i)=FalseForj=5toi+1Step-1Ifa(j)<a(j–1)Thenk=a(j):a(j)=a(j-1):a(j-1)=kflag(i)=TrueEndifNextji=i+1Loop數(shù)組元素a(1)到a(5)的值依次為“27,5,25,36,78”,數(shù)組flag的初值均為False,經(jīng)過該程序段“加工”后，數(shù)組元素放flag(1)到flag(5)中值為True的個(gè)數(shù)是（）A.1B.2C.3D.47.下面程序是一個(gè)改進(jìn)過后冒泡排序：Dima(1to5)asintegera(1)=5:a(2)=10:a(3)=9:a(4)=3:a(5)=7n=5:p=0:swap=TrueDoWhileswap=Trueswap=FalseFori=1ton-1Ifa(i)>a(i+1)Then

t=a(j):a(j)=a(j+1):a(j+1)=tswap=TrueEndifNextIIfswap=TrueThenp=p+1LoopText1.Text=p該程序段執(zhí)行后，在文本框Text1中顯示的內(nèi)容為：（）A.1B.2C.3D.48.以下程序段對數(shù)組a中的6個(gè)數(shù)據(jù)a(1)到a(6)進(jìn)行加工。DimflagasBooleani=1:flag=TrueDoWhilei<=5andflag=Trueflag=FalseForj=6Toi+1Step-1Ifa(j)<a(j-1)Thenk=a(j):a(j)=a(j-1):a(j-1)=kflag=TrueEndifNextji=i+1Loop下列數(shù)組序列中，在加工過程中劃線處語句執(zhí)行次數(shù)最多的是()A.24,29,31,20,15,10

B.10,15,20,24,29,31C.29,10,31,15,20,24D.31,29,24,20,15,10八、排序算法之冒泡DBCD1.n個(gè)數(shù)據(jù)的冒泡升序排序需要經(jīng)過n-1遍的加工，每一遍加工自下而上比較相鄰兩個(gè)數(shù)據(jù)，把較小者交換到上面，在第i遍加工過程中需要進(jìn)行對數(shù)據(jù)的比較。在某些情況下，第遍加工過程中，在上面部分較小數(shù)據(jù)已經(jīng)有序情況下，不需要再進(jìn)行對數(shù)據(jù)的比較。如對“17，18，19，24，23，20”這6個(gè)數(shù)據(jù)排序中，第1遍排序結(jié)束數(shù)據(jù)為“17，18，19，20，24，23”，第2遍排序時(shí)不再需要對20及其前面4個(gè)數(shù)據(jù)進(jìn)行比較。以下程序?qū)崿F(xiàn)了冒泡排序的優(yōu)化，在劃線處填入合適代碼。Dimnasinteger,a(1to100)asintegerPrivateSubCommand1_Click()Dimiasinteger,jasinteger,startasinteger,tasintegeri=2DoWhilei<nstart=nForj=ntoiStep-1If_________________Thent=a(j):a(j)=a(j-1):a(j-1)=t_________________EndifNextji=start+1LoopFori=1tonList2.additem_________NextiEndSub八、排序算法之冒泡a(j)<a(j-1)start=jStr(a(i))2.小華在探究將兩段已按從小到大排序的數(shù)據(jù)連接后用冒泡排序思想再進(jìn)行從小到大排序的情況，編寫VB程序功能如下：在列表框List1中顯示排序前數(shù)據(jù)（存儲(chǔ)在數(shù)組c中）,單擊“排序”按鈕Command1后，在列表框List2中顯示排序后的數(shù)據(jù)。程序運(yùn)行界面如圖所示。實(shí)現(xiàn)上述功能的VB程序如下，在劃線處填入合適的代碼。Constn1=6‘第1段已排序數(shù)據(jù)長度為n1Constn2=5‘第2段已排序數(shù)據(jù)長度為n2Dimc(1ton1+n2)asinteger‘?dāng)?shù)組C長度為n1+n2，依次存儲(chǔ)第1、2段數(shù)據(jù)PrivateSubCommand1_Click()‘?dāng)?shù)組c依次存儲(chǔ)兩段已按從小到大排序的數(shù)據(jù)，并在列表框List1中顯示，代碼略。Fori=n1+1ton1+n2j=1Flag=TrueDoWhile_____________Ifc(j)<c(j-1)Thent=c(j):c(j)=c(j-1):c(j-1)=tElseFlag=FalseEndif________________LoopNextiFori=1to____________List2.additemc(i)NextiEndSub八、排序算法之冒泡j>1andFlagj=j-1n1+n23.小王設(shè)計(jì)一個(gè)計(jì)算比賽得分的VB程序，程序功能如下：依次在文本框Text1中輸入某選手的評委打分，按回車鍵后顯示在列表框List1中，點(diǎn)擊“統(tǒng)計(jì)”按鈕Command1,在標(biāo)簽Label3中輸出該選手的平均得分。平均得分的計(jì)算方法如下：若有n位評委為選手打分，則該選手的平均得分是從這n位評委打分中去掉一個(gè)最高分和一個(gè)最低分后的平均分。程序運(yùn)行界面如圖所示。加框處代碼有錯(cuò),請改正.

Dimd(1to20)assingle,nasinteger‘?dāng)?shù)組d存放評委（≤20人）打分?jǐn)?shù)據(jù)，n存放評委人數(shù)PrivateSubText1_KeyPress(KeyAsciiasinteger)‘在文本框Text1中輸入評委打分，并存入數(shù)組d，統(tǒng)計(jì)評委人數(shù)保存在變量中，代碼略EndSubPrivateSubComman1_Click()DimtempasSingle,sassingle,averassingle,iasinteger,jasintegers=0Fori=n-1To1Step-1Forj=1toiIfd(j)<d(j+1)Thentemp=d(j)d(j)=d(j+1)temp=d(j+1)EndifNextjIfi<>n-1Thens=d(i)Nextiaver=Int(s/(n-2)*100+0.5)/100Label3.Caption=Str(aver)EndSub八、排序算法之冒泡d(j+1)=temps+d(i+1)4.冒泡算法，當(dāng)數(shù)據(jù)已經(jīng)有序時(shí)就停止加工，為此編寫了一個(gè)VB程序，功能如下：運(yùn)行程序時(shí)，在列表框List1中顯示排序前數(shù)據(jù)，單擊“排序”按鈕Command1,在列表框List2中顯示按升序排序后的結(jié)果，在標(biāo)簽Label1中顯示排序加工趟數(shù)、在標(biāo)簽Label2中顯示數(shù)據(jù)變換次數(shù)。運(yùn)行效果如圖所示。實(shí)現(xiàn)上述功能的VB代碼如下，但加框處代碼有錯(cuò)，請改正。Constn=10Dima(1ton)asinteger‘排序前數(shù)據(jù)儲(chǔ)在數(shù)組a中，并在Label1中顯示，代碼略PrivateSubCommand1_Click()DimflagasBoolean,xasinteger,yasintegerx=0:y=0:flag=True:i=1DoWhilei<=n-1andflagflag=FalseForj=ntoi+1Step-1Ifa(j)<>a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tflag=Truex=1EndIfNextjy=y+1i=n–1LoopLabel1.Caption=“經(jīng)過”+Str(y)+“趟排序數(shù)據(jù)有序！”Label2.Caption=“數(shù)據(jù)總共交互”+Str(x)+“次！”Fori=1tonList2.additemStr(a(i))NextiEndSub八、排序算法之冒泡a(j)<a(j-1)x=x+1i=i+15.小劉在研究n個(gè)數(shù)的冒泡排序算法，發(fā)現(xiàn)可以從兩個(gè)方面行優(yōu)化：（1）在每遍冒泡過程中，若最后一次交的是last與last-1位置的，last位置之前的相鄰據(jù)均已有序。進(jìn)行下一遍冒泡，無序區(qū)域設(shè)置[last,n]，一遍排序可能使當(dāng)前無序區(qū)域縮小。（2）若在某一遍排序中沒有數(shù)據(jù)交換，說明待排序數(shù)據(jù)都已經(jīng)有序，冒泡排序程序可在此遍排序后結(jié)束。因此可以引入一個(gè)變量flag，記錄在每遍排序過程中是否發(fā)生了交換。小劉上述方法的冒泡優(yōu)化VB程序，功能如下：“生成數(shù)據(jù)”按Command1后，生成一組隨機(jī)的兩位整數(shù)存入數(shù)組a,并顯示在列表框Last1中。單擊“排序”按Command2后，a中的數(shù)據(jù)進(jìn)行降序排序,排序后的數(shù)據(jù)顯示在列表框Last2中排序過程中實(shí)際的冒泡遍數(shù)顯示在Label2。程序運(yùn)行界面如圖所示。(1)若優(yōu)化后的冒泡排序算法，數(shù)據(jù)28,15,10,8,12進(jìn)行降序排序，冒泡的遍數(shù)________.(2)在劃線填入合適的代碼。Dima(1to20)asintegerPrivateSubCommand1_Click()DimIasinteger,jasintegerList1.Clear:List2.ClearRandomizeFori=1to20______________Forj=1toi-1Ifa(i)=a(j)Theni=i-1:ExitForNextjNextIFori=1to20List1.additemStr(a(i))NextIEndSub八、排序算法之冒泡PrivateSubCommand2_Click()DimflagasBoolean,iasinteger,jasintegerDimtempasInteger,numasInteger,lastasIntegernum=0:last=1Flag=TrueDoWhileflag=True______________Forj=20tolast+1Step-1Ifa(j)>a(j-1)Thentemp=a(j):a(j)=a(j-1):a(j-1)=temp__________________flag=True‘有交換發(fā)生EndifNextjnum=num+1LoopForI=1to20List2.additemStr(a(i))NextILabel3.Caption=“本次排序的冒泡遍數(shù)為：”﹠Str(num)EndSub2a(i)=Int(Rnd*90)+10flag=Falselast=j6.小李編寫“合并區(qū)間”VB程序，功能如下:窗體加載時(shí)，獲取并存儲(chǔ)合并前的區(qū)間的數(shù)據(jù)，并顯示在列表框List1中。單擊“合并”按鈕后,

以區(qū)間左端點(diǎn)數(shù)值對區(qū)間進(jìn)行升序排序，然后相鄰區(qū)間的相交進(jìn)行合并，最后在列表框List2上顯示合并后的區(qū)間.程序運(yùn)行如圖所示：實(shí)現(xiàn)以上功能的VB程序如下，在劃線處填入合適的代碼。Dima(1to20)asinteger,b(1to20)asinteger‘?dāng)?shù)組a、b分別存儲(chǔ)區(qū)間的左端點(diǎn)、右端點(diǎn)數(shù)值PrivateSubForm_Load()‘將區(qū)間左端點(diǎn)存入a，區(qū)間右端點(diǎn)存入數(shù)組b，并在列表框List1顯示，代碼略EndSubPrivateSubCommand1_Click()Dimiasinteger,jasintegerDimcurLasinteger,curRasintegerFori=1ton-1Forj=1ton-IIf________________Thent=a(j):a(j)=a(j+1):a(j+1)=tt=b(j):b(j)=b(j+1):b(j+1)=tEndif____________NexticurL=a(1):curR=b(1)ForI=2tonIfa(i)<=curRThenIfcurR<b(i)Then_____________ElseList2.Additem“[”+Str(curL)+Str(curR)+“]”curL=a(i):curR=b(i)EndIfNextiList2.Additem“[”+Str(curL)+Str(curR)+“]”EndSub

八、排序算法之冒泡a(j)>a(j+1)NextjcurR=b(i)7.活動(dòng)課上，n個(gè)學(xué)生要兩兩組隊(duì)進(jìn)行拔河比賽，要求每個(gè)小組總體重不超過120KG，小林想知道最多可以組成多少個(gè)隊(duì)伍，并希望得到可以的組隊(duì)方案。于是設(shè)計(jì)了如下界面的程序，在文本框Text1中輸入n個(gè)學(xué)生的體重（數(shù)字之間用逗號(hào)隔開），單擊“隊(duì)伍”按鈕Command1后在標(biāo)簽Label1上顯示最多可能組隊(duì)數(shù)量，同時(shí)在列表框List1輸出方案。實(shí)現(xiàn)上述功能程序如下，在劃線處填入合適代碼.Dimnasinteg