C++程序设计增加：算法与流程.ppt

《C++程序设计增加：算法与流程.ppt》由会员分享，可在线阅读，更多相关《C++程序设计增加：算法与流程.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法与流程图 l 主要内容2.1 2.1 算法的概念算法的概念2.2 2.2 简单算法举例简单算法举例2.3 2.3 算法的特性算法的特性2.4 2.4 怎样表示一个算法怎样表示一个算法2.5 2.5 结构化程序设计方法结构化程序设计方法 一个程序应包括两个方面的内容一个程序应包括两个方面的内容:对数据的描述：数据结构对数据的描述：数据结构(data structure)对操作的描述：算法对操作的描述：算法(algorithm)著名计算机科学家沃思提出一个公式:数据结构数据结构+算法算法=程序程序#include using namespace std;int main()int a,b,c;

2、a=10;b=23;c=a+b;couta+b=;coutc;coutp S4：使i的值加1，即i+1-i。S5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。可以设两个变量：一个变量代表被乘数，一个变一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设将每一步骤的乘积放在被乘数变量中。设p p为被为被乘数，乘数，i i为乘数。用循环算法来求结果为乘数。用循环算法来求结果,算法可算法可改写：改写：S1：1pS2：3 iS3：pi pS4：i+

3、2 pS5：若i1000，返回S3。否则，结束。如果题目改为：求如果题目改为：求13510001351000算法只算法只需作很少的改动：需作很少的改动：用这种方法表示的算法具有通用性、用这种方法表示的算法具有通用性、灵活性。灵活性。S3S3到到S5S5组成一个循环，在实现组成一个循环，在实现算法时算法时 要反复多次执行要反复多次执行S3S3，S4S4，S5S5等步等步骤，直到某一时刻，执行骤，直到某一时刻，执行S5S5步骤时经过步骤时经过判断，乘数判断，乘数i i已超过规定的数值而不返回已超过规定的数值而不返回S3S3步骤为止。此时算法结束，变量步骤为止。此时算法结束，变量p p的值的值就是所

4、求结果。就是所求结果。例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来。设n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用g1代表第一个学生成绩，gi代表第i个学生成绩，算法表示如下:S1S1：1 i1 i S2 S2：如果：如果g gi i8080，则打印和，否则不打印。，则打印和，否则不打印。S3S3：i+1 ii+1 i S4 S4：如果：如果i50i50，返回，返回S2S2，继续执行。否则算法结束，继续执行。否则算法结束 变量变量i i作为下标，用来控制序号作为下标，用来控制序号(第几个学生，第第几个学生，第几个成绩几个成绩)。当。当i i超过超过5050

5、时，表示时，表示 已对已对5050个学生的个学生的成绩处理完毕，算法结束。成绩处理完毕，算法结束。如果需要输入成绩如果需要输入成绩S1S1：1 i1 iS2S2：输入：输入n ni i和和g gi i，其中其中n ni i代表第代表第i i个学生的学号，个学生的学号，g gi i代代表第表第i i个学生的成绩。个学生的成绩。S3S3：i+1 ii+1 iS4S4：如果：如果i50i50，返回，返回S2S2，继续执行。，继续执行。S5S5：1 i1 iS6S6：如果：如果g gi i8080，则打印和，否则不打印。，则打印和，否则不打印。S7S7：i+1 ii+1 iS8S8：如果：如果i50i

6、50，返回，返回S6S6，继续执行。否则算法结束，继续执行。否则算法结束例2.3 判定20002500年中的每一年是否闰年，将结果输出。分析：闰年的条件是：闰年的条件是：(1)(1)能被能被4 4整除，但不能被整除，但不能被100100整除的年份都是闰年，如整除的年份都是闰年，如1996,20041996,2004年是闰年；年是闰年；(2)(2)能被能被100100整除，又能被整除，又能被400400整除的年份是闰年。整除的年份是闰年。如如1600,20001600,2000年是闰年。不符合这两个条件的年年是闰年。不符合这两个条件的年份不是闰年。份不是闰年。设设y y为被检测的年份，算法可表示

7、如下为被检测的年份，算法可表示如下：S1S1：2000 2000 y yS2S2：若：若y y不能被不能被4 4整除，则输出整除，则输出y“y“不是闰年不是闰年”。然后。然后转到转到S6S6。S3S3：若：若y y能被能被4 4整除，不能被整除，不能被100100整除，则输出整除，则输出y“y“是闰是闰年年”。然后转到。然后转到S6S6。S4S4：若：若y y能被能被100100整除，又能被整除，又能被400400整除，输出整除，输出y“y“是闰是闰年年”，否则输出，否则输出“不是闰年不是闰年”。然后转到然后转到S6S6。S5:S5:输出输出y“y“不是闰年不是闰年”。S6S6：y+1 y+1

8、 y yS7S7：当：当y2500y2500时，转时，转S2S2继续执行，如继续执行，如y y25002500，算法，算法停止。停止。2.3 2.3 算法的特性算法的特性有穷性：包含有限的操作步骤。确定性：算法中的每一个步骤都应当是确定的。有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信息。有一个或多个输出：算法的目的是为了求解，“解”就是输出。有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果。一个算法应该具有以下特点：2.4 2.4 算法的表示算法的表示可以用不同的方法表示算法，常用的有：可以用不同的方法表示算法，常用的有：自然语言自然语言传统流程图传统流程图结构化

9、流程图结构化流程图伪代码伪代码PADPAD图图 2.4.1 2.4.1 用自然语言表示算法用自然语言表示算法 自然语言就是人们日常使用的语言，可以是自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。用自然语言表示通俗易汉语或英语或其它语言。用自然语言表示通俗易懂，但文字冗长，容易出现懂，但文字冗长，容易出现“歧义性歧义性”。自然语。自然语言表示的含义往往不大严格，要根据上下文才能言表示的含义往往不大严格，要根据上下文才能判断其正确含义，描述包含分支和循环的算法时判断其正确含义，描述包含分支和循环的算法时也不很方便。因此，除了那些很简单的问题外，也不很方便。因此，除了那些很简单的问题外

10、，一般不用自然语言描述算法。一般不用自然语言描述算法。2.4.2 2.4.2 用流程图表示算法用流程图表示算法美国国家标准化协会美国国家标准化协会ANSI(American National ANSI(American National Standard Institute)Standard Institute)规定了一些常用的流程图规定了一些常用的流程图符号：符号：起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流向线连接点连接点例2.6 将求5!的算法用流程图表示如果需要将最后结果打印出来，可在菱形框的下面加一个输出框。例2.7 将例2.2的算法用流程图表示。打

11、印50名 学生中成绩在80分以上者的学号和成绩。如果如果包括这个输入数据的部分，流程图为 例2.8 将例2.3判定闰年的算法用流程图表示 用流程图表示算法要比用文字描述算法逻辑清晰、易于理解。小结：小结：流程图是表示算法的较好的工具。一个流程图是表示算法的较好的工具。一个流程图包括以下几部分流程图包括以下几部分 ：(1)(1)表示相应操作的框；表示相应操作的框；(2)(2)带箭头的流程线；带箭头的流程线；(3)(3)框内外必要的文字说明。框内外必要的文字说明。2.5 2.5 结构化程序设计方法结构化程序设计方法一个结构化程序一个结构化程序 就是用高级语言表示的结构化算就是用高级语言表示的结构化

12、算法。用三种基本结构组成的程序必然是结构化的程法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维序，这种程序便于编写、便于阅读、便于修改和维护。护。结构化程序设计强调程序设计风格和程序结构的结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。规范化，提倡清晰的结构。结构化程序设计方法的基本思路是：把一个复杂问结构化程序设计方法的基本思路是：把一个复杂问题的求解过程题的求解过程 分阶段进行，每个阶段处理的问题分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。都控制在人们容易理解和处理的范围内。采取以下方法来保证得到结构化的程序：

13、采取以下方法来保证得到结构化的程序：自顶向下；自顶向下；逐步细化；逐步细化；模块化设计；模块化设计；结构化编码。结构化编码。两种不同的方法：两种不同的方法：自顶向下，逐步细化；自顶向下，逐步细化；自下而上，逐步积累。自下而上，逐步积累。用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。自顶向下，逐步细化方法的优点：考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。模块设计的方法：模块化设

14、计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。子模块一般不超过50行。划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。作业：写出以下两题的算法，并用流程作业：写出以下两题的算法，并用流程图表示出来图表示出来（9月月15日提交作业）日提交作业）1.1.求：求：2.2.输入一个大于或等于输入一个大于或等于3 3的正整数，判断它是不是一个素数。的正整数，判断它是不是一个素数。提示提示：所谓素数，是指除了：所谓素数，是指除了1 1和该数本身之外，不能被其它和该数本身之外，不能被其它任何整数整除的数。例如，任何整数整除的数。例如，1313是素数。因为它不能被是素数。因为它不能被2 2，3 3，4 4，1212整除。判断一个数整除。判断一个数n(n3)n(n3)是否素数的方法：是否素数的方法：将将n n作为被除数，将作为被除数，将2 2到到(n-1)(n-1)各个整数轮流作为除数，如各个整数轮流作为除数，如果都不能被整除，则果都不能被整除，则n n为素数。为素数。