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

第三章 算法和基本程序设计算法结构化程序设计的方法程序的基本结构顺序结构程序设计数据的输入与输出C程序的上机步骤 C C语言程序设计语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计§3.1 算法«概念：算法是解决问题的策略、规则和方法数据结构数据结构+ +算法算法= =程序程序 C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计«特性v有穷性:一个算法必须在执行有限个操作步骤后终止；v确定性:算法中每一步的含义必须是确切的，不可出现任何二义性； v可行性:算法中的每一步操作都应该能有效执行例如，一个数被0除的操作就是无效的，应当避免这种操作 v有输入:输入是指在算法开始之前所需要的初始数据这些输入的多少取决于特定的问题v输出:在一个完整的算法中至少会有一个输出«评价标准v正确性:合法输入有正确输出v可读性：易懂v健壮性：容错v高效率和低存储量需求程序的灵魂——算法程序及算法 用程序设计语言来描述问题的求解过程，以及对其中参与运算的数据进行合理地组织和安排，就叫做程序设计程序设计程序设计程序设计。

•分析问题•确定算法•编写程序•运行调试•总结过程基本步骤程序设计一般步骤 (1)分析分析问题问题，，建立建立数学模型数学模型 A.确定确定问题问题是什么是什么，，解决问题的步骤解决问题的步骤是什么是什么; B.针对问题，针对问题，找出找出已知的已知的数据和条件数据和条件，，确定确定所所 需的需的输入、处理及输出对象输入、处理及输出对象; ; C.归纳归纳解题过程解题过程为一系列的数学表达式为一系列的数学表达式，， 建立建立各种量之间的关系各种量之间的关系. (即即建立起建立起解决问题的数学模型解决问题的数学模型) 程序及算法程序设计一般步骤 (2)确定数据结构和算法 A.根据建立的数学模型，对指定的输入数据 和预期的输出结果，确定存放数据的数据 结构 ; B.针对所建立的数学模型和确定的数据结构， 选择合适的算法加以实现 ; 这里所说的“算法”指解决某一问题 的方法和步骤，而不仅仅是指"计算" 程序及算法程序设计一般步骤 (3)编制程序 根据确定的数据结构和算法，用程序语言严格地描述解决方案 （即编写程序代码） (4)调试程序 在计算机上用实际的输入数据对程序进行调试，分析所得到的运行结果，进行程序的测试和调整，直至获得预期的结果。

程序及算法程序及算法算法的一般定义 指解决问题的方法和有限的步骤计算机 算法数值运算 （对问题求数值解，例如对微分 方程求解、对函数的定积分求 解、对高次方程求解等 ）非数值运算 （如资料检索、事务管理、数据 处理等）是针对是针对提出的可行提出的可行方案确定解决方案确定解决问题、完成任务问题、完成任务的每一个细节的每一个细节步骤程序及算法问题：有黑和蓝两个墨水瓶，但却错把黑 墨水装在了蓝墨水瓶子里，而蓝墨水 错装在黑墨水瓶子里，要求将其互换 例1-1 算法分析：这是一个非数值运算 问题因为两个瓶子的墨水不 能直接交换，所以，解决这一 问题的关键是需要引入第三个 墨水瓶程序及算法 设第三个墨水瓶为白色，其交换步骤如下： 　　① 将黑瓶中的蓝墨水装入白瓶中；　　② 将蓝瓶中的黑墨水装入黑瓶中；　　③ 将白瓶中的蓝墨水装入蓝瓶中； 　　④ 交换结束 一般步骤 例1-2 问题：给定两个正整数m和n（m≥n），求它们的最大公约数 算法分析：一个数值运算问题， 它有成熟的算法，在我国古代的《算书九章》一书中曾记载了这个 算法。

求最大公约数一般用辗转相除法（也称欧几里德算法）求解 程序及算法辗转相除法 设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图v流程图 C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计例1：求三个整数的和 C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计例2：求三个数中最小的那个数main( ){ float a,b,c,min; scanf(“%f,%f,%f\n”,&a,&b,&c); if (ac) min=c; printf(“min=%f\n”,min);} C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计vN-S结构流程图： 完全去掉流程线，由一些基本框组成一个大的框 基本元素框 C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计例1：求三个整数的和流程图N-S结构流程图 C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计例2：求三个数中最小的那个数流程图N-S结构流程图«背景软件危机 1968年，荷兰学者E.W.Dijkstra提出GOTO语句的三大危害★采用结构化程序设计方法应遵循的原则v自顶向下v模块化 功能模块 模块的划分 模块间的接口 v限制使用GOTO语句§3.2 结构化程序设计方法 C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计1.从程序流程控制的角度，分为三种基本结构： 顺序结构、选择结构、循环结构顺序结构、选择结构、循环结构2.这三种基本结构可以组成所有的各种复杂程序3.结构化程序是只由三种基本结构构成的程序§3.3 程序的基本结构 C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计«顺序结构 由一系列顺序执行的操作组成，是一种线性结构； C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计ABAB流程图N-S图«选择结构 C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计v 二分支选择结构条件程序模块A程序模块B成立不成立条件程序模块B程序模块A成立不成立v多分支选择结构kA1A2AiAnk=k2k=k1k=knk=ki......«循环结构 C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计v当型循环v直到型循环不成立条件条件程序模块成立当条件成立条件成立时执行程序模块程序模块直到条件不成立条件不成立时为止程序模块条件条件不成立成立C语言中提供了3种循环结构：while、 for 、do-while«三种基本结构总结：v共同特点：单入口、单出口v三种结构之间可以是平行关系，也可以互相嵌套，通过结构之间的复合形成复杂的关系 C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计C语言语句分为五类：表达式语句、函数调用语句、复合语句和空语句、控制语句。

★表达式语句 注意注意表达式和表达式语句的区别§3.4 顺序结构程序设计（最基本、最简单） C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计有无分号出现位置★函数调用语句#include float average(float x,float y,float z) /* 定义函数定义函数average()average() */{ float aver; /*/*变量变量averaver为单精度实型为单精度实型* */ / aver=(x+y+z)/3; return(aver); /*/*返回返回averaver值值* */ / }main(){ float a,b,c,ave; a=6.5; b=4.2; c=25.3; ave=average(a,b,c); /*/*调用自定义函数调用自定义函数average()*/average()*/ printf(“average=%f”,ave);}★复合语句：由{ }括起的若干个语句★空语句：直接由分号（；）组成★控制语句：根据控制条件决定程序的执行流程判断语句、循环语句、转移语句§3.6 C 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()v字符输出函数putchar() 函数调用形式： putchar(ch);字符常量或字符变量v字符输入函数：getchar()、getch()、getche()lgetchar() 该函数的输入一直到“回车”才结束 从键盘读入一个字符，并回显lgetch() 不回显，不“回车”，常用于密码输入或菜单选择lgetche() 回显，不“回车”#include “stdio.h”main( ){ char a; a=getchar();} C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计v字符串输入/输出函数l输入 函数调用形式：gets(字符串变量名)； 用回车作为输入结束l输出 函数调用形式：puts(字符串数据)； 将字符串数据显示在屏幕上并换行#include main( ){ char str[80]; gets(str); puts(str);}当输入为“C program”，则输出为： C program C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计«格式输入与输出格式输入与输出函数：scanf()、printf();v格式输出函数 调用形式：printf(“格式控制字符串”，输出项表)；各输出项的输出格式要输出的项注意注意：格式控制字符串和各输出项的数量、顺序、类型要一致d,ix,Xoucse,Efg%%格式字符：十六进制无符号整数不带符号十进制整数十进制整数指数形式浮点小数单一字符字符串八进制无符号整数小数形式浮点小数e和f中较短一种百分号本身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(“%%”);567ff101567AABC5.677890e+02567.789000567.789%例 int a=3,b=4; printf(“%d %d\n”,a,b); printf(“a=%d , b=%d\n”,a,b);输出结果: 3 4 a=3, b=4 C语言程序设计 第第三章三章 算法和基本程序设计算法和基本程序设计l附加格式说明符 .n对实数,指定小数点后位数(四舍五入)对字符串,指定实际输出位数修饰符功 能m输出数据域宽,数据长度

分析：想一想在数学中我们如何判断“三 条边是否构成三角形”的问题 （如：任意两边之和大于第三边举例 1 程序及算法语句描述 如果a+b>c 、 b+c>a 、 a+c>b 三个条件同时成立，则构成三角形； 否则，不是 => if (a+b>c && b+c>a && a+c>b ) printf(“triangle”) ; else printf(“not triangle”) ;程序及算法 ① 将a、b、c值输入到计算机中；　② 判断a+b>c 、b+c>a、a+c>b三个条件 是否成立？同时成立执行第③步， 否则执行第④步；　③ 输出“是三角形”的结论；　④ 输出“不是三角形”的结论； ⑤ 算法结束 算 法程序及算法流程图结 束输出输出triangletriangle输出输出 NotNot triangle trianglea+b>c && b+c>a && a+c>byesnot开 始输入a、b、c程序及算法 试自己写出程序，并上机调试该程序程序及算法。