计算机二级考试VB常用算法难点.doc

计算机二级考试VB常用算法：约数因子1、算法说明 1) 最大公约数：用辗转相除法求两自然数m、n的最大公约数。 （1） 首先，对于已知两数m、n，比较并使得mn； （2） m除以n得余数r； （3） 若r0，则n为求得的最大公约数，算法结束；否则执行步骤（4） （4） mn nr 再重复执行（2） 譬如： 10与5 分析步骤： m=10 n=5 r=m mod n=0 所以n(n=5)为最大公约数 24与9 分析步骤： m=24 n=9 r=m mod n=6 r0 m=9 n=6 r=m mod n=3 r0 m=6 n=3 r=m mod n=0 所以n(n=3)为最大公约数 算法实现 Private Function GCD(ByVal m As Long, ByVal n As Long) As Long Dim temp As Long If m n Then temp = m: m = n: n = temp Dim r As Long Do r = m Mod n If r = 0 Then Exit Do m = n n = r Loop GCD = n End Function 2) 最小公倍数 mn最大公约数 3) 互质数 最大公约数为1的两个正整数 解题技巧 该算法需要识记！ 这种类型题目的扩展是约数和因子题型。2、实战练习 1) 补充代码（2003春二（9） 给定一个十进制正整数，找出小于它并与其互质的所有正整数（所谓互质数是指最大公约数为1的两个正整数，下图是程序执行画面）。 Option Explicit Private Function gcd（ （1） ） As Integer Dim r As Integer r = m Mod n If r = 0 Then gcd = n Else m = n: n = r （2） End If End Function Private Sub Command1_Click() Dim n As Integer, p As Integer n = Val(Text1) For p = n - 1 To 2 Step -1 If （3） Then List1.AddItem p Next p End Sub 2) 编程题（2002秋上机试卷01） 生成一个三行八列的二维数组A(3,8)，其中前两行元素产生的方法是： 用初值X1=26及公式Xi+1=(25Xi+357) Mod 1024，产生一个数列：X1、X2、.、X16 。 其中X1X8作为A的第一行元素；X9X16作为A的第二行元素；A的第三行元素值取前两行同列元素的最大公约数。最后按图示格式显示在图片框中。 计算机二级考试VB常用算法：进制转化1、算法说明 1) 十进制正整数m转换为R（216）进制的字符串。 思路： 将m不断除r取余数，直到商为0，将余数反序即得到结果。 算法实现： Private Function Tran(ByVal m As Integer, ByVal r As Integer) As String Dim StrDtoR As String, n As Integer Do While m o n = m Mod r m = m r If n 9 Then StrDtoR = Chr(65 + n - 10) & StrDtoR 将余数n转换为字符（10转为A，11为B，依次类推，然后放到转换后字符串的前面（实现反序排列） Else StrDtoR = n & StrDtoR End If Loop Tran = StrDtoR End Function2） R（216）进制字符串转换为十进制正整数。 思路：R进制数每位数字乘以权值之和即为十进制数。 算法实现： Private Function Tran(ByVal s As String, ByVal r As Integer) As integer Dim n As Integer, dec As Integer s = UCase(Trim(s) For i% = 1 To Len(s) If Mid(s, i, 1) = A Then n = Asc(Mid(s, i, 1) - Asc(A) + 10 将字母A转换为10，B转换为11，. Else n = Val(Mid(s, i, 1) End If dec = dec + n * r (Len(s) - i) Next i Tran = dec End Function 解题技巧 进制转化的原理要清楚,同时编写代码时候要留意16进制中的AF字符的处理。 2、实战练习 1) 补充代码（2002秋二（9） 本程序是把给定的二进制整数转换为八进制整数。 Private Sub Command1_Click() Dim a As String, b As String, c As String Dim L As Integer, m As Integer, n As Integer a = InputBox(请输入一个二进制数, 输入框) （1） a = String(L, 0) & a （2） For m = 1 To n / 3 b = Mid(a, 3 * m - 2, 3) （3） Next m Text1.Text = c End Sub Private Function zh(s As String) As String Dim i As Integer, n As Integer, p As Integer p = 1 For i = 2 To 0 Step -1 （4） p = p + 1 Next i zh = Str(n) End Function 2) 补充代码（2001春二（7） 下面程序是把给定的16进制正整数转换为10进制数。 Option Explicit Private Sub Form_Click() Dim St As Integer， Dem As Long St=InputBox(输入一个十六进制数) Dem=Convert(St) Print St; =; Dem End Sub Private Function Convert(S As String)As Long Dim N As Integer， I As Integer，Substring As String*1 Dim P As long， K As Long，Asc1 As Integer N= （1） P=16N For I=1 To N P=P/16 Substring= （2） Select Case Substring Case 0 To 9 K=K+P*Val(Substring) Case （3） Asc1=Asc(Substring)-Asc(A)+10 （4） End Select Next I （5） 计算机二级考试VB常用算法：素数1、算法说明 素数（质数）：就是一个大于等于2的整数，并且只能被1和本身整除，而不能被其他整数整除的数。 判别某数m是否是素数的经典算法是： 对于m，从I2，3，4，m1依次判别能否被I整除，只要有一个能整除，m就不是素数，否则m是素数。 Private Function sushu(ByVal n As Long) As Boolean Dim i As Long For i = 2 To n - 1 If (n Mod i) = 0 Then Exit For Next I If I=n then sushu=True End Function 很显然，实际上，我们可以改进上面 For i = 2 To n 1 为： For i = 2 To int（sqr（m） 这样可以很好的提高效率。 以上判断是否为素数的代码务必识记！ 应用举例 求100200之内素数。 Private Sub Command1_Click() Dim j As Integer For j = 100 To 200 If sushu(j) = True Then Print j End If Next j End Sub 解题技巧 识记判断素数的算法过程，根据题意，灵活调用！ 实例说明 编程题（2002年春上机试卷04） 找出10000以内所有可以表示为两个平方数和的素数。 思路： 首先找10000以内的所有素数，对于每个素数判断其是否可以表示为两个平方数之和（即对于任意小于该素数shu的数I，如果I和shuI均为平方数，则说明其可以表示为两个平方数之和。） 判断数I是否为平方数(即是某个数的平方)的方法：sqr（i）=int(sqr(i) Private Sub Command1_Click() Dim j As Integer Dim m As Long, n As Long For j = 2 To 10000 If sushu(j) = True Then If pf(j, m, n) = True Then List1.AddItem j & = & m & + & n End If End If Next j End Sub Private Function pf(ByVal shu As Long, m As Long, n As Long) As Boolean Dim i As Long For i = 1 To shu - 1 If (Sqr(i) = Int(Sqr(i) And (Sqr(shu - i) = Int(Sqr(shu - i) Then pf = True m = i n = shu - i Exit Function End If Next End Function 编程题（2004春上机试卷03） 随机生成15个两位正整数，从中找出所有的素数，并记下它是第几个数，再找出其中最大的素数，并给出它的位置。 计算机二级考试VB常用算法：最值问题1、算法说明 在若干数中求最大值，一般先取第一个数为最大值的初值（即假设第一个数为最大值），然后，在循环体内将每一个数与最大值比较，若该数大于最大值，将该数替换为最大值，直到循环结束。求最小值的方法类同。求若干数平均值，实质上就是先求和，再除以这些数的个数。应用举例随机产生n个1100（包括1和100）的数，求它们的最大值、最小值和平均值。Private Sub Command1_Click() Dim n As Integer, i As Integer, min As Integer, max As Integer, aver As Single, s As Integer n = Val(InputBox(输入个数:) s = Int(Rnd * 100) + 1 max = s min = s aver = s Print 第1个数是： & s For i = 2 To n s = Int(Rnd * 100) + 1 Print 第 &i & 个数是： & s If s max Then max = s If s 0.00001 i = i + 1 t = t / i e = e + t Loop Print 计算了； i； 项目和是：； e Print Exp（1） 与上句输出值进行对比以证明算法的正确性 End Sub 解题技巧 1）由于这类题目往往是根据精度要求来求值，因此我们不能预知具体循环次数，所以这类题目一般用Do循环，很少用For循环。设定循环变量和通项变量，注意各变量的初值； 2）分解通项表达式中各因子，并分别将各因子用循环变量表示； 3）如果步骤2中有的因子比较复杂，难以直接用变量表示，此时可以考虑使用Function过程； 4）根据步骤1、2、3，写出通项表达式； 5）根据精度要求（往往是通项小于10负多少次方这样一个关系表达式），写出一条满足精度要求后跳出循环的语句。通常是用：if 通项表达式10（-N） then exit do ，注意这句话一般需放在累加或者连乘式之前。实例说明 以2002年春上机试卷06编程题为例 根据X值计算： n1，2， 要求：n项绝对值小于等于10-6为止。 1、由于循环次数不确定，因此确定用Do循环结构并定义循环变量用n表示（初值1）；用户输入的值用x表示；通项用dblCos表示；累加值用sum表示，初值为0； 2、分解通项式的组成 可以分解为三部分： 可以表示为：（1）（n+1） 可以表示为：x（2*（n-1） 比较复杂，难以直接表示 3、由于步骤2中复杂， 此时考虑使用过程。 于是定义过程，输入值是n，返回值是 于是有： private Function comp（n as long）as long dim I as long dim result as long result=1 此处注意，由于是连乘，初值为1 for I=1 to 2*（n-1） result=result*I next I comp=result End Function 注意：由于是参数按地址传递，因此对于本题，实参的值不能在过程中被改变！（也是改错题常考的地方！） 4、根据步骤1、2、3，写出通项dblCos的表达式： dblCos=（1）（n+1）* x（2*（n-1）/comp（n） 5、根据精度要求知： If abs（dblCos）=10（-6） then exit do 最后程序为： Private Sub Command1_Click（） Dim n As Long， dblCos As Double， x As Double x = Val（Text1.Text） n = 1 Do dblCos = （-1） （n + 1） * x （2 * （n - 1） / comp（n） If Abs（dblCos） = 10 （-6） Then Exit Do Sum = Sum + dblCos n = n + 1 Loop Print Sum End Sub Private Function comp（n As Long） As Long Dim I As Long Dim result As Long result = 1 此处注意，由于是连乘，初值为1 For I = 1 To 2 * （n - 1） result = result * I Next I comp = result End Function 注意：如果调试运行时死循环，可以按CtrlBreak中断死循环，不需要重新启动机器。（或者Ctrl+Scroll Lock） 2、实战练习 1）补充代码（2003秋二（7） 本程序的功能是求下面数列前n项之和。 S（x，n）=x/2+2！*x3/2*4+3！*x5/2*4*6+n！*x2n-1/2*4*62n Option Explicit Private Sub Command1_Click（） Dim x As Single，s As Single Dim n As Integer，i As Integer x=InputBox（输入：，求数列和，） n=InputBox（输入：，求数列和，） For i=1 To n s=s+fun（x，i） Next i Label1.Caption= （1） Text1=s End Sub Private Function fun（x As Single，n As Integer）As Single （2） p=1 For i=1 To n （3） Next i fun=x（2*n-1）*p End Function 2）编程题（2003春上机试卷03） 按下列公式编写求积分余弦函数值的程序。当通项绝对值小于105时停止计算。 计算机二级考试VB常用算法：排序(1)1、算法说明 1) 选择法排序 (1) 从n个数中选出最小数的下标，出了循环，将最小数与第一个数交换位置； (2) 除第一个数外，在剩下的n-1个数中再按方法（1）选出次小的数，与第二个数交换位置； (3) 以此类推，最后构成递增序列。 譬如： 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 程序代码如下： Private Sub xzPaiXu(a() As Double, sheng As Boolean) a为需要排序的数组，sheng为True则为升序排列，为False，则为降序排列。 Dim i As Integer, j As Integer Dim temp As Double Dim m As Integer For i = LBound(a) To UBound(a) - 1 进行数组大小-1轮比较 m = i在第i轮比较时，假定第i个元素为最值元素，m记录小值元素的数组下标 For j = i + 1 To UBound(a) 在剩下的元素中找出最值元素的下标并记录在m中 If sheng Then 若为升序，则m记录最小元素下标,否则记录最大元素下标 If a(j) a(m) Then m = j End If Next j 将最值元素与第i个元素交换 temp = a(i) a(i) = a(m) a(m) = temp Next i End Sub 调用该过程示例： Option Base 1 Private Sub Command1_Click() Dim b(6) As Double b(1) = 8 b(2) = 6 b(3) = 9 b(4) = 3 b(5) = 2 b(6) = 7 Call xzPaiXu(b, True) For i% = 1 To 6 Print b(i) Next End Sub计算机二级考试VB常用算法：排序(2)2) 冒泡法排序 选择排序法在每一轮排序时找最值元素的下标，出了内循环（一轮排序结束），再交换最小数的位置；而冒泡法在每一轮排序时将相邻的数比较，当次序不对就交换位置，出了内循环，最值数已经冒出。 譬如： 8 6 9 3 2 7 8 6 9 3 2 7 8 6 9 2 3 7 8 6 2 9 3 7 8 2 6 9 3 7 2 8 6 9 3 7 . 2 3 8 6 9 7 . 2 3 6 8 7 9 . 2 3 6 7 8 9 . 2 3 6 7 8 9 程序代码如下： Private Sub mpPaiXu(a() As Double, sheng As Boolean) a为需要排序的数组，sheng为True则为升序排列，为False，则为降序排列。 Dim i As Integer, j As Integer Dim temp As Double Dim m As Integer For i = LBound(a) To UBound(a) - 1 进行n-1轮比较 For j = UBound(a) To i + 1 Step -1 从n到i个元素两两进行比较 If sheng Then 若次序不对，马上进行交换 If a(j) a(j - 1) Then temp = a(j) a(j) = a(j - 1) a(j - 1) = temp End If End If Next j 出了内循环，一轮排序结束，最值元素冒到最上边 Next i End Sub 调用该过程代码基本同上。计算机二级考试VB常用算法：插入与删除1、算法说明数组中元素的插入和删除一般是在已固定序列的数组中插入或删除一个元素，使得插入或删除操作后的数组还是有序的。 基本思路：首先要找到插入位置或要删除的元素。