C语言课件王曙燕chp3算法和基本程序设计.ppt

,第三章算法和基本程序设计,C语言程序设计第三章算法和基本程序设计,3.1算法,概念：算法是解决问题的策略、规则和方法。,数据结构+算法=程序,C语言程序设计第三章算法和基本程序设计,特性有穷性:一个算法必须在执行有限个操作步骤后终止；确定性:算法中每一步的含义必须是确切的，不可出现任何二义性；可行性:算法中的每一步操作都应该能有效执行。例如，一个数被0除的操作就是无效的，应当避免这种操作。有输入:输入是指在算法开始之前所需要的初始数据。这些输入的多少取决于特定的问题。输出:在一个完整的算法中至少会有一个输出。,评价标准正确性:合法输入有正确输出可读性：易懂健壮性：容错高效率和低存储量需求,程序的灵魂算法,程序及算法,用程序设计语言来描述问题的求解过程，以及对其中参与运算的数据进行合理地组织和安排，就叫做程序设计。,分析问题确定算法编写程序运行调试总结过程,基本步骤,程序设计一般步骤,(1)分析问题，建立数学模型A.确定问题是什么，解决问题的步骤是什么;B.针对问题，找出已知的数据和条件，确定所需的输入、处理及输出对象;C.归纳解题过程为一系列的数学表达式，建立各种量之间的关系.(即建立起解决问题的数学模型),程序及算法,程序设计一般步骤,(2)确定数据结构和算法A.根据建立的数学模型，对指定的输入数据和预期的输出结果，确定存放数据的数据结构;B.针对所建立的数学模型和确定的数据结构，选择合适的算法加以实现;,这里所说的“算法”指解决某一问题的方法和步骤，而不仅仅是指计算。,程序及算法,程序设计一般步骤,(3)编制程序根据确定的数据结构和算法，用程序语言严格地描述解决方案。（即编写程序代码）,(4)调试程序在计算机上用实际的输入数据对程序进行调试，分析所得到的运行结果，进行程序的测试和调整，直至获得预期的结果。,程序及算法,程序及算法,算法的一般定义,指解决问题的方法和有限的步骤。,计算机算法,数值运算（对问题求数值解，例如对微分方程求解、对函数的定积分求解、对高次方程求解等）,非数值运算（如资料检索、事务管理、数据处理等）,是针对提出的可行方案确定解决问题、完成任务的每一个细节步骤。,程序及算法,问题：有黑和蓝两个墨水瓶，但却错把黑墨水装在了蓝墨水瓶子里，而蓝墨水错装在黑墨水瓶子里，要求将其互换。,例1-1,算法分析：这是一个非数值运算问题。因为两个瓶子的墨水不能直接交换，所以，解决这一问题的关键是需要引入第三个墨水瓶。,程序及算法,设第三个墨水瓶为白色，其交换步骤如下：将黑瓶中的蓝墨水装入白瓶中；将蓝瓶中的黑墨水装入黑瓶中；将白瓶中的蓝墨水装入蓝瓶中；交换结束。,一般步骤,例1-2,问题：给定两个正整数m和n（mn），求它们的最大公约数。,算法分析：一个数值运算问题，它有成熟的算法，在我国古代的算书九章一书中曾记载了这个算法。求最大公约数一般用辗转相除法（也称欧几里德算法）求解。,程序及算法,辗转相除法,设m=35，n=15，r表示余数。求法如下：(1)35/15（m/n）商2余5(r=5);(2)以n(=15)作m，以r(=5)作n,继续相除；15/5（m/n）商3余数为0(r=0).(3)当余数(r)为0时，此时，n即为两数的最大公约数。35和15的最大公约数为5。,程序及算法,两个正整数分别存放到m和n中；求余数：计算m除以n，将所得余数存到变量r中；判断r是否为0：若r为0,则执行第步，否则执行第步；更新被除数和余数：将n值存放到m中，将r的值存放到n中，并转第步继续循环执行；输出n的当前值，算法结束。,算法描述,程序及算法,C语言程序设计第三章算法和基本程序设计,算法的表示可用自然语言、数学方法、某种计算机语言描述规范的方法：流程图、结构图、伪代码、PAD图,流程图,C语言程序设计第三章算法和基本程序设计,例1：求三个整数的和,C语言程序设计第三章算法和基本程序设计,例2：求三个数中最小的那个数,main()floata,b,c,min;scanf(“%f,%f,%fn”,C语言程序设计第三章算法和基本程序设计,N-S结构流程图：完全去掉流程线，由一些基本框组成一个大的框基本元素框,C语言程序设计第三章算法和基本程序设计,例1：求三个整数的和,流程图,N-S结构流程图,C语言程序设计第三章算法和基本程序设计,例2：求三个数中最小的那个数,流程图,N-S结构流程图,背景软件危机1968年，荷兰学者E.W.Dijkstra提出GOTO语句的三大危害采用结构化程序设计方法应遵循的原则自顶向下模块化功能模块模块的划分模块间的接口限制使用GOTO语句,3.2结构化程序设计方法,C语言程序设计第三章算法和基本程序设计,1.从程序流程控制的角度，分为三种基本结构：顺序结构、选择结构、循环结构2.这三种基本结构可以组成所有的各种复杂程序3.结构化程序是只由三种基本结构构成的程序,3.3程序的基本结构,C语言程序设计第三章算法和基本程序设计,顺序结构由一系列顺序执行的操作组成，是一种线性结构；,C语言程序设计第三章算法和基本程序设计,选择结构,C语言程序设计第三章算法和基本程序设计,二分支选择结构,多分支选择结构,循环结构,C语言程序设计第三章算法和基本程序设计,当型循环,直到型循环,C语言中提供了3种循环结构：while、for、do-while,三种基本结构总结：共同特点：单入口、单出口三种结构之间可以是平行关系，也可以互相嵌套，通过结构之间的复合形成复杂的关系,C语言程序设计第三章算法和基本程序设计,C语言语句分为五类：表达式语句、函数调用语句、复合语句和空语句、控制语句。表达式语句注意表达式和表达式语句的区别,3.4顺序结构程序设计（最基本、最简单）,C语言程序设计第三章算法和基本程序设计,函数调用语句,#includefloataverage(floatx,floaty,floatz)/*定义函数average()*/floataver;/*变量aver为单精度实型*/aver=(x+y+z)/3;return(aver);/*返回aver值*/main()floata,b,c,ave;a=6.5;b=4.2;c=25.3;ave=average(a,b,c);/*调用自定义函数average()*/printf(“average=%f”,ave);,复合语句：由括起的若干个语句,空语句：直接由分号（；）组成,控制语句：根据控制条件决定程序的执行流程判断语句、循环语句、转移语句,3.6C程序的上机步骤,C语言程序设计第三章算法和基本程序设计,C源程序.c文件,目标程序.OBJ文件,可执行程序.exe文件,对源文件进行语法和逻辑结构检查,将目标程序、库函数或其他目标程序连接成一个可执行文件,3.5数据的输入和输出,C语言中没有用于完成I/O操作的关键字，而是采用I/O操作函数；因此需调用库函数,C语言程序设计第三章算法和基本程序设计,#include或#include“stdio.h”,C语言程序设计第三章算法和基本程序设计,字符数据的输入与输出单个字符：putchar()、getchar()、getch()和getche()字符串：puts()、gets(),字符输出函数putchar()函数调用形式：putchar(ch);,字符常量或字符变量,字符输入函数：getchar()、getch()、getche()getchar()该函数的输入一直到“回车”才结束从键盘读入一个字符，并回显getch()不回显，不“回车”，常用于密码输入或菜单选择getche()回显，不“回车”,#include“stdio.h”main()chara;a=getchar();,C语言程序设计第三章算法和基本程序设计,字符串输入/输出函数输入函数调用形式：gets(字符串变量名)；用回车作为输入结束输出函数调用形式：puts(字符串数据)；将字符串数据显示在屏幕上并换行,#includemain()charstr80;gets(str);puts(str);,当输入为“Cprogram”，则输出为：Cprogram,C语言程序设计第三章算法和基本程序设计,格式输入与输出格式输入与输出函数：scanf()、printf();格式输出函数调用形式：printf(“格式控制字符串”，输出项表)；,各输出项的输出格式,要输出的项,注意：格式控制字符串和各输出项的数量、顺序、类型要一致,inta=567;printf(“%d”,a);,inta=255;printf(“%x”,a);,inta=65;printf(“%o”,a);,inta=567;printf(“%u”,a);,chara=65;printf(“%c”,a);,printf(“%s”,“ABC”);,floata=567.789;printf(“%e”,a);,floata=567.789;printf(“%f”,a);,floata=567.789;printf(“%g”,a);,printf(“%”);,567,ff,101,567,A,ABC,5.677890e+02,567.789000,567.789,%,例inta=3,b=4;printf(“%d%dn”,a,b);printf(“a=%d,b=%dn”,a,b);输出结果:34a=3,b=4,C语言程序设计第三章算法和基本程序设计,附加格式说明符,C语言程序设计第三章算法和基本程序设计,格式输入函数函数的调用形式：scanf（“格式控制字符串”，输入项地址表）；功能：按指定格式从键盘读入数据，存入地址表指定的存储单元中,并按回车键结束取地址运算符&,变量的地址或字符串的首地址,例scanf(“%d”,输入：10则a=10,例scanf(“a=%d”,输入：a=10则a=10,C语言程序设计第三章算法和基本程序设计,附加格式说明符（修饰符）,例scanf(“%4d%2d%2d”,输入19991015则1999yy,10mm,15dd,例scanf(“%2d%*3d%2d”,输入1234567则12a,67b,例scanf(“%3c%2c”,输入abcde则ac1,dc2,问题：试写出判断a,b,c是否构成三角形的C语句。分析：想一想在数学中我们如何判断“三条边是否构