第2章算法优秀PPT.ppt

《第2章算法优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第2章算法优秀PPT.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章算法章算法现在学习的是第1页，共28页l 本章要点现在学习的是第2页，共28页l 主要内容l2.12.1算法的概念算法的概念l2.22.2简单算法举例简单算法举例l2.32.3算法的特性算法的特性l2.42.4算法的表示算法的表示l2.52.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,S5

2、0 END50 END计算机语言是计算机语言是编写程序、制编写程序、制作软件的工具作软件的工具现在学习的是第4页，共28页 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）l计算机语言：与计算机交流的工具计算机语言：与计算机交流的工具l程序：求解问题的指令序列程序：求解问题的指令序列l软件：程序的集合软件：程序的集合学习语言学习语言 设计程序设计程序 制作软件制作软件现在学习的是第5页，共28页2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）二、如何学习计算机语言二、如何学习计算机语言学软件与学语言的区别？学软件与学语言的区别？l 软

3、件由语言编制而成，能够解决某类问题，具软件由语言编制而成，能够解决某类问题，具有确定的、有限的功能有确定的、有限的功能l 语言由确定的规则组成，可构造解决各种问语言由确定的规则组成，可构造解决各种问题的软件。题的软件。l 学软件：学软件：学思想、学功能、学操作。学思想、学功能、学操作。熟练工种熟练工种l 学语言：学语言：学规则、学方法、学设计。学规则、学方法、学设计。规范学习，灵活应用规范学习，灵活应用现在学习的是第6页，共28页 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）三、计算机语言分类三、计算机语言分类l面向过程语言面向过程语言l面向对象语言面向对象语

4、言FORTRANFORTRANBASICBASICC CPASCALPASCALCOBOLCOBOLLISPLISPC+C+Turbo PASCALTurbo PASCALV Visual isual BASICBASICV Visual J+isual J+V Visual FoxProisual FoxPro 系统软件设计系统软件设计具有图形功能具有图形功能科学计算科学计算商用商用人工智能人工智能现在学习的是第7页，共28页 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）四、程序设计四、程序设计程序设计程序设计数据结构数据结构算法算法方法方法工具工具程序设计

5、编程 对求解问题的数据描述：数据结构对求解问题的数据描述：数据结构 对求解问题的过程的描述：算法对求解问题的过程的描述：算法加工加工对象对象灵魂，是解决灵魂，是解决“做什么做什么”和和“怎么做怎么做”的的问题问题用于解决指令序列顺序的问题计算机计算机语言语言现在学习的是第8页，共28页 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）四、程序设计（续）四、程序设计（续）？什么是数据结构？什么是数据结构数据元素：数据元素：数据的最小单位数据的最小单位数据结构：数据结构：数据元素的组织形式数据元素的组织形式程序设计程序设计数据结构数据结构算法算法 数据结构的优劣决定了

6、数据结构的优劣决定了 软件或程序的复杂程度和面貌软件或程序的复杂程度和面貌现在学习的是第9页，共28页l目的：目的：改善环境，加快程序开发过程。改善环境，加快程序开发过程。l常用工具：常用工具：描述算法的图形工具、表描述算法的图形工具、表 示结构的开发工具等。示结构的开发工具等。五、程序设计工具五、程序设计工具 2-12-1计算机语言、程序与软件的区别计算机语言、程序与软件的区别(续）续）现在学习的是第10页，共28页六、程序设计的一般步骤六、程序设计的一般步骤l分析问题，建立数学模型l确定数据结构l确定算法，描述算法l编制程序，调试程序l运行结果 2-12-1计算机语言、程序与软件的区别计算

7、机语言、程序与软件的区别(续）续）现在学习的是第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次乘法次

8、乘法 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 算法及算法表示

9、（续）算法及算法表示（续）三、算法的特点三、算法的特点有穷性：一个算法应包含有限的操作步骤，而不能是无限的。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”等。等。有零个或多个输入：所谓输入是指在执行算法时需要从外界取得必要得信息。有一个或多个输出：算法的目的是为了求解，“解”就是输出。有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果。现在学习的

10、是第15页，共28页 2-2 2-2 算法及算法表示算法及算法表示(续）续）四、四、算法的两要素算法的两要素l基本功能操作基本功能操作l控制结构控制结构基本功能操作：基本功能操作：逻辑运算：与、或、非；逻辑运算：与、或、非；算术运算：加、减、乘、除；算术运算：加、减、乘、除；数据比较：大于、小于、等于、不等于、数据比较：大于、小于、等于、不等于、大等于、小于等于；大等于、小于等于；数据传送：输入、输出、赋值。数据传送：输入、输出、赋值。控制结构：控制结构：顺序、选择、循环顺序、选择、循环现在学习的是第16页，共28页 2-2 2-2 算法及算法表示算法及算法表示(续）续）五、五、算法的表示算法

11、的表示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 算法及算法表示算法及算法表示(完）完）计算函数值算法流程图计

12、算函数值算法流程图开 始输入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 一碗面条现在学习的是第2

13、0页，共28页 2-3 2-3 结构化程序设计方法结构化程序设计方法(续）续）一、程序的三种基本结构一、程序的三种基本结构1966年，Bohra和Jacopinil特点：特点：一个入口，一个出口一个入口，一个出口顺序执行顺序执行S1S2abl顺序结构顺序结构现在学习的是第21页，共28页 2-3 2-3 结构化程序设计方法结构化程序设计方法(续）续）l选择结构选择结构 语句语句N条件条件Y 条件条件 语句语句1 语句语句2YN双选择双选择单选择单选择功能功能：判断条件为真时执行语句判断条件为真时执行语句否则，否则，跳过跳过语句语句功能功能：判断条件为真时执行语句判断条件为真时执行语句1否则，否

14、则，执行执行语句语句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 结构化程序设计方法结构化程序设

15、计方法(续）续）二、二、N NS S流程图流程图19731973年美国学者年美国学者I.NassiI.Nassi和和B.ShneidermanB.Shneiderman条件条件YNS1 S22.2.选择结构选择结构S1S21.1.顺序结构顺序结构现在学习的是第25页，共28页3.3.循环结构循环结构 2-3 2-3 结构化程序设计方法结构化程序设计方法(续）续）循环体循环体循环体循环体当满足条件时当满足条件时直到条件满足时直到条件满足时当型循环当型循环直到型循环直到型循环现在学习的是第26页，共28页0t,1it+iti+1i直到直到 t 100输出输出 t 的值的值4 4、传统流程图与、传统

16、流程图与N-SN-S流程图的比较流程图的比较2-3 2-3 结构化程序设计方法结构化程序设计方法(续）续）开始0t,1it+iti+1it 100不成立不成立成立成立输出输出 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输入一个数输入一个数 xx max 是是否否xmaxi+1i直到直到i=10输出输出max直直到到型型循循环环三、模块化程序设计三、模块化程序设计输入一个数输入一个数比较比较输出最大数输出最大数顶层设计顶层设计详细设计详细设计现在学习的是第28页，共28页