C语言第二章：算法

1、第章 基本算法,本章要点: 算法的特征 算法的表示方法 程序设计的基本算法 掌握程序的基本结构,.1 程序与算法,程序包括: (1)对数据的描述 数据结构 (2)对数据处理的描述 算法 算法(algorithm)是对特定问题求解步骤的一种描述。 可将程序总结为： 程序=算法+数据结构+程序设计方法+语言工具和环境,C语言算法的主要特点如下： 1.有穷性 一个算法应该包含有限的操作步骤，而不能是无限的。 2.确定性 算法中的每一个步骤应当是确定的，而不应当是含糊的（多义性），应是十分明确无误的。 3.有0个或多个输入。 4.有一个或多个输出。 5.有效性 算法中的每一个步骤都应当有效的执行，并得

2、到确定的结果。,.2 算法的特征,3.3 算法的表示方法,(1) 自然语言描述法 (2) 传统的流程图表示 常用符号有: (3) N-S流程图表示 (4) 伪代码表示算法 (5) 计算机语言表示算法,一、顺序结构,先执行A操作，再执行B操作，两者是顺序执行关系。,N-S结构流程图,结构化程序设计的三种基本机构,二、选择结构,当P条件为真时，执行A模块，否则执行B模块。,三、循环结构,当P条件成立时，反复执行A,直到P为假。,1.当型循环结构,2.直到型循环结构,先执行A操作，再判断P是否为假，若P为假，再执行A，直到P为真为止。,(a),算法举例1：对一个大于2的正整数，判断它是不是一个素数。

3、 方法：将 n (其中n 2) 作为被除数， 将2 到（n-1) 各个整数轮流作为除数，如果都不能被整除，则n为素数。 算法表示如下： S1：输入n的值 S2：2 i ( i 作为除数） S3: n 被 i 除，得余数 r S4: 如果 r 等于 0 ， 表示 n 能 被 i 整除，则打印 n “不是素数”，算法结束；否则执行S5 S5：i+1 i S6: 如果 i n-1, 返回S3；否则，打印 n “是素数”，算法结束。,算法举例2：求 1-1/2 + 1/3 1/4 + 1/99 1/100。 S1: 1 sign S2: 1 sum S3: 2 deno S4: (-1)*sign s

4、ign S5: sign*(1/deno) term S6: sum+term sum S7: deno+1 deno S8: 若deno 100 返回S4；否则算法结束。,算法举例3 ： 用伪代码表示算法：用介于自然语言和计算机语言之间的文字和符号来描述算法,BEGIN 1 =i while(i 50) input ni和gi i+1=i 1 =i while(i 50) if (gi =80) print ni和gi i+1=i END,算法举例4: 用计算机语言表示算法,求 1-1/2 + 1/3 1/4 + 1/99 1/100。 S1: 1 s S2: 1 sum S3: 2 d S

5、4: (-1)*s s S5: s*(1/d) t S6: sum+t sum S7: d+1 d S8: 若d 100 返回S4；否则算法结束。,main() int s=1; float d=2.0 , sum=1.0, t; while (d0,#include main() float a,b,c,disc,x1,x2,p,q; scanf(%f%f%f, ,例3.4 输入一个三位数，依次输出该数的符号和百号，十位，个位数字 。,#include #include main() char c1,c2,c3,c4; int x; scanf(“%d”, ,运行情况: -345 - 3 4

6、 5,3.7 选择结构,本节要点 关系运算符与关系表达式 逻辑运算符与逻辑表达式 条件运算符与条件表达式 if语句 switch语句 本章难点 if语句的嵌套 switch语句的使用,3.7.1 关系运算符和关系表达式,6 种关系运算符： （小于） （小于或等于） （大于） （大于或等于） （等于） ！ （不等于）,3.7.1.1 关系运算符,结合性：自左向右,关系运算符的优先次序,与其它运算符优先级的比较：,例如： c=da+b,等效于：c=(d(a+b),1. 什么是关系表达式？,3.7.1.2 关系表达式,如：(ab)(by 、s+fd,2. 关系表达式的值,运算结果逻辑值 1“真” ，

7、0“假”,如： 设 a=3, b=2, c=1 求下面关系表达式 的值：,cb (a-b) = = 1 b+ca+b,2. 双分子语句 if (表达式) 语句1 else 语句2,执行过程： 当表达式的值为“真” （非零）时，执行语句1， 否则，执行语句2。,如: if (xy) z=x ; else z=y ;,3. 多分子语句 if (表达式1) 语句1 else if(表达式2) 语句2 else if(表达式3) 语句3 : else if(表达式m) 语句m else 语句n,如：if (grade=85) level=A; else if (grade=70) level=B; e

8、lse if (grade=60) level=C; else level=D;,if 语句说明：, if后面的表达式一般为逻辑表达式或关系表 达式，也可以是任意数值类型表达式。,该语句是合法的：if(3) printf(“ok!”);, if 语句中的“语句”为一个简单语句或复合语句。,如：下面程序段是否有错？,if (x=0) printf(“X is positive.”); x+; else printf(“X is negative.”);,if (x=0) printf(“X is positive.”); x+; else printf(“X is negative.”);,4.

9、 if 语句的嵌套,在 if 语句中又包含一个或多个if 语句称为 if 语句的嵌套。,一般形式：,if (条件1） if (条件2)语句1 else 语句2 else if (条件3)语句3 else 语句4,内嵌if,内嵌if,如： if(x0) if(y0) printf(x0,y0); else printf(“x0，y0) printf(“x0); else printf(“x=0, y6) if (n12) printf(“6n12”); else printf(“n6) if (n12) printf(“6nb) ? a : b,目的简化 if 语句。,条件运算符的优先级：,算数

10、运算符=关系运算符=逻辑运算符(除！),赋值运算符c ,此语句的本意是： if(a0) printf(“abs(a)=%dn”,a); else printf(“abs(a)=%dn”,(-1)*a);,可以改写为： printf(“abs(a)=%dn”,a0?a:(-1)*a);,例：把输入字符中的小写字符转换成大写并输出 。,#include main() char ch; scanf(%c, ,main() int a,b,c,t,max; scanf(%d%d%d, ,3.7.6 switch 语句,一般形式：,switch（表达式） case 常量表达式1：语句序列1 case 常

11、量表达式2：语句序列2 break; ： case 常量表达式n：语句序列n break; default ：语句序列n+1 ,此处break用于退出switch语句,break;,先计算表达式的值，并逐个与其后的常量表达式值相比较； 当表达式的值与某个常量表达式的值相等时，即执行其后的语句； 然后不再进行判断，继续执行后面所有case后的语句； 如表达式的值与所有case后的常量表达式均不相同时，则执行default后的语句。,switch语句的执行过程：,执行过程：,例如： switch(grade) case A : printf(“85100 ”); case B : printf(“

12、7084 ”); case C: printf(“6069 ”); case D :printf(“60 ”); default : printf(“error ”); ,若grade= A，输出结果是什么？,85100 7084 6069 60 error,用break语句处理后的程序段：,switch(grade) case A : printf(“85100 ”); break; case B : printf(“7084 ”); break; case C : printf(“6069 ”); break; case D : printf(“60 ”); break; default

13、: printf(“error ”); ,若grade= A，输出结果又是什么？,85100,完整程序 :,main() char grade; printf(“Input grade(A,B,C,D):”); scanf(“%c”, ,流程图为：,grade,输出 “85100”,输出 “60”,输出 “60-69”,输出 “error”,输出 “70-84”,使用switch语句时还应注意以下几点：,1.在case后的各常量表达式的值不能相同，否则会出现错误。 2.在case后，允许有多个语句，可以不用 括起来。 3.各case和default子句的先后顺序可以变动，而不会影响程序执行结果

14、。 4.default子句可以省略不用。 5.若判断的是一个区间，要将区间转换成单个值。,3.7.7 标号语句和goto,标号语句一般形式：,语句标号：语句 例如：end:,该标志符就成了语句标号，但标号不能用数值表示，例如：12：，3：，5：都是错误的。标号可以与变量同名。,goto语句一般形式：,goto 语句标号； goto语句的作用是使程序改变原来的执行顺序，而跳到指定的语句上执行。 例如：goto sd; sd:printf(“this is a cat!n”);,说明：, goto语句是一种非结构化语句，结构化程序设计方法不提倡使用goto语句，因为滥用goto语句将使程序流程无规

15、律，可读性差。但也不是绝对禁止使用，只有在能够大大提高程序效率时才使用。,且记：不要从循环体外跳到循环体内！,#include main() int i,sum=0; i=1; loop: if(i=100) sum=sum+ i; i+; goto loop; printf(%d,sum); ,sum=0+1 sum=1+2=3 sum=3+3=6 sum=6+4 sum=4950+100=5050,一、例 用if 语句和goto语句构成循环求 1+2+3+100。,二、用goto语句和 if 语句构成循环,计算10！并输出结果。,main() int i=1, sum=1; loop: i

16、f (i=10) sum=sum*i; i+; goto loop; printf(“10!=%dn”,sum); ,运行结果：10!=24320,本应是：10!=3628800,main() int i=1; long sum=1; loop: if (i=10) sum=sum*i; i+; goto loop; printf(“10!=%ldn”,sum); ,3.7.8 选择结构程序设计举例,例 写程序，判断某一年是否闰年。,设：leap代表闰年信息，leap=1闰年，leap=0 非闰年,不能被4整除,非闰年,被4整除，但不能被100整除,闰年,被100整除，又能被400整除,闰年,

17、其他，非闰年,非闰年,main( ) int year, leap=0; scanf(“%d”, ,main( ) int year, leap=0; scanf(“%d”, ,例 已知基本运费、货重，以及路程(s)和折扣的关系标准如下：,s250km 没有折扣 250s500 %2折扣 500s1000 5%折扣 1000s2000 8%折扣 2000s3000 10%折扣 3000s 15%折扣,算法：先按距离的250倍数进行分类，求每类的折 扣，再按公式计算。,编程序，计算运费。 设基本运费p、货物重量w、距离s和折扣d。则总运费的计算公式为： f=p*w*s*(1-d),250 500

18、 1000 2000 3000,s,0,16 14 12 10 8 6 4 2,折扣的变化点都是250的倍数 . c=s/250 代表250的倍数。,1 2 4 8 12 c,总运费的计算公式为： f=p*w*s*(1-d),程序为： main( ) int c,s; float p, w, d , f ; scanf(“%f , %f , %d”, /*750s1000*/ case 4: /*1000s1250*/ case 5: /*1250s1500*/,case 6: /*1500s1750*/ case7: d=8 ; break ; /*1750s2000*/ case8: /*2000s2250*/ case9: /*2250s2500*/ case10: /*2500s2750*/ case11: d=10 ; break; /*2750s=大于等于)，= =(等于)，!=(不等于)。用关系运算符将两个表达式连接起来，进行关系运算的式子称为关系表达式。 (2) C语言提供的逻辑运算符有3种：&(逻辑与)，|(逻辑或)，!(逻辑非)。用逻辑运算符将一个或多个表达式连接起来，进行逻辑运算的式子称为逻辑表达式。 (3) i