全国二级VB常用算法.docx
- 文档编号:8986187
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:53
- 大小:87.60KB
全国二级VB常用算法.docx
《全国二级VB常用算法.docx》由会员分享,可在线阅读,更多相关《全国二级VB常用算法.docx(53页珍藏版)》请在冰点文库上搜索。
全国二级VB常用算法
程序设计算法
计算机由于只能执行算术和逻辑运算,所以其解决问题的方法、步骤和人们生活中的处理不同,必须考虑其特殊性。
在程序设计语言的发展过程中,对不同问题的处理已经形成相对固定的处理方法,这就是程序算法讨论的主要方面。
一、累加算法
累加算法的一般做法是设一个变量s,作为累加器使用,初值为0,设一个变量用来保存加数。
一般在累加算法中的加数都是有规律可循,可结合循环程序来实现。
一个循环程序的设计,如果以下三方面确定下来:
变量的赋初值、循环体的内容、循环结束条件,那么根据循环语句的格式,就很容易写出相应的循环程序。
例:
求1+2+3+……+100的累加和,并打印输出
分析:
设累加器S,初值为0,加数用变量I表示
当I=1时,累加器S=S+I=0+1=1
当I=2时,累加器S=S+I=1+2=3
当I=3时,累加器S=S+I=3+3=6
当I=4时,累加器S=S+I=6+4=10
……
当I=100时,累加器S=S+100=1+2+3+……+99+100=5050
不难看出,I的值从1变化到100的过程中,累加器均执行同一个操作:
S=S+I,S=S+I的操作执行了100次,所以该程序段可写成:
DimIAsInteger,SAsInteger
S=0‘给累加器s赋初值
Fori=1To100
S=S+i‘i既作为循环变量,又作为加数
NextI
Print"1+2+……100=";S
考虑一下:
语句Print"1+2+……100=";S可以放在循环体中吗?
延伸一下:
上述算法对数值型数据,执行的是累加操作,如果对字符串型数据,完成的是字符串的连接。
注意:
用+作为字符串连接符时,+运算符两边必须是字符串类型,但用&运算符时就没有这个限制了。
例:
从键盘上输入一串字符,要求将其加密后显示在文本框Text1中,加密的方法是将每一个字符转变为它的后一位字符,如:
A转变为B,1转变为2。
分析:
因为涉及对每一个字符做相应处理再连接成一个新串,所以可以用类似累加的算法。
定义一个变量str1用来接收输入的原始字符串,变量str2用来接收加密后的字符串,初值为空串。
可用Len()函数得出字符串的长度,用循环控制,从左向右逐个取字符,截取字符的功能可用函数Mid()完成,由于要做加密操作,可利用Asc()函数获得字符的Ascii码,用Chr()函数获得Ascii码对应的字符。
程序段如下:
Dimstr1AsString,chAsString*1
DimiAsInteger,str2AsString
str1=InputBox("输入原始字符串:
")
Fori=1ToLen(str1)
str2=str2+Chr(Asc(Mid(str1,i,1))+1)‘将加密后的字符连接成串
Nexti
Text1.Text=str2
由此可以看出:
对字符串的连接操作,可用累加算法来完成,不过在字符串的操作中,经常要用到字符串处理函数,所以一些常用的函数功能和用法必须掌握。
考虑一下:
如果要实现字符的逆序连接,该怎么办?
考题链接:
下面程序的功能是统计随机生成的十个两位正整数中偶数和奇数的个数,并求出偶数和奇数各自的总和。
(2001年秋季填空题第6题)
PrivateSubForm_click()
DimxAsInteger,s1AsInteger,s2AsInteger
Dimn1AsInteger,n2AsInteger,iAsInteger
Randomize
Fori=1To10
x=Int(Rnd*90)+10
Printx;
IfThen
n2=n2+1:
s2=s2+x
Else
s1=s1+x
EndIf
Nexti
Print"奇数个数=";n1,"偶数个数=";n2
EndSub
二、连乘算法
连乘算法的一般做法是设一个变量t,作为乘法器使用,初值为1,设一个变量用来保存乘数。
例:
求10!
=1*2*3*……*10的结果并打印输出
分析:
与累加算法类似,只不过加法变成乘法。
设乘法器t,初值为1,设变量I存放乘数。
当I=1时,T=T*I=1*1=1
当I=2时,T=T*I=1*2=2
当I=3时,T=T*I=2*3=6
……
当I=10时,T=T*I=1*2*3*……*9*10
所以当I的值从1变化到10的过程中,乘法器均执行同一个操作:
S=S*I,程序段可写成:
DimIAsInteger,TAslong
T=1
ForI=1To10
T=T*I
NextI
Print"1*2*3*……*10=";T
例:
求1!
+2!
+……+10!
的值
分析:
这一题总体上是累加题,只不过加数不再是简单的1、2、3等,而是1!
、2!
到10!
,可考虑设一个变量s作累加器,设一个变量t存放每一次的加数,累加的次数是10次,分别加上1!
到10!
。
设循环变量i值从1变化到10,每一次循环执行一次累加操作,每次累加的加数t为i!
,所以在每次累加之前,应先用连乘算法计算I!
的值,可设循环控制变量j,按如下程序段完成求i!
:
t=1
Forj=1Toi
t=t*j
Nextj
结合累加算法,求!
+2!
+……+10!
的程序段如下:
DimiAsInteger,jAsInteger
DimsAsLong,tAsLong
s=0
Fori=1To10
t=1
Forj=1Toi
t=t*j
Nextj
s=s+t
Nexti
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,所以上述程序段还可进行以下的优化:
DimiAsInteger,jAsInteger
DimsAsLong,tAsLong
s=0
t=1‘这时t=1不可放在循环体内
Fori=1To10
t=t*i
s=s+t
Nexti
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!
归纳一下:
所有累加次数确定的累加程序都可以采用如下的编程模式:
定义累加器s,初值为0或根据情况赋一个特定值,设变量t存放加数,假设累加次数为n次,则程序段可按如下框架编写:
s=0
Fori=1Ton
将加数赋给t
s=s+t
NextI
三、统计算法
例:
在文本框中输入一串字符,统计其中的字母、数字和其他字符的个数。
基本思路:
要统计满足指定要求的字符个数,应定义相应变量(如n)作为计数器,初值为0,每找到符合条件的字符,将指定计数器的值加1。
本题需要定义3个计数器n1、n2、n3,初值为0,对字符串的字符逐个判断,如果是字母,n1加1,如果是数字,n2加1,否则n3加1
PrivateSubCommand1_Click()
DimstrAsString,iAsInteger,chAsString*1
Dimn1AsInteger,n2AsInteger,n3AsInteger
n1=0:
n2=0:
n3=0:
str=Text1.Text
Fori=1ToLen(str)
ch=Mid(str,i,1)
IfUCase(ch)<="Z"AndUCase(ch)>="A"Then
n1=n1+1
ElseIfch>="0"Andch<="9”Then
n2=n2+1
Else
n3=n3+1
EndIf
Nexti
Text2=“字母的个数为"&n1&Chr(13)&Chr(10)
Text2=Text2&“数字的个数为”&n2&Chr(13)&Chr(10)
Text2=Text2&“其他字符的个数为”&n3
EndSub
练习:
1、随机生成两位正整数的二维数组a(4,4),下标从1开始,统计所有元素中0到9十个数字出现的次数,并显示在窗体上。
(1)如何取得两位整数的各个数字
(2)需要设多少个计数器,如何考虑?
四、求最大值和最小值算法示例
例:
随机产生20个1到100之间的整数,打印输出其最大值和最小值。
任何一个随机整数x都可通过随机函数来产生,随机函数Rnd()可产生在0到1之间均匀分布的随机数。
要产生在区间[M,N]之间的随机整数x,可用以下公式完成:
x=Int(Rnd*(N-M+1))+N
所以1到100之间的随机整数x的产生可用以下语句完成:
x=Int(Rnd*100)+1
求最大值和最小值算法思想
在N个数中求最大值和最小值的思路是定义一个变量假设为max,用来存放最大值,定义一个变量假设为min,用来存放最小值。
一般将第1个数赋给max和min,将剩下的每个数分别和max、min比较,如果比max大,将该数赋给max,如果比min小,将该数赋给min,即让max中总是放当前的最大数,让min中总是放当前的最小值,这样当所有数都比较完时,在max中放的就是最大数,在min中放的就是最小数。
PrivateSubForm_click()
DimiAsInteger,xAsInteger
DimmaxAsInteger,minAsInteger
Randomize‘随机函数初始化
max=Int(Rnd*100)+1
min=max‘给max和min赋初值
Fori=1To19
x=Int(Rnd*100)+1‘产生1到100间的随机数
Ifx>maxThenmax=x
Ifx Nexti Print“最大值是”&max Print“最小值是”&min EndSub 练习: 1、随机生成一维数组a(10),要求数组元素为两位正整数,求该数组中的第二大数 五、穷举算法 穷举法是循环程序中具有代表性的基本应用之一。 穷举是一种重复型算法。 它的基本思想是对问题的所有可能状态都一一测试,直到找到答案或将全部可能状态都测试过为止。 循环控制有两种办法: 计数法和标志法。 计数法用于循环次数确定的情况下,一般用For-Next循环比较方便;标志法用于循环次数未知情况,表示达到某一目标后使循环结束。 例: 搬砖问题: 36块砖,36人搬,男搬4,女搬3,两个小孩搬一砖,要求一次全搬完,问男、女和小孩各有多少个? 分析: 假设男人用变量man表示,女人用women表示,小孩用children表示,有以下式子成立: men+women+children=36 4*men+3*women+children/2=36 如果用算术来解方程,可以看出这是一个典型的不定方程,可能有多个解。 穷举法的算法思想是将所有可能的情况全部列出来,逐一进行测试。 由条件可知: 男人(men)的可能取值范围为: 0~8 女人(women)的可能取值范围为: 0~11 可利用双重循环实现对所有可能的男人men和女人women的值进行选择 children=36-men-women 如果满足4*men+3*women+children/2=36 则表示找到一个合理的解。 PrivateSubForm_Click() DimmenAsInteger,womenAsInteger DimchildrenAsInteger Formen=0To8‘men取所有可能的值 Forwomen=0To11‘women取所有可能的值 children=36-men–women‘算出children的人数 If4*men+3*women+children/2=36Then Print"男人有: ";men;"人" Print"女人有: ";women;"人" Print"小孩有: ";children;"人" EndIf Nextwomen Nextmen EndSub 练习: 1、打印所有符合下列条件的3位正整数: 是某一个数的平方数,其中两位数字相同,如100、121等。 2、编程求满足条件abcd=(ab)2+(cd)2的所有四位数,如8833=(88)2+(33)2。 六、判断素数 一个数如果只能被1和其本身整除,而不能被其他任何数整除,那么这个数就称为素数。 例6: 输入一个整数,判断它是否是素数,比如输入7,应输出“7是素数”的提示,如图2所示,输入24,应输出“24不是素数”的提示。 界面如图1所示: 分析: 由素数的定义,判断任一个整数n是否是素数的算法是让n分别整除从2到n-1(或n/2、sqr(n))中的每一个数,如果有一个数能被n整除,则n不是素数,如果所有的数都不能被n整除,则n是素数。 这也是一个典型的循环程序,可设一个循环变量为I,让I从2变化到n-1,如果有一个I能被n整除,说明n不是素数,下面就不用再进行判断,提前跳出循环;如果所有的I都不能被n整除,最后正常结束循环。 关键是如何知道跳出循环后是提前跳出还是正常退出? 对于这种有两种判断结果的处理,一般采用标志变量。 设一个变量,假设命名为Flag,让Flag的初值为True,如果提前跳出循环,Flag的值赋为False,跳出循环后可根据Flag的值判断是提前跳出还是正常结束。 程序如下: PrivateSubCommand1_Click() DimiAsInteger,nAsInteger DimflagAsBoolean flag=True‘给标志变量赋初值 n=Val(Text1.Text) Fori=2Ton-1 IfnModi=0Then flag=False‘如果I能被n整除,将flag赋值为False ExitFor EndIf Nexti Ifflag=TrueThen‘该条件也可写成IfflagThen MsgBoxn&"是素数" Else MsgBoxn&"不是素数" EndIf EndSub 另一种方法: 还可以在循环结束后通过循环控制变量的值来进行素数的判断。 如果是素数,循环将正常结束,循环控制变量将超过终值;如果不是素数,肯定有一个数能够被n整除,循环会提前结束,循环控制变量小于等于终值。 程序如下: PrivateSubCommand1_Click() DimiAsInteger,nAsInteger n=Val(Text1.Text) Fori=2Ton-1 IfnModi=0ThenExitFor Nexti Ifi=nThen‘该条件也可写成IfflagThen MsgBoxn&"是素数" Else MsgBoxn&"不是素数" EndIf EndSub 注意: 1、素数判断的题目在改错题中出现地较多,一般为: (1)循环跳出语句Exitfor/Exitdo或过程跳出语句ExitSub//ExitFunction等的选定 (2)调用过程前标志量的初始化 2、标志量的做法并不局限在素数的判断中,在程序设计中,如果需要在两种状态之间进行识别或结果为是或否、成立或不成立等两种结果时,都可以考虑用标志量法。 七、求最大公约数和最小公倍数 最大公约数可用辗转相除法来求。 假设要求任两个整数m和n的最大公约数,求m和n的余数r,将n的值作为m的新值,将r的值作为n的新值,再不断的求新的m和n的余数r,直到r的值等于0为止,这时m的值就是要求的最大公约数。 注意: 由于循环程序次数不确定,应采用do-loop循环结构。 例: 在两个文本框Text1和Text2中分别输入两个正整数,单击命令按钮Command1后在窗体上输出其最大公约数。 程序如下: PrivateSubCommand1_Click() DimmAsInteger,nAsInteger DimrAsInteger‘定义存放余数的变量r m=Val(Text1.Text) n=Val(Text2.Text) Printm;"和";n;"的最大公约数为"; Do r=mModn m=n n=r LoopUntilr=0 Printm EndSub 考虑一下: 可以将第一条print语句放在执行循环以后吗? (答案: 不可以。 因为执行完循环后m和n已经不是原来的数值了) 将以上程序添加相应语句就可完成求最小公倍数的功能(M和n的最小公倍数等于m*n/m和n的最大公约数)。 程序如下: PrivateSubCommand1_Click() DimmAsInteger,nAsInteger DimrAsInteger DimtAsInteger m=Val(Text1.Text) n=Val(Text2.Text) t=m*n‘记录m*n的初始值 Printm;"和";n;"的最大公约数为"; Do r=mModn m=n n=r LoopUntilr=0 Printm;",最小公倍数为";t/m EndSub 延伸一下: 考虑任意两个数m和n(假设m 1、两个数的最大公约数为1 2、如果这两个数除了1之外没有相同的因子,则两个数互质 flag=True Fori=2Tom IfnModi=0AndmModi=0Then flag=False ExitFor EndIf Nexti 练习: 给定正整数n,求所有小于n的互质数,如n=9,则2、4、5、7、8为9的互质数 八、迭代 迭代是一个不断用新值取代旧值或用旧值推出新值的过程。 迭代算法的程序编制时要从三方面着手: 确定迭代公式(也就是循环体的内容)、公式的初始化以及迭代的终止条件。 1、精确迭代算法示例 例: 兔子繁殖问题: 意大利数学家Fibonacci曾提出一个有趣的问题: 设有一对新生兔子,从第三个月开始它们每个月都生一对兔子。 按此规律,并假设没有兔子死亡,一年后共有多少对兔子。 可以发现每月的兔子数组成如下数列: 1,1,2,3,5,8,13,21,34,…… 打印数列的前20项,且一行输出5个 对数列1,1,2,3,5,8,13,21,34,……可看出: 数列从第3项开始,每1项都是其前2项之和。 假设第1项元素用f1表示,第2项元素用f2表示,每次新元素用f表示 f1f2f 第3月11f=f1+f2=2 第4月12f=f1+f2=3 第5月23f=f1+f2=5 第6月35f=f1+f2=8 …… f1和f2初值为1 f=f1+f2 f1=f2 f2=f 可以看出: 每1个月的兔子数f要由前面的兔子数f1和f2推出,并在求下1个月的兔子数之前要用新值对f1和f2的值进行更新。 这就是迭代算法。 如果迭代的次数确定,可以得到一个确定的值,这样的迭代称为精确迭代。 程序如下: PrivateSubForm_click() Dimf1AsInteger,f2AsInteger DimiAsInteger,fAsInteger f1=1: f2=1‘给f1和f2赋初值 Printf1;f2; Fori=3To20 f=f1+f2 f1=f2 f2=f Printf;‘输出每月的兔子数 IfiMod5=0ThenPrint‘控制每行输5个 Nexti EndSub 2、一元高次方程的求解 一元高次方程的求解没有通用的求根公式,常用迭代法来求方程的近似根。 迭代法求方程f(x)=0的根是将其改写为: x=ψ(x) 选取适当的初值x0,便可通过重复迭代构造序列: x0,x1,x2,……,xn,…… 若该数列收敛,则极限值就是方程的一个解。 牛顿迭代法和二分迭代法都是对一元高次方程求解的近似方法。 (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就作为方程的近似根。 例: 编写程序,利用牛顿迭代法求方程xex-1=0在x0=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国 二级 VB 常用 算法