程序设计语言VB60课件第二章算法.ppt

1、第2章 算 法,学习重点,算法的概念及基本特征。 算法的表示方法。 常用的算法设计方法。,本章内容,2.1 程序的基本组成：输入、处理与输出 2.2 算法与编程工具,2.1.1 计算机解题示例,计算机处理问题的过程,解决一个问题要采取的步骤就是算法。,几个算法的例子：,烧水喝：烧水沏茶喝水 一套太极拳的打法。 去医院看病：,2.1.1 计算机解题示例,2.1.1 计算机解题示例,例：求一个三角形面积,S=p(p-a)(p-b)(p-c) 其中p （abc）/2 输入 a,b,c 得到p,2.1.2 程序设计的一般步骤,1分析 2设计 3选择与创建界面 4编码 5测试与调试 6. 完成文档,2.

2、2 算法与编程工具,算法（Algorithm） 问题求解过程的精确描述 。 计算机算法可分为： 数值运算算法（数学模型） 非数值运算算法,算法示例,例1 古代有一个国王要奖赏他的臣子，问他要什么，臣子说我的要求不高，88的棋盘上第一个格子放1个麦粒，第二个格子放2个麦粒，第三个格子放22个麦粒，第64个格子上放263个麦粒。 数值运算算法,例1,算法示例,例2 高校录取新生时，按招生计划人数和当年学生的高考总分划定分数线，然后进行投档。 非数值运算算法,例2,第一步： 将所有报考该校的考生排序，且计算出省控线以上的考生数。,第二步： 确定校控线。校控线=省控线校控线省控线,算法的基本特征,1确

3、定性 2可行性 3有穷性 4输入性 5输出性,算法设计的要求,1正确性 2可读性 3健壮性 4执行时间与低存储量需求,算法的基本结构,1.顺序结构 2.选择结构 3.循环结构,算法的描述,表示方法： 自然语言 伪代码 传统流程图 N-S结构化流程图,用自然语言描述算法,自然语言日常使用的语言 优点：通俗易懂 缺点：极易产生歧义，表述不够严格 算法举例：例3 例4 例5,例3,问题描述：产生两个1100的随机整数s1和s2，求两数之和。 算法描述： 步骤1：使用公式Int(Rnd*100+1)生成第一个随机数，放入变量s1中。 步骤2：使用公式Int(Rnd*100+1)生成第二个随机数，放入变

4、量s2中。 步骤3：求解s1+s2的结果，并将结果显示出来。,顺序执行各步骤,例4,问题描述：根据用户在文本框Text1中输入的x，求 ，在文本框Text2中显示结果。,算法描述： 步骤1：将Text1中的内容放入变量x中。 步骤2：若x0，则提示错误信息“x不能小于0”，程序结束；否则，转步骤3执行。 步骤3：将的值放入变量y中。 步骤4：将变量y的值在Text2中显示出来。,顺序执行各步骤，在步骤2中选择执行下一个步骤,例5,问题描述：求解 1+2+3+4+5。 算法描述： 步骤1：求解1+2，将结果3放入变量sum中，即1+2sum。 步骤2：将sum中的值和3相加，将结果还放入变量su

5、m中，即sum+3sum。 步骤3：将sum中的值和4相加，将结果还放入变量sum中，即sum+4sum。 步骤4：将sum中的值和5相加，将结果还放入变量sum中，即sum+5sum。 步骤5：输出sum的值。,顺序执行各步骤,例5,问题描述：求解1+2+3+100 算法描述： 步骤1：给变量i赋值为1，变量sum赋值为0。 步骤2：将sum中的值和i的值相加，结果还放入变量sum中，即sum+isum。 步骤3：将i的值增加1，即i+1i。 步骤4：若i的值不大于100，则转步骤2执行；否则转步骤5。 步骤5：输出sum的值。,在步骤2到步骤4之间循环执行,伪代码表示,伪代码一种使用代码和

6、自然语言相结合的代码 。 算法举例：例6 例7 例8,例6,问题描述：产生两个1100的随机整数s1和s2，求两数之和。 算法描述： s1=第一个随机数Rnd*100+1 ; s2=第二个随机数 Rnd*100+1 ; 输出s1+s2 ;,例7,问题描述：根据用户在文本框Text1中输入的x，求 ，在文本框Text2中显示结果。,算法描述： x=Text1中的值; If x 0 Then “x不能小于0” ; End ; Else ; Text2中的值=y ; End If,例8,问题描述：求解1+2+3+100 算法描述： i=1 ; sum=0 ; do sum=sum+i ; i=i+1

7、 ; while i不大于100 ; 输出sum ;,流程图表示,使用图描述信息 常用流程图 1传统流程图 2N-S流程图,1传统流程图,一些常用的流程图符号,表5-1流程图图形符号,1传统流程图,流程图示例,1传统流程图,算法举例：例9 例10 例11,2N-S流程图,N-S流程图规定了三种基本结构的画法,（a）顺序结构,（b）选择结构,（c）当型循环,（d）直到型循环,2N-S流程图,算法举例：例 12 例 13 例 14,常用算法设计方法,1 穷举搜索法 2 递推法 3 回溯法 4 分治法,穷举搜索法,穷举搜索法的基本思想是根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些

8、是需要的，哪些是不需要的。 穷举搜索法常用于解决“是否存在”、“有多少种可能”等类型的问题。,算法举例,例15 找出1200中3的所有倍数。,法1,法2,5.6.2 递推法,递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。 迭代法是一种特殊的递推法，是一种不断用变量的旧值递推新值的过程，常用于求方程或方程组近似根。 （1）确定迭代变量。 （2）建立迭代关系式。 （3）对迭代过程进行控制。,算法举例,例16 验证谷角猜想。 日本数学家谷角静夫在研究自然数时发现了一个奇怪现象：对于任意一个自然数n，若n为偶数，则将其除以2；若n为奇数，则将其乘以3，然后再加1。如此经过有限次运算后，总

9、可以得到自然数1。人们把谷角静夫的这一发现叫做“谷角猜想”。 要求：编写一个程序，由键盘输入一个自然数n，把n经过有限次运算后，最终变成自然数1的全过程打印出来。 分析： 迭代变量为n 迭代关系式：当n为偶数时，n=n/2；当n为奇数时，n=n3+1。 迭代结束的条件为n=1,回溯法,回溯法也称试探法。 在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。,算法举例,例17 八皇后问题。在88的格子中放入8个皇后棋子，放置的条件是任何两个皇后棋子都不占据棋盘上的同一列、同一行或同一对角线。 简化：四皇后问题。,分治法,分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的

10、相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题（1kn），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。,算法举例,例18 用二分法求方程f(x)=0在区间a，b上的实根，设f(a)与f(b)异号。 分析：二分法求解方程的根是将设定区间逐步减半，最后将根锁定在一个极小的区间内，输出根的近似值。 具体过程如下：首先取给定区间的中点c=(a+b)/2；然后判断f(c)是否为0。若f(c)=0，则说明c即为所求的根，求解过程结束；如果f(c)0，则根据一项原则将原区间减半：若f(a)f(c)0，则取原区间的前一半部分；若f(b)f(c)0，则取原区间的后一半部分，最后判断减半后的区间长度是否已经很小：若|a-b|，则求解过程结束，取(a+b)/2为根的近似值；否