《第2章_算法.ppt》由会员分享，可在线阅读，更多相关《第2章_算法.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章l l 主要内容2.1 2.1 算法的概念算法的概念2.2 2.2 简单算法举例简单算法举例2.3 2.3 算法的特性算法的特性2.4 2.4 怎样表示一个算法怎样表示一个算法2.5 2.5 结构化程序设计方法结构化程序设计方法 C程序设计（第三版）程序设计（第三版）http:/ 3一个程序应包括两个方面的内容:对数据的描述：数据结构(data structure)对操作的描述：算法(algorithm)著名计算机科学家沃思提出一个公式:数据结构数据结构+算法算法=程序程序 数据结构算法程序设计方法语言工具数据结构算法程序设计方法语言工具完整的程序设计应该是:C程序设计（第三版）程
2、序设计（第三版）http:/ 4算法：为解决问题而采取的算法：为解决问题而采取的方法和步骤。方法和步骤。计算机算法分为计算机算法分为:数值运算算数值运算算法和非数值运算算法。法和非数值运算算法。C程序设计（第三版）程序设计（第三版）http:/ 5 2.2 2.2 简单算法举例简单算法举例例2.1 求1*2*3*4*5原始的算法：步骤1：先求1*2得到结果2步骤2：算法改写：S1：使p=1S2:使i=2S3:使p*i，乘积放在变量p中，p*ipS4:使i的值加1，即i+1iS5:如果i不大于5，返回步骤S3C程序设计（第三版）程序设计（第三版）http:/ 6 2.2 2.2 简单算法举例简单
3、算法举例例2.2 有50个学生，要求将他们之中成绩在80分以上的学号和成绩输出。算法：S1：1iS2:如果gi80，则输出ni和gi否则不输出S3:i+1iS4:如果i50，返回s2，继续执行，否则，算法结束C程序设计（第三版）程序设计（第三版）http:/ 7 2.2 2.2 简单算法举例简单算法举例例2.3 判定2000-2500年中的每一年是否为闰年，将结果输出。S1：2000 yS2：若y不能被4整除，则输出y“不是闰年”。然后转到S6。S3：若y能被4整除，不能被100整除，则输出y“是闰年”。然后转到S6。S4：若y能被100整除，又能被400整除，输出y“是闰年”，否则输出“不是
4、闰年”。然后转到S6。S5:输出y“不是闰年”。S6：y+1 yS7：当y2500时，转S2继续执行，如y2500，算法停止。C程序设计（第三版）程序设计（第三版）http:/ 8 2.2 2.2 简单算法举例简单算法举例例2.4 求 1-1/2+1/3-1/4+-1/100S1：sign=1S2：sum=1S3：deno=2S4：sign=(-1)*signS5:term=sign*(1/deno)S6：sum=sum+termS7：deno=deno+1S8:若deno100返回S4C程序设计（第三版）程序设计（第三版）http:/ 9 2.2 2.2 简单算法举例简单算法举例例2.5 对
5、一个大于或等于3的正整数，判断它是不是一个素数。S1：输入n的值S2：i=2S3：n被i除，得余数rS4：若果r=0，表示n能被i整除，则输入n“不是素数”，算法结束，否则继续执行S5S5:i+1iS6：如果in-1，返回S3，否则输出n“是素数”C程序设计（第三版）程序设计（第三版）http:/ 10 2.3 2.3 算法的特性算法的特性有穷性。一个算法应包含有限的操作步骤。确定性。算法中的每一个步骤都应当是确定的有零个或多个输入。有一个或多个输出。有效性。C程序设计（第三版）程序设计（第三版）http:/ 11 2.4 2.4 怎样表示一个算法怎样表示一个算法求5！分析题目，写出算法步骤S
6、1-S5根据算法步骤画出流程图根据流程图写出C语言程序C程序设计（第三版）程序设计（第三版）http:/ 12 2.4 2.4 怎样表示一个算法怎样表示一个算法流程图表示算法开始1t2it*i ti+1ii5结束YNC程序设计（第三版）程序设计（第三版）http:/ 13如果如果包括这个输入数据的部分，流程图为C程序设计（第三版）程序设计（第三版）http:/ 14小结：小结：流程图是表示算法的较好的工具。一个流程图包括以下几部分：(1)表示相应操作的框；(2)带箭头的流程线；(3)框内外必要的文字说明。C程序设计（第三版）程序设计（第三版）http:/ 15小结：小结：由三种基本结构顺序组成
7、的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法。顺序结构选择结构循环结构C程序设计（第三版）程序设计（第三版）http:/ 16小结：小结：顺序结构1t2iC程序设计（第三版）程序设计（第三版）http:/ 17小结：小结：选择结构1i2ii5C程序设计（第三版）程序设计（第三版）http:/ 18小结：小结：循环结构APYNC程序设计（第三版）程序设计（第三版）http:/ 19扩展：扩展：只要具有上述四个特点的都可以作为基本结构。可以自己定义基本结构，并由这些基本结构组成结构化程序。此图符合基本结构的特点C程序设计（第三版）程序设计（第三版）http:/ 2
8、0三种基本结构的共同点三种基本结构的共同点只有一个入口只有一个出口结构的每一部分都有机会被执行到结构内不存在“死循环”C程序设计（第三版）程序设计（第三版）http:/ 21N-SN-S图表示算法的优点图表示算法的优点比文字描述直观、形象、易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N-S流程图中的上下顺序就是执行时的顺序。用N-S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行。C程序设计（第三版）程序设计（第三版）http:/ 22用用N-SN-S流程图描述求三个数中最大数流程图描述求三个数中最大数
9、的算法，如图的算法，如图1-41-4所示。所示。C程序设计（第三版）程序设计（第三版）http:/ 23小结：小结：一个结构化的算法是由一些基本结构顺序组成的。在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内(如循环中流程的跳转)；一 个非结构化的算法可以用一个等价的结构化算法代替，其功能不变。如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。C程序设计（第三版）程序设计（第三版）http:/ 24应当强调说明：写出了C程序，仍然只是描述了算法，并未实现算法。只有运行程序才是实现算法。应该说，用计算机语言表示的算法是计算机能够执行的算法。C程序设计
10、（第三版）程序设计（第三版）http:/ 25 2.5 2.5 结构化程序设计方法结构化程序设计方法一个结构化程序 就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维护。结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。结构化程序设计方法的基本思路是：把一个复杂问题的求解过程 分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。C程序设计（第三版）程序设计（第三版）http:/ 26 用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。C程序设
11、计（第三版）程序设计（第三版）http:/ 27自顶向下，逐步细化方法的优点：考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。C程序设计（第三版）程序设计（第三版）http:/ 28模块设计的方法：模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。子模块一般不超过50行。划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。