VB课程-3.常用算法.ppt

第三讲：常用算法,一、计数、求和、求阶乘等简单算法,此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。,二、用辗转相除法求两自然数m，n的最大公约数和最小公倍数。,分析：(1)对于已知两数m，n，使得mn； (2) m除以n得余数r； (3)若r=0，则n为最大公约数结束；否则执行(4)； (4)m n，n r，再重复执行(2)。,设输入m=28,n=20 循环 m n r 赋好初值时：28 20 8 第一次结束：20 8 4 第二次结束： 8 4 0,If m 0) m=n n=r r= m mod n Loop Print “最大公约数=“, n,三、判断素数,基本思想： 把m作为被除数，将2Int(Sqr(m)作为除数，如果都除不尽，m就是素数，否则就不是。可用以下程序段实现 m =val( InputBox(“请输入一个数“) For i=2 To int(sqr(m) If m Mod i = 0 Then Exit For Next i If i int(sqr(m) Then Print “该数是素数“ Else Print “该数不是素数“ End If,？ 如何将其写成一函数。若为素数返回True，不是返回False。,例：验证哥德巴赫猜想（任意一个大于等于6的偶数都可以分解为两个素数之和） 基本思想：N为大于等于6的任一偶数，可分解为n1和n2两个数，分别检查n1和n2是否为素数，如都是，则为一组解。如n1不是素数，就不必再检查n2是否素数。先从n1=3开始，检验n1和n2（n2=N-n1）是否素数。然后使n1=n1+2,再检验n1、n2是否素数，直到n1=N/2为止。,Private Function 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 i End Function,验证哥德巴赫猜想,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 Print n & “=“ & n1 & “+“ & n2 Exit For End if End if Next n1,Private 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 i End Function,四、数组排序 对已知存放在数组中的n个数。,(1)选择法排序 算法思想： 1）对有n个数的序列（存放在数组a(n)中），从中选出最小（升序）或最大（降序）的数，与第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程序,For i = 1 To n - 1 imin = i For j = i + 1 To n If a(imin) a(j) Then imin = j Next j temp = a(i) a(i) = a(imin) a(imin) = temp Next i,（2）冒泡法排序（递增）,算法思想：(将相邻两个数比较，小的调到前头) 1）有n个数（存放在数组a(n)中），第一趟将每相邻两个数比较，小的调到前头，经n-1次两两相邻比较后，最大的数已“沉底”，放在最后一个位置，小数上升“浮起”； 2）第二趟对余下的n-1个数（最大的数已“沉底”）按上法比较，经n-2次两两相邻比较后得次大的数； 3）依次类推，n个数共进行n-1趟比较，在第j趟中要进行n-j次两两比较。,冒泡法排序（升序）的VB程序：,For i = 1 To n - 1 For j = 1 To n-i If a(j) a(j+1) Then temp=a(j) a(j)=a(j+1) a(j+1)=temp End if Next j Next i,？ 编写一个数组排序的子过程,例：删除数组中相同的元素,Public Sub del(a() As Integer) i = LBound(a) Do While i UBound(a) j = i + 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 Loop End Sub,1、a) While 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、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,五、查 找,1、顺序查找法（在一列数中查找某数x） 算法思想：一列数放在数组a(1)-a(n)中，待查找的数放在x 中，把x与a数组中的元素从头到尾一一进行比较查找。 Option Base 1 Private Function Find( a( ) As Single,x!) As Integer Dim n%,p% Find=0 n=Ubound( a ) For p=1 to n If x=a( p) Then Find=p : exit for Next p End Function,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的范围之内， top=mid+1； （4）在确定了新的查找范围后，重复进行以上比较，直到找到或者bot=top。,find = False 判断是否找到的逻辑变量 top = 1 bot = 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(mid) Then bot = mid - 1 Else top = mid + 1 End If Loop If (Not find) Then Print x; “has not found“,六、插 入 法,把一个数插到有序数列中，插入后数列仍然有序） 算法思想：(1). 先确定x插在数组中的位置p p=1 do while xa(p) and p=n p=p+1 loop （2）a(p)a(n)元素向后顺移一个位置以空出a(p)元素放入x： for i=n to p step 1 a(i+1)=a(i) next i a(p)=x,如何将其写成一个过程？,七、矩阵（二维数组）运算,1、矩阵的加、减运算 C(i,j)=a(i,j)+b(i,j) 加法 C(i,j)=a(i,j)-b(i,j) 减法 2、矩阵的乘法 矩阵A有M*L个元素，矩阵B有L*N个元素，则矩阵C=A*B有M*N个元素）。 矩阵C中任一元素：,3、求二维数组中的最大（最小）值,row = 1: Column = 1 For i = 1 To 4 For j = 1 To 5 If a(i, j) a(row, Column) Then row = i Column = j End If Next j Next i Print “最大元素是“; a(row, Column); Print “，在第“ Print “第“ & Column & “列“,4、矩阵转置,设有二维数组a(5,5)，要对它实现转置，可用下面两种方式： For i=1 to 4 For i=2 to 5 For j=i+1 to 5 For j=1 to i-1 t=a(i,j) t=a(i,j) a(i,j)= a(j,i) a(i,j)= a(j,i) a(j,i)=t a(j,i)=t Next j Next j Next i Next i,八、迭 代 法,算法思想： 对于一个问题的求解x，可由给定的一个初值x0，得到一个新的值x1，这个新值x1比初值x0更接近要求的值x；再以新值作为初值，即：x1x0,重新按原来的方法求x1,重复这一过和直到|x1-x0|(某一给定的精度)。此时可将x1作为问题的解。,例：计算的近似值（精度为0.00001），公式为：,例：用迭代法求平方根。 迭代公式为：,九、数制转换,将一个十进制整数m转换成 r (216)进制字符串。 方法：将m不断除 r 取余数，直到商为零，以反序得到结果。,Private Function TrDec(idec%, ibase%) As String Dim strDecR$, iDecR% End Function,strDecR = “ TrDec = strDecR,Do Loop,While idec 0 iDecR = idec Mod ibase strDecR = iDecR & strDecR idec = idec ibase,If iDecR = 10 Then strDecR = Chr$(65 + iDecR - 10) & strDecR Else End If,？小数的转换,十、字符串的一般处理,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), 例如序数k为5，这时 “Z”“U”， “z”“u”，“Y”“T” 当加序数后的字母小于“A”或“a”则 c=Chr(Asc(c)-k +26),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 strT 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=strp End Function,?用select语句实现解密功能,2、统计文本单词的个数,算法思路： （1）从文本（字符串）的左边开始，取出一个字符；设逻辑量WT表示是否准备下一个新单词的开始，初值设为True （2）若所取字符不是“空格”，“逗号”，“分号”或“感叹号”等单词的分隔符，再判断WT是否为True，若WT为True则表是新单词的开始，让单词数Nw=Nw+1，让WT=False; （3）若所取字符是“空格”，“逗号”，“分号”或“感叹号”等单词的分隔符， 则表示当前单词结束，准备下一个单词开始，让WT=True; (4) 再依次取下一个字符，重得（2）(3)直到文本结束。,Nw = 0: Wt = True nL = Len(RTrim(stri) For i = 1 To nL strT = Mid$(stri, i, 1) Select Case strT Case “ “, “,“, “;“, “! “ Wt = True Case Else If Wt Then Nw = Nw + 1 Wt = False End If End Select Next i Print “单词数为：“, Nw,1,2,3,单词数加一的条件： 1、遇到非空格和标点的字符 2、Wt为True,如果单词仅以空格作为分隔符：,方法： （1）查找空格，若找到第一个空格的位置n0，则单词数加1 （2）从原字符串中去除第一个单词及余下字符串的首尾空格 （3）重复（1）（2）直到n=0为止。 Nw = 0 strI = Trim(strI) If Len(strI)0 then nw=1,Do Whlie n0 Loop,N=Instr(strI,“ “),nw=nw+1 strI = Trim(Mid$(strI, n+1) n=Instr(strI,“ “),Print “单词数为：“, Nw,十一、穷举法,穷举法（又称“枚举法”）的基本思想是：一一列举各种可能的情况，并判断哪一种可能是符合要求的解，这是一种“在没有其它办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，常常采用循环来处理穷举问题。 例： 将一张面值为100元的人民币等值换成100张5元、1元和0.5元的零钞，要求每种零钞不少于1张，问有哪几种组合?,十二 递归,1.递归的概念： 用自身的结构来描述自身就称为“递归”。例对阶乘的定义： 2. 递归过程 过程在自身定义的内部调用自己,编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,递推,回归,n=3 Function fac%(n%) If n = 1 Then fac = 1 Else fac = n * fac(n - 1) End If End Function,n=2 Function fac%(n%) If n = 1 Then fac = 1 Else fac = n * fac(n - 1) End If End Function,n=1 Function fac%(n%) If