2.1 算法与程序 2.2 结构化程序设计方法简介 2.3 结构化程序的描述 2.4 简单程序分析.

Presentation on theme: "2.1 算法与程序 2.2 结构化程序设计方法简介 2.3 结构化程序的描述 2.4 简单程序分析."— Presentation transcript:

1 2.1 算法与程序 2.2 结构化程序设计方法简介 2.3 结构化程序的描述 2.4 简单程序分析

2 清华大学出版社 2.1 算法与程序 2.1.1 算法 “ 计算机科学就是关于算法的科学 ” 。 算法： 大陆中文名称出自《周髀算经》、《九章算术》， 英文名称 Algorithm 来自于 9 世纪波斯数学家 al-Khwarizmi ， 因为 al-Khwarizmi 在数学上提出了算法这个概念。 算法 ” 原为 "algorism" ，意思是阿拉伯数字的运算法则，在 18 世纪演变为 "algorithm" 。 第一次编写程序的是 Ada Byron （一位女士） 20 世纪的英国数学家图灵提出了著名的图灵论题，并提出 一种假想的计算机的抽象模型，这个模型被称为图灵机。 图灵机的出现解决了算法定义的难题，图灵的思想对算法 的发展起到了重要作用。

3 清华大学出版社 2.1 算法与程序 算法的定义： 常被定义为是对特定问题求解步骤的一种描述，包含操作的有 限规则和操作的有限序列。 通俗一点讲，算法就是一个解决问题的公式（数学手册上的公 式都是经典算法）、规则、思路、方法和步骤。 算法可以用自然语言描述、伪代码描述，也可以用流程图描述， 但最终要用计算机语言编程，上机实现。 程序与算法： 程序是操作计算机完成特定任务的指令的集合，程序由程序设 计语言来具体实现。 实际中，程序是用来解决特定问题的，而算法是对解决问题步 骤的描述，他是程序设计的基础。 沃思（ N.Wirth ）提出了一个经典的公式： 程序 ＝ 数据结构 ＋ 算法

4 清华大学出版社 2.1 算法与程序 算法应具有如下特点： 有穷性 确定性 有效性 有 0 个或多个输入 有 1 个或多个输出

5 清华大学出版社 2.1 算法与程序 2.1.2 程序 面向机器的语言 面向结构过程的语言 是进行以模块功能和处理过程设计为主的详细设计的基本原则。 C 语言， Pascal 语言等属于结构化语言的代表。 面向对象的语言 是一类以对象作为基本程序结构单位的程序设计语言，指用于 描述的设计是以对象为核心，而对象是程序运行时刻的基本成 分。语言中提供了类、继承等成分。

6 清华大学出版社 2.1 算法与程序 2.1.3 常用开发语言简介 TIOBE 编程语言社区排行榜最新公布（ 2014 年 5 月） 的开发语言排行榜前十依次是 C 、 Java 、 Objective-C 、 C++ ， Visual Basic 、 C# 、 PHP 、 Python 、 JavaScript 和 Perl. JAVA Objective-C C++ Visual Basic C# PHP Python JavaScript Perl

7 清华大学出版社 2.2 结构化程序设计方法简介 概念的提出：最早由 E.W.Dijikstra 在 1965 年提出的，是软 件发展的一个重要里程碑。 主要观点：采用自顶向下、逐步求精及模块化的程序设计 方法；使用三种基本控制结构构造程序，既任何程序都可 由顺序、选择、循环三种基本控制结构构造。 描述方法：可以采用图形、表格和语言进行详细描述。 图形：程序流程图、 N-S 图、 PAD 图 表格：判定表 语言：过程设计语言（ PDL ）

8 清华大学出版社 2.2 结构化程序设计方法简介 要点： 主张使用顺序、选择、循环三种基本结构来嵌套连结成具有复 杂层次的 “ 结构化程序 ” ，严格控制 GOTO 语句的使用。 “ 自顶而下，逐步求精 ” 的设计思想，其出发点是从问题的总体目 标开始，抽象低层的细节，先专心构造高层的结构，然后再一 层一层地分解和细化。 “ 独立功能，单出、入口 ” 的模块结构，减少模块的相互联系使模 块可作为插件或积木使用，降低程序的复杂性，提高可靠性。 结构化程序设计的三种基本结构具体是 指：顺序结构、选择结构和循环结构。

9 清华大学出版社 2.3 结构化程序的描述 结构化程序的描述最常用的方法： （ 1 ）伪代码（ Pseudocode ）：介于自然语言与编程语言之间。 是一种近似于高级程序语言但是又不受语法约束的描述方式， 相比高级程序语言它更类似于自然语言。 例 2-1 输入 3 个数，输出其中最大的数。用伪代码描述该程序。 算法开始 输入三个数 A ， B ， C 如果 A 大于 B 则 记录最大数 Max 值为 A 否则记录最大数 Max 值为 B 如果 C 大于 Max 则 记录最大数 Max 值为 C 输出 Max 算法结束 但是复杂的算法（程序），由于伪代码 相对比较随意，对算法的描述其实是不 严谨的，容易出现推理漏洞。而且，伪 代码描述过程因人而异，对问题的描述 往往不够直观。

10 清华大学出版社 2.3 结构化程序的描述 结构化程序的描述最常用的方法： （ 2 ）流程图描述：千言万语不如一张图，因此使用图形表示算 法的思路是一种极好的方。 一般流程图中的基本图形元素： 通过基本图形中的框和流程线组成的流 程图来表示算法，形象直观，简单方便。 但是，这种流程图对于流程线的走向没 有任何限制，可以任意转向，在描述复 杂的算法时所占篇幅较多。

11 清华大学出版社 2.3 结构化程序的描述 结构化程序的描述最常用的方法： （ 2 ）流程图描述：千言万语不如一张图，因此使用图形表示算 法的思路是一种极好的方。 (a) 一般流程图 基本图形元素： 通过基本图形中的框和流程线组成的流 程图来表示算法，形象直观，简单方便。 但是，这种流程图对于流程线的走向没 有任何限制，可以任意转向，在描述复 杂的算法时所占篇幅较多。

12 清华大学出版社 2.3 结构化程序的描述 结构化程序的描述最常用的方法： （ 2 ）流程图描述：千言万语不如一张图，因此使用图形表示算 法的思路是一种极好的方。 (b) N-S 流程图： 1973 年美国学者 I.Nassi 和 B.Shneiderman 提出了 一种新的流程图形式。这种方法完全去掉了流程线，算法的每一 步都用一个矩形框来描述，把一个个矩形框按执行的次序连接起 来就是一个完整的算法描述。 优点：强制设计人员按结构化程序方法进行思考并描述设计方案， 因为除了表示几种标准结构的符号之处，它不再提供其他描述手段， 这就有效地保证了设计的质量，从而也保证了程序的质量。

13 清华大学出版社 2.3 结构化程序的描述 结构化程序设计中三种基本结构的图形描述： （ 1 ）顺序结构：顺序结构是指程序的执行按语句的先后顺序逐 条执行，没有分支，没有转移。

14 清华大学出版社 2.3 结构化程序的描述 结构化程序设计中三种基本结构的图形描述： （ 2 ）选择结构：选择结构表示程序的处理步骤出现了分支，它 需要根据某一特定的条件选择其中的一个分支执行。 选择结构有单选择、双选择和多选择三 种形式（详见教材第 5 章）。

15 清华大学出版社 2.3 结构化程序的描述 结构化程序设计中三种基本结构的图形描述： （ 3 ）循环结构：循环结构表示程序反复执行某个或某些操作， 直到某条件为假（或为真）时才可终止循环。 注意在循环结构中最主要的是：什么情况下执行循环？哪些操 作需要循环执行？ 循环结构的基本形式有两种： 当型循环 直到型循环

16 清华大学出版社 2.3 结构化程序的描述 结构化程序设计中三种基本结构的图形描述： （ 3 ）循环结构： 当型循环：表示先判断条件，当满足给定的条件时执行循环体， 并且在循环终端处流程自动返回到循环入口；如果条件不满足， 则退出循环体直接到达流程出口处。

17 清华大学出版社 2.3 结构化程序的描述 结构化程序设计中三种基本结构的图形描述： （ 3 ）循环结构： 直到型循环：表示从结构入口处直接执行循环体，在循环终端处 判断条件，如果条件满足，返回入口处继续执行循环体，直到条 件为假时再退出循环到达流程出口处，是先执行后判断。

18 清华大学出版社 2.4 简单程序分析 例 2-2 求解 1+2+3+…+100 的和，画出程序流程图。 解题思路： 先初始当前求和数 i 等于 1 ，和值 sum 等于 0 ；当求 和数 i 小于等于 100 时，和值 sum 等于已经计算的和 值 sum 加上当前的求和数 i ；然后将 i 的值增加 1 ，如 此不断循环，直到 i 大于 100 。这样，最后 sum 的值 就是 1+2+3+…+100 的和，程序最后输出 sum 。

19 清华大学出版社 2.4 简单程序分析 例 2-2 求解 1+2+3+…+100 的和，画出程序流程图。 根据此思路，画出程序的一般流程图和相应的 N-S 流程图 变量 i 用来控制循环， 当 i<=100 时，执行 循环体； 在循环体内进行求 和及变量 i 值的增加。

20 清华大学出版社 2.4 简单程序分析 例 2-3 输入三个数 A 、 B 、 C ，求出其中的最大值，画出 程序流程图。 解题思路： 三个数求最大值的方法很多，这里采用：先比较 两个数 A 、 B ，如果 A>B ，则将 A 赋值给变量 Max ， 否则把 B 的值赋值给 Max ；再比较 Max 与 C ，如果 Max>C ，则输出 Max 即为最大值，否则把 C 的值赋 值给 Max ，再输出最大值 Max 。

21 清华大学出版社 2.4 简单程序分析 例 2-3 输入三个数 A 、 B 、 C ，求 出其中的最大值，画出程序流 程图。 根据此思路，画出程序的一般流 程图和相应的 N-S 流程图

22 清华大学出版社 2.4 简单程序分析 例 2-4 先后输入若干个整数，要求求出其中的最大数，当 输入的数小于 0 时结束，画出程序流程图。 解题思路： 先输入一个数，在没有其他数参加比较之前，它显然 是当前最大数，把它放到变量 max 中。然后输入第二 个数，并与 max 比较，如果第二个数大于 max ，则用第 二个数取代 max 中原来的值。如此重复输入并比较， 每次比较后都将最大值存在 max 中，直到输入的数小 于 0 时结束。这样，最终 max 中的值就是所有输入数中 的最大值。

23 清华大学出版社 2.4 简单程序分析 例 2-4 先后输入若干个整数， 要求求出其中的最大数，当输 入的数小于 0 时结束，画出程序 流程图。 根据此思路，画出程序的一般流 程图和相应的 N-S 流程图 变量 x 用来控制循环 的次数，当 x>0 时， 执行循环体； 在循环体内进行两个 数的比较和输入 x 值.