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