VB 第十二讲.ppt
第十二讲第十二讲 常用算法及综合应用常用算法及综合应用Visual Basic 程序设计教程程序设计教程内蒙古科技大学工程训练中心韩 艳主要内容主要内容 累加、连乘累加、连乘 穷举法穷举法:素数问题素数问题 递推法递推法:Fibonacci数列数列2工程训练中心一、一、常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一1 1、累加、连乘、累加、连乘 累加：就是在原有和的基础上再加一个数，并重复该操作；连乘：在原有积的基础上再乘以一个数，并重复该操作；例如例如：求求100100以内的自然数之和。其中以内的自然数之和。其中sumsum为累加和变量，为累加和变量，i i为循环控制变量为循环控制变量 求求1010以内的偶数连乘之乘积以内的偶数连乘之乘积；Private Sub Command1_Click()sum=0 For i=1 to 100 sum=sum+i Next Print sum End Sub Private Sub Command1_Click()p=1 For i=2 to 10 Step 2 p=p*i Next Print p End Sub 3工程训练中心5.4 5.4 常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一2 2、穷举法、穷举法 根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验那些是需要的，哪些是不需要的。例例【5-205-20】算经算经中出了一道题：中出了一道题：“鸡翁一，值钱五；鸡母一，值钱三；鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”解题思路解题思路：设x，y，z分别为鸡翁、鸡母、鸡雏的数，则有：5*x+3*y+z/3=100(元)x+y+z=100(只)则按x取值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 N4工程训练中心5.4 5.4 常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一2 2、穷举法穷举法 例例【5-255-25】将一张将一张1 1元钞票分成一分、二分和五分硬币，每种至少元钞票分成一分、二分和五分硬币，每种至少8 8枚，问枚，问有多少种方案？有多少种方案？解题思路解题思路：每种硬币至少8枚，则1分最多有44枚（1002*85*8）/1，2分硬币最多有26枚，5分硬币最多有15枚。则1分币取值：844，2分币取值：826，5分币取值：815，各依次取值，直到满足：1分币总值2分币总值5分币总值100分5工程训练中心素数问题素数问题例：例：编写程序，对任意输入的正数编写程序，对任意输入的正数n(nn(n3)3)判断其是否是素数判断其是否是素数。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解题思路：解题思路：素数：也称质数，即除了素数：也称质数，即除了1和自身外，不能被任何整数整除的整数。和自身外，不能被任何整数整除的整数。穷举法穷举法：用：用n依次除以依次除以2n1间的各个数，只要都除不尽，即为素数。间的各个数，只要都除不尽，即为素数。一、一、常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一改进算法改进算法：用用n依次除以依次除以2 间间的各个数，只要都除不尽，即为的各个数，只要都除不尽，即为素数。素数。6工程训练中心素数问题素数问题 例例 ：编写程序，在窗体上每编写程序，在窗体上每5 5个一行，输出个一行，输出100100200200间的所有素数。间的所有素数。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 i Int(Sqr(n)Then Print n;If number Mod 5=0 Then Print 每每5个素数为一行个素数为一行 number=number+1 End If Next解题思路解题思路：需要设置两层循环，其中外层循环负责控制取值范围，即100200；内层循环具体判断每一个数是否为素数。一、一、常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一7工程训练中心5.65.6 综合应用举例综合应用举例综合应用举例综合应用举例例：例：求整数求整数351351432432之间既不能被之间既不能被3 3整除又不能被整除又不能被8 8整除的数的个数及这些数的整除的数的个数及这些数的和。和。解题思路解题思路：不能被3整除：n mod 30；不能被8整除：n mod 80 Dim i As Integer,n As Integer,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 数的和是：数的和是：;8工程训练中心例例 ：输入两个整数，求它们的最大公约数输入两个整数，求它们的最大公约数一、一、常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一9工程训练中心5.4 5.4 常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一常用算法与数据结构一3 3、递推法、递推法例例【5-265-26】【斐波那契数列斐波那契数列】有一个数列，第一个数为有一个数列，第一个数为1 1，第二个是为，第二个是为1 1，第三，第三个是前两个数之和，以后每个数都是前两个数之和，要求输出该数列的第个是前两个数之和，以后每个数都是前两个数之和，要求输出该数列的第N N项项。解题思路解题思路：可先把前两个数分别赋给变量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赋给B10工程训练中心5.65.6 综合应用举例综合应用举例综合应用举例综合应用举例例例【5-275-27】猴子吃桃子。有猴子第一天吃掉一半多一个，第二天吃掉剩下的一猴子吃桃子。有猴子第一天吃掉一半多一个，第二天吃掉剩下的一半多一个，半多一个，如此，到第七天吃时，只剩下如此，到第七天吃时，只剩下1 1只桃子，问一共有多少只桃子？只桃子，问一共有多少只桃子？解题思路解题思路：设第n n天桃子数为x xn n，前一天的桃子数：x xn n1 1，则有 x xn n=x=xn-1n-1(x(xn-1n-1)/2+1)/2+1)，即：，即：x xn-1n-1=(=(x xn n1)*21)*2 ；已知第七天只剩下1只桃子，则可依据上式倒推到第六天剩下的桃子，以及第五天剩下的桃子，直至第一天的桃子。Dim n as integer,i as integer x=1 FontSize=12 Print Tab(10);第第7天桃子数天桃子数:;x Print For i=6 To 1 Step-1 x=(x+1)*2 Print Tab(10);第第&I&天桃子数天桃子数&x&只只 Print N11工程训练中心
