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