03控制结构_常见算法.ppt

1、计算机语言VB,基本控制结构_常见算法,2020年7月16日11时59分,2/20,算 法,算法：是对某个问题求解的过程。算法有很多表达方式，通俗地讲，程序就是用计算机语言表达的算法；流程图就是图形化了的算法。同一问题有多种算法描述。算法是程序的核心、编程的基础。 算法种类：数值算法和非数值算法。,2020年7月16日11时59分,3/20,复习基本控制结构语句,顺序结构 InputBox（）函数 MsgBox函数与语句 Print方法 选择结构 IfThenElse条件语句 情况语句Select CaseEnd Select 条件语句嵌套 循环结构 ForNext循环语句 DoLoop循环语

2、句 多重循环（循环嵌套）,2020年7月16日11时59分,4/20,主要内容,累加与连乘算法 穷举(枚举)算法 递推(迭代)算法,2020年7月16日11时59分,5/20,累加与连乘,累加：是在原有和的基础上每次加一个数。 连乘：是在原有积的基础上每次乘一个数。,示例1：求1到100间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 1到100间5的倍数和7的倍数之和为:; sum,2020年7月16日11时59分,6/20,示

3、例2：求e= 1+1/1!+1/2!+1/3!+1/n!，直到最后一项的绝对值小于0.00001 为止。,Dim i e,2020年7月16日11时59分,7/20,练习题,累加、连乘 练习1：求/4= 1-1/3+1/5-1/7，直到最后一项的绝对值小于0.000001为止。 练习2：求S=a+aa+aaa+aaa(n个a)。其中a为19的一个正整数。如a=2，n=4，则求S=2+22+222+2222。,2020年7月16日11时59分,8/20,穷举法（枚举法）,穷举算法：对问题的所有可能解一一测试，直到找出所有解或将全部状态测试过为止。 穷举算法循环控制两种办法： 记数法：先要确定循环

4、次数，然后逐次测试，完成测试次数后，循环结束。 标志法：在循环次数无法事先确定的情况下，先确定一个结束目标，达到目标后，循环结束。 使用穷举法需掌握的两条原则：确定搜索范围和选择搜索策略。,2020年7月16日11时59分,9/20,示例3：百钱买百鸡。（鸡翁一,值钱五，鸡母一,值钱三，鸡雏三,值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？） 分析 依题意，列方程： Cocks + hens + chicks=100 5*cocks + 3*hens + chicks/3 = 100 各变量取值范围：,Cocks: 120 Hens: 133 Chicks: 399,2020年7月16日11时

5、59分,10/20,Cocks hens chicks,1,1,98,2,97,33,66,2,1,2,33,97,96,65,20,1,2,33,2020年7月16日11时59分,11/20,Dim cocks%, hens%, chicks% Print Tab(5); 公鸡; Tab(10); 母鸡; Tab(20); 小鸡 For cocks = 1 To 20 For hens = 1 To 33 chicks = 100 - cocks - hens If cocks * 5 + hens * 3 + chicks 3 = 100 _ and chicks mod 3=0 Then

6、 Print Tab(5); cocks; Tab(10); hens; Print Tab(20); chicks End If Next hens Next cocks,2020年7月16日11时59分,12/20,示例4：求素数。 分析： 素数：只能被1和自己整除的数。 判断数n是否为素数的方法： 在2sqr(n)中能否找到一个整数i能将n整除，若i存在，则n不是素数；若找不到i，则n为素数。 如: 11：要用2、3除 16：要用2、3、4除,2020年7月16日11时59分,13/20,Dim n As Integer, i As Integer n = InputBox(请输入一个正

7、数(=3) i = 2: flag = 1 : k = Int(Sqr(n) for i=2 to k If n Mod i = 0 Then flag = 0 Exit For End If next i If flag = 1 Then Print n; 是一个素数！ Else Print n; 不是一个素数！ End If,2020年7月16日11时59分,14/20,练习题,穷举法 练习1：搬砖问题：36块砖，36人搬，男搬4，女搬3，两个小孩抬一块砖。要求一次全搬完，问男、女、小孩各若干？ 练习2：求50以内的素数。 练习3：编写程序输出所有的水仙花数。水仙花数是一个3位数，其各位数

8、的立方和等于该数，如153=13+53+33,2020年7月16日11时59分,15/20,递推法（迭代法）,迭代：不断用新值取代变量的旧值或由旧值递推出变量的新值的过程。 与迭代有关因素：初值、迭代式子、迭代次数。 示例分析：人口增长问题：现有12亿人，按年2%的增长速度，10年后将有多少人？ 设人口用变量P表示； 现有人口数P=12亿 (初值); 第一年后人口P=P*（1+0.02）(迭代式子)；,第二年后人口P=P*（1+0.02）(迭代式子) ；,10年后人口，将上述表达式执行10 (迭代次数)次。,2020年7月16日11时59分,16/20,示例5：兔子繁殖问题：设有一对新生兔子，

9、从第三个月开始每个月都生一对兔子，按此规律，并假设没有兔子死亡，一年后共有多少对兔子？（裴波那契数列） 分析： 每月兔子对数（用f表示）呈如下规律： 1，1，2，3，5，8，13，21，34 迭代规律：,f1=f2=1 （初值） f3=f1+f2 （迭代式子） f4=f2+f3 （迭代式子） f12=f10+f11 （迭代式子） n=10 （迭代次数）,2020年7月16日11时59分,17/20,f1 = 1 f2 = 1 Print f1 ; f2; For i = 3 To 12 f3 = f1 + f2 Print f3; f1 = f2 f2 = f3 Next i,2020年7月1

10、6日11时59分,18/20,示例6：求2个非负整数的最大公约数、最小公倍数。(辗转相除法) 分析：,u=55 v=15,r= u Mod v 10,u=15,v=10,r= u Mod v 5,u=10,v=5,r= u Mod v 0,u=5,v=0(终止）,2020年7月16日11时59分,19/20,a = InputBox(请输入第一个整数) b = InputBox(请输入第二个整数) If a 0 r = u Mod v u = v v = r Loop Print a & 和 & b & 的最大公约数为： & u k = a * b / u Print a & 和 & b & 的最小公倍数为： & k,2020年7月16日11时59分,20/20,练习题,递推法 练习1：小猴吃桃：第一天小猴摘下若干桃子，当即吃了一半，还觉得不过