C语言程序设计 第二章 程序的灵魂 -- 算法

主要内容 2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化算法设计方法

2.1 算法的概念 沃思公式： 数据结构＋算法＝程序 具体化： 程序＝算法＋数据结构＋程序设计方法＋语言工具和环境 　 数据结构＋算法＝程序 具体化： 程序＝算法＋数据结构＋程序设计方法＋语言工具和环境　 对数据的描述，要指定数据的类型、数据的组织形式 对操作的描述，即操作步骤

2.1 算法的概念 做任何事都有一定的次序和步骤；如：召开会议，购物等； 算法是为解决一个问题而采取的方法和步骤； 注意： 解决同一个问题可以有不同的方法和步骤，方法有优劣之分， 采用简单的和运算步骤少的方法为优！

2.1 算法的概念 算法分两大类别 数值运算算法：目的是求数值解，算法成熟； 非数值运算算法：种类繁多，要求各异，难以规范

2.2 简单算法举例 例1 求１×２×３×４×５ 手工计算方法： 通用的方法: 设两个变量（被乘数p,乘数i） 第一步：1=>p 例1　求１×２×３×４×５ 手工计算方法： 通用的方法: 设两个变量（被乘数p,乘数i） 第一步：1=>p 第二步：2=>i 第三步：p×i=>p 第四步： i+1=>i 第五步：若i≤5，返回第三步；否则结束 １×２，得2； ① ２×３，得6； ② ６×４，得24; ③ ④ ２４×５=120

2.2 简单算法举例 如果题目改为求1×3×5×7×9×11 第一步：1=>p 第二步：3=>i 第三步：p×i=>p 第四步： i+2=>i 第五步：若i≤11，返回第三步；否则结束 用这种方法表示的算法具有通用性、灵活性

2.2 简单算法举例 例2 有50个学生，要求将他们之中成绩在80分以上者打印出来 例2 有50个学生，要求将他们之中成绩在80分以上者打印出来 算法分析：用n表示学生学号，n1代表第一个学生学号，ni代表第i个学生的学号，g1代表第一个学生成绩，gi代表第i个学生成绩 算法 第一步: 1=>i 第二步: 若gi≥80则打印ni和gi，否则不打印 第三步: i+1=>i 第四步: 若i≤50返回第二步，否则算法结束

2.2 简单算法举例 例3 判断2000-2500年中的每一年是否闰年，将结果输出。 分析：闰年的条件： 能被４整除，但不能被100整除的 例3 判断2000-2500年中的每一年是否闰年，将结果输出。 分析：闰年的条件： 能被４整除，但不能被100整除的 年份都是闰年，如1996,2004年是闰 年； 能被100整除，又能被400整除的年 份是闰年，如1600,2000年是闰年。 不符合这两个条件的年份不是闰年 y不能被４整除 ① y能被４整除但不能被100整除 ② 闰年 非闰年 ③y能被100整除又能被400整除 ④其他

2.2 简单算法举例 算法 2000=>y 若y不能被４整除，输出y“不是闰年”，然后转到第5步

2.2 简单算法举例 例4 求 1- 1/2 + 1/3 -1/4+ … + 1/99 - 1/100 算法： sign=1 sum=1 deno=2 sign=-sign term=sign×(1/deno) sum=sum+term deno=deno+1 若deno≤100返回第4步,否则算法结束

2.3 算法的特性 算法应具有以下特点: 有穷性 确定性 有零个或多个输入 有一个或多个输出 有效性

2.4 怎样表示一个算法 用自然语言表示算法：通俗易懂，但文字冗长，容易产生歧义。 用流程图表示算法： 直观形象，容易理解。

2.4 怎样表示一个算法 . . 算法的三种基本结构 选择结构 p A B 成立 不成立 a b A B a b 顺序结构 当 型 2.4 怎样表示一个算法 选择结构 p A B 成立 不成立 a b 算法的三种基本结构 A B a b 顺序结构 当 型 （while） 循 环 p 成立 A b a . 不成立 A p 不成立 成立 a b . 直 到 型 （until） 循 环

2.4 怎样表示一个算法 例1 用流程图表示算法：１×２×３×４×５ 第一步：1=>p 第二步：2=>i 2.4 怎样表示一个算法 例1　用流程图表示算法：１×２×３×４×５ 第一步：1=>p 第二步：2=>i 第三步：p×i=>p 第四步： i+1=>i 第五步：若i≤5，返回第三 步；否则结束 开始 1=>p 2=>i p×i=>p i+1=>i i≤5 N 结束 Y

2.4 怎样表示一个算法 例2 有50个学生，要求将他们之中成绩在80分以上者打印出来．用流程图表示算法。 第一步: 1=>i 2.4 怎样表示一个算法 例2 有50个学生，要求将他们之中成绩在80分以上者打印出来．用流程图表示算法。 第一步: 1=>i 第二步: 若gi≥80则打 印ni和gi，否则不打印 第三步: i+1=>i 第四步: 若i≤50返回第 二步，否则算法结束 开始 1=>i gi≥80 Y N 打印ni和gi i+1=>i i≤50 结束

2.4 怎样表示一个算法 例 用伪代码表示１×２×３×４×５： 开始 置t的初值为1 置i的初值为2 当i≤５，执行下面操作 使t＝t×i 2.4 怎样表示一个算法 例　用伪代码表示１×２×３×４×５： 开始 置t的初值为1 置i的初值为2 当i≤５，执行下面操作 　 使t＝t×i 　 使i＝i＋1 (循环到此结束) 打印t的值 结束

2.4 怎样表示一个算法 也可以写成以下形式： BEGIN (算法开始) 1=>t 2=>i while i<=5 2.4 怎样表示一个算法 也可以写成以下形式： BEGIN (算法开始) 1=>t 2=>i while i<=5 { t×i=>t i+1=>i } print t END (算法结束)

2.4 怎样表示一个算法 用计算机语言表示算法：求５！用c语言表示 void main( ) { int i,t; t=1; i=2; 2.4 怎样表示一个算法 用计算机语言表示算法：求５！用c语言表示 void main( ) { int i,t; t=1; i=2; while(i<=5){ t=t*i; 　 /* 120 */ i=i+1; } printf("%d",t);

2.5 结构化程序设计方法 一个结构化程序就是用高级语言表示的结构化算法 用三种基本结构组成的程序必然是结构化程序 结构化程序的特点 自顶向下 逐步细化 模块化设计 结构化编码

本章小结 算法的概念 简单算法的设计 算法的特性 算法的表示（流程图、伪代码） 算法的3种结构 结构化程序设计思想