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

计算机二级考试VB常用算法：约数因子
1、算法说明
1)        最大公约数：用辗转相除法求两自然数m、n的最大公约数。
（1）        首先，对于已知两数m、n，比较并使得m>n；
（2）        m除以n得余数r；
（3）        若r＝0，则n为求得的最大公约数，算法结束；否则执行步骤（4）
（4）        m→n   n→r  再重复执行（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
                          r≠0 m=9 n=6
                          r=m mod n=3
                          r≠0 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)        最小公倍数
         m×n÷最大公约数
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=(25×Xi+357) Mod 1024，产生一个数列：X1、X2、......、X16 。
其中X1~X8作为A的第一行元素；X9~X16作为A的第二行元素；A的第三行元素值取前两行同列元素的最大公约数。最后按图示格式显示在图片框中。

计算机二级考试VB常用算法：进制转化
1、算法说明
1)        十进制正整数m转换为R（2－16）进制的字符串。
         思路： 将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 Function  
2）        R（2－16）进制字符串转换为十进制正整数。
         思路：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进制中的A－F字符的处理。
 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=16^N
                           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，从I＝2，3，4，……，m－1依次判别能否被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））
这样可以很好的提高效率。
以上判断是否为素数的代码务必识记！
应用举例
求100－200之内素数。
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和shu－I均为平方数，则说明其可以表示为两个平方数之和。）
判断数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个1－100（包括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 < min Then min = s
        aver = aver + s
    Next i
    aver = aver / n
    Print "max="; max; "min="; min; "aver="; aver
End Sub
解题技巧
最大值、最小值、平均值类型题目往往和数组放在一起考！有的不仅求这些值，还要对具有最大值或者最小值的行或列或者某个元素进行处理，这时就要在记录最大、最小值时，同时记录该值所在的行号和列号。
计算机二级考试VB常用算法(1)：累加和连乘
1、算法说明
　　    累加形式：V=V+e
　　    连乘形式：V=V*e
　　    其中：V是变量，e是递增表达式。累加和连乘一般通过循环结构来实现。
　　    注意：需在执行循环体前对变量V赋初值。一般的，累加时置初值0；连乘时置初值为1.
　　    举例
　　    求N！的结果。
　　    Private Sub Command1_Click（）
　　    Dim n%， i%， s&
　　    n = Val（InputBox（"输入n"））
　　    s = 1
　　    For i = 1 To n
　　    s = s * i
　　    Next i
　　    Print s
　　    End Sub
　　    错误的写法：
　　    Private Sub Command1_Click（）
　　    Dim n%， i%， s&
　　    n = Val（InputBox（"输入n"））
　　    For i = 1 To n
　　    s = 1             ‘赋初值语句位置不对！
　　    s = s * i
　　    Next i
　　    Print s                ‘输出s的值为n，而不是n！
　　    End Sub
　　    应用举例
　　    根据下列公式，求自然对数e的的近似值。

　　    要求：误差小于0.00001
　　    Private Sub Command1_Click（）
　　    Dim i%， n&， t！， e！
　　    e = 2
　　    i = 1
　　    t = 1
　　    Do While t > 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值计算：

　　    n＝1，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
　　    注意：如果调试运行时死循环，可以按Ctrl＋Break中断死循环，不需要重新启动机器。（或者Ctrl+Scroll Lock）
　　    2、实战练习
　　    1） 补充代码（2003秋二（7））
　　    本程序的功能是求下面数列前n项之和。
　　    S（x，n）=x/2+2！*x^3/2*4+3！*x^5/2*4*6+……+n！*x^2n-1/2*4*6……2n
　　    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）
　　    按下列公式编写求积分余弦函数值的程序。当通项绝对值小于10－5时停止计算。

计算机二级考试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
            Else
                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
            Else
                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、算法说明数组中元素的插入和删除一般是在已固定序列的数组中插入或删除一个元素，使得插入或删除操作后的数组还是有序的。
基本思路：首先要找到插入位置或要删除的元素。