文档介绍：第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为止。于是可以得到改进的算法如下:
7
算法的表示
方法2:用变量 sum 和 i 分别表示两个加数,和也用变量 sum 表示。用自然语言描述如下:
s1: sum = 1;
s2: i = 2;
s3: 若 i<=100,重复步骤s4~s5,否则转去执行s6;
s4: sum = sum + i;
s5: i = i + 1;
s6: 输出sum的值。
上述算法是一个循环算法:S3到S5组成一个循环,在实现算法时要反复多次执行S3,S4,S5等步骤,直到某一时刻,执行S5步骤时经过判断,加数i已超过规定的数值而不返回S3步骤为止。此时算法结束,变量sum的值就是所求结果。
8
算法的表示
传统流程图采用一组规定的图形符号、流程线和文字说明来表示各种操作算法。美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号,已为世界各国程序工作者普遍采用,如表3-1所示。
用传统流程图描述例3-1的算法,如图3-1所示。
用传统流程图表示算法直观形象,易于理解,能够比较清晰地表达各种处理之间的逻辑关系,是表示算法的较好的工具。但由于对流程线的使用没有严格限制,易造成流程的随意转移,不能保证是结构化的,从而难以阅读和修改。
9
算法的表示
符号
名称
用途
起止框
用于描述控制流程的开始和结束:开始框内标注“开始”字样,结束框内标注“结束”字样
输入输出框
用于表示数据的输入和输出:框内标明输入输出的变量
处理框
用于描述数据加工和处理:常采用文字加符号来表示计算公式和赋值操作
判断框
用于描述条件判断和转移关系:框内描述条件关系,两个流出边分别标注 Yes/No、Y/N、True/False或“真/假”,