C语言程序设计第二章算法

If the counter is not equal to zero Set the average to the total divided by the counter Print the average
else Print “No grade were entered”
31
初始化变量阶段 输入数据值和对程序中 的变量作相应调整阶段 计算打印最终结果阶段
2020/8/13
三种基本结构
15
1966年，Bohra和Jacopini提出了以下 三种基本结构，作为表示一个良好算法的 基本单元。
顺序结构 选择结构 循环结构 A
B
成立
P
A
不成立
B
不成立
P
成立
循环体A
B
顺序结构
选择结构
循环结构
2020/8/13
16
当型(While型)循环结构
– 它的功能是当给定的条件p1成立时，执行A框操作，执行完A后，再 判断条件p1是否成立执行A ，如果仍然成立，再执行A框，如此反复 框，直到某一次p1条件不成立为止，此时不执行A框，而从b点脱离 循环结构。
total = total + grade; counter= counter +1; printf("Enter Grade:"); scanf("%d",&grade); } /* －－终止阶段－－*/ if( counter != 0 ){ average=(float)total/counter; printf("Class average is %.2f\n", average ); } else printf("No grads were entered\n"); getch(); }
编写 程序
调试和运行
翻译
程序
(编译或解释)
输入 程序
得到 运行结果
2020/8/13
什么是程序？
4
著名的计算机科学家沃思提出: 数据结构+算法=程序
描述数据类型, 组织形式
描述对数据的 操作步骤
算法是计算机为求解某一问题而采用的方法,步骤.
2020/8/13
算法的概念
5
例如：读入三个数，找出并打印其中的最大数 算法：
作业：用C写出描述比较两个数的大小, 输出大的一个数的算法。
2020/8/13
结构化程序设计方法
25
程序的三种基本结构 –顺序结构程序：按照书写顺序依次执行语句 –选择结构程序：按照条件判断选择执行语句 –循环结构程序：通过条件控制循环执行语句
三种基本结构的共同点： • 都是只有一个入口和一个出口； • 结构内的每一个框都有机会被执行； • 结构内没有死循环。
b）确定性。算法的每一步都应当是明确无误的，不能 含义模糊，使执行者无所适从。
c）有零个或多个输入
d）有一个或多个输出
e）有效性。算法中的每一步都应该能有效的执行，执 行算法最后应该能得到确定的结果。
2020/8/13
怎样表示一个算法
9
算法的描述方式 – 用自然语言描述算法 – 用流程图描述算法 – 用N-S结构图描述算法 – 用伪代码描述算法 – 用计算机语言描述算法
2020/8/13
结构化程序设计的基本原则：
26
如果一个程序仅包含这三种基本结构（由这些基 本结构顺序组成），则称为结构化程序。
结构化程序设计的基本原则：
–采用自顶向下、逐步细化的方法进行设计；
–采用模块化原则和方法进行设计。即将大型 任务从上向下划分为多个功能模块，每个模 块又可以划分为若干子模块，然后分别进行 模块程序的编写；
getch(); }
29
2020/8/13
实例研究2
30
用自顶向下、逐步细化的方法制定算法开 发一个求全班平均成绩的程序，程序在每 次运行时都能够处理任意个数的成绩。
2020/8/13
实例分析2
顶层：determine the class average for the quiz 第一步求精： Initialize variables Input,sum,and count the quiz grades Calculate and print the class average 第二步求精 Initialize total to zero Initialize counter to zero
17
打印5个数：1，2，3，4，5。
2020/8/13
三种基本结构的特点
18
以上三种基本结构，有以下共同特点： (1) 只有一个入口。 (2) 只有一个出口。 (3) 结构内的每一部分都有机会被执行到。 (4) 结构内不存在“死循环”(无终止的循环)。
已经证明，任何复杂的问题都可以三种基本算 法结构来描述：顺序、选择、循环。因此用计 算机语句描述的程序也包含三种基本结构。
直到型(Until型)循环
– 它的功能是先执行A框，然后判断给定的p2条件是否成立，如果p2条 件不成立，则再执行A，然后再对p2条件作判断，如果p2条件仍然不 成立，又执行A……如此反复执行A，直到给定的p2条件成立为止， 此时不再执行A，从b点脱离本循环结构。
2020/8/13
当型循环、直到型循环的应用例子
例如：输出两个数中的最大数
2020/8/13
用自然语言描述算法
10
第一步：输入x和y的值
第二步：比较x和y的值，如果x大于y，则 输出x的值，否则输出y的值。
易于理解，但 冗长，不够精 确，难于描述 复杂算法。
例如当描述“输出10个 数中最大数”的算法时， 会冗长、难于理解
2020/8/13
用流程图描述算法
第一步求精：
Initialize variables
Input,sum,and count the quiz grades
Calculate and print the class average
第二步求精:
Initialize total to zero Initialize counter to zero
2020/8/13
用伪代码描述算法
23
用介于自然语言和计算机语言之间的文字 和符号来描述算法.
用伪代码描述比较两个数的大小,输出大的 一个数的算法：
Main() { a=第1个数; b=第2个数; If (a>b)
输出a ; Else 输出b; }
2020/8/13
用计算机语言描述算法
24
要完成一件工作，包括设计算法和实现 算法两个部分。设计算法的目的是为了 实现算法。因此，不仅要考虑如何设计 一个算法，也要考虑如何实现一个算法。
Input the first grade While the user has not as yet entered the sentinel
Add this grade into the running total Add one to the grade counter Input the next grade(possibly the sentinel)
–每个模块都是用结构化程序实现，即都只能 由三种基本结构组成，并通过计算机语言的 结构化语句实现。
2020/8/13
实例研究1
27
1.怎样制定算法
–某个班有10个学生，已知他们参加某次 考试的成绩，求全班同学在这次考试中 的平均成绩。
2020/8/13
实例分析1
28
顶层：determine the class average for the quiz
初始化变量阶段
While student counter is less than or equal to ten Input the next exam grade Add this grade into the running total Add one to the student counter
B
A
B
A
B
直到P成立
顺序
选择
循环
2020/8/13
用N-S结构图描述算法
21
输入x、y的值
x>y
T
F
z=x z=y
输出z的值
用N-S结构图描述的算法
2020/8/13
22
利用N-S图进行详细设计具有以下优点： （1） 功能域明确。 （2） 不可能任意控制转移。 （3） 很容易确定全局和局部数据的作用域。 （4） 很容易表现嵌套关系，也可以表示模块 的层次结构起止框 开始输入/输出框 输入x和y
判断框
Y
x >y ?
处理框 z= x
N z= y
流程线
输出z
结束 图1.5 用流程图描述算法
2020/8/13
传统流程图的弊端
14
传统流程图的弊端
传统的流程图用流程线指出各框的执行顺 序，对流程线的使用没有严格限制。
这种算法难以阅读，也难以修改，从而使 算法的可靠性和可维护性难以保证。
2020/8/13
实例2
#include <stdio.h> void main() {
float average; int counter, grade, total; /* －－初始化阶段－－*/ total = 0;counter = 0; /* －－处理阶段－－*/ printf("Enter Grade, -1 to end.\n"); scanf("%d", &grade ); while( grade != -1 ){
① 输入X1,X2,X3 ② 将X1与X2的大数存于MAX中 ③ 将X3与MAX的大数存于MAX中 ④ 输出MAX