VB課程-常用算法課件

1、（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 一、計數(shù)、求和、求階乘等簡單算法此類問題都要使用循環(huán)，要注意根據(jù)問題確定循環(huán)變量的初值、終值或結(jié)束條件，更要注意用來表示計數(shù)、和、階乘的變量的初值。nnnnsn并求出當(dāng)時的精度為：計算：,00001. 0) 1(!1.3! 32221222（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 二、用輾轉(zhuǎn)相除法求兩自然數(shù)m，n的最大公約數(shù)和最小公倍數(shù)。分析：(1)對于已知兩數(shù)m，n，使得mn；(2) m除以n得余數(shù)r；(3)若r=0，則n為最大公約數(shù)結(jié)束；否則執(zhí)行(4)；(4)m n，n r，再重復(fù)執(zhí)行(2)。 設(shè)輸入設(shè)輸入m

2、=28,n=20m=28,n=20 循環(huán)循環(huán) m n r賦好初值時：賦好初值時：28 20 8第一次結(jié)束：第一次結(jié)束：20 8 4第二次結(jié)束：第二次結(jié)束： 8 4 0 If m n Then t = m: m = n: n = t r=m mod n Do While (r 0) m=n n=r r= m mod n Loop Print 最大公約數(shù)最大公約數(shù)=, n（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 三、判斷素數(shù)n基本思想： 把m作為被除數(shù)，將2Int(Sqr(m)作為除數(shù)，如果都除不盡，m就是素數(shù)，否則就不是?？捎靡韵鲁绦蚨螌崿F(xiàn)nm =val( InputBox(

3、請輸入一個數(shù)請輸入一個數(shù))For i=2 To int(sqr(m) If m Mod i = 0 Then Exit ForNext iIf i int(sqr(m) Then Print 該數(shù)是素數(shù)該數(shù)是素數(shù)Else Print 該數(shù)不是素數(shù)該數(shù)不是素數(shù)End If？ 如何將其寫成如何將其寫成一函數(shù)。若為素一函數(shù)。若為素數(shù)返回數(shù)返回TrueTrue，不，不是返回是返回FalseFalse。（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 例：例：驗證哥德巴赫猜想（任意一個大于等于驗證哥德巴赫猜想（任意一個大于等于6的偶數(shù)都的偶數(shù)都可以分解為兩個素數(shù)之和）可以分解為兩個素數(shù)之和）

4、 基本思想：基本思想：N N為大于等于為大于等于6 6的任一偶數(shù)，可分解為的任一偶數(shù)，可分解為n1n1和和n2n2兩個數(shù)，分別檢查兩個數(shù)，分別檢查n1n1和和n2n2是否為素數(shù)，如都是，則是否為素數(shù)，如都是，則為一組解。如為一組解。如n1n1不是素數(shù)，就不必再檢查不是素數(shù)，就不必再檢查n2n2是否素數(shù)。是否素數(shù)。先從先從n1=3n1=3開始，檢驗開始，檢驗n1n1和和n2n2（n2=N-n1n2=N-n1）是否素數(shù)。然）是否素數(shù)。然后使后使n1=n1+2,n1=n1+2,再檢驗再檢驗n1n1、n2n2是否素數(shù)，是否素數(shù)，直到直到n1=N/2n1=N/2為止為止。Private Function

5、 Prime( m as Integer) As Boolean Dim i% Prime=True For i=2 To int(sqr(m) If m Mod i = 0 Then Prime=False: Exit For Next iEnd Function（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 驗證哥德巴驗證哥德巴赫猜想赫猜想 Dim n%,n1%,n2% n=Val(InputBox(輸入大于輸入大于6的正整數(shù)的正整數(shù)) For n1=3 to n2 step 2 n2=n-n1 If prime(n1) Then If prime(n2) then Prin

6、t n & = & n1 & + & n2 Exit For End if End ifNext n1Private Function Prime( m%) As Boolean Dim i% Prime=True For i=2 To int(sqr(m) If m Mod i = 0 Then Prime=False: Exit For End if Next iEnd Function（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 四、數(shù)組排序 對已知存放在數(shù)組中的n個數(shù)。(1)選擇法排序算法思想： 1）對有n個數(shù)的序列（存放在數(shù)組a(n)中

7、），從中選出最小（升序）或最大（降序）的數(shù)，與第1個數(shù)交換位置；2）除第1 個數(shù)外，其余n-1個數(shù)中選最小或最大的數(shù)，與第2個數(shù)交換位置；3）依次類推，選擇了n-1次后，這個數(shù)列已按升序排列。原始數(shù)據(jù)：8 6 9 3 2 7第一輪后：2 6 9 3 8 7第二輪后：2 3 9 6 8 7第三輪后：2 3 6 9 8 7第四輪后：2 3 6 7 8 9第五輪后：2 3 6 7 8 9（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 選擇法排序（升序）的VB程序For i = 1 To n - 1For i = 1 To n - 1 imin = i imin = i For j =

8、i + 1 To n For j = i + 1 To n If a(imin) a(j) Then imin = j If a(imin) a(j) Then imin = j Next j Next j temp = a(i) temp = a(i) a(i) = a(imin) a(i) = a(imin) a(imin) = temp a(imin) = tempNext iNext i（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC （2）冒泡法排序（遞增）冒泡法排序（遞增） 算法思想：(將相鄰兩個數(shù)比較，小的調(diào)到前頭)1）有n個數(shù)（存放在數(shù)組a(n)中），第一趟將每相鄰

9、兩個數(shù)比較，小的調(diào)到前頭，經(jīng)n-1次兩兩相鄰比較后，最大的數(shù)已“沉底”，放在最后一個位置，小數(shù)上升“浮起”；2）第二趟對余下的n-1個數(shù)（最大的數(shù)已“沉底”）按上法比較，經(jīng)n-2次兩兩相鄰比較后得次大的數(shù)； 3）依次類推，n個數(shù)共進(jìn)行n-1趟比較，在第j趟中要進(jìn)行n-j次兩兩比較。8693268932689326839268329 683296382963289 （一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 冒泡法排序（升序）的VB程序：For i = 1 To n - 1For i = 1 To n - 1 For j = 1 To n-i For j = 1 To n-i

10、If a(j) a(j+1) Then If a(j) a(j+1) Then temp=a(j) temp=a(j) a(j)=a(j+1) a(j)=a(j+1) a(j+1)=temp a(j+1)=temp End if End if Next j Next jNext iNext i？ 編寫一個數(shù)組編寫一個數(shù)組排序的子過程排序的子過程（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 例：刪除數(shù)組中相同的例：刪除數(shù)組中相同的元素元素Public Sub del(a() As Integer) i = LBound(a) Do While i UBound(a) j = i

11、+ 1 Do While j = UBound(a) If a(i) = a(j) Then n = UBound(a) For k = j + 1 To n a(k - 1) = a(k) Next k ReDim Preserve a(n - 1) Else j = j + 1 End If Loop i = i + 1 LoopEnd Sub1、a) While j=Ubound(a) b) While jUbound(a) c) Until jLbound(a)2、a) a(k)=a(k+1) b) a(k-1)=a(k) c) a(k)=a(k-1) d) a(k+1)=a(k)3、

12、a)ReDim Preserve a(n) b)ReDim a(n+1) c)ReDim Preserve a(n+1) d)ReDim Preserve a(n-1)4、a)i=i+1 b)i=i-1 c)j=j+1 d)j=j-1_（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 五、查 找1、順序查找法、順序查找法（在一列數(shù)中查找某數(shù)（在一列數(shù)中查找某數(shù)x） 算法思想：一列數(shù)放在數(shù)組a(1)-a(n)中，待查找的數(shù)放在x 中，把x與a數(shù)組中的元素從頭到尾一一進(jìn)行比較查找。Option Base 1Private Function Find( a( ) As Single,x!

13、) As Integer Dim n%,p% Find=0 n=Ubound( a )For p=1 to n If x=a( p) Then Find=p : exit forNext pEnd Function （一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 2、折半查找法（只能對有序數(shù)列進(jìn)行查找）算法思想：n個有序數(shù)存放在數(shù)組a(1) a(n)中，要查找的數(shù)為x。變量top,bot,mid 分別表示查找范圍的頂部、底部和中間，mid=(top+bot)2，若：（1）x=a(mid)，則已找到退出，否則進(jìn)行下面的判斷；（2）xa(mid)，x必定落在mid+1和bot的范圍之

14、內(nèi)， top=mid+1；（4）在確定了新的查找范圍后，重復(fù)進(jìn)行以上比較，直到找到或者bot=top。（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC find = False 判斷是否找到的邏輯變量判斷是否找到的邏輯變量 top = 1bot = n n為數(shù)組下標(biāo)的上界為數(shù)組下標(biāo)的上界Do While bot = top And Not find mid = (top + bot) / 2 If x = a(mid) Then find = True Print the position is ; mid ElseIf x a(p) and p a(row, Column) Th

15、en If a(i, j) a(row, Column) Then row = i row = i Column = j Column = j End If End If Next j Next jNext iNext iPrint Print 最大元素是最大元素是; a(row, Column); ; a(row, Column); Print “Print “，在第，在第 & row & & row & 行行, ; , ; Print Print 第第 & Column & & Column & 列列 （一）VB入門 授課教師

16、：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 4、矩陣轉(zhuǎn)置、矩陣轉(zhuǎn)置設(shè)有二維數(shù)組a(5,5)，要對它實現(xiàn)轉(zhuǎn)置，可用下面兩種方式：For i=1 to 4 For i=2 to 5For i=1 to 4 For i=2 to 5 For j=i+1 to 5 For j=i+1 to 5 For j=1 to i-1 For j=1 to i-1 t=a(i,j) t=a(i,j) t=a(i,j) t=a(i,j) a(i,j)= a(j,i) a(i,j)= a(j,i) a(i,j)= a(j,i) a(i,j)= a(j,i) a(j,i)=t a(j,i)=t a(j,i)=t a(j,i)

17、=t Next j Next j Next j Next j Next i Next i Next i Next ia(1,1) a(1,2) a(1,3) a(1,4) a(1,5)a(2,1) a(2,2) a(2,3) a(2,4) a(2,5)a(3,1) a(3,2) a(3,3) a(3,4) a(4,5)a(4,1) a(4,2) a(4,3) a(4,4) a(4,5)a(1,1) a(1,2) a(1,3) a(1,4) a(1,5)a(2,1) a(2,2) a(2,3) a(2,4) a(2,5)a(3,1) a(3,2) a(3,3) a(3,4) a(4,5)a(4,

18、1) a(4,2) a(4,3) a(4,4) a(4,5)（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 八、迭 代 法算法思想： 對于一個問題的求解x，可由給定的一個初值x0，得到一個新的值x1，這個新值x1比初值x0更接近要求的值x；再以新值作為初值，即：x1x0,重新按原來的方法求x1,重復(fù)這一過和直到|x1-x0|(某一給定的精度)。此時可將x1作為問題的解。例：計算的近似值（精度為0.00001），公式為：) 12() 12()2(.5343122222nnn)(21001xaxx例：用迭代法求平方根。 迭代公式為：（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VB

19、ASIC 九、數(shù)制轉(zhuǎn)換將一個十進(jìn)制整數(shù)m轉(zhuǎn)換成 r (216)進(jìn)制字符串。方法：將m不斷除 r 取余數(shù)，直到商為零，以反序得到結(jié)果。Private Function TrDec(idec%, ibase%) As String Dim strDecR$, iDecR%End Function strDecR = TrDec = strDecR DoLoop While idec 0 iDecR = idec Mod ibase strDecR = iDecR & strDecR idec = idec ibase If iDecR = 10 Then strDecR = Chr$(65

20、 + iDecR - 10) & strDecR Else End If？小數(shù)的轉(zhuǎn)換？小數(shù)的轉(zhuǎn)換（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 十、字符串的一般處理1.簡單加密和解密加密的思想將每個字母C加（或減）一序數(shù)K，即用它后的第K個字母代替，變換式公式： c=chr(Asc(c)+k)例如序數(shù)k為5，這時 “A”“F”， “a”“f”，“B”“G” 當(dāng)加序數(shù)后的字母超過“Z”或“z”則 c=Chr(Asc(c)+k -26)例如：You are good Dtz fwj ltti 解密為加密的逆過程將每個字母C減（或加）一序數(shù)K，即 c=chr(Asc(c)-k)

21、,例如序數(shù)k為5，這時 “Z”“U”， “z”“u”，“Y”“T” 當(dāng)加序數(shù)后的字母小于“A”或“a”則 c=Chr(Asc(c)-k +26)（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC Private Function Pwp(strI as string, k as integer) As String Dim i%, nL%, iA%, strp$, strT$ i = 1: strp = nL = Len(RTrim(strI) For I =1 to nL strT = Mid$(strI, i, 1) 取第取第i個字符個字符 If (strT = A And st

22、rT Asc(Z) Then iA = iA - 26 strp = strp + Chr$(iA) ElseIf (strT = a And strT Asc(z) Then iA = iA - 26 strp = strp + Chr$(iA) Else strp = strp + strT End If Next i pwp=strpEnd Function?用用select語句實現(xiàn)語句實現(xiàn)解密功能解密功能（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 2、統(tǒng)計文本單詞的個數(shù)算法思路： （1）從文本（字符串）的左邊開始，取出一個字符；設(shè)邏輯量WT表示是否準(zhǔn)備下一個新單詞的開

23、始，初值設(shè)為True （2）若所取字符不是“空格”，“逗號”，“分號”或“感嘆號”等單詞的分隔符，再判斷WT是否為True，若WT為True則表是新單詞的開始，讓單詞數(shù)Nw=Nw+1，讓W(xué)T=False; （3）若所取字符是“空格”，“逗號”，“分號”或“感嘆號”等單詞的分隔符， 則表示當(dāng)前單詞結(jié)束，準(zhǔn)備下一個單詞開始，讓W(xué)T=True; (4) 再依次取下一個字符，重得（2）(3)直到文本結(jié)束。（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC Nw = 0: Wt = TruenL = Len(RTrim(stri)For i = 1 To nL strT = Mid$(stri

24、, i, 1) Select Case strT Case , , ;, ! Wt = True Case Else If Wt Then Nw = Nw + 1 Wt = False End If End SelectNext iPrint 單詞數(shù)為：單詞數(shù)為：, NwNw= 0Yes, it is. WtTrueFalseTrueFalseTrueFalse1 2 3單詞數(shù)加一的條件：單詞數(shù)加一的條件：1 1、遇到非空格和標(biāo)、遇到非空格和標(biāo)點的字符點的字符2 2、WtWt為為TrueTrue True（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 如果單詞僅以空格作為分隔符：

25、方法： （1）查找空格，若找到第一個空格的位置n0，則單詞數(shù)加1（2）從原字符串中去除第一個單詞及余下字符串的首尾空格（3）重復(fù)（1）（2）直到n=0為止。Nw = 0strI = Trim(strI)If Len(strI)0 then nw=1Do Whlie n0LoopN=Instr(strI, ) nw=nw+1 strI = Trim(Mid$(strI, n+1) n=Instr(strI, )Print 單詞數(shù)為：單詞數(shù)為：, NwThis is a book5（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 十一、窮舉法窮舉法（又稱“枚舉法”）的基本思想是：一一列

26、舉各種可能的情況，并判斷哪一種可能是符合要求的解，這是一種“在沒有其它辦法的情況的方法”，是一種最“笨”的方法，然而對一些無法用解析法求解的問題往往能奏效，常常采用循環(huán)來處理窮舉問題。例： 將一張面值為100元的人民幣等值換成100張5元、1元和0.5元的零鈔，要求每種零鈔不少于1張，問有哪幾種組合?（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 十二 遞歸1.遞歸的概念： 用自身的結(jié)構(gòu)來描述自身就稱為“遞歸”。例對階乘的定義：2. 遞歸過程 過程在自身定義的內(nèi)部調(diào)用自己)!2() 1()!1()!1(!nnnnnn1) 1fac(*11)fac(nnnnn（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC 編fac(n)=n! 的遞歸函數(shù) Function fac(n As Integer) As Integer If n = 1 Then fac = 1 Else fac = n * fac(n - 1) End If End Function遞推回歸（一）VB入門 授課教師：葉夏 計算機(jī)應(yīng)用基礎(chǔ)及VBASIC n=3Function fac%(n%) If n = 1 Then fac = 1 Else fac = n * fac(n - 1) End IfEnd