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()float a,b,c,min;scanf(“%f,%f,%fn”,C语言程序设计 第三章 算法和基本程序设计,N-S结构流程图:完全去掉流程线,由一些基本框组成一个大的框 基本元素框,C语言程序设计 第三章 算法和基本程序设计,例1:求三个整数的和,流程图,N-S结构流程图,C语言程序设计 第三章 算法和基本程序设计,例2:求三个数中最小的那个数,流程图,N-S结构流程图,背景软件危机 1968年,荷兰学者提出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语言程序设计 第三章 算法和基本程序设计,函数调用语句,#include float average(float x,float y,float z)/*定义函数average()*/float aver;/*变量aver为单精度实型*/aver=(x+y+z)/3;return(aver);/*返回aver值*/main()float a,b,c,ave;a=6.5;b=4.2;c=25.3;ave=average(a,b,c);/*调用自定义函数average()*/printf(“average=%f”,ave);,复合语句:由 括起的若干个语句,空语句:直接由分号(;)组成,控制语句:根据控制条件决定程序的执行流程判断语句、循环语句、转移语句,3.6 C程序的上机步骤,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()char a;a=getchar();,C语言程序设计 第三章 算法和基本程序设计,字符串输入/输出函数输入 函数调用形式:gets(字符串变量名);用回车作为输入结束输出 函数调用形式:puts(字符串数据);将字符串数据显示在屏幕上并换行,#include main()char str80;gets(str);puts(str);,当输入为“C program”,则输出为:C program,C语言程序设计 第三章 算法和基本程序设计,格式输入与输出格式输入与输出函数:scanf()、printf();格式输出函数 调用形式:printf(“格式控制字符串”,输出项表);,各输出项的输出格式,要输出的项,注意:格式控制字符串和各输出项的数量、顺序、类型要一致,int a=567;printf(“%d”,a);,int a=255;printf(“%x”,a);,int a=65;printf(“%o”,a);,int a=567;printf(“%u”,a);,char a=65;printf(“%c”,a);,printf(“%s”,“ABC”);,float a=567.789;printf(“%e”,a);,float a=567.789;printf(“%f”,a);,float a=567.789;printf(“%g”,a);,printf(“%”);,567,ff,101,567,A,ABC,5.677890e+02,567.789000,567.789,%,例 int a=3,b=4;printf(“%d%dn”,a,b);printf(“a=%d,b=%dn”,a,b);输出结果:3 4 a=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,10 mm,15 dd,例 scanf(“%2d%*3d%2d”,输入 1234567 则12a,67b,例 scanf(“%3c%2c”,输入 abcde 则ac1,d c2,问题:试写出判断a,b,c是否构成三角形 的C语句。分析:想一想在数学中我们如何判断“三 条边是否构成三角形”的问题。(如:任意两边之和大于第三边。),举例 1,程序及算法,语句描述,如果a+bc、b+ca、a+cb 三个条件同时成立,则构成三角形;否则,不是。=if(a+bc,程序及算法,将a、b、c值输入到计算机中;判断a+bc、b+ca、a+cb三个条件 是否成立?同时成立执行第步,否则执行第步;输出“是三角形”的结论;输出“不是三角形”的结论;算法结束。,算 法,程序及算法,流程图,程序及算法,试自己写出程序,并上机调试该程序。,程序及算法,