（中职）编程基础——C语言项目二 算法与流程图教学课件（）.pptx

（中职）编程基础C语言项目二 算法与流程图教学课件（工信版）项目二 算法与流程图项目概述:近些年，编程从少数程序员的特有技能逐步向通用技能扩散，大有“全民编程”之势；编程的核心在于算法；编程语言纷繁复杂，高级、中级、低级兼备，但无论使用哪种语言算法都是绕不开的。C语言中所谓的算法实际上就是程序设计的主思想,这些思想就是C语言代代码中的各种语句、运算或者指令信息的体现。而流程图则是将编程中的算法思想通过绘制图形以及流程的形式展示出来。本项目将C语言中的算法以及流程图相关内容进行详细讲解。学习目标:了解算法概念；理解算法的特性；了解算法的优劣；掌握用流程图描述算法。知识框架:任务3 比谁更聪明任务4 流程图任务3 比谁更聪明任务描述:计算1+2+3+100的和。任务分析:本任务中100个数逐个相加在一起后的结果，如果按照变量赋值的方法来实现，显然进行100个变量是不合适的，通过使用循环结构，对循环变量进行赋初值后，判断循环变量是否超出100，如果未超出就累加到变量s中，这样循环执行循环体后，就得到了想要的结果。知识准备:著名的计算机科学家沃斯曾提出过一个公式：数据结构+算法=程序。也就是说,一个完整的程序应该包含数据结构和算法。数据结构就是程序中所使用到的数据的类型以及数据的组织形式。而就现在而言,设计一个C语言程序不仅需要数据结构和算法,还需要程序的设计方法以及一个语言工具和环境。所以一个程序的组成可以表示为：程序结构+算法+程序设计方法+语言工具和环境。任务3 比谁更聪明2.1算法在现实生活中，算法无处不在，当人们遇见一个问题并对这个问题进行思考时,就是在使用算法。因此算法可以理解为针对出现的问题所设计的具体步骤以及解决方法。对同一个问题，可以有不同的解题方法和步骤，有的方法只须进行很少的步骤，而有些方法则需要较多的步骤；一般来说，希望采用方法简单、运算步骤少得方法。因此，为了有效地进行解题，不仅需要保证算法的正确，还要考虑算法的质量，选择合适的算法。任务3 比谁更聪明计算机中的算法大致可分为以下两种类别。（1）数值运算算法数值运算算法主要用于针对数值问题进行求解，比如求解方程的根、求解函数的，这类需要借助数学公式进行相应的计算。（2）非数值运算算法。这类算法所包括的面十分广泛，比如在图书索、人事管理、车辆调度中的应用，一般需要建立一个过程模型，根据模型制定算法。任务3 比谁更聪明2.2算法的特性总地来说,算法在解决问题时具有以下特性。l1.有穷性算法应当包含有限的操作步骤，不能无穷无尽，不论在做什么样的运算，一定要注意所包含的上限问题,也就是说要在有限的操作步骤内可以解决问题。l2.确定性算法中的每个步骤都必须是确定的、十分清晰，不得具有二义性。若是某个操作是含糊的、模棱两可的话，解决问题的结果可能就会出现分歧。任务3 比谁更聪明l3.有零个或多个输入输入是指在执行算法时需要从外界来获取若必要的初始量等信息。例如:c=a+b;此时需要用户给定变量a和变量b的值以计算变量c的值。又例如:printf(Hello);此时只是需要输出一段字符串，不需要用户入任何数据，此为零输入。l4.有一个或多个输出算法的最终目的就是为了求解，通过输出的方式将求出的结果显示出来。若是一个程序在执行结束后没有返回任何信息，那么此程序就没有执行的价值。任务3 比谁更聪明l5.有效性算法在执行时,每一个步骤必须都能够有效地执行，并且得到确定的结果。例如:int a=2,b=0;c=a/b;此时，“c=a/b”便为一个无效语句，因为使0作为分母是没有意义的。任务3 比谁更聪明2.3算法的优劣一个产品的质量可以用好坏来区分,算法同也有优劣,评判一个算法的优劣性可以从以下几个方面来讲。1.正确性正确性是说算法在制定完成后能否满足具体问题的要求，也就是说针对任何合法的输入，该算法都能够得出合理正确的结果。2.可读性算法在制定完成后，该算法被理解的难易程即为可读性。可读性对于一个算法来说十分重要，若是一个算法令人难以理解，,那么这个算法就得不到推广也不能进行交流，对于算法的修改、维护以及拓展都十分不利。因此制定算法的时候，需要尽量将算法写得通俗易懂，简单明了。任务3 比谁更聪明3.健壮性在一个程序完成之后，运行该程序的用户对程序的理解会因人而异，开发人员不能够确保每一个用户都能够按照要求来进行输入。健壮性就是说当用户输入的数据非法时，该算法能够做出相应的判断，不会因为输入了错误的数据而造成程序的崩溃瘫痪。4.时间复杂度与空间复杂度时间复杂度是指一个算法在运行的过程中所消耗的时间。影响一个算法的时间复杂度主要有以下几个因素。(1)问题的规模大小。例如,求解10以内自然数之和与求解1000以内自然数之和所花费的时间是不同的。(2)源程序的编译功能强弱以及经过编译所产的机器代码质量的优劣。(3)根据计算机的系统硬件所决定的机器执行一条目标指令所需要的时间。(4)程序中语句所执行的次数。(5)使用不同的计算机语言所实现的效率。任务3 比谁更聪明时间复杂度在一个非常小的程序中可能很体会出来，但是在一个特别大的程序中就会发现一个程序在运行的过程中时间复杂度是举足轻重的。所以说编写出一个更为高效且高速的算法是开发人员对算法不断改进的目标。空间复杂度是指算法在运行的过程中所需要的内存空间的大小。一个算法在计算机的内存中所占用的存储空间包含了算法本身所占的内存空间、算法在对数据输入输出时所占用的内存空间以及算法在运行的过程中所占用的临时存储空间。就目前而言,计算机发展日新月异，对于空间复杂度的考虑已经不再那么要了，但是编程时开发人员也是需要注意的。任务3 比谁更聪明在计算机科学中，算法是指描述用计算机解决给定问题的过程。计算1+2+3+100的算法可表示为：步骤1：0s步骤2：1i步骤3：s+is步骤4：i+1i步骤5：如果i100，转到步骤3，否则，结束。任务实施:任务3 比谁更聪明在上面的算法中，符号s和i表示变量，符号表示给变量赋值。步骤1和步骤2表示给变量s和i赋初值0和1；步骤3将变量i的当前值累加到变量s中；步骤4使变量i在原来的基础上增加1；步骤5判断i的值如果小于等于100，重复做步骤3和步骤4，构成一个循环，而当i的值不小于等于100的时候，循环结束，这时，变量s的值就是要求的计算结果。任务3 比谁更聪明本次任务描述了整个计算过程中算法的实现，下面就将算法以程序的形式录入电脑，以此来验证一下算法。程序的运行结果如图2-1所示。#includemain()int i,s=0;for(i=1;i=100;i+)s+=i;printf(s=%d,s);图2-1 1+2+100的和任务3 比谁更聪明本任务主要讲解算法究竟是什么，算法具有的特性分析及算法优劣的评价等知识，通过1到100的累加求和来分析算法的怎么来实现，通过程序来验证算法。任务总结:任务3 比谁更聪明计算100以内自然数的偶数和或奇数和，应该使用怎样的算法？任务拓展:案例4 流程图案例描述:判定2000-2500年中的每一年是否为闰年，并将结果输出。案例分析:先分析闰年的条件:（1）能被4整除，但不能被100整除的年都是闰年,如2008年、2012年、2048年是闰年；（2）能被400整除的年份是闰年,如2000年是闰年。不符合这两个条件的年份是不是闰年。例如2009年、2100年不是闰年。根据以上条件，采用外循环内判断的方法来绘制流程图，这样设计程序时思路就清晰了。案例4 流程图2.4用自然语言表示算法任务2的任务实施中，其算法是用自然语言来表示的，自然语言就是人们日常使用的语言,可以是汉语、英语或其他语言。用自然语言表示通俗易懂,但文字冗长,容易出现歧义。自然语言表示的含义往往不大严格,要根据上下文才能判其正确含义。例如有这样一句话:“张先生对李先生说他的孩子考上了大学”,请问是张先生的孩子考上大学还是李先生的孩子考上大学呢?光从这句话本身难以判断。此外,用自然语言来描述包含分支和循环的算法不大方便。因此,除了那些很简单的问题外,一般不用自然语言表示算法。案例4 流程图2.5用流程图表示算法使用流程图可以将算法以图形的形式清晰地绘制出来,流程图是使用一些简单的几何图形以及流程线来表示算法中的各种操作和语句，流程图基本元素如图2-2所示。图2-2流程图基本元素 案例4 流程图1.一个流程图包括以下几部分：（1）表示相应操作的框；（2）带箭头的流程线；（3）框内外必要的文字说明。需要提醒的是：流程线不要忘记画箭头，因为它是反映流程的先后的，如不画出箭头就难以判定各框的执行次序了。2.使用流程图表示算法,具有以下优点：（1）结构清晰,逻辑性强；（2）易于理解,画法简单；（3）便于描述,形式规范。案例4 流程图3.流程图的三种基本结构1966年，Bohra和Jacopini提出了以下3种基本结构，用这3种基本结构作为表示一个良好算法的基本单元。（1）顺序结构。顺序结构是程序代码中最基本的结构，它属于一种线性结构，顺序结构的代码在执行的时候是按照语句的先后顺序逐条执行的，也就是从上至下，一条一条执行，不会漏过任何语句或者代码。如图2-3所示，虚线框内是一个顺序结构，其中A和B两个框是顺序执行的；即在执行完A框所指定的操作后，接着执行B框所指定的操作。案例4 流程图图2-3顺序结构流程图图2-4选择结构流程图 案例4 流程图（2）选择结构。选择结构又称为分支结构，如图2-4所示，通过判断某个条件表达式的结果成立与否，来执行相应的操作时，需要使用到选择结构。选择结构必包含一个判断框，先进行条件p判断，通过返回的判断结果来选择接下来的执行语句，若条件p成立，则执行语句A，若条件p不成立，则执行语句B。注意：无论p条件是否成立，只能执行A框或B框之一，不可能既执行A框又执行B框，无论走哪一条路径，在执行完A或B之后，都经过b点，然后脱离本选择结构。A或B两个框中可以有一个是空的，即不执行任何操作。案例4 流程图（3）循环结构。又称重复结构，即反复执行某一部分的操作，有两类循环结构。当型循环结构。当型循环结构如图2-5所示，它的作用是：当给定的条件p1成立时，执行A框操作，执行完A后，再判断条件p1是否成立，如果仍然成立，再执行A框，如此反复执行A框，直到某一次p1条件不成立为止，此时不执行A框，而从b点脱离循环结构。直到型循环结构。直到型循环结构如图2-6所示，它的作用是：先执行A框，然后判断给定的条件p2是否成立，如果p2条件成立，则再执行A，然后再对p2条件作判断，如果p2条件仍然成立，又执行A如此反复执行A，直到给定的p2条件不成立为止，此时不执行A框，而从b点脱离本循环结构。同一个问题既可以用当型循环结构来处理，也可以用直到型循环结构来处理。案例4 流程图图2-5当型循环结构流程图图2-6直到型循环结构流程图案例4 流程图以上3种基本结构，有以下共同特点：（1）只有一个入口。图2.3图2.6中的a点为入口点。（2）只有一个出口。图2.3图2.6中的b点为出口点。请注意：一个判断框有两个出口，而一个选择结构只有一个出口。不要将判断框的出口和选择结构的出口混淆。（3）结构内的每一部分都有机会被执行到。也就是说，对每一个框来说，都应当有一条从入口到出口的路径通过它。（4）结构内不存在“死循环”（无终止的循环）。案例4 流程图2.6用N-S流程图表示算法1973年,美国学者I.Nassi和B.Shneiderman出了一种新的流程图形式,在这种流程图中,完全去掉了带箭头的流程线，全部算法写在一个矩形框内，在该框内还可以包含其他从属于它的框，或者说，由一些基本的框组成一个大的框，这种流程图又称N-S结构化流程图（N和S是两位美国学者的英文姓氏的首字母）。案例4 流程图N-S流程图用以下的流程图符号：（1）顺序结构。顺序结构用图2-7形式表示,A和B两个框组成一个顺序结构。（2）选择结构。选择结构用图2-8表示,它与图2-4所表示的意思是相同的。当P条件成立时执行A操作,P不成立则执行B操作。图2-7顺序结构图2-8选择结构图2-9当型循环结构图2-10直到型循环结构（3）循环结构。当型循环结构用图2-9形式示,当p1条件成立时反复执行A操作，直到p1条件不成立为止；直到型循环结构如图2-10所示。用以上3种N-S流程图中的基本框可以组成复杂的N-S流程图，以表示算法。案例4 流程图S流程图比文字描述直观、形象易于理解；比传统流程图索凑易画，尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N-S流程图中的上下顺序就是执行时的顺序,也就是图中位置在上面的先执行,位置在下面的后执行。写算法和看算法只需从上到下进行就可以了,十分方便。案例4 流程图2.7结构化程序设计方法一个结构化程序就是用计算机语言表示的结构化算法,用3种基本结构组成的程序必是结构化的程序。这种程序便于编写、阅读、修改和维护,这就减少了程序出错的机会,高了程序的可靠性,保证了程序的质量。结构化程序设计强调程序设计风格和程序构的规范化,提倡清晰的结构。怎样才能得到一个结构化的程序呢?如果面临一个复杂的问题,是难以一下子写出一个层次分明、结构清晰、算法正确的程序的。结构化程序设计方法的基本思路是:把一个复杂问题的求解过程分阶段进行,每个阶段处理的问题都控制在人们容易理解和处理的范围内。案例4 流程图具体说,采取以下方法来保证得到结构化的程序:（1）自顶向下；（2）逐步细化；（3）模块化设计；（4）结构化编码。在接受一个任务后应怎样着手进行呢?有种不同的方法:一种是自顶向下,逐步细化；一种是自下而上，逐步积累。案例4 流程图设计房屋就是用自顶向下、逐步细化的方法。先进整体规划,然后确定建筑物方案，再进行各部分的设计,最后进行细节的设计(如门窗、楼道等),而绝不会在没有整体方案之前先设计楼道和功能间。而在完成设计,有了图纸之后,在施工阶段则是自下而上实施的,用一砖一瓦先实现一个局部,然后由各部分组成一个建筑物。在程序设计中常采用模块设计的方法,尤其程序比较复杂时,更有必要。在拿到一个程序模块以后根据程序模块的功能将它划分为若干个子模块,如果这些子模块的规模还嫌大,可以再划为更小的模块。这个过程采用自顶向下的方法来实现。程序中的子模块在C语言中通常用函数来实现。模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个小任务，每一个子任务就相对简单了。在设计好一个结构化的算法之后，还要善于进行结构化编码。所谓编码就是将已设计好的算法用计算机语言来表示，即根据已经细化的算法正确地写出计算机程序。案例4 流程图任务实施:设year为被检测的年份。算法可表示如下:S1：2000yearS2：若year不能被4整除，则输出year的值和“不是闰年”。然后转到S6，检查下一个年份S3：若year能被4整除，不能被100整除，则输出year的值和“不是闰年”，然后转到S6S4：若year能被400整除，输出year的值和“是闰年”，然后转到S6S5：输出year的值和“不是闰年”S6：year+1yearS7：当year2500时,转S2继续执行，否则算法停止。案例4 流程图在这个算法中，采取了多次判断；先判断year能否被4整除,如不能,则year必然不是闰年。如year能被4整除，并不能马上决它是否闰年,还要检查它能否被100整除。如不能被100整除,则肯定是闰年(例如2008年)。如能被100整除，还不能判断它是否闰年，还要检查它能否被400整除，如果能被40整除，则是闰年，否则不是闰年。根据以上分析，依据判定条件一步一步缩小检查判断的范围，直至得到相应的结果。流程图如图2-11所示，用流程图表示算法要比文字描述算法逻辑清晰、易于理解。案例4 流程图图2-11判断是否为闰年的流程图案例4 流程图任务总结:在本次任务中通过分析2000你2500年中每一年是否为闰年的自然语言叙述算法和流程图表示算法，将步骤进行细化分解后，逐步缩小范围，最终输出结果。以上任务还可以通过N-S流程图的方式来分析，如图2-12所示，可以根据习惯选择适合个人思维的流程图来分析算法。图2-12判断是否为闰年N-S流程图案例4 流程图任务拓展:绘制以下两个任务的流程图：1.求方程式ax2+bx+c=0的根，分别考虑（1）有两个不等的实根；（2）有两个相等的实根。2.依次将10个数输入，输出其中最大的数。项目总结C语言中所谓的算法实际上就是程序设计的主要思想，这些思想就是C语言代码中的各种语句、运算或者指令信息的体现。而程图则是将编程中的算法思想通过绘制图形以及流程的形式展示出来。本项目通过两个任务的实现，介绍了算法的基本知识和流程图的基本结构，并通过任务实例分析算法的实现过程，用传统流程图和N-S图实现复杂算法逐步细化分解；最后介绍了结构化程序设计的方法。项目总结学习程序设计的目的不只是为了掌握某一种特定的语言,而应当学习程序设计的一般方法。脱离具体的语言去学习程序设计是困难的,但是,学习语言是为了设计程序,它本身绝不是目的。高级语言有许多种,每种语言也都在不断发展,因此千万不能只拘于一种具体的语言,而应当能举一反三,在需要的时候能很快地使用另一种语言编程。关键是掌握算法,有了正确的算法,用任何语言进行编码都不是什么困难的事。达标检测:一、填空题1.算法是针对出现的问题所设计的 以及 。2.计算机中的算法大致可分为 、两类。3.时间复杂度是指一个算法在 所消耗的时间。4.流程图的三种基本结构，分别是 、。5.结构化程序设计方法：、。二、简单题1.算法的特性有哪些？2.用传统流程图（或N-S流程图）求解以下问题的算法。（1）有两瓶水，要求将瓶子里盛放的水互换。（2）有3个数a，b，c，要求按大到小的顺序输出。（3）求两个数m和n的最大公约数。