第2章算法精.ppt
第第2章算法章算法第1页，本讲稿共28页l 本章要点第2页，本讲稿共28页l 主要内容l2.1算法的概念l2.2简单算法举例l2.3算法的特性l2.4算法的表示l2.5结构化程序设计方法第3页，本讲稿共28页 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别一、什么是计算机语言一、什么是计算机语言10 R=520 L=2*3.14*R20 L=2*3.14*R30 S=3.14*R*R30 S=3.14*R*R40 PRINT R,L,S40 PRINT R,L,S50 END50 END计算机语言是计算机语言是编写程序、制编写程序、制作软件的工具作软件的工具第4页，本讲稿共28页 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）l计算机语言：与计算机交流的工具计算机语言：与计算机交流的工具l程序：求解问题的指令序列程序：求解问题的指令序列l软件：程序的集合软件：程序的集合学习语言 设计程序 制作软件第5页，本讲稿共28页2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）二、如何学习计算机语言二、如何学习计算机语言学软件与学语言的区别？学软件与学语言的区别？l 软件由语言编制而成，能够解决某类问题，具软件由语言编制而成，能够解决某类问题，具有确定的、有限的功能有确定的、有限的功能l 语言由确定的规则组成，可构造解决各种问语言由确定的规则组成，可构造解决各种问题的软件。题的软件。l 学软件：学软件：学思想、学功能、学操作。学思想、学功能、学操作。熟练工种熟练工种l 学语言：学语言：学语言：学语言：学规则、学方法、学设计。学规则、学方法、学设计。规范学习，灵活应用规范学习，灵活应用第6页，本讲稿共28页 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）三、计算机语言分类三、计算机语言分类l面向过程语言面向过程语言l面向对象语言面向对象语言FORTRANFORTRANBASICBASICC CPASCALPASCALCOBOLCOBOLLISPLISPC+C+Turbo PASCALTurbo PASCALV Visual isual BASICBASICV Visual J+isual J+V Visual FoxProisual FoxPro 系统软件设计具有图形功能科学计算商用人工智能第7页，本讲稿共28页 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）四、程序设计四、程序设计程序设计程序设计数据结构数据结构算法算法方法方法工具工具程序设计编程 对求解问题的数据描述：数据结构对求解问题的数据描述：数据结构 对求解问题的过程的描述：算法对求解问题的过程的描述：算法加工对象灵魂，是解决灵魂，是解决“做什么做什么”和和“怎么做怎么做”的的问题问题用于解决指令序列顺序的问题计算机语言第8页，本讲稿共28页 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）四、程序设计（续）四、程序设计（续）？什么是数据结构？什么是数据结构数据元素：数据元素：数据的最小单位数据的最小单位数据结构：数据结构：数据元素的组织形式数据元素的组织形式程序设计数据结构算法 数据结构的优劣决定了数据结构的优劣决定了 软件或程序的复杂程度和面貌软件或程序的复杂程度和面貌第9页，本讲稿共28页l目的：目的：改善环境，加快程序开发过程。改善环境，加快程序开发过程。l常用工具：常用工具：描述算法的图形工具、表描述算法的图形工具、表 示结构的开发工具等。示结构的开发工具等。五、程序设计工具 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）第10页，本讲稿共28页六、程序设计的一般步骤六、程序设计的一般步骤l分析问题，建立数学模型l确定数据结构l确定算法，描述算法l编制程序，调试程序l运行结果 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）第11页，本讲稿共28页六、程序设计的一般步骤六、程序设计的一般步骤 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(完）完）分析问题建立数学模型确定数据结构和算法编写程序调试运行分析整理结果第12页，本讲稿共28页 2-2 2-2 算法及算法表示算法及算法表示l算法：算法：完成一项任务的具体步骤完成一项任务的具体步骤l计算机语言的别名：计算机语言的别名：算法语言算法语言 2R=L，R2=S 3次乘法次乘法,1次乘方次乘方 R=A，2A=L，AR=S 3次乘法次乘法 2R=L，RR=S 4次乘法次乘法 一、什么是算法例求圆周长和圆面积求圆周长和圆面积数学模型：数学模型：L L2 2 R SR S R R2 2三种算法：三种算法：可读性好执行效率高 综合综合的优点的优点 第13页，本讲稿共28页 2-2 2-2 算法及算法表示（续）算法及算法表示（续）二、计算机算法类别数值运算算法非数值运算算法非数值运算算法比较成熟容易实现有程序库应用广泛种类繁多难以规范特定问题必须特定处理第14页，本讲稿共28页 2-2 2-2 算法及算法表示（续）算法及算法表示（续）三、算法的特点有穷性：一个算法应包含有限的操作步骤，而不能是无限的。i=0;S=0;while(1)S=S+i;i=i+1;i=0;S=0;while(i100)S=S+i;i=i+1;确定性：算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的，即不能有歧义。如：如：“手举过头顶手举过头顶”，“n被一个整数除，被一个整数除，得余数得余数r”等。等。有零个或多个输入：所谓输入是指在执行算法时需要从外界取得必要得信息。有一个或多个输出：算法的目的是为了求解，“解”就是输出。有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果。第15页，本讲稿共28页 2-2 2-2 算法及算法表示算法及算法表示(续）续）四、算法的两要素l基本功能操作基本功能操作l控制结构控制结构基本功能操作：基本功能操作：逻辑运算：与、或、非；逻辑运算：与、或、非；算术运算：加、减、乘、除；算术运算：加、减、乘、除；数据比较：大于、小于、等于、不等于、数据比较：大于、小于、等于、不等于、大等于、小于等于；大等于、小于等于；数据传送：输入、输出、赋值。数据传送：输入、输出、赋值。控制结构：控制结构：顺序、选择、循环顺序、选择、循环第16页，本讲稿共28页 2-2 2-2 算法及算法表示算法及算法表示(续）续）五、算法的表示l图形符号图形符号起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流向线连接点连接点第17页，本讲稿共28页 2-2 2-2 算法及算法表示算法及算法表示(续）续）l用流程图表示算法 t=1开始t2tt3tt4t11t5t输出t结束开始 t=1 i=2titi+1ii511输出 t结束例例2:2:求求1 1 2 2 3 3 4 4 5 5，即，即5 5。用流程图表示法。用流程图表示法。方方法法一：一：方方法法二：二：第18页，本讲稿共28页 2-2 2-2 算法及算法表示算法及算法表示(完）完）计算函数值算法流程图开 始输入a,b,c,x输出m结束xaYbx+a2ma(c-x)+c2mN 求最大公约数算法流程图m/n余数rnmrnN开 始输入m,n输出n结束r=0?Y求余数选择结构流程图选择结构流程图循环结构流程图循环结构流程图第19页，本讲稿共28页2-3 2-3 结构化程序设计方法结构化程序设计方法传统流程图利用利用goto指令可以毫无受限制地使流程随意地转指令可以毫无受限制地使流程随意地转来转去。来转去。(1)毫无规律毫无规律(2)阅读费力阅读费力(3)逻辑复杂逻辑复杂BS算法：a bowl of spaghetti 一碗面条第20页，本讲稿共28页 2-3 2-3 结构化程序设计方法结构化程序设计方法(续）续）一、程序的三种基本结构一、程序的三种基本结构1966年，Bohra和Jacopinil特点：特点：一个入口，一个出口一个入口，一个出口顺序执行顺序执行S1S2abl顺序结构第21页，本讲稿共28页 2-3 2-3 结构化程序设计方法结构化程序设计方法(续）续）l选择结构选择结构 语句N条件Y 条件 语句1 语句2YN双选择双选择单选择单选择功能功能：判断条件为真时执行语句判断条件为真时执行语句否则，否则，跳过跳过语句语句功能功能：判断条件为真时执行语句判断条件为真时执行语句1否则，否则，执行执行语句语句2第22页，本讲稿共28页 2-3 2-3 结构化程序设计方法结构化程序设计方法(续）续）语句1N条件1Y条件2条件nYY语句2语句3语句nNN多分支多分支功能功能：从多个条件中从多个条件中选择满足条件的一个选择满足条件的一个分支执行。分支执行。第23页，本讲稿共28页 2-3 2-3 结构化程序设计方法结构化程序设计方法(续）续）l循环结构循环结构循环体N条件Y当型循环当型循环直到型循环直到型循环条件NY循环体先循环后判断先循环后判断入口出口第24页，本讲稿共28页2-3 2-3 结构化程序设计方法结构化程序设计方法(续）续）二、二、N NS S流程图流程图19731973年美国学者年美国学者I.NassiI.Nassi和和B.ShneidermanB.Shneiderman条件YNS1 S22.选择结构S1S21.顺序结构第25页，本讲稿共28页3.循环结构 2-3 2-3 结构化程序设计方法结构化程序设计方法(续）续）循环体循环体当满足条件时直到条件满足时当型循环直到型循环第26页，本讲稿共28页0t,1it+iti+1i直到 t100输出 t 的值4、传统流程图与N-S流程图的比较2-3 2-3 结构化程序设计方法结构化程序设计方法(续）续）开始0t,1it+iti+1it100不成立成立输出 t 的值结束例例1 1：1+2+3+1+2+3+直到直到t t大于大于100100，输出，输出t t？第27页，本讲稿共28页例例2 2：输入：输入1010个整数，个整数，要求打印出其中最大要求打印出其中最大的数。用的数。用N-SN-S图表示图表示。2-3 2-3 结构化程序设计方法结构化程序设计方法(完）完）输入1个数max计数器 i=1输入一个数 xxmax 是否xmaxi+1i直到i=10输出max直到型循环三、模块化程序设计输入一个数比较输出最大数顶层设计详细设计详细设计第28页，本讲稿共28页
