基本算法介绍

基本算法介绍

算法实际上就是用计算机解决某个问题的方法和步骤，学习完循环和分支结构的语句后，实际上就可以编写任何复杂的程序了，而在程序的编写之前必须掌握程序算法的基本思想，即对不同问题处理时的计算机的解题步骤，下面就介绍一些基本的算法思想。

注意：对某一类问题的解决，有很多解决的方法，因此，同一个问题的程序设计，针对不同的算法可能编写出不同的程序，而我们在下面介绍的只是对某类问题的通用算法思想。另外，算法的设计不针对某一个具体的问题，希望大家在学习时，不要仅满足掌握相关例题的程序设计，而要学习算法的基本思想，学会以后遇到类似的问题时能运用该思想来解决问题。

1． 累加算法

累加是程序设计中最常遇见的问题，比如求某单位职工的所有工资总和等。

累加算法的一般做法是定义一个变量 s ，作为累加器使用，一般初值为0，再定义一个变量用来保存加数。一般在累加算法中的加数都是有规律可循，可结合循环程序来实现。

由前面可知，一个循环程序的设计，如果以下三方面确定下来：变量的赋初值、循环体的内容、循环结束条件，那么根据循环语句的格式，就很容易写出相应的循环程序。

例5-2-8 求1+2+3+„„+100的累加和，并在窗体上打印输出。

分析：

设累加器S 专门存放累加的结果，初值为0，加数用变量I 表示

当I=1时， S 的值应为0+1=1，即S= 0+1= S+I （执行语句S=S+I）

当I=2时， S 的值应为1+2= 3，即S =1+2= S+I （执行语句S=S+I）

当I=3时， S 的值应为3+3= 6，即S= 3+3 = S+I （执行语句S=S+I）

当I=4时， S 的值应为6+4= 10，即S= 6+4 = S+I （执行语句S=S+I）

„„

当I=100时，累加器S=S+100=1+2+3+„„+99+100=5050（执行语句S=S+I）

不难看出，I 的值从1变化到100的过程中，累加器均执行同一个操作：S=S+I，S=S+I的操作执行了100次，所以该程序段可写成：

Dim i As Integer, s As Integer

s= 0 ‘给累加器s 赋初值

For i= 1 To 100

s= s +i ‘i 既作为循环变量，又作为加数

Next I

Print "1+2+„„+100="; S

考虑一下：语句Print "1+2+„„+100="; S可以放在循环体中吗？

归纳一下：

所有累加程序的基本思想都是定义累加器s ，初值为0或根据情况赋一个特定值，定义一个变量t 存放加数，只不过在不同情况下，加数t 的值不同，在循环体中，每次产生指定的加数t ，执行s = s +t，直到循环结束为止。

如果累加次数确定，累加程序一般可以采用如下的编程模式（假设累加次数为n 次）： s = 0

„„ ‘其他的变量初始化语句（如果需要的话）

For i = 1 To n

将加数赋给t

s = s + t

Next I

如果累加次数不确定，累加程序一般可以采用如下的编程模式：

s = 0

„„ ‘其他的变量初始化语句（如果需要的话）

Do

将加数赋给t

s = s + t

Loop Until 循环结束条件

例5-2-9 求1+1/x+1/x2+„„+1/xn （x>1）的累加和，要求精确到10-6。

分析：

很显然，这也是一个累加的算法题，但累加次数不确定，所以应用Do-Loop 型循环实现。

加数t 为1/xn ，x 由用户从键盘上输入，n 的值从1开始，每次循环，n 的值增加1，由前面的归纳可以编写程序如下：

Private Sub Command1_Click()

Dim x As Single, n As Integer

Dim s As Single, t As Single

n = 1

s = 1

x = InputBox("请输入x 的值，x 要求大于1")

Do

t = 1 / x ^ n ‘产生每次的加数t

n = n + 1 ‘

s = s + t ‘累加

Print t

Loop Until t

Print s

End Sub

延伸一下：

上述算法对数值型数据，执行的是累加操作，但如果用于字符串型数据，完成的则是字符串的连接。

如果需要实现字符串的连接，定义一个字符串型变量s 作为字符连接器，一般赋初值为””（空串），变量t 作为被连接的字符，则在循环体中执行s=s+t时完成的就是字符串的顺序连接。

比如：如果t 分别被赋值为字符“A ”、“B ”、“C ”、“D ”，在4次循环中，执行s=s+t，循环执行过程如下：

（1） s=s+t=”A ” （t=“A ”)

（2） s=s+t=”AB ” （t=“B ”)

（3） s=s+t=”ABC ” （t=“C ”)

（4） s=s+t=”ABCD ” （t=“D ”)

如果需要实现字符的逆序连接，比如上述的结果为“DCBA ”，则只需将循环体中s=s+t改为s=t+s。

注意：用+作为字符串连接符时，+运算符两边必须是字符串类型，但用&运算符时就没有这个限制，所以在实现字符的顺序连接时最好用语句s=s & t来实现。

例5-2-10 从键盘上输入一串字符，要求将其加密后显示在文本框Text1中，加密的方法是将每一个字符转变为它的后一位字符，如：A 转变为B ，1转变为2。

分析：

因为涉及对每一个字符做相应处理再连接成一个新串，所以可以用类似累加的算法。定义一个变量str1用来接收输入的原始字符串，变量str2用来接收加密后的字符串，初值为空串。可用Len 函数得出字符串的长度，用循环控制，从左向右逐个取字符，截取字符的功能可用Mid 函数完成，由于要做加密操作，可利用Asc 函数获得字符的Ascii 码，用Chr 函数获得Ascii 码对应的字符。

程序段如下：

Dim str1 As String, ch1 As String * 1

Dim i As Integer, str2 As String,ch2 As String * 1

str1 = InputBox("输入原始字符串：")

For i = 1 To Len(str1)

Ch1= Mid(str1, i, 1) ‘获得字符串str1的每一个字符赋给变量ch1

Ch2= Chr(Asc(ch1) + 1) ‘将ch1的下一个字符赋给变量ch2

str2 = str2 +ch2 ‘将ch2中赋的字符连接成串

Next i

Text1.Text = str2

由此可以看出：对字符串的连接操作，可用累加算法来完成，不过在字符串的操作中，经常要用到字符串处理函数，所以一些常用字符串函数的功能和用法必须掌握。

考虑一下：上例中如果要实现字符的逆序连接，该怎么实现？

2．连乘算法

连乘算法和累加算法的思想类似，只不过一个做乘法，一个做加法。

连乘算法的一般做法是设一个变量t ，作为乘法器使用，初值一般为1，设一个变量k

用来保存每次需要乘的乘数，在循环体中执行t=t*k的语句即可。

例5-2-11 求10！=1*2*3*„„*10的结果并打印输出。

分析：

设乘法器T ，初值为1，设变量k 存放乘数。

当k=1时，T=T*k=1*1=1

当k=2时，T=T*k=1*2=2

当k=3时，T=T*k=2*3=6

„„

当k=10时，T=T*k=1*2*3*„„*9*10

所以当k 的值从1变化到10的过程中，乘法器均执行同一个操作：T=T*k，程序段可写成：

Dim k As Integer, T As long

T= 1

For k= 1 To 10

T = T* k

Next I

Print "1*2*3*„„*10=";T

例5-2-12 求1！+2！+„„+10！的值。

分析：

这一题总体上是累加题，只不过加数不再是简单的1、2、3等，而是1！、2！到10！，可考虑设一个变量s 作累加器，设一个变量t 存放每一次的加数，累加的次数是10次，分别加上1！到10！。

按照前面的确定次数的累加程序框架，可以很方便地确定累加程序为：

s = 0

For i = 1 To 10

将加数i! 赋给t

s = s + t

Next I

注意：加数t 不能直接赋i! ，即t=i!，因为VB 中没有阶乘运算符。

在每次累加之前，应用连乘算法计算i! 的值，可设循环控制变量j ，按如下程序段完成求i! ：

t = 1

For j = 1 To i

t = t * j

Next j

结合累加算法，求！+2！+„„+10！的程序段就可以编写如下：

Dim i As Integer, j As Integer

Dim s As Long, t As Long

s = 0

For i = 1 To 10

t = 1

For j = 1 To i 内循环求i!

t = t * j

Next j

s = s + t

Next i

Print "1!+2!+„„+10!="; s

程序执行流程是：I=1，计算t=1!，s=0+1!=1!

I=2，计算t=2!，s=1!+2!

I=3，计算t=3!，s=1!+2!+3!

„„

I=10，计算t=10!，s=1!+2!+3!+4!+5!+6!+7!+8!+9!+10!

考虑一下：

1）语句t=1是否可以和s=0一样，放在外循环的外面？

（答案：不可以！循环变量的初始化位置要牢记以下原则：外循环变量初始化应放在外循环的外面，内循环变量初始化应放在外循环体的里面，内循环体的外面。）

2）变量s 和t 可以将其类型定义为Integer （整型）吗？

（答案：不可以！因为8! 的值就已经超过整型所能表示的最大值32767，所以s 和t 必须定义成长整型（Long ），否则会发生溢出。）

本例中主要通过双重循环实现，其实还可以只用一重循环来完成本程序的功能。 将上述程序用一重循环优化一下：

由于n!=(n-1)!*n，即2!=1!*2，3!=2!*3，„„，10!=9!*10，所以上述程序段还可进行以下的优化：

Dim i As Integer, j As Integer

Dim s As Long, t As Long

s = 0

t = 1

For i = 1 To 10

t = t *i ‘求i!

s = s + t

Next i

Print "1!+2!+„„+10!="; s

执行流程为：

I=1，计算t=1*1=1!，s=0+1!=1!

I=2，计算t=1!*2=2!，s=1!+2!

I=3，计算t=2!*3=3!，s=1!+2!+3!

„„

I=10，计算t=9!*10=10!，s=1!+2!+3!+4!+5!+6!+7!+8!+9!+10!

注意：这时给t 赋初值1不可放在循环体内。

3．统计算法

统计问题在程序设计中也是经常遇到的。算法的基本思想是：程序中有多少个统计要求，就要定义多少个变量作为计数器，满足指定的计数要求，就将相应的计数器的值加1（执行类似于n=n+1的操作）。

例5-2-13 在文本框中输入一串字符，统计其中的字母、数字和其他字符的个数。 分析：

要统计满足指定要求的字符个数，应定义相应变量作为计数器，初值为0，每找到符合条件的字符，将指定计数器的值加1。

本题需要定义3个计数器n1、n2、n3，分别统计字母、数字和其他字符的个数，初值为0。对字符串中的字符逐个判断，如果是字母，n1执行加1操作，如果是数字，n2加1，否则n3加1。程序如下：

Private Sub Command1_Click()

Dim str As String, i As Integer, ch As String * 1

Dim n1 As Integer, n2 As Integer, n3 As Integer

n1 = 0: n2 = 0: n3 = 0 ‘计数器赋初值为0

str = Text1.Text

For i = 1 To Len(str)

ch = Mid(str, i, 1) ‘逐个取字符串中的每个字符赋给ch

If UCase(ch) = "A" Then ‘如果是字母，计数器n1加1

n1 = n1 + 1

ElseIf ch >= "0" And ch

n2 = n2 + 1

Else ‘如果是其他字符，计数器n3加1

n3 = n3 + 1

End If

Next i

‘分三行在文本框中输出统计的结果，Chr(13) & Chr(10)是回车换行符

Text2 = “字母的个数为" & n1 & Chr(13) & Chr(10)

Text2= Text2 & “数字的个数为” & n2 & Chr(13) & Chr(10)

Text2= Text2 & “其他字符的个数为” & n3

End Sub

4．求最大值和最小值算法

在N 个数中求最大值和最小值的思路是：定义一个变量，假设为max ，用来存放最大值，定义一个变量，假设为min ，用来存放最小值。一般将N 个数中的第1个数赋给max 和min 作为初始值，然后将剩下的每个数分别和max 、min 比较，如果比max 大，将该数赋给max ，如果比min 小，将该数赋给min ，即让max 中总是放当前的最大数，让min 中总是放当前的最小值，这样当所有数都比较完时，在max 中放的就是最大数，在min 中放的就是最小数。

例5-2-14 随机产生20个1到100之间的整数，打印输出其最大值和最小值。

分析：

根据随机函数Rnd ，在程序中要产生1到100之间的随机整数x 可用语句x = Int(Rnd*100)+1完成。

很显然，要产生20个随机整数，应该用For-Next 循环实现。根据求最大值和最小值算法思想，应先产生1个随机正整数，作为max 和min 的初始值，然后再利用循环产生剩下的19个数，分别和max 、min 进行比较，具体程序见下面：

Private Sub Form_click()

Dim i As Integer, x As Integer

Dim max As Integer, min As Integer

Randomize ‘ 随机函数初始化

max = Int(Rnd * 100) + 1

min = max „给max 和min 赋初值

For i = 1 To 19

x = Int(Rnd * 100) + 1 ‘产生1到100间的随机数

If x > max Then max = x

If x

Next i

Print “最大值是” & max

Print “最小值是” & min

End Sub

5．穷举算法

穷举法是循环程序中具有代表性的基本应用之一。穷举是一种重复型算法，它的基本思想是对问题的所有可能状态都一一测试，直到找到答案或将全部可能状态都测试过为止。

例5-2-15 有36块砖，要求36个人搬，1个男人搬4块，1个女人搬3块，两个小孩搬一块砖，要求一次全搬完，问男、女和小孩各有多少个？

分析：

假设男人用变量men 表示，女人用women 表示，小孩用children 表示，根据题目要求可以列出如下式子：

men+women+children=36 （1）

4*men+3*women+children/2=36 （2）

如果用算术来解方程，可以看出这是一个典型的不定方程，可能有多个解，所以只能采用穷举法，将所有可能的情况全部列出来，逐一进行测试。

由条件（2）并结合条件（1）可知：

男人(men)的可能取值范围为：0～8

女人(women)的可能取值范围为：0～11

可利用双重循环对所有可能的男人men 和女人women 的值进行选择，而一旦男人men 和女人women 的值确定下来，则根据条件（1）可知小孩children=36-men-women，如果此时children 为偶数，并且men 和women 、children 满足4*men+3*women+children/2=36，则表示找到一个合理的解。

根据上述分析，可以很方便地写出下列程序：

Private Sub Form_Click()

Dim men As Integer, women As Integer

Dim children As Integer

For men=0 To 8 ‘men取所有可能的值

For women=0 To 11 ‘women取所有可能的值

children=36-men–women ‘算出children 的人数(满足条件1)

If children Mod 2=0 And 4*men+3*women+children/2=36 Then ‘满足条件2 Print "男人有："; men; "人"

Print "女人有："; women; "人"

Print "小孩有："; children; "人"

End If

Next women

Next men

End Sub

6．判断素数

一个数如果只能被1和其本身整除，而不能被其他任何数整除，那么这个数就称为素数。比如2、3、5等就是素数。

例5-2-16 在文本框Text1中输入一个整数，界面如图5-2-1所示，判断它是否是素数，比如输入7，应输出“7是素数”的提示，如图5-2-2所示；输入24，应输出“24不是素数”的提示。

图5-2-1 图5-2-2

分析：

由素数的定义，判断任一个整数n 是否是素数，可以采用穷举的算法思想，将n 可能整除的数全部列出来（从2到n-1），如果有一个数能被n 整除，则n 不是素数，如果所有的数都不能被n 整除，则n 是素数。

这也是一个典型的循环程序，可设一个循环变量为I ，让I 从2变化到n-1，如果有一个I 能被n 整除，说明n 不是素数，下面就不用再进行判断，提前跳出循环；如果所有的I 都不能被n 整除，说明该数是素数，最后正常结束循环。

根据分析，很容易写出下列程序段：

n = Val(Text1.Text)

For i = 2 To n - 1

If n Mod i = 0 Then Exit For

Next i

关键是循环执行结束之后，如何知道n 是否是素数？

因为n 如果不是素数，肯定会有一个数能够被n 整除，循环会提前结束；n 如果是素数，从2到n-1没有一个数能够被n 整除，循环会正常结束。

循环结束后如何知道是提前跳出还是正常退出？

可以在循环结束后通过循环控制变量的值来判断。如果循环是正常结束，循环控制变量的值会超过终值；如果循环是提前跳出，循环控制变量的值会小于等于终值。

所以，在循环结束后可以通过循环控制变量的值来判断n 是否是素数，完整的程序如下： Private Sub Command1_Click()

Dim i As Integer, n As Integer

n = Val(Text1.Text)

For i = 2 To n - 1

If n Mod i = 0 Then Exit For

Next i

If i = n Then

MsgBox n & "是素数"

Else

MsgBox n & "不是素数"

End If

End Sub

优化一下：

其实只要从2到n/2或sqr(n)中的每个数都不能被n 整除，则n 就是素数。

通用的做法：

由于判断一个数是否是素数只能有两个结果：True 和False ，对于这种有两种判断结果的处理，程序设计中还经常采用标志变量法。

定义一个标志变量，类型为布尔型，假设命名为Flag 。如果n 是素数，Flag 的值为True ，如果n 不是素数，Flag 的值为False ，那么跳出循环后就可以根据Flag 的值判断n 是否是素数。

注意：布尔型变量的初始值为False 。

程序如下：

Private Sub Command1_Click()

Dim i As Integer, n As Integer

Dim flag As Boolean

flag = True ‘给标志变量赋初值为True

n = Val(Text1.Text)

For i = 2 To n - 1

If n Mod i = 0 Then

flag = False ‘如果I 能被n 整除，说明n 不是素数，将flag 赋值为False

Exit For

End If

Next i

‘Flag 赋初值为True ，如果n 是素数，则所有的I 都不能被n 整除，Flag 的值仍为True

‘如果n 不是素数，肯定存在一个I 能被n 整除，flag 的值为False

If flag = True Then ‘该条件也可写成If flag Then

MsgBox n & "是素数"

Else

MsgBox n & "不是素数"

End If

End Sub

注意：

标志量的做法并不局限在素数的判断中，在程序设计中，如果需要在两种状态之间进行识别或结果为是或否、成立或不成立等两种结果时，都可以考虑用标志量法。

7．求最大公约数和最小公倍数

求任意两个正整数的最大公约数，可用辗转相除法来求。

假设要求任两个整数m 和n 的最大公约数，辗转相除法的算法思想是：先求m 和n 的余数r ，如果余数r 不等于0，则将n 的值赋给m ，将r 的值赋给n ，再不断的求新的m 和n 的余数r ，直到r 的值等于0为止，这时m 的值就是要求的最大公约数。

很显然，这也是个循环程序，由于不断地求m 和n 的余数r 以及给m 和n 赋新值的操作需要多次执行，所以应该作为循环体的内容，程序段如下：

r = m Mod n

m = n

n = r

注意：由于循环程序次数不确定，应采用do-loop 循环结构，循环执行的终止条件为r=0。

例5-2-17 在两个文本框Text1和Text2中分别输入两个正整数，单击命令按钮Command1后在窗体上输出其最大公约数。

分析：

根据前面的分析，知道循环体的内容和循环终止条件，很容易写出对应的Do-Loop 型循环程序。

Private Sub Command1_Click() Dim m As Integer, n As Integer

Dim r As Integer ‘定义存放余数的变量r m = Val(Text1.Text) n = Val(Text2.Text)

Print m; "和"; n; "的最大公约数为"; Do

r = m Mod n m = n n = r

Loop Until r = 0 Print m End Sub 考虑一下：

1）可以将第一条print 语句放在执行循环以后吗？

（答案：不可以。因为执行完循环后m 和n 已经不是原来的数值了） 2）上述循环程序段可以改为下面的程序段吗？

Do Until r = 0 r = m Mod n m = n n = r Loop

（答案：不可以。因为在执行循环前r 没有被赋值，r 初始值为0，所以循环终止条件开始就成立，循环一次也不执行）

如果希望用Do Until-Loop结构来编写程序求最大公约数，可以这样编写： r = m Mod n Do Until r = 0 m = n n = r

r = m Mod n Loop

思考一下：循环结束后，最大公约数为多少？ （答案：变量n 的值就是所要求的最大公约数）

将以上程序添加相应语句就可完成求最小公倍数的功能（M 和n 的最小公倍数等于m*n/m和n 的最大公约数）。

程序如下：

Private Sub Command1_Click() Dim m As Integer, n As Integer Dim r As Integer Dim t As Integer m = Val(Text1.Text) n = Val(Text2.Text)

t = m * n ‘记录m*n的初始值 Print m; "和"; n; "的最大公约数为"; Do

r = m Mod n m = n n = r

Loop Until r = 0

Print m; ",最小公倍数为"; t / m End Sub 8．迭代

迭代的思想在程序设计中应用也是非常广泛的，所谓迭代其实就是在程序设计过程中，对指定的变量不断用新值取代旧值或用旧值推出新值的过程。可以看出，上面的辗转相除法求任意两个正整数的最大公约数算法过程也是一种迭代。

迭代算法的程序编制时要从三方面着手：确定迭代公式（也就是循环体的内容）、迭代变量的初始化以及迭代的终止条件。

1）精确迭代算法

例5-2-18 兔子繁殖问题：

意大利数学家Fibonacci 曾提出一个有趣的问题：设有一对新生兔子，从第三个月开始它们每个月都生一对兔子。按此规律，并假设没有兔子死亡，一年后共有多少对兔子。要求打印数列的前20项，且一行输出5个。

分析：

可以发现每月的兔子数组成如下数列： 1,1,2,3,5,8,13,21,34,……，稍加分析，可以看出：数列从第3项开始，每1项都是其前2项之和。

假设第1项元素用f1表示，第2项元素用f2表示，每次新元素用f 表示。

可以知道，开始时f1=1，f2=1 。

第3月的兔子数f 等于第1个月和第2个月的兔子数之和，所以f=f1+f2=2 如何求第4个月的兔子数？

由于第4个月的兔子数等于第2和第3个月的兔子数之和，此时f1中放第1个月的兔子数，f2中放第2个月的兔子数，f 中放第3个月的兔子数。由于求第4个月的兔子数时已经不需要第1个月的兔子数，所以可以将f1中放第2个月的兔子数，即f1=f2，将f2中放第3个月的兔子数，即f2=f，用变量f 存放第四个月的兔子数，很显然，f=f1+f2。

可以看出，第5个月、第6个月„„的兔子数都可以依次推出来。

由于从第3个月开始，每个月的兔子数f 都是等于f1+f2，即f=f1+f2。为了求出下一个月的兔子数，再执行f1=f2，f2=f更新f1和f2的值，所以很容易确定循环体的内容为：

f=f1+f2 f1=f2 f2=f

其中f1和f2初值为1。 可以看出：

从第3个月开始，每个月的兔子数f 要由前面的兔子数f1和f2 推出，并在求下1个月的兔子数之前要用新值对f1和f2的值进行更新。这就是迭代算法。

在本例中，迭代的次数是确定的，并且每次迭代后都可以得到一个确定的值，象这样的迭代称为精确迭代。

根据前面的分析，可以编写程序如下： Private Sub Form_click()

Dim f1 As Integer, f2 As Integer Dim i As Integer，f As Integer f1 = 1: f2 = 1 ‘给f1和f2赋初值 Print f1; f2; For i = 3 To 20 f = f1 + f2 f1 = f2 f2 = f

Print f; „输出每月的兔子数

If i Mod 5 = 0 Then Print „控制每行输5个 Next i End Sub 2）近似迭代算法

如果迭代算法的次数不确定，且最终得不到精确的数值，象这样的迭代称为近似迭代。 一元高次方程的求解一般没有通用的求根公式，所以常用近似迭代法来求方程的近似根。

近似迭代法求方程f(x)=0的根是将其改写为： x=ψ(x)

选取适当的初值x 0，便可通过重复迭代构造序列：x 0,x 1,x 2, ……,x n , …… 若该数列收敛，则极限值就是方程的一个解。

可以看出，用近似迭代法求一元高次方程的根，只要找出其迭代公式x=ψ(x)就可以了。 牛顿迭代法和二分迭代法都是对一元高次方程求解的近似方法。 (1) 牛顿迭代法

牛顿迭代法求f(x)=0的根是在根的附近找一个初值作为x 0，过x 0做方程的切线，与x 轴的交点为x 1，再过x 1作切线，交x 轴于点x 2，……。可以知道，只要给定一个初始值x ，通过以上操作，可不断的得到新的值x ，并且x 无限的接近函数在x 轴的交点，即方程的根。所以经过若干次迭代后，可得到方程较高精度的近似根。牛顿切线法迭代公式为

xi+1 = xi － f(xi )/f’(xi )

其中：f ’(xi ) 是f(xi ) 的导数 注意：

牛顿迭代的结束条件：当|x i+1-x i |≤ε或|f(xi )|≤ ε时， x i+1就作为方程的近似根。 这里不能将结束条件写成|x i+1-x i |=0或|f(xi )|=0，因为计算机中实型数据是近似表示，不能精确的表示数据0，如果写成这样的条件，可能永远都满足不了，所以，对于正数而言，如果比给定的误差值小，比如小于10-6，就认为该数近似为0。

例5-2-19 编写程序，利用牛顿迭代法求方程x 3-x 4+4x2-1=0在x 0=0.5附近的一个根，要求精确到10-7。

分析：

根据前面的牛顿迭代公式，可以得出： A ）循环初值 x=0.5

B ）迭代公式 x = x- (x3-x 4+4x2-1) / (3x2- 4x3 + 8x) （循环体的内容） C ）结束条件： | x3-x 4+4x2-1|

确定了循环体的内容、循环的结束条件和循环量的初值，可以很方便的编写程序如下： Private Sub Command1_Click() Dim x As Single, Eps As Single

x=InputBox("输入初始值x:", "牛顿迭代法") Eps=InputBox("输入允许误差Eps"," 牛顿迭代法") Do

x =x - (x ^ 3 - x ^ 4 + 4 * x ^ 2 - 1) / (3 * x ^ 2 - 4 * x ^ 3 + 8 * x) Loop Until Abs(x ^ 3 - x ^ 4 + 4 * x ^ 2 - 1)

（2）二分迭代法算法

如果方程f(x)=0在区间[a,b]上单调，并且f(a)与f(b)异号，则在区间[a,b]上必有一个

实根。

用二分迭代法求方程f(x)=0 在区间[a,b]上的实根，基本思想是：在区间[a,b]上取中点c=(a+b)/2，若f(a)*f(c)0，则实根在区间[c,b]中，将c 赋给a ；在新区间[a,b]中再取中点c ，继续做如上操作，直到|a-b|的值小于给定的误差精度值。

可以知道，在取中点的过程中，区间[a,b]在不断地缩小，a 和b 的值不断的接近方程和x 轴的交点，即方程的根，直到|a-b|的值小于给定的误差精度值，这时a 或b 就是方程的根。

例5-2-20 设计一个用二分法求方程f(x)=x3-x 4+4x2-1=0在区间[0，1]上的一个实根，要求精确到10-7。

分析：

根据二分法的思想，应该定义3个变量，分别是a 、b 和c ，初始时a=0，b=1，c 表示区间的中点。

循环体的内容为： c=(a+b)/2

如果f(a)*f(c)

确定了循环体的内容、循环的结束条件和循环量的初值，可以很方便的编写程序如下 Private Sub Form_click()

Dim a As Single,b As Single,c As Single,e As Single e = InputBox("请输入误差精度") a = 0: b = 1

Print “在误差” & e & “范围内, 方程在[0,1]上的根为:”; Do

c = (a + b) / 2

If (a^3 -a^4+4*a^2-1)*(c^3-c^4+4*c^2-1)

Loop Until Abs(a - b)

9．常见数学问题的相关算法

数学问题在VB 程序设计中应用非常广泛，最常用的有求因子、回文数、反序数、升序数等问题。

1）求因子问题

一个数n 的因子是指在1到n-1的所有数中能被该数整除的数。

根据定义，如果用程序来输出一个数n 的所有因子，可用如下的程序段实现： For i = 1 To n - 1 If n Mod i = 0 Then Print i; End If Next i 延伸一下：

求因子问题在判断任意两个数m 和n 互质中也经常用到。

如果任意两个数m 和n 除了1之外没有相同的因子，则称两个数互质。判断任意两个数m 和n 是否互质，一般有两种方法：

A ）两个数的最大公约数为1

如果任意两个数m 和n 的最大公约数为1，那么这两个数肯定互质，所以可以利用前面介绍的求最大公约数的算法判断。

B ）根据两个数互质的定义来判断，即这两个数除了1之外有没有公共因子，如果有，则两个数不互质；如果除了1之外没有其他公共的因子，则两个数互质。

对于任意两个正整数m 和n ，假设m

因为两个数是否互质只有两个结果：是和否，所以也可以用标志变量法来判断。 根据前面的分析，很容易写出下列程序段： flag = True For i = 2 To m

If n Mod i = 0 And m Mod i = 0 Then ‘如果有一个数i 能同时被m 和n 整除，说明不互质

flag = False Exit For End If Next i

循环结束后，可以根据flag 的值判断两个数是否互质。 结合在素数判断中的处理，大家也可以将上面的程序段改为： For i = 2 To m

If n Mod i = 0 And m Mod i = 0 Then Exit For Next i

跳出循环后，就可以根据循环控制变量和终值的关系判断两个数是否互质：如果i>m，说明n 和m 互质，否则，n 和m 不互质。

2）取得数的各位数字

编写程序解决一个数字是否是回文数、升序数等问题时，都需要取得数的各位数字进行判断，下面介绍如何获得一个数中的各位数字的两种通用方法。

（1）利用\和Mod 运算符实现

整除\和求余数Mod 运算符经常配合使用求一个数的各位数字。 对任一数字，比如n=384，定义变量r 来存放每次获得的数字。 i) 执行r=n mod 10就可以得到其个位数r=4

执行n=n\10就可以得到n=38。

ii) 再执行r=n mod 10就可以得到其个位数r=8 执行n=n\10就可以得到n=3

iii) 再执行r=n mod 10就可以得到其个位数r=3 执行n=n\10就可以得到n=0

可以看出，一个三位的正整数n 最多只需要3次操作就可以获得从个位到百位的每个数字。很显然，r=n mod 10和n=n\10是循环体的内容，循环的执行直到n=0为止。

对应的程序段如下：

Dim n As Integer, r As Integer n = InputBox("input n") Do

r = n Mod 10 n = n \ 10 Print r

Loop Until n = 0

通过这个程序段就可以获得任一正整数从个位、十位到最高位的每个数字，比如输入384，依次可以获得4、8、3三个数字。

（2）将数值转化为字符串进行处理

由于对字符串的操作可以通过mid 函数很方便地获得每个字符，所以可以将数值转化为数字字符串来获得每个数字。

（i) 将数值变量n 的值转化为数字字符串str

str=cstr(n) ‘cstr 函数实现将数字转化为数字串，并且不包含前置空格 （ii) 获得数字字符串str 中的每个字符

For i = 1 To Len(str) ‘Len 函数返回str 的串长 ch = Mid(str, i, 1) „„ Next i

对应的程序段如下：

Dim n As Integer, str As String Dim i As Integer, ch As String * 1 n = InputBox("input n")

str = CStr(n)

For i = 1 To Len(str) ch = Mid(str, i, 1) Print ch， Next i

通过这个程序段就可以获得任一正整数从最高位到个位的每个数字，比如输入384，依次可以获得3、8、4三个数字。

3）判断一个数是否是回文数

一个数如果对应数字都相同，则称该数为回文数，如121、1342431等。

由于判断回文数时需要获得数值的高位和对应的低位数字进行比较，如果对应位置的数字都相同，则该数是回文数；如果有对应位置的数字不相同，则数字不是回文数，所以用字符串的方法处理比较方便。

判断一个数x 是否是回文数，可用如下程序段： Dim x As Integer, i As Integer Dim s As String

x = InputBox("输入x 的值")

s = CStr(x) ‘注意：只能用Cstr ，而不能用str For i = 1 To Len(s) / 2

‘如果有对应位置的数字不相同就提前跳出循环

If Mid(s, i, 1) Mid(s, Len(s) - i + 1, 1) Then Exit For Next i

If i > Len(s) / 2 Then ‘如果循环正常结束，说明对应位置的数字都相同，是回文数

Print x; "是回文数" End If

4）判断一个数是否是升序数

升序数是指右边的数字总是大于等于左边的数字。判断一个数是否是升序数可以采用以下算法思想：对要判断的数，从左边第二个数字开始，看它是否比左边的数字大，如果是，就继续判断下去，直到结束；如果不是，说明不满足升序数的条件，就提前跳出循环，最后根据循环控制变量的值来判断是否是升序数。

在取数字时，从数字的高位逐个取数字进行判断，所以用字符串的方法处理比较方便。 判断一个数x 是否是升序数，可用如下程序段： Dim x As Integer, i As Integer Dim s As String

x = InputBox("输入x 的值") s = CStr(x)

For i = 2 To Len(s) ‘从左边第二个数字开始取，直到结束

‘如果右边的数字比左边数字小，说明不符合升序的条件，则提前跳出循环

If Mid(s, i, 1)

If i > Len(s) Then Print x; "是升序数" End If 考虑一下：

（1）将上述程序段改为下面的程序段对不对？错在哪里？ Dim x As Integer, i As Integer Dim s As String

x = InputBox("输入x 的值") s = CStr(x)

For i = 2 To Len(s) ‘从左边第二个数字开始取，直到结束 If Mid(s, i, 1)

Print x; "不是升序数"

Else

Print x; "是升序数" End If Next i

（2）判断一个数是否是回文数或升序数，除了用上面的方法判断之外，还可以用什么方法？

其实，这里的判断方法和前面的素数判断类似，因为最终只有两种结果，所以也可以用标志变量法来实现。

比如，判断一个数x 是否是升序数，用标志变量法编写的程序段如下： Dim x As Integer, i As Integer Dim s As String, flag As Boolean x = InputBox("输入x 的值") s = CStr(x) flag = True

For i = 2 To Len(s) '从左边第二个数字开始取，直到结束 If Mid(s, i, 1)

If flag Then ‘如果标志变量flag 值为True ，则x 是升序数 Print x; "是升序数"

End If