VB程序设计的常用算法09.doc

Visual Basic 常用算法从逻辑结构上看，应用程序= 算法+ 数据结构。（ 1）数据结构（ Data-Structure ），计算机将数据元素依据某种逻辑联系进行存储和组织的方式。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重依赖于是否选择了最优的数据结构。选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。（ 2）算法（ Algorithm）， 由基本运算及规定的运算顺序所构成的完整解题步骤。一个算法应该具有以下五个重要的特征：有穷性 ，算法必须保证执行有限步之后结束。确切性 ，算法的每一步骤必须有确切的定义。输入 ，算法有0 个或多个输入，以描述运算量的初始值。0 个输入是指算法本身包含了初始值。输出 ，算法有一个或多个输出，以反映对输入数据加工后的结果。没有结果的算法是毫无意义的。可行性 ，算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。计算机科学家尼克劳斯-沃思曾著过一本著名的书数据结构十算法= 程序，可见算法在计算机科学界与计算机应用界的地位。这算法的描述 ：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果） 、采用什么结构、使用什么语句以及如何安排这些语句等。程序（ Programme ）就是用计算机语言描述的算法。 流程图（ Flow Charts ）就是图形化的算法。 解决同一问题可以有多种算法描述 。实际问题的算法种类繁多，总体上可以分为两大类： 数值算法 和非数值法。对 VB 程序语言设计的初学者，可能会感到掌握控件的使用不难，难得的是理解和掌握算法。但是，算法是程序的核心、编程的基础，离开算法，一事无成。我们将介绍常用的 VB 算法。一、常见数学问题算法1、累加和连乘累加 是在原有和的基础上在循环体中每次加上一个数，最后根据条件结束累加，最终得到累加和。连乘 是在原有积得基础上在循环体中每次乘以一个数，最后根据条件结束连乘，最终得到连乘积。此类问题都要结合循环结构实现，根据问题确定循环变量的初值、终值或结束条件。【注意】 累加和变量、连乘积变量必须在循环外赋初值。一般累加和初值为0、连乘积初值为1。 对于多重循环，赋初值在外循环体外还是在内循环体外根据实际问题决定。【计算的近似值】用公式：1111计算，直到最后一项的绝对值小于10- 6为止。3574PrivateSub Form_Click( )Dims As Integer,n As Single, t As Single,pi As Singlet = 1' 第一项pi = 0' 累加和初始值为0n = 1' 每一项的分母值s = 1' 第一项符号Do While(Abs(t) >= 0.000001)pi = pi + t' 将每一项求和，得到/4 的近似值n = n + 2' 产生每一项的分母值s = -s' 产生每一项的符号值t = s / n' 产生每一项Looppi = pi * 4Print" =" piEndSub【斐不拉齐数列】输出斐不拉齐数列（Fibonacci ）的前40 个项： 1、1、 2、 3、 5、 8、 13、 F11n1数列中的第1、2 项为 1，其后每项都等于其前两项之和，其递推公式：F11n2FnFn 1Fn 2 n3PrivateSub Form_Click( )Dimf1 As Long,f2 As Long,i As Integerf1 = 1' 数列第一项f2 = 1' 数列第二项Printf1, f2,' 打印数列前两项Fori = 3To40' 循环输出第3至40项f3 = f1 + f2' 计算下一个数列项Print f3,' 打印输出下一个数列项f1 = f2' 为下一个数列项计算做准备f2 = f3' 为下一个数列项计算做准备If i Mod 5 = 0Then Print'当每行输出 5个以后换行NextiEndSub【计算 e 的近似值】 求自然对数e 的近似值，要求其误差小于0.00001，近似公式为：11111ne1111!2!3!n!i 0i!i 01i!PrivateSubForm_Click( )Dimi%,n&,t!,e!e = 0'存放累加和i = 0'循环控制变量n = 1'存放连乘积t = 1'级数第 i 项初始值Do Whilet > 0.00001e = e + t'将每一项加入累加和i = i + 1'产生阶乘下一个乘数n = n * i'乘以乘数i 得到每一项的阶乘t = 1 / n'产生每一项EndLoopPrintSub" 计算了"i;" 项的和是"e【计数统计】用随机函数产生100 个 0， 99 范围内的随机整数，统计个位上的数字分别为1， 2， 3， 4，5，6， 7，8， 9，0 的数的个数并打印出来。使用数组来处理，用数组a(1 to 100) 存放产生的确100 个随机整数， 数组 x(1 to 10) 来存放个位上的数字分别为 1， 2， 3， 4，5， 6， 7，8， 9， 0 的数的个数。即个位是1 的个数存放在x(1) 中，个位是2 的个数存放在x(2)中，个位是0 的个数存放在x(10) 。PrivateSubForm_Click( )Dima(1 To 100) , x(1 To 10)AsIntegerDimi, pAsIntegerFori = 1To 100'产生100 个 0 ， 99 范围内的随机整数，每行10 个打印出来a(i) = Int(Rnd * 100)Ifa(i) < 10ThenPrintSpace(2);a(i);ElseEndIfPrintSpace(1);Ifi Mod 10 = 0Thena(i);PrintNexti'统计个位上的数字分别为1， 2， 3， 4，5， 6， 7， 8， 9， 0x(1),x(2),.,x(10) 中，将统计结果打印出来Fori = 1To 100p = a(i)Mod10' 求个位上的数字Ifp = 0Thenp = 10' 统计数字的个数x(p) = x(p) + 1NextiPrint" 统计结果 "Fori = 1To10' 打印计数统计的结果p = iIfi = 10Thenp = 0Print" 个位数为 " + Str(p) + "共 " + Str(x(i) + "个 "NextiEndSub的数的个数，并将统计结果保存在数组#2、最大公约数（最小公倍数）求两个正整数X 和 Y 的最大公约数，可以使用递推算法，辗转相除得到。用M 表示被除数，N 表示除数（ M>N ）， R 表示余数。 输入两个正整数M 和 N ，且 M>N ；计算 M 除以 N 得余数 R；如果 R 不为 0 时，使 M=N和 N=R 后转移到第2 步再次计算；如果 R=0 时， N 就是所求的 最大公约数 。最小公倍数 就是两个数的乘积再除以最大公约数的结果。PrivateSubCommand1_Click( )Dimx, y, m, n, rAsIntegerx = Val(Text1.Text):y = Val(Text2.Text)' 从文本框中输入连个正整数Ifx > yThen'使得 M>N ，即将两个正整数排序m = x:n = yElsem = y:n = xEndIfDo'求最大公约数r = mModnm = n:n = rLoopWhile r <> 0'求最小公倍数并分行打印出两个结果Label3.Caption = "最大公约数为： " & m &vbCrLf& " 最小公倍数为： " & x * y / mEnd Sub【说明】 x 和 y 保存了两个正整数的原值，以便最后计算最小公倍数；If 语句保证了 m>n，但省略 If 语句也不会出错，因为r = m Mod n ： m = n : n = r 会自动将较大的数交换到m 中。#3、穷举法解方程将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现，也称为“枚举法” 。这是一种“在没有其它办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。【百钱买百鸡】我国古代数学家张丘建在算经中曾提出一个有趣的“百钱买百鸡 ”问题。 题意 为：已知用 5 文钱可以买一只公鸡，3 文钱可以买1 只母鸡，用1 文钱可以买3 只小鸡，如果要用100 文钱买100 只鸡。请问公鸡、母鸡和小鸡应各买多少只？5x3 yz（ 1）分析： 设变量 x 表示公鸡， y 表示母鸡， z 表示小鸡。则有方程组：1003xyz 100上述方程组中，有 3 个求和数，但只有两个方程，帮方程组有多个解。为解决这类问题一般需要使用穷举法。即先对各求知数的所有可能进行穷举，然后再依次判断哪些值能满足要求。PrivateDimForSubForm_Click( )x As Integer,y As Integer,x = 0To100Fory = 0To100Forz = 0To100num = num + 1If(x + y + z = 100Print" 公鸡 ="EndIfNextzz As Integer,num As LongAnd5 * x + 3 * y + z / 3 = 100)x," 母鸡 ="y," 小鸡 ="ThenzNextyNextxPrint" 方法一的If语句测试了"num;" 次 "EndSub（ 3）通过分析可知，公鸡、母鸡和小鸡的可能值为：PrivateSubForm_Click （）Dimx As Integer,y As Integer,z As Integer,Forx=0To20Fory=0To33z=100-x-ynum=num+1If5*x+3*y+z/3=100Then020、 033、 100- x- y。num As IntegerNextPrintEndify, x“公鸡 =” ; x;“母鸡 =” ; y;“小鸡 =” ; zEndPrintSub" 方法二If语句测试"num;" 次 "【说明】 通过 num 变量可以测试循环的次数，还可以使用系统变量Now 在方法二中两层循环的Next 相邻时，可以合而为一：Nexty, x 。【注意】 在多重循环中，为了提高运行的速度，要考虑对程序优化问题： 利用已知条件，尽量减少循环的次数。 合理地选择内、外层的循环控制变量，即将循环次数多的放在内循环。 尽量少用变体型变量，在方法一中x、 y、 z 使用变体型，运行的时间可由测试循环使用的时间。4s 减少到 19s。【换零钱程序】将一张面值为100 元的人民币等值换成100 张5 元、1 元和0.5 元的零钞，要求每种零钞不少于1 张，问有哪几种组合？PrivateSubForm_Click( )Dimi%,j%,k%Print"5 元", "1元", "0.5元"Fori = 1To20Forj = 1To100 - ik = 100 - i - jIf5 * i + 1 * j + 0.5 * k = 100Printi, j, kEndIfNextjNextiEndSubThen#4、素数问题素数（质数）就是只能被1 和它本身整除的整数。 如果整数m 不能被 2m - 1 之间的数所整除，则m 是素数。反之，如果找到一个2 m- 1 之间的数能够整除m，则证明m 不是素数。结合循环结构使用穷举法测试2 m- 1。 实际上，如果整数m 能被分解为两个因子a 和 b，那么其中较小一个因子必定小于m0.5。 只要找到一个能整除m 的数 x 后，已经能证明m 不是素数， x 的后续数据可以不再验证，可使用Exit for 有条件提前退出循环。【穷举法素数判断】输入一个正整数m，并判断m 是否为素数。PrivateSubForm_Click（）Dimm As Integer,k As Integer,i As Integerm=Val(InputBox(“请输入一个正整数： ” )k=Sqr(m)'求 m 的平方根Fori=2To k'从 2 到 k 测试是否为m 的因子，如果是素数则正常退出循环IfmModi=0 Then Exit For'找到一个因子，不是素数则提前退出循环NextiIf i>k Then'根据结束循环的方式，打印素数判断的结果Printm,”是素数 ”ElsePrintm,”不是素数 ”EndIfEndSub【说明】如果程序是因为找到了一个能整除m 的数，而通过 Exit for 语句退出 For 循环的，则 i<=Sqr(m) ；反之，如果是正常结束循环的话，则应执行i=k+1 。因此，可以根据是否（i>k ）来判断“是素数”或“不是素数”。【随机产生素数】随机产生20 个两位素数。PrivateSubForm_Click （）Dimm As Integer,count As Integer,i As Integer,k As IntegerRandomizeDoUntilcount>=20m=Int(Rnd*90)+10' 随机产生一个两位十进制数k=Sqr(m)' 判断该数是否素数Fori=2TokIfm Mod i=0ThenExit ForNextiIfi>kPrintThen m;” ”;' 如果是素数则打印输出到窗体上，并计数加1count=count+1Ifcount Mod 10=0ThenPrint' 一行打印输出10 个EndIfLoopEndSub【说明】 首先通过随机函数产生一个两位整数，然后再判断该整数是否是素数。如果是素数，则素数计数器 count 加 1；如果不是素数，则产生下一个随机数。程序反复执行，直到产生 20 个满足条件的随机素数为止。 外循环是一个Do UntilLoop 循环，内循环是一个ForNext 循环。 语句 “ Ifcount Mod 10=0ThenPrint ” 的作用，是保证每行输出10 个素数。【寻找素数】找出 100 以内的素数。PrivateSubCommand1_Click( )Dimi As Integer,m As IntegerText1.ForeColor = vbRedText1.Text = ""Form = 2To100Fori = 2Tom - 1Ifm Mod i = 0ThenGoToNotS'不是素数则停止判断，直接退出当前的两层循环NextiText1.Text = Text1.Text&""&mNotS:Next mEndSub不用上述循环体内只要能被i 整除，就不可能是素数，可利用GoTo 语句，通过设计一个标志变量Flag，在循环体内用GoTo 语句退出循环。但程序中尽量少用或Flag 记录素数的判断结果，在循环结束后再根据Flag显示判断结果。PrivateSubCommand2_Click( )Dimi As Integer,m As Integer,Flag As BooleanText1.ForeColor = vbBlueText1.Text = ""Form = 2To100Flag = True'假设待判断的m 为素数，将标志变量修改为TrueFori = 2Tom - 1Ifm Mod i= 0ThenFlag = False'不是素数，则将素数标志变量修改为NextiIfFlagThenText1.Text = Text1.Text&""&mNextmEndSubFalse#5、最大值和最小值在若干个数中求最大值，一般先假设一个较小的数为最大值的初值，若无法估计较小的值，则取第一个数为最大值的初值，然后将每一个数与最大值比较，若该数大于最大值，将该数替换为最大值，依次逐一比较。【最短残料】 有一根长度为321m 的钢材料，要将它截取成两种规格的短料，规格17m 和 27m，每种至少1 段，分隔成a、 b 各多少段后，剩余的残料r 最少？该题利用二重循环求残料r 的最小值正数，因为残料不可能为负。a、b 的长度分别为PrivateSubForm_Click( )Dima%,b%,r!,ia%,ib%, t!r = 321Forb = 1ToInt(321 - 17) / 27)Fora = 1ToInt(321 - b * 27) / 17)t = 321 - b * 27 - a * 17Ift >= 0 And t < rThenr = t' 求最短的残料ia = a' 最短残料时a 的段数ib = b' 最短残料时b 的段数'最小值初值取钢材料的长度'b 最多的段数'a 最多的段数'当前的残料'当前的残料 >= 零并且比最短的残料小EndIfNextaNextbPrintPrintPrint" 最短残料时a 的段数：" 最短残料时b 的段数：" 最短残料为："r""iaibEndSub【寻找最大值和最小值】从 10 个范围1, 100 随机数中找出其最大值和最小值。PrivateSubForm_Click( )Dima(1 To 10)AsInteger,iAsIntegerDimmin, maxAsInteger,minindexAsInteger,Fori = 1To10a(i) = Int(Rnd * 100) + 1Printa(i);NextiPrintmin = a(1):max = a(1):minindex = 1:Fori = 2To10Ifa(i) < minThenmin = a(i):minindex = iIfa(i) > maxThenmax = a(i):maxindex = imaxindexAsmaxindex = 1IntegerEndNextPrintPrintSubi" 第 "" 第 "&&minindex maxindex&" 个数最小：&" 个数最大：""&min&max#6、递推（迭代）“递推法” 也称为 “跌代法 ”，把一个复杂的计算过程转化为“简单过程的多次重复” 。每次重复都从旧值的基础上 “递推” 出新值，并由 “新值代替旧值”进行下一次递推。算法思想 ：对于一个问题的求解x，可由给定的一个初值 x0，根据某一迭代公式得到一个新的值x1，这个新值 x1 比初值 x0 更接近要求的值x；再以新值作为初值，即：x1 x0，重新按原来的方法求x1，重复这一过和直到 |x1-x0|<（某一给定的精度） 。此时可将 x1作为问题的解。【猴子吃桃的递推】 小猴子在一天摘了若干个桃子，当天吃掉一半多一个；第二天接着吃了剩下的桃子的一半多一个；以后每天都吃尚存桃子的一半零一个，到第7 天早上要吃时只剩下一个了，问小猴子那天共摘下了多少个桃子？这是一个典型的“递推 ”问题，先从最后一天推出倒数第二天的桃子，再从倒数第二天的桃子推出倒数第三天的桃子 ···。设第 n 天的桃子为 X n，那么它是前一天的桃子数Xn 1 的二分之一减一。 即：X n=0.5X n1 1，也就是： X n 1=（ X n+1 ） ×2PrivateSub Form_Click( )Dimn%, i%, x%x = 1' 第 7天的桃子Print" 第 7 天的桃子数为： 1 只"Fori = 6 To1 Step -1x = (x + 1) * 2Print" 第 " i; "天的桃子数为： " x;" 只 "NextiEndSubPrintIf【迭代法求平方根】已知求平方根的迭代公式为：x11 (x0a ) ，用迭代法求某个数的平方根。2x0PrivateSubForm_Click( )Dimx As Singlex = Val(InputBox("输入一个大于0 的正数： ", "求平方根 ", 0)Ifx > 0ThenPrintx&" 的平方根为： " Fsqrt(x)ElseIf x = 0ThenPrint"0的平方根为 0！ "Else" 此数不能求平方根！"EndEndSubPrivate Function Fsqrt( a As single ) Dim x0 As Single, x1 As Single x0 =a/2 ' 迭代初值 x1 = 0.5*(x0 + a/x0)AS singleDox0 = x1' 为下一次迭代作准备x1 = 0.5*(x0 + a/x0)Loop WhileAbs(x1 - x0) > 0.00001Fsqrt=x1EndFunction#7、二分法解高次方程假 设方程 f(x)=0 在区间 (a, b) 内有唯一的根 x，则 f(a) 与 f(b) 的符号必然相反。二分法利用这个性质进过若干次迭代缩小根所在的区间，得到一个在一定误差范围内的近似根。（ a）方程的根在中点左侧（ b）方程的根在中点右侧二分法求根示意图 取 (a, b) 的中点 x0=(a+b)/2 ，将求根区间分成两半，开始缩小根的区间。 如果 f(x 0)与 f(a)同号 ，则根的真值x 在中点 x0 的右侧，如图（b）所示。这时根的取值区间缩小为(x 0 ,b) ，即用 x0 取代 a 的位置。如果f(x 0)与 f(a) 异号 ，则根的真值x 在中点 x0 的左侧，如图（a）所示。这时根的取值区间缩小为 (a, x 0) ，即用 x0 取代 b的位置。 根据新的区间范围重复“取中点判断”，直到 f(x 0)=0 或区间长度 b- a< ，则 x0 即为方程 f(x)=0的近似根，误差小于 。【二分法求解方程】 求方程 x3+4x 2-10=0在区间 (1,4)内的实数根。要求精确到小数点后第4 位。PrivateSub Form_Click( )Dima, b, xAs Doublea = 1:b = 4While b - a > 0.00001x = (a + b) / 2' 求出根所在区间的中间点 xf1 = a 3 + 4 * a 210' 求左边界点 a 的方程值f = x 3 + 4 * x 210' 求中间点 x 的方程值Iff1 * f > 0Thena = xElseb = x'根据两个方程值的符号异同，缩小根的区间范围EndIfWendPrint"x="CInt(x * 10000) / 10000EndSub#8、牛顿切线法解高次方程给方程f(x) 假定一个初值x0 作为方程的近似根，牛顿切线法迭代公式为： xi1xif /xi ， f /xi 是 fxi的导数，经过若干次fxi迭代后，当 xi1xi时， xi 1 就作为方程的高精度近似根。由图可知，牛顿切线法的实质是逐步以切线与x轴的交点来作为曲线与 x 轴交点的近似值。【牛顿切线法解高次方程】 求方程 f(x)=3x3- 4x2-5 x+13=0 的根。PrivateSub Form_Click( )Dimx, x0, f, f1A