C语言-算法.pptVIP

《C语言程序设计》 第2章 算 法 作 业 E-mail: toclw@163.com 学习资料 E-mail: clstu@163.com 口 令 cls123 1.4 程序与算法 1.4.1 程序与程序设计 著名计算机科学家沃思提出一个公式： 程序 = 数据结构 + 算法 数据结构是对程序中数据的描述，主要是数据的类型和数据的组织形式； 算法是对程序中操作的描述，即操作步骤。 程序的灵魂 — 算法 著名计算机科学家沃思（Niklklaus Wirth）提出： 数据结构十算法 = 程序 一个C程序应包括两个方面的内容： 数据的描述 操作步骤，即动作的描述 2. 程序设计 编写C语言程序，掌握一定的程序设计技巧。 用计算机解决问题 --- 编程的过程： ① 分析问题，确定解决问题的方法和步骤。 ② 编写程序 ③ 上机运行程序得出结果。 程序设计的关键：要学会使用计算机语言，更要掌握解题的步骤和方法 。 “算法” 就是研究解题的步骤和方法。 用计算机求解问题——程序设计 程序设计的步骤 程序 ＝ 算法 十 数据结构 十 语言工具十程序设计方法 以上四个方面是一个程序设计人员所应具备的。 1.4.2 算法 1. 算法的概念 为解决一个问题而采取的方法和步骤. 算法是程序的灵魂，反映了计算机执行的过程；算法设计是程序设计的重要环节。 同一个问题可以有不同的算法。 2.算法的分类(计算机能否执行、特征） 数值算法 (求方程的根，定积分 ) 非数值算法 ( 排序，图书情报资料检索 ). 3.算法的评价(优劣) : 算法复杂性 = 算法所需要的计算机资源. 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 其中n是问题的规模（输入大小）。 简单、运算步骤少的，也就是运算快、内存开销小的算法（算法的时空效率）。 对同一个问题，可有不同的解题方法和步骤 例： 求 4. 算法的特性 有穷性 确定性 有零个或多个输入 有一个或多个输出 有效性 算法中的每一步都应该能有效地执行。 1.4.3 怎样表示一个算法 常用的算法表示方法： 自然语言（通俗、易学） 传统流程图（直观） 结构化流程图（N-S流程图） 伪代码 （实用） 计算机语言 （编程） ( 重点：传统流程图，N-S流程图 ) 1. 用自然语言表示 用自然语言表示通俗易懂，但文字冗长，容易出现歧义。 自然语言表示的含义往往不太严格，要根据上下文才能准确判断其含义。 用自然语言描述分支和循环的算法，不很直观。因此，除了简单问题，一般不采用自然语言描述算法。 第1种：使用自然语言描述求n!的算法。 ① 确定一个n的值； ② 假设等号右边的算式项中的初始值i 为1； ③ 假设变量f 中存放n!的值，且初始值为1； ④ 如果 i ? n 时，执行⑤，否则转出执行⑧； ⑤ 计算f 乘以i的值后，重新赋值给f； ⑥ 计算 I 加1，然后将值重新赋值给i； ⑦ 转去执行 ④； ⑧ 输出f 的值，即n!的值，算法结束。 2. 用流程图表示算法 用一些图框表示各种操作，用箭头表示算法流程。 优点: 直观形象，易于理解。 美国标准化协会ANSI 规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用。 表1-1 流程图的符号表示 三种结构的特点： 只有一个入口和出口. 结构内的每一部分都有机会被执行到. 结构内不存在死循环（无终止的循环）. 多分支选择结构 N-S流程图 Bohra和Jacopini提出了三种基本结构; 1973年美国学者I.Nassi和B.Shneiderman提出N--S流程图. (1) 顺序结构 （2）二分支选择结构 （3）循环结构 1)当型(WHILE型)循环 2) 直到型(UNTIL)循环结构 两类循环的比较 基本框,可以组成复杂的N--S流程图 算法举例 例1 求 1 × 2× 3 × 4 × 5. 自然语言法： 步骤1：先求1×2，得到结果2。 步骤2：将步骤1得到的乘积2乘以3，得到结果6。 步骤3：将6再