文档介绍：第3章程序的控制结构
2
本章主要内容
算法
C语句概述
顺序结构
循环结构
综合例子
选择结构
3
算法
计算机科学家沃思提出:
数据结构+算法=程序
可以把“算法”理解为完成一件事情或解决一个问题而采取的方法和步骤。如何求解一个方程、如何安排去某地旅游的路线或行程等都包含着某种算法。当然我们只讨论计算机算法,即计算机可以实现的算法。
4
按数据的处理方式,计算机中的算法可分为:
(1)数值运算:目的是求数值解,如求方程的根,求函数的定积分等。
(2)非数值运算:目前使用范围广泛,如办公自动化处理、图书情报检索等。
一般来说,不同的问题,有不同的解决方法和步骤,而对同一问题,也可能有不同的解决方法和步骤,也就是有不同的算法。算法有优劣,一般而言,应当选择简单的、运算步骤少的,运算快、内存开销小的算法。
算法
5
算法的特性
算法包含的操作步骤是有限的,每一步都应在合理的时间内完成。
算法中的每一步骤都应是唯一的和确定无误的,不允许有岐义性。如“输出成绩优秀的同学名单”就有岐义,“成绩优秀”的含义不明确。
(可行性、正确性)
算法中每一步骤都应是能有效地执行,且能得到确定的结果,例如:求一个负数的对数,就是一个无效的步骤。
有些算法无需从外界输入数据,如计算6!,而有的算法需从外界输入数据,如计算n! 。
即算法必须得到结果,没有结果的算法是毫无意义的。
6
算法的表示
所谓自然语言,即人们日常使用的语言,可以是汉语、英语、其他语言及其混合体。用自然语言表示通俗易懂,但文字冗长,容易出现岐义性。
[例3-1] 计算1+2+3+…+100的和。
方法1:可以采用最原始方法:1+2,+3,+4,一直加到100,加99次。将这一思路用自然语言描述为如下算法:
s1: 计算 1 + 2;
s2: 使得 s1 + 3;
s3: 使得 s2 + 4;
计算100以内自然数的和,需要99个步骤。
即s99: s98 + 100。
观察上述的算法,可以考虑使用一个变量(sum)既用来存放每一次的求和结果,又用来表示每一次求和时的被加数。这样方法1中的99个步骤可以表示为:
s1: sum=sum+2; (在这之前先把sum初始化为1)
s2: sum=sum+3;
s3: sum=sum+4;
s99: sum=sum+100;
再次观察上述的算法,可以考虑再使用一个变量i来表示加数,让i从2开始,不断地做sum=sum+i 这一个相同的循环操作,直到i超过100为止。于是可以得到改进的算法如下:
9
算法的表示
符号
名称
用途
起止框
用于描述控制流程的开始和结束:开始框内标注“开始”字样,结束框内标注“结束”字样
输入输出框
用于表示数据的输入和输出:框内标明输入输出的变量
处理框
用于描述数据加工和处理:常采用文字加符号来表示计算公式和赋值操作
判断框
用于描述条件判断和转移关系:框内描述条件关系,两个流出边分别标注 Yes/No、Y/N、True/False或“真/假”,表示条件成立或不成立时的转移关系
调用框
用于描述过程调用或模块调用:框内标注函数或模块名
流程线
用于连接两个图形框:箭头描述处理过程的转移方向
连接框
用于描述多张流程图的连接:应附加文字标识连接关系
表3-1 传统流程图常用的图形符号
传统流程图的流程:
这种如同乱麻一样的算法称为BS型算法,意为一碗面条(A Bowl of Spaghetti),乱无头绪。
缺点:难以阅读、修改,使算法的可靠性和可维护性难以保证。
解决办法:必须限制箭头的滥用,即不允许无规律地使流程随意转向,只能顺序地进行下去。