02_01_C语言程序设计_第二章 算法：程序的灵魂_周常欣

第2章 算法---程序的灵魂 算法---程序的灵魂
2.1 算法概述 算法概述 2.2 简单的算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法
2.1 算法概述 算法概述
一个程序主要包括以下两方面的信息： 一个程序主要包括以下两方面的信息：
(1) 对数据的描述。在程序中要指定用到哪些 对数据的描述。在程序中要指定用到哪 数据以及这些数据的类型和数据的组织形式 这就是数据结构(data structure) 这就是数据结构 (2) 对操作的描述。即要求计算机进行操作的 对操作的描述。 步骤 也就是算法(algorithm) 也就是算法
S1：sign=1 ： S2：sum=1 ： -1 S3： S3：deno=2 S4：sign=(-1)*sign -1/2 ： S5：term=sign*(1/deno) 1-1/2 ： S6：sum=sum+term ： 3 满足，返回S4 满足，返回 S7：deno=deno+1 ： S8：若deno≤100返回 ；否则算法结束 返回S4； ： 返回 sign—当前项符号 当前项符号 term—当前项的值 当前项的值 sum—当前各项的和 当前各项的和 deno—当前项分母 当前项分母
2.1 算法概述 算法概述
数据是操作的对象 操作的目的是对数据进行加工处理， 操作的目的是对数据进行加工处理，以 得到期望的结果 著名计算机科学家沃思(Nikiklaus 著名计算机科学家沃思 Wirth)提出一个公式： 提出一个公式： 提出一个公式 算法 + 数据结构 = 程序
2.1 算法概述 算法概述
个学生， 例2.2 有50个学生，要求将成绩在 分 个学生 要求将成绩在80分 以上的学生的学号和成绩输出。 以上的学生的学号和成绩输出。

教材认为：
程序 =算法+数据结构+程序设计方法+语言工具和环境
灵魂 加工对象 工具
<
>
C语言程序设计
第二章 程序的灵魂——算法
§2.1 算法的概念
为解决一个问题而采取的方法和步骤，就成 为算法。例如：歌曲的乐谱，建造房子等。 算法核心是解决“做什么”和“怎么做”的 问题。
P15页的例2.1，求1……5之积。 可以有多种方法，一般采用简单和运算步骤少 的。准确、高效
第二章 程序的灵魂——算法
§课后作业
P36页习题：
2.4、2.8（结合实验指导读懂答案） 用N-S图表示2.4题中⑴⑵⑹ 用传统流程图求解以下问题：将一个16进制数 转化为10进制数
复习二进制的基本概念
“计算机文化基础”一书中P27~33页
<
>
P 真 A
假
当P为真 A
直到型循环结构
A 假 P 真 A 直到P为真
注：A,B,A1….An可以是一个简单 语句，也可以是一个基本结构 < >
C语言程序设计
第二章 程序的灵魂——算法
三种基本结构的共同特点：
只有一个入口； 只有一个出口； 结构内的每一部分都有机会被执行到； 结构内不存在“死循环”。
三种基本结构
顺序结构
A A B N-S图
流程图
B
<
>
C语言程序设计
第二章 程序的灵魂——算法
选择结构 二分支选择结构
真
P
假 真 B A
P B
假
A
k k=k1 k=k2 k=kn k=ki ... Ai ... An
多分支选择结构

强调：程序设计风格和程序结构的规范化
核心思想：自顶向下，逐步求精，模块化设计， 结构化编码
一个编程实例
引例
设计算法
计算1+2+3+ · +100 即：1 n · · n
累加算法 1+2+3+ · + t · · 0→s , 1→n 输入 t nn ≤ t ≤100 s + n→s n +1→n 打印s
输出S的值
输出S
结束
实际上，一个程序除了以上两个主要要素之外， 还应当采用结构化程序设计方法进行程序设计，并 且用某一种计算机语言表示。因此，可以这样表示：
程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具和环境
也就是说，以上4个方面是一个程序设计人员所 应具备的知识。在设计一个程序时要综合运用这几 方面的知识。在这4个方面中，算法是灵魂，数据结 构是加工对象，语言是工具，编程需要采用合适的 方法。算法是解决“做什么”和“怎么做”的问题。 程序中的操作语句，实际上就是算法的体现。
先执行，后判断
sum=0; i= 0; do { sum+=i; i++； } while （i<=100）;
二、 三种结构的共同特点
单入口单出口
结构内的每一部分都有机会被执行 不存在“死循环”
三、 结构化程序设计的优点
用三种基本结构组成的程序是结构化程序 优点：易编、易读、易懂、易维护
上面的S1，S2…代表步骤1，步骤2……S是step(步)的 缩写。这是写算法的习惯用法。 请读者仔细分析这个算法，能否得到预期的结果。显然 这个算法比前面列出的算法简练。 如果题目改为求1×3×5×7×9×11。 算法只需作很少的改动即可： S1： 1=>p S2： 3=>i S3： p×i=>p S4： i+2=>i S5： 若i≤11，返回S3； 否则，结束。

-23-
第2章 程序的灵魂—算法
2.4 算法的表示
N-S流程图 ❖ 1973年美国学者I.Nassi和B.Shneiderman提出的一种新的流程图 形式。 ❖ N-S流程图的特点 没有流程线 全部算法写在一个矩形框内，该框内还可包含其它从属于它 的框。 适于结构化程序设计。
-24-
第2章 程序的灵魂—算法
=100 + 50 + 49×100 = 5050
-4-
第2章 程序的灵魂—算法
2.1 算法的概念
计算机算法 即计算机能执行的算法。 ❖ 数值运算的算法 可由库函数实现，如求函数的定积分等。 ❖ 非数值运算的算法 如查找、排序，事务管理系统等。
-5-
第2章 程序的灵魂—算法
2.2 简单算法举例
例2.1 求1×2 ×3 ×4 ×5 设被乘数为T，乘数为I，乘积结果仍放在变量T中，作为下一个被乘数。 S1：使T = 1 S2：使I = 2 S3：使T ×I，可表示为：T ×I=>T。 S4：使I的值加1，即I+1=>I。 S5：如果I不大于5，返回重新执行S3，以及其后的步骤S4， S5；否则， 算法结束。
-3-
第2章 程序的灵魂—算法
2.1 算法的概念
广义算法 ❖ 算法是为解决一个问题而采取的方法和步骤。 ❖ 对同一个问题，可以有不同的解题方法和步骤。
例如：求1+2+3+…+100 方法1：先进行1+2，再加3，再加4，一直加到100。 方法2：100 + (1+99)+(2+98)+…+(49+51)+50
第2章 程序的灵魂—算法
2.4 算法的表示