VB课程-常用算法课件

1、（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC 一、计数、求和、求阶乘等简单算法此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。nnnnsn并求出当时的精度为：计算：,00001. 0) 1(!1.3! 32221222（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC 二、用辗转相除法求两自然数m，n的最大公约数和最小公倍数。分析：(1)对于已知两数m，n，使得mn；(2) m除以n得余数r；(3)若r=0，则n为最大公约数结束；否则执行(4)；(4)m n，n r，再重复执行(2)。 设输入设输入m

2、=28,n=20m=28,n=20 循环循环 m n r赋好初值时：赋好初值时：28 20 8第一次结束：第一次结束：20 8 4第二次结束：第二次结束： 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 最大公约数最大公约数=, n（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC 三、判断素数n基本思想： 把m作为被除数，将2Int(Sqr(m)作为除数，如果都除不尽，m就是素数，否则就不是。可用以下程序段实现nm =val( InputBox(

3、请输入一个数请输入一个数)For i=2 To int(sqr(m) If m Mod i = 0 Then Exit ForNext iIf i int(sqr(m) Then Print 该数是素数该数是素数Else Print 该数不是素数该数不是素数End If？ 如何将其写成如何将其写成一函数。若为素一函数。若为素数返回数返回TrueTrue，不，不是返回是返回FalseFalse。（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC 例：例：验证哥德巴赫猜想（任意一个大于等于验证哥德巴赫猜想（任意一个大于等于6的偶数都的偶数都可以分解为两个素数之和）可以分解为两个素数之和）

4、 基本思想：基本思想：N N为大于等于为大于等于6 6的任一偶数，可分解为的任一偶数，可分解为n1n1和和n2n2两个数，分别检查两个数，分别检查n1n1和和n2n2是否为素数，如都是，则是否为素数，如都是，则为一组解。如为一组解。如n1n1不是素数，就不必再检查不是素数，就不必再检查n2n2是否素数。是否素数。先从先从n1=3n1=3开始，检验开始，检验n1n1和和n2n2（n2=N-n1n2=N-n1）是否素数。然）是否素数。然后使后使n1=n1+2,n1=n1+2,再检验再检验n1n1、n2n2是否素数，是否素数，直到直到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入门 授课教师：叶夏 计算机应用基础及VBASIC 验证哥德巴验证哥德巴赫猜想赫猜想 Dim n%,n1%,n2% n=Val(InputBox(输入大于输入大于6的正整数的正整数) 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入门 授课教师：叶夏 计算机应用基础及VBASIC 四、数组排序 对已知存放在数组中的n个数。(1)选择法排序算法思想： 1）对有n个数的序列（存放在数组a(n)中

7、），从中选出最小（升序）或最大（降序）的数，与第1个数交换位置；2）除第1 个数外，其余n-1个数中选最小或最大的数，与第2个数交换位置；3）依次类推，选择了n-1次后，这个数列已按升序排列。原始数据：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入门 授课教师：叶夏 计算机应用基础及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入门 授课教师：叶夏 计算机应用基础及VBASIC （2）冒泡法排序（递增）冒泡法排序（递增） 算法思想：(将相邻两个数比较，小的调到前头)1）有n个数（存放在数组a(n)中），第一趟将每相邻

9、两个数比较，小的调到前头，经n-1次两两相邻比较后，最大的数已“沉底”，放在最后一个位置，小数上升“浮起”；2）第二趟对余下的n-1个数（最大的数已“沉底”）按上法比较，经n-2次两两相邻比较后得次大的数； 3）依次类推，n个数共进行n-1趟比较，在第j趟中要进行n-j次两两比较。8693268932689326839268329 683296382963289 （一）VB入门 授课教师：叶夏 计算机应用基础及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？ 编写一个数组编写一个数组排序的子过程排序的子过程（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC 例：删除数组中相同的例：删除数组中相同的元素元素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入门 授课教师：叶夏 计算机应用基础及VBASIC 五、查 找1、顺序查找法、顺序查找法（在一列数中查找某数（在一列数中查找某数x） 算法思想：一列数放在数组a(1)-a(n)中，待查找的数放在x 中，把x与a数组中的元素从头到尾一一进行比较查找。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入门 授课教师：叶夏 计算机应用基础及VBASIC 2、折半查找法（只能对有序数列进行查找）算法思想：n个有序数存放在数组a(1) a(n)中，要查找的数为x。变量top,bot,mid 分别表示查找范围的顶部、底部和中间，mid=(top+bot)2，若：（1）x=a(mid)，则已找到退出，否则进行下面的判断；（2）xa(mid)，x必定落在mid+1和bot的范围之

14、内， top=mid+1；（4）在确定了新的查找范围后，重复进行以上比较，直到找到或者bot=top。（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC find = False 判断是否找到的逻辑变量判断是否找到的逻辑变量 top = 1bot = n n为数组下标的上界为数组下标的上界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、：叶夏 计算机应用基础及VBASIC 4、矩阵转置、矩阵转置设有二维数组a(5,5)，要对它实现转置，可用下面两种方式：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入门 授课教师：叶夏 计算机应用基础及VBASIC 八、迭 代 法算法思想： 对于一个问题的求解x，可由给定的一个初值x0，得到一个新的值x1，这个新值x1比初值x0更接近要求的值x；再以新值作为初值，即：x1x0,重新按原来的方法求x1,重复这一过和直到|x1-x0|(某一给定的精度)。此时可将x1作为问题的解。例：计算的近似值（精度为0.00001），公式为：) 12() 12()2(.5343122222nnn)(21001xaxx例：用迭代法求平方根。 迭代公式为：（一）VB入门 授课教师：叶夏 计算机应用基础及VB

19、ASIC 九、数制转换将一个十进制整数m转换成 r (216)进制字符串。方法：将m不断除 r 取余数，直到商为零，以反序得到结果。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？小数的转换？小数的转换（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC 十、字符串的一般处理1.简单加密和解密加密的思想将每个字母C加（或减）一序数K，即用它后的第K个字母代替，变换式公式： c=chr(Asc(c)+k)例如序数k为5，这时 “A”“F”， “a”“f”，“B”“G” 当加序数后的字母超过“Z”或“z”则 c=Chr(Asc(c)+k -26)例如：You are good Dtz fwj ltti 解密为加密的逆过程将每个字母C减（或加）一序数K，即 c=chr(Asc(c)-k)

21、,例如序数k为5，这时 “Z”“U”， “z”“u”，“Y”“T” 当加序数后的字母小于“A”或“a”则 c=Chr(Asc(c)-k +26)（一）VB入门 授课教师：叶夏 计算机应用基础及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语句实现语句实现解密功能解密功能（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC 2、统计文本单词的个数算法思路： （1）从文本（字符串）的左边开始，取出一个字符；设逻辑量WT表示是否准备下一个新单词的开

23、始，初值设为True （2）若所取字符不是“空格”，“逗号”，“分号”或“感叹号”等单词的分隔符，再判断WT是否为True，若WT为True则表是新单词的开始，让单词数Nw=Nw+1，让WT=False; （3）若所取字符是“空格”，“逗号”，“分号”或“感叹号”等单词的分隔符， 则表示当前单词结束，准备下一个单词开始，让WT=True; (4) 再依次取下一个字符，重得（2）(3)直到文本结束。（一）VB入门 授课教师：叶夏 计算机应用基础及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 单词数为：单词数为：, NwNw= 0Yes, it is. WtTrueFalseTrueFalseTrueFalse1 2 3单词数加一的条件：单词数加一的条件：1 1、遇到非空格和标、遇到非空格和标点的字符点的字符2 2、WtWt为为TrueTrue True（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC 如果单词仅以空格作为分隔符：

25、方法： （1）查找空格，若找到第一个空格的位置n0，则单词数加1（2）从原字符串中去除第一个单词及余下字符串的首尾空格（3）重复（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 单词数为：单词数为：, NwThis is a book5（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC 十一、穷举法穷举法（又称“枚举法”）的基本思想是：一一列

26、举各种可能的情况，并判断哪一种可能是符合要求的解，这是一种“在没有其它办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，常常采用循环来处理穷举问题。例： 将一张面值为100元的人民币等值换成100张5元、1元和0.5元的零钞，要求每种零钞不少于1张，问有哪几种组合?（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC 十二 递归1.递归的概念： 用自身的结构来描述自身就称为“递归”。例对阶乘的定义：2. 递归过程 过程在自身定义的内部调用自己)!2() 1()!1()!1(!nnnnnn1) 1fac(*11)fac(nnnnn（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC 编fac(n)=n! 的递归函数 Function fac(n As Integer) As Integer If n = 1 Then fac = 1 Else fac = n * fac(n - 1) End If End Function递推回归（一）VB入门 授课教师：叶夏 计算机应用基础及VBASIC n=3Function fac%(n%) If n = 1 Then fac = 1 Else fac = n * fac(n - 1) End IfEnd