常用算法及调试方法

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,常用算法举例,算法是对某个问题求解过程的描述,一、若干初等数学问题：,1.累加、连乘,1100的5或7的倍数的和,Sum = 0,For i = 1 To 100,If i Mod 5 = 0 Or i Mod 7 = 0 Then,Sum = Sum + i,End If,Next i,Print Sum,310的乘积,t = 1,For i =3 To 10,t = t * i,Next i,Print t,1,例,求自然对数e的近似值,要求其误差小于0.00001，近似公式为:,该例题涉及两个问题：,（1）用循环结构求级数和的问题。本例根据某项值的精度来控制循环的结束与否。,（2）累加：,e=e+t,循环体外对累加和的变量清零,e=0,连乘：,n=n*i,循环体外对连乘积变量置1,n=1,Private Sub Form_Click(),Dim i%,n&, t!, e!,e = 0 : n = 1, e存放累加和、n存放阶乘,i = 0 : t = 1, i计数器、t第i项的值,Do While t 0.00001,e = e + t : i = i + 1, 累加、连乘,n = n * i : t = 1 / n,Loop,Print 计算了 ; i; 项的和是 ; e,End Sub,2,2.求素数,素数是一个大于,2，且,不能被,1,和本身以外的整数整除的整数。,判别某数,m,是否为素数最简单的方法是:,对于m 从 i=2，3，m-1判别m能否被i整除，只要有一个能整除，m不是素数，否则m是素数。,例,求100以内素数的代码：,For m = 2 To 100,For i = 2 To m - 1,If (m Mod i) = 0 Then GoTo,NotNextM,Next i,Print m,NotNextM:,Next m,m是否为素数,求100以内的素数,思考：,此例用GoTo语句对非素数不作判断，若不用GoTo语句，如何修改程序？,例：,用筛选法求素数,3,3.穷举法,“穷举法”也称为“枚举法”或“试凑法”， 即将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现。,例,百元买百鸡问题。假定小鸡每只5角，公鸡每只2元，母鸡每只3元。现在有100元钱要求买100只鸡，编程列出所有可能的购鸡方案。,设母鸡、公鸡、小鸡各为x、y、z只，根据题目要求，列出方程为：,x+y+ z =100,3x+2y+0.5z=100,三个未知数，两个方程，此题有若干个解。,解决此类问题采用“试凑法”，把每一种情况都考虑到。,方法一：最简单三个未知数利用三重循环来实现。,方法二：从三个未知数的关系，利用两重循环来实现。,4,4.递推法,“递推法”又称为“迭代法”，其基本思想是把一个复杂的计算过程转化为简单过程的多次重复。每次重复都从旧值的基础上递推出新值，并由新值代替旧值。,例,猴子吃桃子。小猴在某天摘桃若干个，当天吃掉一半多一个；第二天吃了剩下的桃子的一半多一个；以后每天都吃尚存桃子的一半多一个，到第,7,天要吃时只剩下一个，问小猴共摘下了多少个桃子？,分析：这是一个“递推”问题，先从最后一天推出倒数第二天的桃子，再从倒数第二天的桃子推出倒数第三天的桃子,。设第n天的桃子为,x,n,，那么它是前一天的桃子数,的,x,n-1,的一半减1，即,x,n-1,= （,x,n,+1）*2,5,5.最小、最大值,在若干个数中求最大值，一般先假设一个较小的数为最大值的初值，若无法估计较小的值，则取第一个数为最大值的初值；然后将每一个数与最大值比较，若该数大于最大值，将该数替换为最大值；依次逐一比较。,例 随机产生10个100200之间的数，求最大值。,Private Sub Command1_Click(),Max = 100,For i = 1 To 10,x = Int(Rnd * 101 + 100),Print x;,If x Max Then Max = x,Next i,Print,Print 最大值=; Max,End Sub,6,6、,数制转换,例,将一个十进制整数,m,转换成,r,(216)进制字符串。,方法：将,m,不断除,r,取余数，直到商为零，以反序得到结果。,7,7、,例,加密和解密,简单加密的思想是：,将每个字母C加一序数K，式子 c=chr(Asc(c)+k),例如序数k为5，这时 “A”,“F”， “a”,“f”，“B”,“G”,当加序数后的字母超过“Z”或“z”则 c=hr(Asc(c)+k -26)。,解密为加密的逆过程。,8,二、排序,选择、冒泡、插入法排序、合并排序等。,前两种排序欲排序的数据全部输入后，再进行排序；,插入法排序每输入一项，马上插入到数组应在的位置，数组始终有序。,例,插入排序，,实现的步骤：,(1)输入欲排序的数据项x；在数组a中找x应所处的位置j;,(2)从数组的最后一个元素开始到下标j依次往后移，使j位置空出；,(3)将x放入位置j处，一个数据插入完成；,(4)有若干个数重复(1)(3)。,9,例,合并排序,，将两个有序的数组合并成另一个有序的数组。假设有序的数组为A、B，合并后的数组为C。合并排序的思想为：,（1）先在A、B数组中各取第一个元素进行比较，将小（递增次序）的元素放入C数组；,（2）取小的元素所在数组的下一个元素与上次比较后较大的元素比较，重复上述过程，直到某个数组被先排完；,（3）将另一个数组剩余元素抄入C数组，合并排序完成。,10,三、查找,1、顺序查找,。,顺序查找根据查找的关键值与数组中的元素逐一比较(数组可无序),Public Sub Search(a() As Variant, ByVal key As Variant, index%),Dim i%,For i = LBound(a) To UBound(a),If key = a(i) Then, 找到，元素的下标在index中，结束查找,index = i,Exit Sub,End If,Next i,index = -1, 找不到， index形参的值为-1,End Sub,平均查找次数 n/2,11,Keya(mid) low=mid+1 查找区域缩小一半,继续,直到找到或查找区,域中无元素.,本例用递归实现,Sub birsearch(a(),low%, high%, key,index,%),2、二分法查找（折半法查找）,要查找的数组,必须有序,。,思想：要查找的关键值Key同数组的中间mid项元素比较:,12,34,56,78,111,222,333,444,555,666,777,888,Low,high,mid,444,Key,12,四、,二分法求根,思想： 已知求根区间a,b有一根，每次把求根区间缩小一半,直到找到解或求根区间足够小。,方法：求a,b的中点c，判断,f(c)=0, c,为求得的根，结束；,f(a)与f(c)同号,则a,c无根，c代替a；,否则c,b无根，c代替b；,使求根区间缩小一半，重复上述步骤，直到区间小于精度。,Public Function halfRoot(ByVal a!, ByVal b!),Dim c!,Do While Abs(b - a) 0.00001,c = (a + b) / 2,If f(c) = 0 Then,Exit Do,ElseIf f(a) * f(c) 0 Then,a = c,Else,b = c,End If,Loop,halfRoot = c,End Function,13,五、字符串处理,例,编写一个英文打字训练的程序，要求如下：,(1)在标签框内随机产生30个字母的范文；,(2)当焦点进入文本框时开始计时，并显示当时时间；,(3)在键入文本框按产生的范文输入相应的字母；,(4)当键入满了30个字母后结束计时，禁止向文本框输入内容 ，与范文逐一比较，显示打字的速度和正确率。,14,程序调试,一.错误类型,（1）编辑错误,在编辑代码时，VB会对键入的代码直接进行语法检查。当发现代码存在打字错误，遗漏关键字或标点符等语法错误，VB在Form窗口中弹出一个子窗口，提示出错信息，出错的那一行变成红色。这时，用户必须单击“确定”按钮，关闭出错提示窗，然后对出错行进行修改。,15,（2）编译错误,编译错误指按了“启动”按钮，VB开始运行程序前，先编译执行的程序段时，产生的错误。此类错误由于用户未定义变量、遗漏关键字等原因产生。这时，Visual Basic也弹出一个子窗口，提示出错信息，出错的那一行被高亮度显示。,16,（3） 运行错误,运行时错误指VB在编译通过后，运行代码时发生的错误。这类错误往往是指令代码执行了一非法操作引起的。例如类型不匹配、试图打开一个不存在的文件等。,17,（4） 逻辑错误,程序运行后，得不到所期望的结果，这说明程序存在逻辑错误。这类错误往往是程序存在逻辑上的缺陷所引起。例如，运算符使用不正确、语句的次序不对、循环语句的起始、终值不正确等。通常，逻辑错误不会产生错误提示信息，故错误较难排除，需要程序员仔细地阅读分析程序以及调试。,18,二.调试错误,(1)VB的三种模式,设计模式,设计,进行程序的界面设计、属性设置、代码编写等。,运行模式,运行,执行“运行,/,启动”命令，可以查看程序代码，但不能修改。,中断模式,中断,当在运行模式，按了“中断”命令或当程序出现运行时错误时进入中断模式。可以查看代码、修改代码、检查数据。,(2),调试窗口,有三个调试窗口，它们是：“立即”窗口、“监视”窗口、和“本地”窗口。可单击视图菜单中的对应命令打开这些窗口。,19,（3）设置断点和逐语句跟踪,断点是告诉VB挂起程序执行的一个标记，当程序执行到断点处即暂停程序的运行，进入中断模式。设置或删除断点的步骤：,中断模式下，直接查看某个变量的值，只要把鼠标指向所关心的变量处，稍停一下，就在鼠标下方显示该变量的值。,断点标记,当前行,20,