基本算法介绍

基本算法介绍 算法实际上就是用计算机解决某个问题的方法和步骤，学习完循环和分支结构的语句后，实际上就可以编写任何复杂的程序了，而在程序的编写之前必须掌握程序算法的基本思想，即对不同问题处理时的计算机的解题步骤，下面就介绍一些基本的算法思想。 注意：对某一类问题的解决，有很多解决的方法，因此，同一个问题的程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ，针对不同的算法可能编写出不同的程序，而我们在下面介绍的只是对某类问题的通用算法思想。另外，算法的设计不针对某一个具体的问题，希望大家在学习时，不要仅满足掌握相关例题的程序设计，而要学习算法的基本思想，学会以后遇到类似的问题时能运用该思想来解决问题。 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 < 0.000001 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 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) <= "Z" And UCase(ch) >= "A" Then ‘如果是字母，计数器n1加1 n1 = n1 + 1 ElseIf ch >= "0" And ch <= "9” Then ‘如果是数字，计数器n2加1 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 < min Then min = 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) 选取适当的初值x0，便可通过重复迭代构造序列：x0,x1,x2,……,xn,…… 若该数列收敛，则极限值就是方程的一个解。 可以看出，用近似迭代法求一元高次方程的根，只要找出其迭代公式x=ψ(x)就可以了。 牛顿迭代法和二分迭代法都是对一元高次方程求解的近似方法。 (1) 牛顿迭代法 牛顿迭代法求f(x)=0的根是在根的附近找一个初值作为x0，过x0做方程的切线，与x 轴的交点为x1，再过x1作切线，交x轴于点x2，……。可以知道，只要给定一个初始值x，通过以上操作，可不断的得到新的值x，并且x无限的接近函数在x轴的交点，即方程的根。所以经过若干次迭代后，可得到方程较高精度的近似根。牛顿切线法迭代公式为 xi+1 = xi － f(xi)/f’(xi) 其中：f’(xi)是f(xi)的导数 注意： 牛顿迭代的结束条件：当|xi+1-xi|≤ε或|f(xi)|≤ ε时， xi+1就作为方程的近似根。 这里不能将结束条件写成|xi+1-xi|=0或|f(xi)|=0，因为计算机中实型数据是近似表示，不能精确的表示数据0，如果写成这样的条件，可能永远都满足不了，所以，对于正数而言，如果比给定的误差值小，比如小于10-6，就认为该数近似为0。 例5-2-19 编写程序，利用牛顿迭代法求方程x3-x4+4x2-1=0在x0=0.5附近的一个根，要求精确到10-7。 分析： 根据前面的牛顿迭代公式，可以得出： A）循环初值 x=0.5 B）迭代公式 x = x- (x3-x4+4x2-1) / (3x2- 4x3 + 8x) （循环体的内容） C）结束条件： | x3-x4+4x2-1|<10-7 确定了循环体的内容、循环的结束条件和循环量的初值，可以很方便的编写程序如下： 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)<=Eps Text1.Text=Str(x) End Sub （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，则实根在区间[a,c]中，将c赋给b；若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-x4+4x2-1=0在区间[0，1]上的一个实根，要求精确到10-7。 分析： 根据二分法的思想，应该定义3个变量，分别是a、b和c，初始时a=0，b=1，c表示区间的中点。 循环体的内容为： c=(a+b)/2 如果f(a)*f(c)<0，b=c,否则，a=c 循环的结束条件：| a-b|<10-7 确定了循环体的内容、循环的结束条件和循环量的初值，可以很方便的编写程序如下 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)<0 Then ‘判断f(a)与f(c)是否异号 b = c Else a = c End If Loop Until Abs(a - b) < e Print a End Sub 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，假设mm，说明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) < Mid(s, i - 1, 1) Then Exit For Next i 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) < Mid(s, i - 1, 1) Then 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) < Mid(s, i - 1, 1) Then flag = False Exit For End If Next i If flag Then ‘如果标志变量flag值为True，则x是升序数 Print x; "是升序数" End If 数组相关算法程序设计 1．数组的排序 假设已将n个数存放在数组中，要求将其按从小到大的顺序排序。 排序是程序设计中很重要的算法，排序的算法有很多，这里介绍两种常见的算法：选择法和冒泡法。 1）选择法排序 选择法的排序思想是： a、 将第一个数依次与后面的n-1个数进行比较，如果有一个数比它小，就执行交换操作，经过这一轮比较，产生最小数放在第一个数中。 b、 将第二个数再依次与后面的n-2个数进行比较，如果有一个数比它小，就执行交换操作，经过这一轮比较，产生第二小的数放在第二个数中。 c、 重复执行以上操作，最后是第n-1个数和第n个数进行比较，如果后者小于前者，执行交换，否则保持原值。 从以上的排序过程可以看出：n个元素排序要进行n-1轮的比较，每一轮中要进行若干次比较，所以排序的算法是一个双重循环。若用循环变量i表示比较的轮数，则i的值从1变化到n-1，当i=1时， a(1)分别与a(2)到a(n)的每一个元素进行比较，一旦有元素比a(1)小就执行交换；当i=2时， a(2) 分别与a(3)到a(n)的每一个元素进行比较，一旦有元素比a(2)小就执行交换；所以在第i轮的比较中， a(i)分别与a(i+1)到a(n)的每一个元素进行比较，一旦有元素比a(i)小就执行交换。若用j表示内循环的控制变量，则j的值是从i+1变化到n。因为涉及到交换，所以还需定义变量Temp作交换时的临时变量。 例6-15 随机产生10个三位正整数，用选择法将其按增序排序，并输出原始顺序和排序后的顺序。（分析见上面） 程序如下： Option Base 1 Private Sub Form_Click() Dim a(10) As Integer, i As Integer, j As Integer Dim temp As Integer Randomize Print "原始顺序：" For i = 1 To 10 a(i) = Int(Rnd * 900) + 100 ‘利用随机函数产生数组元素的值 Print a(i); Next i Print For i = 1 To 9 ‘10个元素，外围循环需要9次 For j = i + 1 To 10 ‘每次a(i)都和其后面的每个元素作比较 If a(i) > a(j) Then ‘如果a(i) > a(j)就执行交换 temp = a(i) a(i) = a(j) a(j) = temp End If Next j Next i Print "排序后的顺序：" For i = 1 To 10 Print a(i); Next i End Sub 优化一下： 从上面排序的执行可以看出，在第i轮的比较中，只要有一个数比它小就执行交换，实际上这里有很多交换是无效的，因为每一轮比较中，a(i)只需与当前的最小元素执行一次交换既可，无需发现比它小的数就执行交换。因此可将选择法优化一下，过程如下： a、 对有n个数的序列，从中选出最小的数，与第1个数交换。 b、 除第1个数外，其余n-1个数再按a的方法选出最小的数，与第2个数交换。 c、 重复以上操作，直到最后只剩下一个数时结束。 假设数组a中有5个元素，下标从1到5，分别被赋值为 12、23、15、34、9。 排序的执行过程如下所示：（下划线部分表示执行交换的两个数组元素） 原始数据 12、23 、15、34、9 a(1) a(2) a(3) a(4) a(5) 第1遍交换后 9 、23 、15、34、12 a(2) a(3) a(4) a(5) 第2遍交换后 9 、12 、15、34、23 a(3) a(4) a(5) 第3遍交换后