程序准备算法的概念.ppt

,绪论,程序设计基础知识,本章要点,什么是程序设计 什么是算法，如何设计算法 结构化程序设计的思想和方法,共 29 页 第 3 页,计算机是如何工作的？ Program的中文词义： 名词：程序、次序、计划、节目单、说明书 动词：为.编制程序、设计、制定大纲、为.安排节目 Microsoft?,共 29 页 第 4 页,计算机语言：是规则和符号的集合，是与计算机交流的工具 程序：用某种计算机能够识别的语言(符号)编写的求解问题的指令序列 软件：以程序为主要表现的：数据结构+算法+文档的集合,概念,共 29 页 第 5 页,懂得计算机是如何工作的； 掌握一种计算机语言； 学会问题的分解与复合； 学会一种思考方法。,本课程的目标：,共 29 页 第 6 页,算法：完成一项任务的具体步骤,1. 算法的概念,二、算法和算法的表示,“一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。” 任何解决问题的过程都是由一定的步骤组成的，把解决问题确定的方法和有限的步骤称作为算法。,共 29 页 第 7 页,例1：计算一元二次方程求的根。,分析：这是一个初中数学问题。我们已经知道： a不能为0，否则就不是一元二次方程了，在这个前提下可以使用求根公式，同时还必须注意到：若 没有实根；,依据此公式计算出两个实根。,共 29 页 第 8 页, 将a、b、c和x的值输入到计算机； 判断a 0?如果条件成立，否则退出； 计算 的值，(设用符号T代表该值) 判断：若T0 ？则本方程无实根，然后执行第步； 否则，可以使用求根公式计算 输出的值； 算法结束。,这是用自然语言描述的算法,分步求解的过程：,共 29 页 第 9 页,例2：计算函数M(x)的值。函数M(x)为：,算法分析：这是一个数值运算问题。其中M代表要计算的函数值，有两个不同的表达式，根据x的取值决定采用哪一个算式。根据计算机具有逻辑判断的基本功能，用计算机解题的算法如下：,共 29 页 第 10 页, 将a、b、c和x的值输入到计算机； 判断xa?如果条件成立，执行第步，否则执行第步； 按表达式bx+a2计算出结果存放到M中，然后执行第步； 按表达式a(c-x)+c2计算出结果存放到M中，然后执行第步； 输出M的值； 算法结束。,这是用自然语言描述的算法,共 29 页 第 11 页,例：有黑和蓝两个墨水瓶，但却错把黑墨水装在了蓝墨水瓶子里，而蓝墨水错装在了黑墨水瓶子里，要求将其互换。,算法分析：这是一个非数值运算问题。因为两个瓶子的墨水不能直接交换，所以，解决这一问题的关键是需要引入第三个墨水瓶。设第三个墨水瓶为白色，其交换步骤如下：,共 29 页 第 12 页,将蓝瓶中的黑墨水装入白瓶中 将黑瓶中的蓝墨水装入蓝瓶中 将白瓶中的黑墨水装入黑瓶中 交换结束,共 29 页 第 13 页,2.常用算法简介,（1）交换两个变量的值 采用间接交换方法,a,t,b,(2)计数器和累加器 计数器：用于统计循环的次数。如：i=i+1 累加器：用于实现数值求和。如：sum=sum+x,共 29 页 第 14 页,（3）枚举法（穷举法或试凑法） 根据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到所有情况验证完。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。 如：8角的硬币组成问题。,(4)递推法（迭代法） 利用问题本身所具有的某种递推关系求解问题。 从初值出发，归纳出新值与旧值间直到最后值为止存在的关系，从而把一个复杂的计算过程转换为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。 如：牛顿公式问题。,共 29 页 第 15 页,（5）求最大值、最小值问题 采用如同打擂台的方法。 在n个数中，先假设第一个数为最大值，成为擂主，依次同第2，3，n个数据逐一比较，一旦某个数大，马上替换擂主；所有值比较完，最大值也就获得。 求最小值问题则先假设第一个数为最小值。,共 29 页 第 16 页,3.算法的基本特征,算法是一个有穷规则的集合，这些规则确定了解决某类问题的一个运算序列。算法的基本特征：,有穷性：算法必须在执行有限个操作后终止； 确定性：算法中每一步的含义必须是确切的，不可出现任何二义性； 有效性：算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的； 有零个或多个输入 ； 有一个或多个输出。,共 29 页 第 17 页,4.算法的表示,可以用不同的方法表示算法，常用的有： 自然语言 传统流程图 结构化流程图 伪代码 PAD图,共 29 页 第 18 页,结束,(1)用流程图表示算法,美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号：,共 29 页 第 20 页,例： 有50个学生 ，要求将他们之中成绩在80分以上者打印出来。用g代表学生成绩， gi 代表第i个学生成绩。,算法可表示如下： S1：1i S2：如果gi 80 ，则打印 gi ，否则不打印 S3： i+1 i S4: 如果 i 50, 返回S2， 继续执行； 否则，算法结束。,共 29 页 第 21 页,程序流程图示例,共 29 页 第 22 页,2.程序的三种基本结构,(1) 顺序结构 程序按照语句的书写次序顺序执行。,先执行A操作，再执行B操作，两者是顺序执行关系。,共 29 页 第 23 页,(2) 选择结构 通过判断特定条件，选择一个分支执行。,当P条件为非零时，执行A操作，否则执行B操作,当P条件为非零时，执行语句操作，否则跳过语句操作,共 29 页 第 24 页,( 3)循环结构 在给定条件下，反复执行循环体，直到条件不满足为止.,1)形式a,当P为非零时，反复执行A,直到P为零为止。,共 29 页 第 25 页,2)形式b,先执行A操作，再判断P是否为非零，若P为非零，再执行A，直到P为零为止。,共 29 页 第 26 页,传统流程图的弊端 传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以毫不受限制地使流程随意地转向，使流程图变得毫无规律，阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。如图：,共 29 页 第 27 页,传统流程图的流程可以是：,缺点：难以阅读、修改，使算法的可靠性和可维护性难以保证。 解决办法：必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序地进行下去。,共 29 页 第 28 页,2. NS流程图,NS流程图: 表示算法的图形工具。基本单元是矩形框,用不同的形状线分割,表示三种结构.只有一个入口,一个出口,没有流程线。 N-S图的优点 比文字描述直观、形象、 易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N-S流程图中的上下顺序就是执行时的顺序。,共 29 页 第 29 页,NS流程图,3.循环结构,共 29 页 第 30 页,传统流程图与N-S流程图的比较,例1：1+2+3+ 加到100为止,共 29 页 第 31 页,三、结构化程序设计方法,结构化程序设计方法是公认的面向过程编程应遵循的基本方法和原则。结构化程序设计方法主要包括： 只采用三种基本的程序控制结构来编制程序，从而使程序具有良好的结构； 程序设计自顶而下； 用结构化程序设计流程图表示算法。,共 29 页 第 32 页,例：输入10个整数，要求打印出其中最大的数。用N-S图表示。,详细设计,共 29 页 第 33 页,计算机语言分类,面向过程语言 面向对象语言,FORTRAN BASIC C PASCAL COBOL LISP,C+ C# Visual C Visual BASIC Visual J+,共 29 页 第 34 页,一、 程序设计的基本概念,计算机的别名：数据处理机 数据元素：数据的最