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

《C语言程序设计课件第2章.ppt》由会员分享，可在线阅读，更多相关《C语言程序设计课件第2章.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 算法与算法描述返回主目录返回主目录第2章 算法与算法描述 本章主要介绍算法的基本概念、本章主要介绍算法的基本概念、一般特性、算法的实现和算法的描述一般特性、算法的实现和算法的描述方法。方法。1.1.算法的一般特性算法的一般特性2.2.算法的简单举例算法的简单举例3.3.算法的描述方法算法的描述方法第2章 算法与算法描述程序的具体程序的具体操作实现步操作实现步骤，也就是骤，也就是算法。算法。算法是指为了解决一个特定的问题所采用的方法和步骤算法是指为了解决一个特定的问题所采用的方法和步骤。一、算法的概念一、算法的概念计算机程序都包含两个方面的内容：计算机程序都包含两个方面的内容：操作对象操

2、作对象和和操作过程操作过程程序要处理的数程序要处理的数据对象（也叫数据对象（也叫数据结构），包括据结构），包括数据的类型、值数据的类型、值和相应组织形式和相应组织形式第2章 算法与算法描述算法是程序的一个重要组成部分，程序离不开算法，事实上算算法是程序的一个重要组成部分，程序离不开算法，事实上算法的设计是程序设计的核心任务之一，是程序设计的灵魂法的设计是程序设计的核心任务之一，是程序设计的灵魂 坐火车从武汉到北京开会，应先买车票，然后准时到车站检票坐火车从武汉到北京开会，应先买车票，然后准时到车站检票上车，火车到达北京后下车，最后乘公交车到会场，这就是算上车，火车到达北京后下车，最后乘公交车到

3、会场，这就是算法。这些步骤都是按一定顺序进行的，缺一不可，次序也不能法。这些步骤都是按一定顺序进行的，缺一不可，次序也不能出错。也就是说，要处理一件事情，应事先考虑好具体的实施出错。也就是说，要处理一件事情，应事先考虑好具体的实施步骤，然后按部就班地进行。步骤，然后按部就班地进行。对于同一个问题，可以有不同的算法。就像从武汉到北京开会，对于同一个问题，可以有不同的算法。就像从武汉到北京开会，可以选择坐飞机，坐火车、长途客车或自驾车，不同的人可以可以选择坐飞机，坐火车、长途客车或自驾车，不同的人可以综合考虑时间和经济承受能力选取一个合适的行程。在程序设综合考虑时间和经济承受能力选取一个合适的行程

4、。在程序设计中，尽管解决一个问题的算法有多种，但要考虑到算法的质计中，尽管解决一个问题的算法有多种，但要考虑到算法的质量，选择合理的算法。量，选择合理的算法。第2章 算法与算法描述二、算法的一般特性二、算法的一般特性1.1.任何一个算法的操作步骤应该是有限的，具有任何一个算法的操作步骤应该是有限的，具有“有穷性有穷性”，否则将无法得到结果。，否则将无法得到结果。2.2.算法中的每一个步骤应该是确定的算法中的每一个步骤应该是确定的 ，具有，具有“确定性确定性”。3.3.执行算法时应该与外界有必要的信息交流，有零个或多个执行算法时应该与外界有必要的信息交流，有零个或多个数据输入。数据输入。4.4.

5、能输出具体结果，有一个或多个输出。能输出具体结果，有一个或多个输出。5.5.算法应当面面俱到，每一个步骤都能有效地执行，能得到算法应当面面俱到，每一个步骤都能有效地执行，能得到确定的结果，具有确定的结果，具有“有效性有效性”。第2章 算法与算法描述一、算法的简单举例一、算法的简单举例例例1 求求123420的值，写出相应算法。的值，写出相应算法。具体分析如下：具体分析如下：123420 每次都将前一次的乘积乘以后面的数每次都将前一次的乘积乘以后面的数 t t为被乘数，为被乘数，i i为乘数为乘数 ，将每，将每一步的乘积放到被乘数中一步的乘积放到被乘数中算法如下：算法如下：第一步：使第一步：使t

6、=1t=1第二步：使第二步：使i=2i=2第三步：使第三步：使titi，乘积结果仍放在变量，乘积结果仍放在变量t t中，可表示为：中，可表示为：ti=tti=t第四步：使第四步：使i i的值加的值加1 1，即，即i+1=ii+1=i第五步：如果第五步：如果i i的值不大于的值不大于2020，返回，重新执行第三步，以及后面，返回，重新执行第三步，以及后面的第四步、第五步；否则，输出的第四步、第五步；否则，输出t t，算法结束。，算法结束。第2章 算法与算法描述例例2 2 求求1+2+3+4+201+2+3+4+20的值，写出相应算法。的值，写出相应算法。具体分析如下：具体分析如下：1 1+2+3

7、+4+20+2+3+4+20 每次都将前一次的和加上后面的数每次都将前一次的和加上后面的数 s s为被加数，为被加数，i i为加数为加数 ，将，将每一步的和放到被加数中每一步的和放到被加数中算法如下：算法如下：第一步：使第一步：使s=1s=1第二步：使第二步：使i=2i=2第三步：使第三步：使s+is+i，和结果仍放在变量，和结果仍放在变量s s中，可表示为：中，可表示为：s+i=ss+i=s第四步：使第四步：使i i的值加的值加1 1，即，即i+1=ii+1=i第五步：如果第五步：如果i i的值不大于的值不大于2020，返回，重新执行第三步，以及后面，返回，重新执行第三步，以及后面的第四步、

8、第五步；否则，输出的第四步、第五步；否则，输出s s，算法结束。，算法结束。第2章 算法与算法描述算法可表示如下：算法可表示如下：第一步：输入第一步：输入n n的值的值第二步：使第二步：使i=2i=2第三步：第三步：n n除以除以i,i,得到余数得到余数r r第四步：如果第四步：如果r r等于等于0 0，表示，表示n n能被能被i i整除，则打印整除，则打印“n“n不是素不是素数数”，算法结束。否则执行第五步，算法结束。否则执行第五步 第五步：第五步：i+1=ii+1=i第六步：如果第六步：如果in-1,in-1,返回执行第三步。否则打印返回执行第三步。否则打印“n“n是素数是素数”，然后结束

9、。，然后结束。例例 3 判定一个大于或等于判定一个大于或等于3的正整数是否为素数。的正整数是否为素数。素数是指除素数是指除1 1和该本身以外，不能被其它任何整数整除的数。和该本身以外，不能被其它任何整数整除的数。例如，例如，1313是素数，因为它不能被是素数，因为它不能被2 2、3 3、4 4、.、1212整除。整除。判断一个数判断一个数n(n3)是否素数：将是否素数：将n作为被除数，将作为被除数，将2到（到（n-1）各个整数轮流作为除数，如果都不能整除，则各个整数轮流作为除数，如果都不能整除，则n为素数。为素数。第2章 算法与算法描述算法的常用表示方法有：算法的常用表示方法有：自然语言描述法

10、、流程图描述法、自然语言描述法、流程图描述法、伪代码描述法、计算机语言描述法伪代码描述法、计算机语言描述法等。等。一、算法的描述方法一、算法的描述方法1.1.自然语言描述法自然语言描述法自然语言是人们在日常生活中进行交流的语言，用自然语言描自然语言是人们在日常生活中进行交流的语言，用自然语言描述算法显得通俗易懂，但文字表述比较繁琐，语义也不太严格，述算法显得通俗易懂，但文字表述比较繁琐，语义也不太严格，容易出现容易出现“歧义性歧义性”。用自然语言描述比较复杂的算法，容易。用自然语言描述比较复杂的算法，容易造成混淆，很不方便，所以，一般情况下不采用自然语言描述造成混淆，很不方便，所以，一般情况下

11、不采用自然语言描述算法。算法。第2章 算法与算法描述 2.2.用流程图表示算法用流程图表示算法流程图是用一些简单的图框来表示各种算法的具体操作过程，直观形象，易于理解。美国标准化协会ANSI规定了一些常用的流程图符号 起止框起止框输入输出框输入输出框判断框判断框处理框处理框流程线流程线连接点连接点注释框注释框第2章 算法与算法描述例例3 3 求求1x2x3x4xx201x2x3x4xx20的值，画出流程图。的值，画出流程图。开始开始t=1t=1i=20i=20输出输出t t结束结束i=2i=2t=t*it=t*ii=i+1i=i+1真真假假#include stdio.h#include st

12、dio.hmain()main()float t,i;float t,i;t=1;t=1;i=2;i=2;dodot=t*i;t=t*i;i=i+1;i=i+1;while(i=20);while(iy then print xelse print y第2章 算法与算法描述算法：算法：设置设置t t的初值为的初值为1 1设置设置i i的初值为的初值为2 2当当i=20i=20，执行下面操作：，执行下面操作：使使t=t*it=t*i 使使i=i+1i=i+1(循环体到此结束循环体到此结束)打印打印t t的值的值例例5 5 求求1 x 2 x 3 x 4 xx 201 x 2 x 3 x 4 xx

13、 20的值，用伪代码表示算法的值，用伪代码表示算法也可以写成以下形式：也可以写成以下形式：BEGIN：t=1i=2while i=20t=t*i i=i+1pring tEND第2章 算法与算法描述算法如下：算法如下：BEGIN：input nflag=0i=2whlie i=n-1if n%i=0 then flag=1else i=i+1 end ifend doif flag=1 then print(“是素数是素数”)else print(“不是素数不是素数”)end if例例6.判定一个大于或等于判定一个大于或等于3的正整数是否为素数，用伪代码表示的正整数是否为素数，用伪代码表示第2

14、章 算法与算法描述 4.4.用计算机语言表示算法用计算机语言表示算法 例例7 1 x 2 x 3x 4 xx 20的值。的值。用用C语言描述算法的程序源代码如下：语言描述算法的程序源代码如下：#include stdio.hmain()float i,t;t=1;i=2;while(i=20)t=t*i;i=i+1;printf(%.2f,t);第2章 算法与算法描述例例7 判定一个大于或等于判定一个大于或等于3的正整数是否为素数用的正整数是否为素数用C语言表语言表示。示。用用C语言描述算法的程序源代码如下：语言描述算法的程序源代码如下：#include stdio.hmain()int n,i,r;scanf(%d,&n);i=2;dor=n%i;if(r=0)printf(it is not prime number!n);goto loop;i=i+1;while(i=n-1);printf(it is prime number!n);loop:;