VB 第十二讲.ppt

1、第十二讲 常用算法及综合应用,Visual Basic 程序设计教程,内蒙古科技大学工程训练中心 韩 艳,工程训练中心,2,主要内容,累加、连乘 穷举法:素数问题 递推法:Fibonacci数列,工程训练中心,3,一、常用算法与数据结构一,1、累加、连乘 累加：就是在原有和的基础上再加一个数，并重复该操作； 连乘：在原有积的基础上再乘以一个数，并重复该操作； 例如：求100以内的自然数之和。其中sum为累加和变量，i为循环控制变量 求10以内的偶数连乘之乘积；,Private Sub Command1_Click() sum=0 For i=1 to 100 sum=sum+i Next Pr

2、int sum End Sub,Private Sub Command1_Click() p=1 For i=2 to 10 Step 2 p=p*i Next Print p End Sub,工程训练中心,4,5.4 常用算法与数据结构一,2、穷举法 根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验那些是需要的，哪些是不需要的。 例【5-20】 算经中出了一道题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？” 解题思路：设x，y，z分别为鸡翁、鸡母、鸡雏的数，则有： 5*x+3*y+z/3=100(元) x+y+z=100(只) 则按x取值

3、0100，y取值：0100，依次取值，直到满足上式即可；,Dim x%, y%, z As Integer FontSize = 14 Print cock, hen, chick For x = 0 To 100 For y = 0 To 100 z = 100 - x - y If 5 * x + 3 * y + z / 3 = 100 Then Print x, y, z Next Next,工程训练中心,5,5.4 常用算法与数据结构一,2、 穷举法 例【5-25】将一张1元钞票分成一分、二分和五分硬币，每种至少8枚，问有多少种方案？ 解题思路：每种硬币至少8枚，则1分最多有44枚（1

4、002*85*8）/1，2分硬币最多有26枚，5分硬币最多有15枚。 则1分币取值：844， 2分币取值：826， 5分币取值：815， 各依次取值，直到满足：1分币总值2分币总值5分币总值100分,工程训练中心,6,素数问题 例：编写程序，对任意输入的正数n(n3)判断其是否是素数。,Dim n As Integer, i As Integer rem n为判断的正数, i为循环变量 n = Val(InputBox(请输入一个正数：) i = 2 Do While n mod i0 and i = n Then Print n; 是素数; Else Print n; 不是素数“ Endif

5、,解题思路： 素数：也称质数，即除了1和自身外，不能被任何整数整除的整数。穷举法：用n依次除以2n1间的各个数，只要都除不尽，即为素数。,一、常用算法与数据结构一,改进算法：用n依次除以2 间的各个数，只要都除不尽，即为素数。,工程训练中心,7,素数问题 例 ：编写程序，在窗体上每5个一行，输出100200间的所有素数。,number为输出计数器，n为输出的素数，i，k为循环变量 Dim number As Integer, n As Integer, i As Integer, k As Integer number = 1 For n = 100 To 200 i = 2 Do While

6、 i Int(Sqr(n) Then Print n; If number Mod 5 = 0 Then Print 每5个素数为一行 number = number + 1 End If Next,解题思路：需要设置两层循环，其中外层循环负责控制取值范围，即100200；内层循环具体判断每一个数是否为素数。,一、常用算法与数据结构一,工程训练中心,8,5.6 综合应用举例,例： 求整数351432之间既不能被3整除又不能被8整除的数的个数及这些数的和。 解题思路：不能被3整除： n mod 30；不能被8整除：n mod 80,Dim i As Integer, n As Integer,

7、sum As Long For i = 351 To 432 If (i Mod 3) 0 And (i Mod 8) 0 Then n = n + 1 sum = sum + i End If Next FontSize = 14 Print 数的个数：; n Print 数的和是：; sum,工程训练中心,9,例 ：输入两个整数，求它们的最大公约数,一、常用算法与数据结构一,工程训练中心,10,5.4 常用算法与数据结构一,3、递推法 例【5-26】 【斐波那契数列】有一个数列，第一个数为1，第二个是为1，第三个是前两个数之和，以后每个数都是前两个数之和，要求输出该数列的第N项。 解题思路

8、：可先把前两个数分别赋给变量A和B中，再计算CAB；再将上一轮B的值移到A中，将上一轮的C的值移到B中，再计算C=A+B，得到的就是第四个数； 再B的值移到A中，C的值移到B中，计算C=A+B，得到的就是第五个数以此循环，以此循环，就可得到第N个数；,A B C 1 1 2 1 2 3 2 3 5 .,C=A+B -2=1+1 第一轮 A=1: B=1 -将上一轮的B赋给A、C赋给B,工程训练中心,11,5.6 综合应用举例,例【5-27】 猴子吃桃子。有猴子第一天吃掉一半多一个，第二天吃掉剩下的一半多一个，如此，到第七天吃时，只剩下1只桃子，问一共有多少只桃子？ 解题思路：设第n天桃子数为xn，前一天的桃子数：xn1，则有 xn=xn-1(xn-1)/2+1)，即：xn-1=(xn1)*2 ； 已知第七天只剩下1只桃子，则可依据上式倒推到第六天剩下的桃子，以及第五天剩下的桃子，直至第一天的桃子。,Dim n as integer, i as integer x = 1