程序与算法课件

第4章

程序与算法12/17/20221第4章

程序与算法12/14/2022112/17/20222§2C语言程序的基本结构§2

C语言程序的基本结构一.C语言程序结构main()

程序首部{

说明语句

数据结构

语句

输入语句

执行语句运算处理

算法设计}

输出语句12/17/2022212/14/20222§2C语言程序的基本结构§2C12/17/20223生成执行程序的四个过程

编辑、编译、连接、运行12/17/2022312/14/20223生成执行程序的四个过程12/14/2012/17/20224§4C语言编程环境编译方式用户目标程序源程序执行程序库文件连接程序编译程序编辑程序错误信息结果编译连接编辑.c.obj.exe运行12/17/2022412/14/20224§4C语言编程环境编译方式用户目标12/17/20225END课堂练习题[1.1]运行的程序的后缀是______。[1.2]C语言源程序文件的后缀是______，经过编译后,生成文件的后缀是______，经过连接后，生成文件的后缀是______。[1.3]结构化程序由____、____、____三种基本结构组成。.EXE.C.OBJ.EXE顺序分支循环完12/17/2022512/14/20225END课堂练习题[1.1]运行的几个知识要点程序=数据结构+算法“数据结构”就是要告诉程序要用到哪些数据、哪种类型的数据、数据间的关系以及数据存储方法。“算法”就是计算机解题所进行操作的步骤，是程序的逻辑抽象，是解决问题的数学过程，是对解题过程准确而完整的描述。编程是一种“把一件事情交给计算机去做”的行为，这个行为通过程序语言加以描述。算法设计是编程前必须要做的事，解决“做什么”和“如何做”的问题，然后程序再根据算法实现出来，因此算法是程序设计的灵魂。§1程序设计与算法概述12/17/20226几个知识要点程序=数据结构+算法§1程序设计与算法概述12几个知识要点C语言本身的语法规则C语言从基本字符集到关键字、标识符、常量、变量、函数和表达式等基本“单词”，再到基本语句，结合具体的语言规则和要求就构成C语言的程序。C程序的组成要素和设计、调试步骤函数是构成程序的基本单位，语句是构成函数的基本单位。函数用于实现某一项功能，语句用于体现完成这个功能所进行操作的详细步骤。程序设计就是分析解决问题的方法步骤，并将其记录下来的过程。程序设计过程包括分析、设计、编码、测试、排错、文档编写等阶段。§1程序设计与算法概述12/17/20227几个知识要点C语言本身的语法规则§1程序设计与算法概述11.程序设计的步骤一个初级程序员对于一个简单的问题，若要用计算机解决，具体步骤大致为：①确定待解决问题的计算或处理方法；②将实际问题转变为一个数学问题，用数学模型(表达式)描述；③编制程序框图，确定程序结构；④选择计算机语言和它的工作模式；⑤编制程序；⑥上机编辑、调试（包括编译和连接），消除语法错误；⑦如果结果正确则生成最终的用户程序，否则返回①从头重来，找出逻辑或设计错误所在。§1程序设计与算法概述12/17/202281.程序设计的步骤一个初级程序员对于一个简单的问题，若要用计如何表示算法？

处理思路：公式？输入要求？

错误处理方法？解决问题方法？2.算法举例【例4-1】输入三角形三个边的值，计算这个三角形的面积。如何输入？如何计算和输出？输入的是什么类型的值，输出类型、精度如何？输入值错误（不能构成三角形）如何解决？§1程序设计与算法概述12/17/20229如何表示算法？处理思路：公式？输入要算法描述图示#include<stdio.h>#include<math.h>intmain(){inta,b,c;floats,area;scanf(“%d,%d,%d”,&a,&b,&c);if(“不能构成三角形”){printf(“inputerror!”);return0;}else{s=(a+b+c)/2.0;area=sqrt(s*(s-a)*(s-b)*(s-c));printf(“area=%.2f”,area);}return0;}12/17/202210算法描述图示#include<stdio.h>12/14/目录§1程序设计与算法概述§2程序设计思想

§3算法描述方法§4算法特性与评价方法§5本章小节

第4章算法12/17/202211目录§1程序设计与算法概述第4章算法12/14/2§2程序设计思想4.2.1

结构化程序设计思想

1.基本概念1966年C.Bobm提出任何程序都可以用顺序、选择、循环三种基本结构来组合，这样编写出来的程序易懂易读也易于修改，提高了程序可靠性。这样的程序称为结构化程序，编写这样的程序称为结构化程序设计。“分而治之”是一种解决复杂问题的常用方法，是结构化程序设计思想的具体体现。大问题可以分解为若干关联的小问题，小问题又可以分解为若干更小、更具体的问题。把小问题逐一求解，大问题就得到解决。2.结构化程序设计的方法（1）自顶向下、逐步细化。（2）模块化。（3）结构化编码。12/17/202212§2程序设计思想4.2.1结构化程序设计思想196“自顶向下、逐步细化”方法“自顶向下、逐步细化”就是从一个大问题出发，往下逐步分解，由宏观到微观，由一般问题到具体细节实现等进行有序、有层次、有步骤的分析，最终在编写程序前，给出所有方法步骤的细节。例如：计算学院教师的平均工资。这个任务比较复杂，可分解为如下几点：（1）找出每个教师的收入；（2）计算共有多少教师；（3）计算工资总额；（4）计算平均工资。对于第（3）步又可再细分为：①找出一位教师档案；②读出工资数额；③累计求和；重复上述三步骤。对于①可再次进一步细分为：打开档案；找出正确记录；从磁盘读取数据。§2程序设计思想12/17/202213“自顶向下、逐步细化”方法“自顶向下、逐步细化”就是从一个模块化设计

结构化程序设计的另一个概念是模块化设计，把一个大的复杂的问题逐层分解为一系列小的简单的模块来进行处理，每个小模块只完成单一的具体任务。模块内部联系紧密，而与其他模块之间联系较弱，这样的模块称为独立性高的模块，实现“高内聚、低耦合”。模块化“功能分解”即按照问题的功能进行模块划分，把相近功能的任务放到一个模块中。

§2程序设计思想12/17/202214模块化设计 结构化程序设计的另一个概念是模块化设计，把一1)模块之间接口关系简单，每个模块完成独立的工作，易于被人理解，所编写出来的程序可读性和可理解性好；

2)各个模块功能单一，要修改某一个模块时只涉及到要修改的模块而不涉及到其他模块，不会出现修改程序时牵一发动全身的现象；3)人们可以单独验证、测试一个个模块，保证其正确性；4)可以利用现有模块，像搭积木一样进行开发新的程序。独立性高的模块有以下优点：§2程序设计思想12/17/2022151)模块之间接口关系简单，每个模块完成独立的工作，易于被模块之间是一种层次结构，上层模块对下层模块进行调用，下图所示是报表生成程序的层次结构，以柜形框表示模块，框中的模块名称表明模块的功能，提出顶层的模块“做什么”而不涉及“怎样做”，最下层模块功能十分具体，涉及“怎样做”的精确描述，易于编程。报表生成程序数据输入数据计算求和求平均求方差打印报表§2程序设计思想12/17/202216模块之间是一种层次结构，上层模块对下层模块进结构化编码通过顺序、分支、循环三种基本结构通过函数方式实现功能通过多程序（.c文件）实现项目1.三种基本控制结构：

顺序控制、选择控制、循环控制。2.模块化组织结构：按功能划分模块，每个模块易于理解且不可再分，用函数实现模块化组织结构。3.程序设计过程：自顶而下、逐步细化。结构化程序设计要点§2程序设计思想12/17/202217结构化编码通过顺序、分支、循环三种基本结构1.三种基本控结构化程序有三种基本结构顺序结构选择结构循环结构语句执行的顺序与程序书写的顺序一致条件成立，执行A；否则，执行B重复执行某组动作结构条件成立时，反复执行A；条件不成立，停止重复执行动作A，当某一条件成立时，停止C程序的基本结构12/17/202218结构化程序有三种基本结构顺序结构选择结构循环结构语句执行的顺main(){inta,b,c;a=5;b=6;c=a+b;printf(“%d”,c);}程序执行的顺序和语句书写的顺序一致有一个数据入口一个数据出口AB基本结构顺序结构12/17/202219main()程序执行的顺序和语有一个数据入口AB基本结构顺条件ABYN当条件满足时,执行语句A；否则,执行语句B有一个数据入口一个数据出口键盘输入一个整数,判断其正负例inta;aa>0if(a>0)printf(“a为正数”);elseprintf(“a为负数”);语句A语句B打印a的值选择结构12/17/202220条件ABYN当条件满足时,执行语有一个数据入口键盘输入一个整YN求1~100的自然数之和

X<=100x=1S=0语句若条件满足,重复执行语句内容；否则,退出循环条件一个数据入口一个数据出口s=s+x;x=x+1;语句S条件不满足,不执行任何语句循环结构

1.当型循环12/17/202221YN求1~100的自然数之和X<=100x=1语句若语句NY求1+2+3+~n<=1000的最大的n例:n=1,s=0;s=s+nn=n+1……S>1000n=1s=0语句不论条件是否满足,语句至少执行一次

2.直到型循环s=1+2+3+……n=?(s<1000)

12/17/202222语句NY求1+2+3+~n<=1000的最大的n例:n=13.结构化程序设计的特点1）以三种基本结构的组合进行程序的编写；2）程序的编写采用模块化结构；3）自顶向下，逐步求精；4）限制使用goto语句，不用或少用goto语句，通常只允许用它从一个循环中跳出而不允许从外部跳入一个循环；5）每一个结构只允许有一个入口和一个出口。各部分之间接口简单，逻辑清晰；6）采用结构化语言编写程序，程序结构清晰易于阅读和修改；7）采用良好的编程风格。§2程序设计思想12/17/2022233.结构化程序设计的特点1）以三种基本结构的组合进行4.程序设计步骤1.分析问题，建立数学模型。2.确定数据结构。3.确定算法，描述算法。4.编制程序，调试程序。5.运行程序，得到结果。程序设计要求：书写正确，结果正确§2程序设计思想12/17/2022244.程序设计步骤1.分析问题，建立数学模型。程序设计要求4.2.2面向对象的程序设计基本概念1.基本概念面向对象程序设计的本质是把数据与处理数据的过程当成一个整体——对象。类（CLASS）：定义了一类事物的抽象特点，包括事物的属性和它具有的行为（称为方法）。父类、子类

实例(Instance)对象(Object)：是类的实例，是某个类别的具体化的事物。方法（method）是一个类能做的事情，代表具体操作功能。

消息（Message）继承（Inheritance）多态性（Polymorphism）§2程序设计思想12/17/2022254.2.2面向对象的程序设计基本概念1.基本概念类（CL2.面向对象程序设计的优点稳定性好可重用性好与人类习惯的思维方法一致易于开发大型软件产品可维护性好§2程序设计思想12/17/2022262.面向对象程序设计的优点稳定性好§2程序设计思想目录§1程序设计与算法概述§2程序设计思想§3算法描述方法§4算法特性与评价方法§5本章小节

第4章算法12/17/202227目录§1程序设计与算法概述第4章算法12/14/2算法分类利用计算机解题，一般有两类算法：数值计算算法和非数值计算算法。数值计算是指求数值解的问题（如计算方程根，求最大公约数等），往往有现成的模型、计算方法和公式对应。非数值计算主要解决需要用分析推理、逻辑推导才能解决的问题。由于种类繁多、要求各异，只有一些典型的非数值计算方法（如排序、查找算法等），许多问题需要设计解决问题的专门算法。§3算法描述方法12/17/202228算法分类利用计算机解题，一般有两类算法：数值计算算法和非数值2.算法的描述自然语言传统流程图NS结构化流程图伪代码程序代码（最准确的描述）。§3算法描述方法12/17/2022292.算法的描述自然语言§3算法描述方法12/14/20§3算法描述方法2.算法的表示②传统流程图描述

下图表示程序流程图的基本符号，建议初学者养成编写程序前先画图的习惯，通过流程图使你的算法思想和实现步骤得以体现，便于检查、修改和交流。程序流程图基本符号12/17/202230§3算法描述方法2.算法的表示②传统流程图描述 下图表三种基本结构的流程图描述模块A模块BYesNo条件判断模块A模块B§3算法描述方法12/17/202231三种基本结构的流程图描述模块A模块BYesNo条件判断模块A三种基本结构的流程图描述模块A模块BYesNo条件判断模块A模块B模块A条件？No条件？模块ANo§3算法描述方法12/17/202232三种基本结构的流程图描述模块A模块BYesNo条件判断模块A②流程图

人们普遍采用程序流程图是因为它简单、直观。把执行的流程表达得一清二楚，易于理解。然而，它也有不少缺陷，程序流程图中的箭头十分灵活，使用不当会影响到程序结构的清晰。X1=(-b+)/2aX2=(-b-)/2a开始输入a,b,cS=b*b-4*a*cS>=0y打印X1，X2打印“无实根解”n结束方程ax２+bx+c＝0的求解算法§3算法描述方法12/17/202233②流程图 人们普遍采用程序流程图是因为它简开始s=0,a=0输入na=a+1s=s+aa<nYN输出s结束

用规定的一系列图形、流程线和文字说明算法中的基本操作和控制流程。scanf(“%d”,&n);printf(“%d”,s);While(a<n)流程图应用举例：例如计算:s=Σa;a=1~n§3算法描述方法12/17/202234开始输入na=a+1a<nYN输出s结束用规定的一3.NS结构化流程图 N-S图的基本形式模块1模块2模块3条件TF

模块A模块B

While

条件模块

模块

Until条件顺序分支循环1循环2§3算法描述方法12/17/2022353.NS结构化流程图 N-S图的基本形式模块1While

N-S图举例

输入系数a,b,cS=b*b-4*a*cS>=0

打印“无实根解”X1=(-b+)/2aX2=(-b–)/2a打印X1,X2FT方程ax２+bx+c＝0的求解§3算法描述方法12/17/202236N-S图举例【例4-2】用传统流程图和NS结构化流程图分别描述“求3个整数中的最大值”的算法。问题分析：求3个整数最大值方法很多，但都需要通过判断解决。具体步骤为：（1）输入3个整数；（2）通过判断比较，找出最大值；（3）输出最大值，然后结束。算法设计：本例的关键是如何比较找到最大值。方法很多，这里给出一种做法如下：（1）先设定一个变量max用于保存最大值；（2）把先输入的第一个数作为最大值放入max变量中；（3）把第二个输入的数与最大值量max进行比较，若比max中值大，则放入max中；（4）同样进行第三个数与max的比较，并保存最大值；（5）最后输出最大值。§3算法描述方法12/17/202237【例4-2】用传统流程图和NS结构化流程图分别描述“求3个整NoNo开始输入a,b,c3个数amaxbmaxcmaxb>maxc>max输出max结束输入a,b,camaxb>max?YesNobmax

c>max?YesNocmax输出max值§3算法描述方法12/17/202238NoNo开始输入a,b,c3个数amaxbmaxc4．伪代码描述伪代码（Pseudocode）是用介于自然语言和计算机语言之间的文字和符号表示算法，即程序设计语言具有的关键字用英文表示，其它的可用汉字、英文、数字和公式等表示，便于书写和阅读即可。用此方法描述算法并无格式要求，只要简单、清晰、易懂。【例4-3】用伪代码描述例4-2问题的算法。开始申请4个变量a,b,c,max，其中max用于存放最大值；先后从键盘输入3个整数给变量a,b,c；amax当b≤max时，继续进行比较，否则执行bmax继续判断：当c>max时，执行cmax输出max的值结束§3算法描述方法12/17/2022394．伪代码描述伪代码（Pseudocode）是用介于自然语5．用计算机语言描述用计算机语言描述算法，应该是上述步骤完成后的最后一步，也是最精确的一步。这一步的描述要求必须按照程序设计语言的语法规则编写规范的程序代码，只有这样才能上机调试和运行。例4-2问题的C语言程序代码描述如下：/*求3个整数中的最大值*/#include<stdio.h>intmain(){inta,b,c,max;scanf(“%d,%d,%d”,&a,&b,&c);max=a;if(b>max)max=b;if(c>max)max=c;printf(“max=%d\n”,max);return0;}NoNo开始输入a,b,c3个数amaxbmaxcmaxb>maxc>max输出max结束§3算法描述方法12/17/2022405．用计算机语言描述用计算机语言描述算法，应该是上述步骤完成算法举例

程序设计的关键是算法设计，有了算法，再用计算机语言去实现算法，就容易了。例1：计算1+2+3+…+100之和。算法步骤分析：S1:累加器变量sum赋初值0，即sum=0S2:计数器变量i赋初值1，即i=1S3:使累加器变量值sum加计数器变量值i,结果仍放在sum中,即sum=sum+i,此时sum值为

sum=sum+i=0+1=1S4:使计数器变量i加1,结果仍放在i中,即i=i+1,此时i值为

i=i+1=1+1=2依此类推……§3算法描述方法12/17/202241算法举例程序设计的关键是算法设计，有了算法，再程序流程图和N-S图如下图所示

图1累加运算程序流程图开始

sum=0i=0sum=sum+ii=i+1i<=100打印NY图2累加运算N-S图

§3算法描述方法12/17/202242程序流程图和N-S图如下图所示C语言程序算法如下

main(){inti=1,sum=0;/*定义变量及其数据类型*/

while(i<=100)

/*循环控制结构*/{sum+=i; i=i+1;}/*循环体结束*/printf(“sum=%d\n”,sum);/*输出累加结果*/}

程序算法不是唯一的，这个问题还有其它的算法。§3算法描述方法12/17/202243C语言程序算法如下main()§3算法以此类推可以很容易表示出其它问题的算法例2：计算下式之和的算法，当分母大于100时程序结束，输出计算结果。程序算法如下。§3算法描述方法12/17/202244以此类推可以很容易表示出其它问题的算法例2：计算下式例2算法的N-S图如下所示§3算法描述方法12/17/202245例2算法的N-S图如下所示§3算法描述方法12/14/附加知识：PAD图 PAD图的基本符号S1S2S3While条件SUntil条件S顺序分支循环S1S2条件T§3算法描述方法12/17/202246附加知识：PAD图 PAD图的基本符号S1S2S3WhiPAD图 方程ax２+bx+c＝0的求解输入系数a,b,cS=b*b-4*a*cS>=0打印X1,X2打印“无实根解”

X2=(-b–)/2aX1=(-b+)/2a§3算法描述方法12/17/202247PAD图 方程ax２+bx+c＝0的求解输入系数a,b,目录§1程序设计与算法概述§2程序设计思想§3算法描述方法§4算法特性与评价方法§5本章小节

第4章算法12/17/202248目录§1程序设计与算法概述第4章算法12/14/24.4.1算法的特性

1.有穷性：算法包含的操作步骤是有限的，每一步都应在合理的时间内完成。2.确定性：算法中的每一步应该是确定的，而不应当是含糊的、模棱两可的和歧义的。3.有效性（可行性）：算法中的每一步应该能有效执行，且能得到确定的结果。4.有零个或多个输入：输入是计算机在执行算法时，需要从外界得到必要的信息。5.有一到多个输出：算法的目的是求得问题的解（计算结果），而解只有输出才有意义。§4算法特性与评价方法12/17/2022494.4.1算法的特性

1.有穷性：算法包含的操作步骤是有4.4.2算法分析与评价

1．正确性：算法应当满足具体问题的需求，设计和选择算法应该正确反映这种需求。对“正确”一词的理解，可分以下四个层次：（1）程序不含语法错误；（2）程序对于几组输入数据能够得到满足规格说明要求的结果；（3）程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到满足规格说明要求的结果；（4）程序对于一切合法的输入数据都能够得到满足规格说明要求的结果。第一层次是调试程序确保能够执行的需要，结果对与否不能保证；第二层次说明程序基本没有逻辑错误，但对于边缘数据、特殊数据等还没有检验，不能说明程序不会出现大问题；第三个层次是软件开发中“软件测试”环节所采用的方法，是判断能否达到商品化软件标准的要求；最后一个层次是理想化的要求，一般无法达到。§4算法特性与评价方法12/17/2022504.4.2算法分析与评价

1．正确性：算法应当满足具体问题4.4.2算法分析与评价

2．可读性：算法主要是为了人的阅读与交流，其次才是机器执行。只有可读性好的软件才能有助于他人对算法的理解，有助于程序代码的实现。提高可读性的方法一般有两点：一是严格遵循程序代码编写规范要求编写程序；二是添加必要的注释。3．健壮性：当输入非法数据时，算法程序能做出适当的反映（如显示输入错误提示等）或针对性的处理，而不会产生莫名其妙的输出结果或不可控的执行。§4算法特性与评价方法12/17/2022514.4.2算法分析与评价

2．可读性：算法主要是为了人的阅4.4.2算法分析与评价

4．高效率：算法效率指的是算法执行所使用的时间（一般为ns纳秒级）。对于一个问题，如果有多个算法可以解决，执行时间最短的效率最高。5．低存储量：算法存储量需求一般指算法执行过程中所需要的最大存储空间。§4算法特性与评价方法12/17/2022524.4.2算法分析与评价

4．高效率：算法效率指的是算法执附件知识：程序设计风格1.良好的程序设计风格语句形式化（准确）。程序一致性（各部分风格一致，文档格式一致）。适当使用注释（增加可读性）。标识符贴近实际，要求见名知意。“清晰第一，效率第二”§4算法特性与评价方法12/17/202253附件知识：程序设计风格语句形式化（准确）。“清晰第一，效率第

2．如何形成良好的设计风格１）源程序文档化符号名的命名程序注释视觉组织２）数据说明的方法数据说明的次序规范化说明语句中变量安排有序化使用注释语句来说明复杂的数据结构§4算法特性与评价方法12/17/2022542．如何形成良好的设计风格１）源程序文档化§4算法3）语句的结构在一行内只写一条语句；程序编写应优先考虑清晰性；除非对效率有特殊要求，要清晰第一，效率第二；首先保证程序正确，然后才提高速度；避免使用临时变量；避免不必要的转移；尽可能使用库函数；避免复杂的条件语句；尽量减少使用“否定”条件的条件语句；数据结构要有利于程序的简化；要模块化，使程序的功能尽可能单一化；利用信息隐蔽，确保模块的独立性；从数据出发去构造程序；不要修补不好的程序，要重新编写。§4算法特性与评价方法12/17/2022553）语句的结构在一行内只写一条语句；程序编4）输入和输出对所有的数据要检验合法性检查输入项的各项重要组合的合理性输入格式要简单输入数据时，应允许使用自由格式允许缺省值输入一批数据时，使用结束标志屏幕要给出提示信息加注释，保持输入格式和语句的一致性§4算法特性与评价方法12/17/2022564）输入和输出对所有的数据要检验合法性§4算法特性与评目录§1程序设计与算法概述§2程序设计思想§3算法描述方法§4算法特性与评价方法§5本章小节

第4章算法12/17/202257目录§1程序设计与算法概述第4章算法12/14/2什么是goto?结构化程序设计的提出是从goto语句(转向语句)的使用而引起的，goto语句使程序员随心所欲地从程序的一处转到另一处，充分发挥程序员的“技巧”，但过多使用goto语句会使程序结构十分零乱，流程一会儿向前，一会儿向后，令人眼花缭乱，顾此失彼，程序可读性差，难以阅读和理解，因此有的学者建议在程序中禁用goto语句，从而引起争论。§5本章小结12/17/202258什么是goto?结构化程序设计的提出是从goto语句(转向语§5本章小结

本章是计算机程序设计的基础，介绍了程序设计过程以及程序设计算法，学习时要重点理解和掌握的是计算机算法的表示方法，列举了用自然语言描述解决问题过程的特点与不足；作为一个程序设计人员，应该熟悉并掌握比较常用的程序流程图描述方法，以及N-S图描述算法的基本技能，最终需要使用计算机语言，即程序设计语言描述并实现。本章通过算法举例以训练引导学生用计算机的思维表达解决问题的过程，以最终实现算法，这就是程序设计算法的根本。12/17/202259§5本章小结本章是计算机程序设计的基础，介绍了程§5本章小结（1）算法是程序设计的核心。（2）描述算法的方法有很多，编写程序是最后一种方法，也是最严谨、最必要的方法。（3）解决一个问题，设计一组程序有不同的思想方法可以实现。（4）实际使用中，三种基本结构是根据需要而选择的，但一般顺序结构是一定会有的，因为程序是解决问题的有序步骤的集合。（5）由于问题的不同，由于不同设计者思考的方法不同，导致问题不可能只有一种程序设计方法和途径。

12/17/202260§5本章小结（1）算法是程序设计的核心。12/14/2END练习思考题1.简述程序设计包含哪些步骤？2.什么是计算机程序设计算法?3.用哪些方法表示计算机算法，各有哪些利弊？4.程序流程图有哪些表示符号，你认为有哪些优缺点？5.简述N-S图有什么特点？6.请用程序流程图和N-S图表示从键盘输入两个数，用计算机判别其大小的算法。12/17/202261END练习思考题1.简述程序设计包含哪些步骤？12/演讲完毕，谢谢观看！演讲完毕，谢谢观看！第4章

程序与算法12/17/202263第4章

程序与算法12/14/2022112/17/202264§2C语言程序的基本结构§2

C语言程序的基本结构一.C语言程序结构main()

程序首部{

说明语句

数据结构

语句

输入语句

执行语句运算处理

算法设计}

输出语句12/17/20226412/14/20222§2C语言程序的基本结构§2C12/17/202265生成执行程序的四个过程

编辑、编译、连接、运行12/17/20226512/14/20223生成执行程序的四个过程12/14/2012/17/202266§4C语言编程环境编译方式用户目标程序源程序执行程序库文件连接程序编译程序编辑程序错误信息结果编译连接编辑.c.obj.exe运行12/17/20226612/14/20224§4C语言编程环境编译方式用户目标12/17/202267END课堂练习题[1.1]运行的程序的后缀是______。[1.2]C语言源程序文件的后缀是______，经过编译后,生成文件的后缀是______，经过连接后，生成文件的后缀是______。[1.3]结构化程序由____、____、____三种基本结构组成。.EXE.C.OBJ.EXE顺序分支循环完12/17/20226712/14/20225END课堂练习题[1.1]运行的几个知识要点程序=数据结构+算法“数据结构”就是要告诉程序要用到哪些数据、哪种类型的数据、数据间的关系以及数据存储方法。“算法”就是计算机解题所进行操作的步骤，是程序的逻辑抽象，是解决问题的数学过程，是对解题过程准确而完整的描述。编程是一种“把一件事情交给计算机去做”的行为，这个行为通过程序语言加以描述。算法设计是编程前必须要做的事，解决“做什么”和“如何做”的问题，然后程序再根据算法实现出来，因此算法是程序设计的灵魂。§1程序设计与算法概述12/17/202268几个知识要点程序=数据结构+算法§1程序设计与算法概述12几个知识要点C语言本身的语法规则C语言从基本字符集到关键字、标识符、常量、变量、函数和表达式等基本“单词”，再到基本语句，结合具体的语言规则和要求就构成C语言的程序。C程序的组成要素和设计、调试步骤函数是构成程序的基本单位，语句是构成函数的基本单位。函数用于实现某一项功能，语句用于体现完成这个功能所进行操作的详细步骤。程序设计就是分析解决问题的方法步骤，并将其记录下来的过程。程序设计过程包括分析、设计、编码、测试、排错、文档编写等阶段。§1程序设计与算法概述12/17/202269几个知识要点C语言本身的语法规则§1程序设计与算法概述11.程序设计的步骤一个初级程序员对于一个简单的问题，若要用计算机解决，具体步骤大致为：①确定待解决问题的计算或处理方法；②将实际问题转变为一个数学问题，用数学模型(表达式)描述；③编制程序框图，确定程序结构；④选择计算机语言和它的工作模式；⑤编制程序；⑥上机编辑、调试（包括编译和连接），消除语法错误；⑦如果结果正确则生成最终的用户程序，否则返回①从头重来，找出逻辑或设计错误所在。§1程序设计与算法概述12/17/2022701.程序设计的步骤一个初级程序员对于一个简单的问题，若要用计如何表示算法？

处理思路：公式？输入要求？

错误处理方法？解决问题方法？2.算法举例【例4-1】输入三角形三个边的值，计算这个三角形的面积。如何输入？如何计算和输出？输入的是什么类型的值，输出类型、精度如何？输入值错误（不能构成三角形）如何解决？§1程序设计与算法概述12/17/202271如何表示算法？处理思路：公式？输入要算法描述图示#include<stdio.h>#include<math.h>intmain(){inta,b,c;floats,area;scanf(“%d,%d,%d”,&a,&b,&c);if(“不能构成三角形”){printf(“inputerror!”);return0;}else{s=(a+b+c)/2.0;area=sqrt(s*(s-a)*(s-b)*(s-c));printf(“area=%.2f”,area);}return0;}12/17/202272算法描述图示#include<stdio.h>12/14/目录§1程序设计与算法概述§2程序设计思想

§3算法描述方法§4算法特性与评价方法§5本章小节

第4章算法12/17/202273目录§1程序设计与算法概述第4章算法12/14/2§2程序设计思想4.2.1

结构化程序设计思想

1.基本概念1966年C.Bobm提出任何程序都可以用顺序、选择、循环三种基本结构来组合，这样编写出来的程序易懂易读也易于修改，提高了程序可靠性。这样的程序称为结构化程序，编写这样的程序称为结构化程序设计。“分而治之”是一种解决复杂问题的常用方法，是结构化程序设计思想的具体体现。大问题可以分解为若干关联的小问题，小问题又可以分解为若干更小、更具体的问题。把小问题逐一求解，大问题就得到解决。2.结构化程序设计的方法（1）自顶向下、逐步细化。（2）模块化。（3）结构化编码。12/17/202274§2程序设计思想4.2.1结构化程序设计思想196“自顶向下、逐步细化”方法“自顶向下、逐步细化”就是从一个大问题出发，往下逐步分解，由宏观到微观，由一般问题到具体细节实现等进行有序、有层次、有步骤的分析，最终在编写程序前，给出所有方法步骤的细节。例如：计算学院教师的平均工资。这个任务比较复杂，可分解为如下几点：（1）找出每个教师的收入；（2）计算共有多少教师；（3）计算工资总额；（4）计算平均工资。对于第（3）步又可再细分为：①找出一位教师档案；②读出工资数额；③累计求和；重复上述三步骤。对于①可再次进一步细分为：打开档案；找出正确记录；从磁盘读取数据。§2程序设计思想12/17/202275“自顶向下、逐步细化”方法“自顶向下、逐步细化”就是从一个模块化设计

结构化程序设计的另一个概念是模块化设计，把一个大的复杂的问题逐层分解为一系列小的简单的模块来进行处理，每个小模块只完成单一的具体任务。模块内部联系紧密，而与其他模块之间联系较弱，这样的模块称为独立性高的模块，实现“高内聚、低耦合”。模块化“功能分解”即按照问题的功能进行模块划分，把相近功能的任务放到一个模块中。

§2程序设计思想12/17/202276模块化设计 结构化程序设计的另一个概念是模块化设计，把一1)模块之间接口关系简单，每个模块完成独立的工作，易于被人理解，所编写出来的程序可读性和可理解性好；

2)各个模块功能单一，要修改某一个模块时只涉及到要修改的模块而不涉及到其他模块，不会出现修改程序时牵一发动全身的现象；3)人们可以单独验证、测试一个个模块，保证其正确性；4)可以利用现有模块，像搭积木一样进行开发新的程序。独立性高的模块有以下优点：§2程序设计思想12/17/2022771)模块之间接口关系简单，每个模块完成独立的工作，易于被模块之间是一种层次结构，上层模块对下层模块进行调用，下图所示是报表生成程序的层次结构，以柜形框表示模块，框中的模块名称表明模块的功能，提出顶层的模块“做什么”而不涉及“怎样做”，最下层模块功能十分具体，涉及“怎样做”的精确描述，易于编程。报表生成程序数据输入数据计算求和求平均求方差打印报表§2程序设计思想12/17/202278模块之间是一种层次结构，上层模块对下层模块进结构化编码通过顺序、分支、循环三种基本结构通过函数方式实现功能通过多程序（.c文件）实现项目1.三种基本控制结构：

顺序控制、选择控制、循环控制。2.模块化组织结构：按功能划分模块，每个模块易于理解且不可再分，用函数实现模块化组织结构。3.程序设计过程：自顶而下、逐步细化。结构化程序设计要点§2程序设计思想12/17/202279结构化编码通过顺序、分支、循环三种基本结构1.三种基本控结构化程序有三种基本结构顺序结构选择结构循环结构语句执行的顺序与程序书写的顺序一致条件成立，执行A；否则，执行B重复执行某组动作结构条件成立时，反复执行A；条件不成立，停止重复执行动作A，当某一条件成立时，停止C程序的基本结构12/17/202280结构化程序有三种基本结构顺序结构选择结构循环结构语句执行的顺main(){inta,b,c;a=5;b=6;c=a+b;printf(“%d”,c);}程序执行的顺序和语句书写的顺序一致有一个数据入口一个数据出口AB基本结构顺序结构12/17/202281main()程序执行的顺序和语有一个数据入口AB基本结构顺条件ABYN当条件满足时,执行语句A；否则,执行语句B有一个数据入口一个数据出口键盘输入一个整数,判断其正负例inta;aa>0if(a>0)printf(“a为正数”);elseprintf(“a为负数”);语句A语句B打印a的值选择结构12/17/202282条件ABYN当条件满足时,执行语有一个数据入口键盘输入一个整YN求1~100的自然数之和

X<=100x=1S=0语句若条件满足,重复执行语句内容；否则,退出循环条件一个数据入口一个数据出口s=s+x;x=x+1;语句S条件不满足,不执行任何语句循环结构

1.当型循环12/17/202283YN求1~100的自然数之和X<=100x=1语句若语句NY求1+2+3+~n<=1000的最大的n例:n=1,s=0;s=s+nn=n+1……S>1000n=1s=0语句不论条件是否满足,语句至少执行一次

2.直到型循环s=1+2+3+……n=?(s<1000)

12/17/202284语句NY求1+2+3+~n<=1000的最大的n例:n=13.结构化程序设计的特点1）以三种基本结构的组合进行程序的编写；2）程序的编写采用模块化结构；3）自顶向下，逐步求精；4）限制使用goto语句，不用或少用goto语句，通常只允许用它从一个循环中跳出而不允许从外部跳入一个循环；5）每一个结构只允许有一个入口和一个出口。各部分之间接口简单，逻辑清晰；6）采用结构化语言编写程序，程序结构清晰易于阅读和修改；7）采用良好的编程风格。§2程序设计思想12/17/2022853.结构化程序设计的特点1）以三种基本结构的组合进行4.程序设计步骤1.分析问题，建立数学模型。2.确定数据结构。3.确定算法，描述算法。4.编制程序，调试程序。5.运行程序，得到结果。程序设计要求：书写正确，结果正确§2程序设计思想12/17/2022864.程序设计步骤1.分析问题，建立数学模型。程序设计要求4.2.2面向对象的程序设计基本概念1.基本概念面向对象程序设计的本质是把数据与处理数据的过程当成一个整体——对象。类（CLASS）：定义了一类事物的抽象特点，包括事物的属性和它具有的行为（称为方法）。父类、子类

实例(Instance)对象(Object)：是类的实例，是某个类别的具体化的事物。方法（method）是一个类能做的事情，代表具体操作功能。

消息（Message）继承（Inheritance）多态性（Polymorphism）§2程序设计思想12/17/2022874.2.2面向对象的程序设计基本概念1.基本概念类（CL2.面向对象程序设计的优点稳定性好可重用性好与人类习惯的思维方法一致易于开发大型软件产品可维护性好§2程序设计思想12/17/2022882.面向对象程序设计的优点稳定性好§2程序设计思想目录§1程序设计与算法概述§2程序设计思想§3算法描述方法§4算法特性与评价方法§5本章小节

第4章算法12/17/202289目录§1程序设计与算法概述第4章算法12/14/2算法分类利用计算机解题，一般有两类算法：数值计算算法和非数值计算算法。数值计算是指求数值解的问题（如计算方程根，求最大公约数等），往往有现成的模型、计算方法和公式对应。非数值计算主要解决需要用分析推理、逻辑推导才能解决的问题。由于种类繁多、要求各异，只有一些典型的非数值计算方法（如排序、查找算法等），许多问题需要设计解决问题的专门算法。§3算法描述方法12/17/202290算法分类利用计算机解题，一般有两类算法：数值计算算法和非数值2.算法的描述自然语言传统流程图NS结构化流程图伪代码程序代码（最准确的描述）。§3算法描述方法12/17/2022912.算法的描述自然语言§3算法描述方法12/14/20§3算法描述方法2.算法的表示②传统流程图描述

下图表示程序流程图的基本符号，建议初学者养成编写程序前先画图的习惯，通过流程图使你的算法思想和实现步骤得以体现，便于检查、修改和交流。程序流程图基本符号12/17/202292§3算法描述方法2.算法的表示②传统流程图描述 下图表三种基本结构的流程图描述模块A模块BYesNo条件判断模块A模块B§3算法描述方法12/17/202293三种基本结构的流程图描述模块A模块BYesNo条件判断模块A三种基本结构的流程图描述模块A模块BYesNo条件判断模块A模块B模块A条件？No条件？模块ANo§3算法描述方法12/17/202294三种基本结构的流程图描述模块A模块BYesNo条件判断模块A②流程图

人们普遍采用程序流程图是因为它简单、直观。把执行的流程表达得一清二楚，易于理解。然而，它也有不少缺陷，程序流程图中的箭头十分灵活，使用不当会影响到程序结构的清晰。X1=(-b+)/2aX2=(-b-)/2a开始输入a,b,cS=b*b-4*a*cS>=0y打印X1，X2打印“无实根解”n结束方程ax２+bx+c＝0的求解算法§3算法描述方法12/17/202295②流程图 人们普遍采用程序流程图是因为它简开始s=0,a=0输入na=a+1s=s+aa<nYN输出s结束

用规定的一系列图形、流程线和文字说明算法中的基本操作和控制流程。scanf(“%d”,&n);printf(“%d”,s);While(a<n)流程图应用举例：例如计算:s=Σa;a=1~n§3算法描述方法12/17/202296开始输入na=a+1a<nYN输出s结束用规定的一3.NS结构化流程图 N-S图的基本形式模块1模块2模块3条件TF

模块A模块B

While

条件模块

模块

Until条件顺序分支循环1循环2§3算法描述方法12/17/2022973.NS结构化流程图 N-S图的基本形式模块1While

N-S图举例

输入系数a,b,cS=b*b-4*a*cS>=0

打印“无实根解”X1=(-b+)/2aX2=(-b–)/2a打印X1,X2FT方程ax２+bx+c＝0的求解§3算法描述方法12/17/202298N-S图举例【例4-2】用传统流程图和NS结构化流程图分别描述“求3个整数中的最大值”的算法。问题分析：求3个整数最大值方法很多，但都需要通过判断解决。具体步骤为：（1）输入3个整数；（2）通过判断比较，找出最大值；（3）输出最大值，然后结束。算法设计：本例的关键是如何比较找到最大值。方法很多，这里给出一种做法如下：（1）先设定一个变量max用于保存最大值；（2）把先输入的第一个数作为最大值放入max变量中；（3）把第二个输入的数与最大值量max进行比较，若比max中值大，则放入max中；（4）同样进行第三个数与max的比较，并保存最大值；（5）最后输出最大值。§3算法描述方法12/17/202299【例4-2】用传统流程图和NS结构化流程图分别描述“求3个整NoNo开始输入a,b,c3个数amaxbmaxcmaxb>maxc>max输出max结束输入a,b,camaxb>max?YesNobmax

c>max?YesNocmax输出max值§3算法描述方法12/17/2022100NoNo开始输入a,b,c3个数amaxbmaxc4．伪代码描述伪代码（Pseudocode）是用介于自然语言和计算机语言之间的文字和符号表示算法，即程序设计语言具有的关键字用英文表示，其它的可用汉字、英文、数字和公式等表示，便于书写和阅读即可。用此方法描述算法并无格式要求，只要简单、清晰、易懂。【例4-3】用伪代码描述例4-2问题的算法。开始申请4个变量a,b,c,max，其中max用于存放最大值；先后从键盘输入3个整数给变量a,b,c；amax当b≤max时，继续进行比较，否则执行bmax继续判断：当c>max时，执行cmax输出max的值结束§3算法描述方法12/17/20221014．伪代码描述伪代码（Pseudocode）是用介于自然语5．用计算机语言描述用计算机语言描述算法，应该是上述步骤完成后的最后一步，也是最精确的一步。这一步的描述要求必须按照程序设计语言的语法规则编写规范的程序代码，只有这样才能上机调试和运行。例4-2问题的C语言程序代码描述如下：/*求3个整数中的最大值*/#include<stdio.h>intmain(){inta,b,c,max;scanf(“%d,%d,%d”,&a,&b,&c);max=a;if(b>max)max=b;if(c>max)max=c;printf(“max=%d\n”,max);return0;}NoNo开始输入a,b,c3个数amaxbmaxcmaxb>maxc>max输出max结束§3算法描述方法12/17/20221025．用计算机语言描述用计算机语言描述算法，应该是上述步骤完成算法举例

程序设计的关键是算法设计，有了算法，再用计算机语言去实现算法，就容易了。例1：计算1+2+3+…+100之和。算法步骤分析：S1:累加器变量sum赋初值0，即sum=0S2:计数器变量i赋初值1，即i=1S3:使累加器变量值sum加计数器变量值i,结果仍放在sum中,即sum=sum+i,此时sum值为

sum=sum+i=0+1=1S4:使计数器变量i加1,结果仍放在i中,即i=i+1,此时i值为

i=i+1=1+1=2依此类推……§3算法描述方法12/17/2022103算法举例程序设计的关键是算法设计，有了算法，再程序流程图和N-S图如下图所示

图1累加运算程序流程图开始

sum=0i=0sum=sum+ii=i+1i<=100打印NY图2累加运算N-S图

§3算法描述方法12/17/2022104程序流程图和N-S图如下图所示C语言程序算法如下

main(){inti=1,sum=0;/*定义变量及其数据类型*/

while(i<=100)

/*循环控制结构*/{sum+=i; i=i+1;}/*循环体结束*/printf(“sum=%d\n”,sum);/*输出累加结果*/}

程序算法不是唯一的，这个问题还有其它的算法。§3算法描述方法12/17/2022105C语言程序算法如下main()§3算法以此类推可以很容易表示出其它问题的算法例2：计算下式之和的算法，当分母大于100时程序结束，输出计算结果。程序算法如下。§3算法描述方法12/17/2022106以此类推可以很容易表示出其它问题的算法例2：计算下式例2算法的N-S图如下所示§3算法描述方法12/17/2022107例2算法的N-S图如下所示§3算法描述方法12/14/附加知识：PAD图 PAD图的基本符号S1S2S3While条件SUntil条件S顺序分支循环S1S2条件T§3算法描述方法12/17/2022108附加知识：PAD图 PAD图的基本符号S1S2S3WhiPAD图 方程ax２+bx+c＝0的求解输入系数a,b,cS=b*b-4*a*cS>=0打印X1,X2打印“无实根解”

X2=(-b–)/2aX1=(-b+)/2a§3算法描述方法12/17/2022109PAD图 方程ax２+bx+c＝0的求解输入系数a,b,目录§1程序设计与算法概述§2程序设计思想§3算法描述方法§4算法特性与评价方法§5本章小节

第4章算法12/17/2022110目录§1程序设计与算法概述第4章算法12/14/24.4.1算法的特性

1.有穷性：算法包含的操作步骤是有限的，每一步都应在合理的时间内完成。2.确定性：算法中的每一步应该是确定的，而不应当是含糊的、模棱两可的和歧义的。3.有效性（可行性）：算法中的每一步应该能有效执行，且能得到确定的结果。4.有零个或多个输入：输入是计算机在执行算法时，需要从外界得到必要的信息。5.有一到多个输出：算法的目的是求得问题的解（计算结果），而解只有输出才有意义。§4算法特性与评价方法12/17/20221114.4.1算法的特性

1.有穷性：算法包含的操作步骤是有4.4.2算法分析与评价

1．正确性：算法应当满足具体问题的需求，设计和选择算法应该正确反映这种需求