C语言程序设计课件第2章.ppt

返回主目录,C语言程序设计,（第2章 算法与算法描述）,本章主要介绍算法的基本概念、一般特性、算法的实现和算法的描述方法。,1. 算法的一般特性 2. 算法的简单举例 3. 算法的描述方法,程序的具体操作实现步骤，也就是算法。,算法是指为了解决一个特定的问题所采用的方法和步骤。,一、算法的概念,计算机程序都包含两个方面的内容：操作对象和操作过程,程序要处理的数据对象（也叫数据结构），包括数据的类型、值和相应组织形式,算法是程序的一个重要组成部分，程序离不开算法，事实上算法的设计是程序设计的核心任务之一，是程序设计的灵魂,坐火车从武汉到北京开会，应先买车票，然后准时到车站检票上车，火车到达北京后下车，最后乘公交车到会场，这就是算法。这些步骤都是按一定顺序进行的，缺一不可，次序也不能出错。也就是说，要处理一件事情，应事先考虑好具体的实施步骤，然后按部就班地进行。,对于同一个问题，可以有不同的算法。就像从武汉到北京开会，可以选择坐飞机，坐火车、长途客车或自驾车，不同的人可以综合考虑时间和经济承受能力选取一个合适的行程。在程序设计中，尽管解决一个问题的算法有多种，但要考虑到算法的质量，选择合理的算法。,二、算法的一般特性,1. 任何一个算法的操作步骤应该是有限的，具有“有穷性”，否则将无法得到结果。 2. 算法中的每一个步骤应该是确定的 ，具有“确定性”。 3. 执行算法时应该与外界有必要的信息交流，有零个或多个数据输入。 4. 能输出具体结果，有一个或多个输出。 5. 算法应当面面俱到，每一个步骤都能有效地执行，能得到确定的结果，具有“有效性”。,一、算法的简单举例,例1 求123420的值，写出相应算法。 具体分析如下： 123420 每次都将前一次的乘积乘以后面的数,t为被乘数，i为乘数 ，将每一步的乘积放到被乘数中 算法如下：,第一步：使t=1 第二步：使i=2 第三步：使ti，乘积结果仍放在变量t中，可表示为：ti=t 第四步：使i的值加1，即i+1=i 第五步：如果i的值不大于20，返回，重新执行第三步，以及后面的第四步、第五步；否则，输出t，算法结束。,例2 求1+2+3+4+20的值，写出相应算法。 具体分析如下： 1 + 2 + 3 + 4 + 20 每次都将前一次的和加上后面的数,s为被加数，i为加数 ，将每一步的和放到被加数中 算法如下：,第一步：使s=1 第二步：使i=2 第三步：使s+i，和结果仍放在变量s中，可表示为：s+i=s 第四步：使i的值加1，即i+1=i 第五步：如果i的值不大于20，返回，重新执行第三步，以及后面的第四步、第五步；否则，输出s，算法结束。,算法可表示如下： 第一步：输入n的值 第二步：使i=2 第三步：n除以i,得到余数r 第四步：如果r等于0，表示n能被i整除，则打印“n不是素数”，算法结束。否则执行第五步 第五步：i+1=i 第六步：如果in-1,返回执行第三步。否则打印“n是素数”，然后结束。,例 3 判定一个大于或等于3的正整数是否为素数。,素数是指除1和该本身以外，不能被其它任何整数整除的数。例如，13是素数，因为它不能被2、3、4、12整除。,判断一个数n(n3)是否素数：将n作为被除数，将2到（n-1）各个整数轮流作为除数，如果都不能整除，则n为素数。,算法的常用表示方法有：自然语言描述法、流程图描述法、伪代码描述法、计算机语言描述法等。,一、算法的描述方法,1. 自然语言描述法 自然语言是人们在日常生活中进行交流的语言，用自然语言描述算法显得通俗易懂，但文字表述比较繁琐，语义也不太严格，容易出现“歧义性”。用自然语言描述比较复杂的算法，容易造成混淆，很不方便，所以，一般情况下不采用自然语言描述算法。,2. 用流程图表示算法 流程图是用一些简单的图框来表示各种算法的具体操作过程，直观形象，易于理解。美国标准化协会ANSI规定了一些常用的流程图符号,起止框,输入输出框,判断框,处理框,流程线,连接点,注释框,例3 求1x2x3x4xx20的值，画出流程图。,运行程序,例4 判定一个大于或等于3的正整数是否为素数，用流程图表示。,3. 用伪代码表示算法,例如，打印“x和y这两个数的最大数”的算法可以用伪代码表示如下：,if xy then print x else print y,算法： 设置t的初值为1 设置i的初值为2 当i=20，执行下面操作： 使t=t*i 使i=i+1 (循环体到此结束) 打印t的值,例5 求1 x 2 x 3 x 4 xx 20的值，用伪代码表示算法,也可以写成以下形式： BEGIN： t=1 i=2 while i=20 t=t*i i=i+1 pring t END,算法如下： BEGIN： input n flag=0 i=2 whlie i=n-1 if n%i=0 then flag=1 else i=i+1 end if end do if flag=1 then print(“是素数”) else print(“不是素数”) end if,例6. 判定一个大于或等于3的正整数是否为素数，用伪代码表示,4. 用计算机语言表示算法,例7 1 x 2 x 3x 4 xx 20的值。 用C语言描述算法的程序源代码如下： #include “stdio.h“ main() float i,t; t=1; i=2; while(i=20) t=t*i; i=i+1;