算法第25章復習

1、個人采集整理僅供參照學習算法的程序實現(xiàn)本章要點：列舉算法、分析算法、冒泡排序、選擇排序、次序查找和對分查找的基本思想，以及利用這些算法進行程序設計，解決實質問題。本章難點：冒泡排序、選擇排序和對分查找的算法及程序實現(xiàn)。注意點：使用列舉算法，要求列舉出全部可能的狀況，不可以遺漏，也不可以重復。此外使用列舉算法計算容量較大，需要重申程序優(yōu)化舉措，提升計算機的效率。對分查找算法效率高，但要求數(shù)組中的數(shù)據(jù)是有序的。列舉算法：就是按問題自己的性質，一一列舉該問題全部可能的解，并在逐個列舉的過程中，查驗每個可能解是不是問題的真實解，如是，就采用這個解，不然就扔掉它實例：自行車胎壞掉的時候，修車師傅檢查壞掉

2、的地點，就是一個列舉算法,他選定某一個地點為開端地點，而后按次序一塊塊的檢查過來，直到找到壞掉的地點，需要注意的問題是：找到一個壞掉的地點后，還要持續(xù)找嗎？為了安全起見，建議持續(xù)找由此，在使用列舉算法的時候的注意事項，即要把全部可能的狀況都找出來，不然有可能會遺漏答案。典型實例:水仙花數(shù)：假如一個三位數(shù)等于它的每個數(shù)字的立方和，則此數(shù)稱為“水仙花”數(shù)，如：153=13+53+33程序段以下：Fori=100To999a=i100b=i10Mod10c=iMod10Ifa3+b3+c3=iThenList1.AddItem(Str(i)sum=sum+1EndIfNexti其余參照實例：百錢買百

3、雞，孫子算經(jīng)，紙幣問題，包裝問題分析算法及程序實現(xiàn)分析算法的基本思想是用分析的方法找出表示問題的前提條件與所求結果之間關系的數(shù)學表達式，并經(jīng)過數(shù)學表達式的計算來實現(xiàn)問題的求解。例題1：求解一元二次方程1、剖析問題從我們往常解題的步驟來剖析（問題的前提條件abc與所求結果x的關系的數(shù)學表達式）bb24acx=2a2、將數(shù)學表達式轉為計算機語言形式dimx1,x2asdouble1個人采集整理僅供參照學習dima,b,cASDoubleifb*b-4*a*c=0thenx1=(-b+sqr(b*b-4*a*c)/(2*a)x2=(-b-sqr(b*b-4*a*c)/(2*a)text1.text=

4、“x1=“+str(x1)text2.text=“x2=“+str(x2)elseprint方“程無解”endif例題2：火車托運轉李，要依據(jù)行李的重量按以下標準收費：若不超出50千克，按每千克0.35元收費，若超出50千克，超出部分則按每千克0.5元收費。輸入托運轉李的重量，計算并輸出托運轉李的花費。下邊程序若用于實現(xiàn)上述目標，則劃線紅色加粗處的語句應改正為_subcommand1_click()dimxasdoublex=val(text1.text)ifx50thentext2.text=str(0.35*x)elsetext2.text=str(0.5*x)endifendsub答案：

5、劃線處的填空內容挨次改正為x=50和str(50*0.35+0.5*(x-50)其余參照實例：儲蓄問題，人口問題排序算法的剖析及實現(xiàn)-冒泡排序和選擇排序排序的意義:排序是為了將一組凌亂的數(shù)據(jù)變?yōu)橐唤M有序的數(shù)據(jù)。（遞加或遞減）冒泡排序:理解：冒泡排序是在一列數(shù)據(jù)中把較小的數(shù)據(jù)逐次向上推移的一種排序技術。數(shù)組:為了儲存一組數(shù)據(jù),我們需要用到數(shù)組變量比如dimd(1to1000)asinteger定義了一個數(shù)組變量d,下標從1到1000d(1)d(2)d(3)d(4)d(1000)27363218冒泡排序用數(shù)組來儲存一系列同種類的數(shù)據(jù),而后調整數(shù)組中的元素比如:dimd(1to4)asinteger

6、定義一個數(shù)組變量d2個人采集整理僅供參照學習(1)d(2)(3)d(4)d(1)(2)d(3)d(4)d(1)d(2)(3)d(4)以i表示次數(shù)2727273636j-11832j-118j3618j3232第1次冒泡排序時j從4開始到21818182727j-12736j-132j3232j3636第2次冒泡排序時j從4開始到31818272732j-13236j36第3次冒泡排序時j從4開始到4當ij-118j273632從1到3變化時第1次冒泡排序時j從4開始到2每次j從4到i+1時d(j)比d(j-1)小,則交換它們Forj=4to2step-1ifd(j)d(j-1)then交換d(

7、j)和d(j-1)的值第2次冒泡排序時j從4開始到3Forj=4to3step-1ifd(j)d(j-1)then交換d(j)和d(j-1)的值第3次冒泡排序時j從4開始到4Forj=4to4step-1ifd(j)d(j-1)then交換d(j)和d(j-1)的值3個人采集整理僅供參照學習程序代碼：Fori=1Ton-1Forj=nToi+1Step-1Ifd(j)i?結束YYd(j)d(j-1)?N交換d(j)與d(j-1)的數(shù)據(jù)生成隨機數(shù),顯示在list1j=j-1PrivateSubCommand2_Click()產(chǎn)生8個隨機數(shù)Randomize隨機數(shù)初始化List1.Clear原始數(shù)

8、據(jù)清空List2.Clear將排序后的列表數(shù)據(jù)清空Fori=1To8d(i)=Int(Rnd*1000)Rnd函數(shù)返回的隨機數(shù)介于0和1之間，可等于0，但不等于1List1.AddItemStr(d(i)將數(shù)據(jù)顯示到原始數(shù)據(jù)列表中NextEndSub冒泡排序算法4個人采集整理僅供參照學習PrivateSubCommand1_Click()對8個數(shù)進行冒泡法排序List2.Clear將排序后的列表數(shù)據(jù)清空Fori=1To7Forj=8Toi+1Step-1Ifd(j)d(j)thenmin=jNextjIfmin不等于1時，交換d(1)和d(min)第2遍選擇273632j=418Min=j18

9、3632275個人采集整理僅供參照學習d(1)181818d(2)36Min=23636d(3)32j=332Min=j32Min=jj=3d(4)272727j=4Min=21818Forj=3to43627ifd(min)d(j)thenmin=j3232NextjIfmin2then交換d(2)和d(min)Min=j2736j=4第3遍選擇d(1)18Min=3d(2)27Forj=4to4d(3)32Min=3ifd(min)d(j)thenmin=jNextjd(4)36j=4Ifmin3then交換d(3)和d(min)剖析用i來表示次數(shù)的變化第1遍選擇，j從2開始到4Min=1

10、Forj=2to4ifd(min)d(j)thenmin=jNextjIfmin1，交換d(1)和d(min)第2遍選擇，j從3開始到4第3遍選擇，j從4開始到4Min=2Min=3Forj=3to4Forj=4to4ifd(min)d(j)thenmin=jifd(min)d(j)thenmin=jNextjNextjIfmin2then交換d(2)和d(min)Ifmin3then交換d(3)和d(min)程序實現(xiàn)6個人采集整理僅供參照學習數(shù)組元素的個數(shù)Fori=1Tonum-1選擇第i個最小的數(shù)Min=iForj=i+1Tonum假如找到更小的，用min記著它的編號Ifd(Min)d(j

11、)ThenMin=jNextjIfMiniThen假如最小的數(shù)所在的地點不是i，則交換k=d(i)d(i)=d(Min)d(Min)=kEndIfNexti生成隨機數(shù),顯示在list1PrivateSubCommand2_Click()產(chǎn)生8個隨機數(shù)Randomize隨機數(shù)初始化List1.Clear原始數(shù)據(jù)清空List2.Clear將排序后的列表數(shù)據(jù)清空Fori=1To8d(i)=Int(Rnd*1000)Rnd函數(shù)返回的隨機數(shù)介于0和1之間，可等于0，但不等于1List1.AddItemStr(d(i)將數(shù)據(jù)顯示到原始數(shù)據(jù)列表中NextEndSub選擇法排序PrivateSubComman

12、d1_Click()對8個數(shù)進行選擇法排序List2.Clear將排序后的列表數(shù)據(jù)清空Fori=1To7選擇第i個最小的數(shù)Min=iForj=i+1To8假如找到更小的，用min記著它的編號Ifd(Min)d(j)ThenMin=jNextjIfMiniThen假如最小的數(shù)所在的地點不是i，則交換k=d(i)d(i)=d(Min)d(Min)=kEndIfNextiFori=1To8List2.AddItemStr(d(i)在列表2中顯示排序后的數(shù)據(jù)Nexti7個人采集整理僅供參照學習EndSub選擇排序和冒泡排序的比較以n個數(shù)據(jù)為例交換次數(shù)履行時間冒泡O(n2)長選擇O(n)短查找算法次序查

13、找和對分查找查找算法查找是一種查問數(shù)據(jù)的技術，其目標是能以比較少的步聚和較短的時間找到所需的對象次序查找的基本思想是從第一個數(shù)據(jù)開始，按數(shù)據(jù)的次序逐個將數(shù)據(jù)與給定的值進行比較。若某個數(shù)據(jù)和給定的值相等，則查找成功，找到所查數(shù)據(jù)的地點；反之，查找不可功。次序查找輸入查找的元素值key=32從數(shù)組d的第1個元素d(1)開始，挨次判斷各元素d(1)27i=1的值能否與查找鍵key的值相等。d(2)36i=2d(3)32i=3此時d(i)=key,數(shù)組中的第3個地點d(4)18d(1)27i=1假如輸入查找的元素值key=22d(2)36i=2d(3)32i=3d(4)18i=4i=5此時i等于5,超

14、出數(shù)組中元素個數(shù),找不到8個人采集整理僅供參照學習次序查找的流程圖開始i1Nid(m)查找范圍應當變?yōu)閐(9)d(16)16數(shù)組d():Key=52我們用變量I和J記錄所要查找范圍的開端和停止地點98下標101517182227354548J=16元素第2次比較：Keyd(m)查找范圍應當變?yōu)閐(9)d(11)I=952656772859798M=fix(i+j)/2)=12J=1610個人采集整理僅供參照學習下標110元素215Key=52317418522627第3次比較：Key=d(m)735找到了845948I=91052M=fix(i+j)/2)=101165J=1112671372148515971698代碼剖析command4的click過程Key=Val(Text2.Text)i=1j=numDoWhilei=jm=(i+j)2Ifd(M)=KeyThenLabel6.Caption=在數(shù)組的+Str(M)+地點中Ex