常用算法总结.doc

常用算法总结（一）
一、变量值的交换
算法思想:若交换两个变量的值，必须引入第三个新的变量进行传递.
以下代码是错误的：
X=12 ：Y=34 ：X=Y ：Y=X
正确的代码是：
X=12 ：Y=23 ：T=X ：X=Y ：Y=T
二、判断一个数是否能被另一个数整除
算法思想：可以用整除的定义(余数为0）或X除以Y等于X整除Y等表达式进行判断.
条件表达式可以为：X mod Y=0 或 X＼ Y=X/Y 或 Int(X/Y）=X/Y
如果以上条件表达式为True，则表示X能被Y整除。
三、累加、阶乘、计数和求平均值
算法思想：使用循环语句，并用一个变量存放累加的中间及最终结果。
注：
累加求和时变量初值为0，计算阶乘时变量初值为1.
统计计个数（计数）时可用一个变量作为统计个数的累加变量,每次加1即可。
求平均值算法思想是先求和，再除以个数。
条件求和(或计数）:在循环语句中加入If－End If判断语句。
例题：计算1到10之间所有整数的累加和以及10!.
n=10
sum=0 ‘累加求和时，变量的初值一定为0
prod=1 ‘累乘（连乘）时，变量的初值一定为1
For i=1 To n
sum=sum+i
prod=prod*i
Next i
Print sum，prod
例题:统计0-100之间能被3整除的数的个数、累加和及其平均值.
s=0
n=0
For i=0 To 100
If i mod 3 =0 Then
s=s+i
n=n+1
End If
Next i
Print n,s,s/n
四、对数组中的元素逐一进行操作
算法思想:在VB中，对于数组中元素的操作，往往使用到For循环.通用代码为:
Dim 数组名（［下标下界］ To 下标上界）
……
For i=LBound（数组名） To UBound（数组名）
……
数组名 （ i ） ……
……
Next i
通过以上循环，可以对数组中所有元素逐一操作。
注：
1) LBound函数：返回数组的下界
UBound函数：返回数组的上界
2）如果数组上界和下界已经确定，可以不使用函数，直接指明即可。例如
Option Base 1
Dim a（100） As Integer
For i=1 To 100
……
a （ i ） ……
……
Next i
3）对于二维数组，要使用For循环的嵌套实现对数组中元素的操作,其中外层循环变量控制第一维下标的变化，内层循环变量控制第二维下标的变化，例如：
Option Base 1
Dim a（2，3) As Integer
For i=1 to 2
For j=1 to 3
……
a （i,j） ……
……
Next j
Next i
例题：
1．对下标为偶数的元素进行处理的程序代码
Option Base 1
……
For i=1 to UBound（a) ‘循环变量i可代表数组元素的下标
If i mod 2 =0 Then
a (i） ……
End If
Next i
2．对数组元素中数据为偶数的元素进行处理
Option Base 1
……
For i=1 to UBound(a） ‘循环变量i代表数组元素的下标
If a（i） mod 2 =0 Then
a （i) ……
End If
Next i
五、交换数组元素
算法思想:若某一维数组有n个元素,将第1个元素和第n个元素交换,将第2个元素和第n—1个元素交换……，需要交换n＼ 2次(如果交换n次,则回到初始状态）;对于二维数组，若进行行交换或列交换，需要使用循环语句，每次循环需要使用变量值交换算法。
例题：交换一维数组（5个元素)的元素值
b = Array(1， 3， 5, 7， 9)
For i = 0 To 5＼ 2
tmp = b（i）
b(i） = b（5 - i — 1）
b（5 - i — 1） = tmp
Next i
End Sub
例题：一维数组元素交换的通用代码：
n = UBound（数组名）
For i = LBound（数组名） To n ＼ 2
t = b（i）
b（i） = b（n）
b（n) = t
n = n - 1
Next i
例题：交换二维数组Mat第二列和第四列的数据
For i=LBound(Mat，1) To UBound（Mat，1)
t = Mat(i， 2）
Mat（i， 2) = Mat（i, 4)
Mat（i, 4） = t
Next i
例题：交换二维数组Mat第一行和第三行的数据
For j=LBound（Mat，2） To UBound（Mat,2）
t = Mat（1， j）
Mat(1，j） = Mat(3，j)
Mat(3,j) = t
Next i
六、求数组元素中的最大值、最小值
算法思想：假设数组中第一个元素为最大值，并赋给变量Max，然后使用循环结构依次与第2个数组元素至最后一个元素进行比较，如果某数组元素的值大于Max，则将该元素的值赋给Max(同时可记录下该数组元素在数组中的位置）。
例题：显示数组a中的最大值及其下标.
Option Base 1
Dim Max As Integer， Index As Integer
Max=a（1）
aIndex=1
For i=2 to UBound(a）
If a（i）〉Max Then
Max=a（i）
aIndex=i
End If
Next i
Print Max ， i
求最小值的方法与此类似，差别在于取第一个元素为最小值Min，与2个数组元素至最后一个元素进行比较时判断关系有所调整，即
Min=a（1)
If a（i）〈Min Then
Min=a(i)
End If
七、常用字符处理函数
Mid函数：从字符串指定位置取指定个字符，格式为Mid (字符，p，n） ,从第p个字符开始,向后截取n个字符（若n省略则取到最后）.
Left和Right函数:从字符串左边或右边取指定个字符，格式为 Left （字符，n）和Right （字符，n)。
Len函数：测试字符串长度。
UCase和LCase函数:UCase将小写字母转换为大写字母;LCase将大写字母转换为小写字母。
Instr([首字符位置 , ] 字符串1， 字符串2 ［ ， n］）：在字符串1中查找字符串2，如果找到，返回字符串2的第一个字符在字符串1中出现的位置.首字符位置是可选的,如果不指定，从字符串起始位置开始查找；如果指明，从指定的位置开始查找。
Asc函数：返回字符串中第一个字符的ASCII码.
Chr函数：将一个数值转换为其所对应的字符.
字符的比较规则是按ASCII码顺序比较，规则为 空格〈"A”~"Z”〈”a”~”z"
小写字母的ASCII比大写字母的ASCII小32。
例题：
1．将所有文本转换为大写(小写）字母
可以直接使用UCase（LCase）函数转换。例如：
Text2。Text=UCase(Text1。Text）
2．对某个字符串的所有字符逐一处理
算法思想：如果对某个字符串的所有字符逐一处理，即从字符串的第1个字符开始到最后一个字母，每次处理1个字符。可以使用For循环实现.通用代码为:
For i=1 To Len(s）
s1=Mid（s，i，1）
……
Next i
3．字符转换
算法思想：通过字符的ASCII码进行处理（使用Asc函数）,然后再使用Chr函数将ASCII转换成字符。
例题：将文本框Text1中字符按如下规律转换a－b、b－c……z－a，并显示在文本框Text2中。
s = Text1.Text
n = Len（s）
For i = 1 To n
s1 = Mid（s, i， 1)
If s1 〉= "a” And s1 〈= ”y" Then
s2 = s2 + Chr（Asc（s1） + 1)
ElseIf s1 = "z” Then
s2 = s2 + ”a"
End If
Next i
Text2。Text = s2
例题：将文本框Text1中的小写字母转换其对应的大写字母，将大写字母转换成小写字母，并显示在文本框Text2中。
Private Sub Command1_Click（)
s = Text1。Text
n = Len（s）
m = Asc（"a”) - Asc（”A”)
For i = 1 To n
s1 = Mid（s， i, 1）
If s1 >= ”a" And s1 <= ”z” Then
s2 = s2 + Chr(Asc（s1) - m)
End If
If s1 >= "A” And s1 <= ”Z” Then
s2 = s2 + Chr(Asc（s1) + m）
End If
Next i
Text2。Text = s2
End Sub
4．判断是否回文函数
所谓回文是指顺读与倒读都一样的字符串，如“rececer”
Function foundhuiwen（p As String）
foundhuiwen = True
k = Len（p）
For i = 1 To k / 2
If Mid（p， i， 1） <〉 Mid（p， k + 1 — i， 1） Then
foundhuiwen = False
Exit For
End If
Next
End Function
如果foundhuiwen函数返回值为True，表明字符串p为回文,否则表示不是回文.
5．统计某字符出现次数
算法思想：对字符串中字符逐一判断,如果是某字符,则统计变量加1.
例题:统计文本框Text1中字符i和j出现的次数（不区分大小写）。
Private Sub Command1_Click（)
s = Text1。Text
n = Len（s)
For i = 1 To n
s1 = Mid（s, i， 1）
If UCase（s1） = ”I" Then ni = ni + 1
If UCase（s1） = "J” Then nj = nj + 1
Next i
Print ni, nj
End Sub
八、素数
素数定义：只能被1和本身整除的正整数称为素数（或称质数）。例如11就是素数，它只能被1和11整除。
算法思想:判别某数n是否是素数的方法有很多，最简单的是从素数的定义来求解。对于n，从i=2,3，…,n—1判别n能够被i整除，只要有一个能整除，n就不是素数，否则n是素数。此种算法比较简单,但速度慢，因此,可以将n被2到  (或n/2)间的所有整数除，如果都除不尽,则n就是素数，否则n是非素数。

注:执行For循环时，循环变量等于终值仍进入循环，遇到Next语句，循环变量会自动加上步长，因此如果循环正常完成后，循环变量的值将大于终值。
例如:
For i=1 To 4
 If …… Then Exit For
Next i
Print i
如果循环正常结束，则输出结果为5（大于4)。如果循环过程中满足If条件，执行Exit For语句退出循环，则i的值一定小于5。
例题:判断n是否是素数。
Private Sub Command2_Click(）
 n = Val（Text1。Text)
 For j = 2 To n - 1
    If n Mod j = 0 Then Exit For
 Next j
 If j 〉 n-1 Then Print "是素数” Else Print ”不是素数”
End Sub
例题:输出2～n范围的全部素数。
Private Sub Command1_Click（）
n = Val（Text1。Text)
For i = 2 To n
   For j = 2 To Sqr(i)
      If i Mod j = 0 Then Exit For
 Next j
  If j 〉 Sqr(i） Then Print i
Next i
End Sub
使用Do While循环判断是否是素数的代码为：
Private Function isprime(a As Integer) As Boolean
    Dim flag As Boolean
    flag = True
    b = 2
   Do While b 〈= Int(a / 2） And flag
        If Int(a / b) = a / b Then
            flag = False
        Else
            b = b + 1
        End If
    Loop
    isprime = flag
End Function
End Sub
其中flag作为标志变量，首先赋值为True，在循环体中,如果满足If条件（即n能被其他数整除），则flag重新赋值为False，最后根据flag的值可知n是否是素数。
九、最大公约数和最小公倍数
算法思想：
(1）对于已知两数x、y,使得x〉y
（2)x除以y得余数r；
（3)若r=0，则x为求得的最大公约数，算法结束；否则执行步骤（4）
（4）x←y，y←r，再重复执行(2）
求得了最大公约数后,最小公倍数就可很方便地求出，即将原来的两数相乘除以最大公约数。
Private Sub Form_Click（）
 x = Val(InputBox（"请输入第一个数：”))
 y = Val(InputBox（"请输入第二个数：”)）
 If x 〈 y Then
     t = x
     x = y
     y = t
 End If
 x 1 = x
 y1 = y
 Print x， y
 Do While y 〈> 0
    r = x Mod y
    x = y
    y = r
 Loop
 Print ”最大公约数为:"； x
 Print ”最小公倍数为:”； x1 ＊y1 / x
End Sub

十、完数
定义：一个数如果正好等于它的因子之和,这个数就称为完数。例如，6的因子为1、2、3，而6=1+2+3,因此6是“完数"。
例题：编程找出1000以内的所有完数.
Private Sub Command1_Click（)
OutputWanNumber 1000
End Sub

’求完数的过程
Sub OutputWanNumber（ByVal n As Integer)
Dim i As Integer
Dim j As Integer
Dim s As Integer

For i = 1 To n
 s = 0
 For j = 1 To i＼ 2
    If i Mod j = 0 Then s = s + j
 Next j
 If s = i Then Print i & ”是完数”
Next i
End Sub

十一、水仙花数
定义:“水仙花数”是指一个三位数，其中各位数字的立方和等于该数本身（如153＝13+53+33)
分析:此题的关键是要知道如何分离出一个三位数中的各位数字。
例题:找出100~999之间的所有“水仙花数”。
Private Sub Command1_Click（）
 For i = 100 To 999
    a = Int（i / 100）
    b = Int(（i — 100 * a） / 10)
    c = i — Int（i / 10) ＊ 10
    If i = a ^ 3 + b ^ 3 + c ^ 3 Then
      Print i
    End If
 Next i
End Sub

Private Sub Command1_Click（）
 For n = 100 To 999
    s = 0
    a = n
    Do While a 〈〉 0
     b = a Mod 10
     s = s + b ＊ b ＊ b
     a = a＼ 10
    Loop
    If s = n Then Print n
 Next n
End Sub
十二、数列
以下数列:1,1，2，3，5,8，13，21，…,的规律是从第3个数开始，每个数是它前面两个数之和。

Private Sub Command1_Click()
    Dim a（50） As Long
Dim f As Long
    a（1) = 1
    a（2） = 1
    For i = 3 To Val（Text1。Text)
       f = a（i - 2） + a（i — 1）
       a（i) = f
    Next
    Text2。Text = f
End Sub

以下数列:1，1，3,5，9，15，25，41，…，的规律是从第3个数开始，每个数是它前面两个数的和加1.
Private Sub Command1_Click(）
    Dim f As Long
    a（1） = 1
    a(2） = 1
    For i = 3 To Val(Text1.Text）
       f = a(i — 2) + a（i — 1) + 1
       a（i) = f
    Next
    Text2。Text = f
End Sub

十三、排序
本算法主要应用于数组。排序算法有种,其中“冒泡”排序法是较为常见的一种。
算法思想：从数组的第一个元素开始，每一项(i)都与下一个元素（i+1)进行比较，如果下一个元素的值较小，就将这两项的位置交换，从而使值较小的数据项“升"到上面（最大数“沉底"），重复这种操作直到最后一个元素，然后再回到开始进行重复处理。当整个数组不再出现交换项目时，排序结束。
       例题:数组a种有5个元素,每个元素值分别为10、8、21、7、5，用冒泡排序法进行排序。
Option Base 1
Private Sub Command1_Click（)
arr1 = Array（2， 4, 1, 5， 3）
For i = 5 To 2 Step —1
 For j = 1 To i - 1
If arr1(j) 〉 arr1(j + 1) Then
     t = arr1（j）
     arr1（j) = arr1（j + 1)
     arr1(j + 1） = t
End If
   Next j
Next i
For i = 1 To 5
Print arr1（i)；
Next i
End Sub
5