C语言第二章：算法

第３章基本算法本章要点:算法的特征算法的表示方法程序设计的基本算法掌握程序的基本结构３.1程序与算法程序包括:(1)对数据的描述数据结构(2)对数据处理的描述算法算法(algorithm)是对特定问题求解步骤的一种描述。可将程序总结为：程序=算法+数据结构+程序设计方法+语言工具和环境C语言算法的主要特点如下：1.有穷性一个算法应该包含有限的操作步骤，而不能是无限的。2.确定性算法中的每一个步骤应当是确定的，而不应当是含糊的（多义性），应是十分明确无误的。3.有0个或多个输入。4.有一个或多个输出。5.有效性算法中的每一个步骤都应当有效的执行，并得到确定的结果。３.2算法的特征3.3算法的表示方法(1)自然语言描述法(2)传统的流程图表示常用符号有:(3)N-S流程图表示(4)伪代码表示算法(5)计算机语言表示算法起止框输入/输出框判断框处理框流程线连接点一、顺序结构BA(a)AB(b)先执行A操作，再执行B操作，两者是顺序执行关系。N-S结构流程图结构化程序设计的三种基本机构二、选择结构当P条件为真时，执行A模块，否则执行B模块。APB真假(a)P真假AB(b)三、循环结构当P条件成立时，反复执行A,直到P为假。1.当型循环结构PA假真(a)当P为真A(b)当P为真2.直到型循环结构先执行A操作，再判断P是否为假，若P为假，再执行A，直到P为真为止。AP假真(a)A直到P为真(b)算法举例1：对一个大于2的正整数，判断它是不是一个素数。方法：将n(其中n2)作为被除数，将2到（n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。算法表示如下：S1：输入n的值S2：2i(i作为除数）S3:n被i除，得余数rS4:如果r等于0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5S5：i+1iS6:如果in-1,返回S3；否则，打印n“是素数”，算法结束。算法举例2：求1-1/2+1/3–1/4+…+1/99–1/100。S1:1signS2:1sumS3:2denoS4:(-1)*signsignS5:sign*(1/deno)termS6:sum+termsumS7:deno+1denoS8:若deno100返回S4；否则算法结束。算法举例3：用伪代码表示算法：用介于自然语言和计算机语言之间的文字和符号来描述算法BEGIN1=iwhile(i50){inputni和gii+1=i}1=iwhile(i50){if(gi=80)printni和gii+1=i}END算法举例4:用计算机语言表示算法求1-1/2+1/3–1/4+…+1/99–1/100。S1:1sS2:1sumS3:2dS4:(-1)*ssS5:s*(1/d)tS6:sum+tsumS7:d+1dS8:若d100返回S4；否则算法结束。main(){ints=1;floatd=2.0,sum=1.0,t;while(d=100){s=-s;t=s/d;sum=sum+t;d=d+1;}printf(“%f”,sum);}３.４小结(1)算法是程序的灵魂，计算机程序设计的实质是算法的设计。(2)C语言算法的特点是：①有穷性②确定性③有0个或多个输入④有一个或多个输出⑤有效性(3)算法的表示①用自然语言表示②用流程图表示算法，三种最基本的程序设计算法为：顺序结构，选择结构和循环结构。3.5C语句介绍一、C程序结构C程序源程序文件1源程序文件2源程序文件n••••••预处理命令全局变量声明函数1函数n••••••函数首部函数体局部变量声明执行语句二、C语句概述C语句分类：1.控制语句2.函数调用语句3.赋值语句4.空语句5.复合语句一条完整的C语句必须以“;”结束。“;”是一个语句不可缺少的一部分。1.控制语句：完成一定的控制功能。C有9种控制语句：⑴if()~else~（条件语句）⑵for()~（循环语句）⑶while()~（循环语句）⑷do~while()（循环语句）⑸continue（结束本次循环语句）⑹break（中止执行switch或循环语句）⑺switch（多分支选择语句）⑻goto（转向语句）⑼return（从函数返回语句）2.函数调用语句由一次函数调用加一个“;”构成。如：printf(“HelloWorld!”);函数调用分号3.赋值语句由表达式加上“;”构成。如：x+4*y；算术表达式语句4*7，4+8；逗号表达式语句x=4*7;赋值表达式语句(赋值语句)4.空语句由一个“;”构成。即：;作用：①程序转向点；②什么也不做的循环体。while(i=11);5.复合语句用{}括起的一组语句。如：if(x1x2){y=x1*x1+x2;printf(y=%d,y);}不能省略不能加“;”说明:(1)复合语句中的每一个语句还可以是复合语句；(2)复合语句尽管可由多个语句组合，但它只相当于一个语句，在任何单一语句可以存在的地方，复合语句都可以存在。(3)在复合语句内，不仅可以有执行语句，还可以有定义部分，定义部分应该出现在可执行语句的前面。3.6顺序结构程序设计(顺序结构)(选择结构)(循环结构)特点：程序按语句从上到下的排列顺序依此执行，每条语句必须执行且只能执行一次，没有执行不到或执行多次的语句。例如：已知圆柱体半径6米，高7米，求体积。#definePI3.1415main(){floatr,h,s,v;r=6;h=7;s=PI*r*r;v=s*h;printf(“V=%f\n”,v);}例3.1输入三角形的三条边，求三角形的面积。分析：已知∶三角形的三条边a,b,c。求解∶三角形的面积area。计算公式∶设s=（a+b+c）/2area=)(*)(*)(*csbsass开始给a,b,c赋值计算s=(a+b+c)/2计算area=)(*)(*)(*csbsass结果输出结束#includemath.hmain(){floata,b,c,s,area;scanf(“%f%f%f”,&a,&b,&c);s=(a+b+c)/2.0;area=sqrt(s*(s-a)*(s-b)*(s-c));printf(“a=%fb=%fc=%fs=%f”,a,b,c,s);printf(“area=%f”,area);}例3.2从键盘输入一个大写字母，要求改用小写字母输出。分析：已知∶字符变量c1为大写字母。求解∶将字符变量c2中放入相应的小写字母。计算公式∶c2=c1+32(小写改成大写字母？）开始计算c2=c1+32输出c1结束输入一大写字母放入c1中输出c2#includestdio.hmain(){charc1,c2;c1=getchar();/*键盘输入一个大写字母*/printf(“%c,%d\n”,c1,c1);c2=c1+32;printf(“%c,%d\n”,c2,c2);}输入:A输出:A,65a,97例3.3求ax2+bx+c=0的根，a，b，c由键盘输入，设b2-4ac0#includemath.hmain(){floata,b,c,disc,x1,x2,p,q;scanf(%f%f%f,&a,&b,&c);disc=b*b-4*a*c;p=-b/(2*a);q=sqrt(disc)/(2*a);x1=p+q;x2=p-q;printf(”x1=%fx2=%f,x1,x2);}运行情况:a=1,b=3,c=2x1=-1.000000x2=-2.000000例3.4输入一个三位数，依次输出该数的符号和百号，十位，个位数字。#includestdi.h#includemath.hmain(){charc1,c2,c3,c4;intx;scanf(“%d”,&x);/*输入一个三位数*/c4=(x=0?’+’:’-’);/*将x的符号存入c4中*/x=abs(x);/*求三位数的绝对值*/c3=x%10+48;/*获得个位数字，加48后转换为对应的字符*/x=x/10;/*获得x的前两位*/c2=x%10+48;/*获得十位数字，加48后转换为对应的字符*/c1=x/10+48;/*获得百位数字，加48后转换为对应的字符*/printf(“%c%c%c%c”,c4,c1,c2,c3);}运行情况:-345-3453.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)(bc)、‘a’‘b’、xy、s+fd2.关系表达式的值运算结果∶逻辑值1——“真”，0——“假”如：设a=3,b=2,c=1求下面关系表达式的值：cb(a-b)==1b+ca值为０值为１值为０如果关系运算对象的类型不同，也要先进行类型转换。3.7.2逻辑运算符和逻辑表达式3种逻辑运算符：①！（逻辑非）②&&（逻辑与）③||(逻辑或）3.7.2.1逻辑运算符优先级(高)(低)如：!aa为真，则!a为假。a||ba、b之一为真，则a||b为真。a&&ba、b同时为真，则a&&b为真。与其它运算符优先级的比较：(高)(低)！算术运算符关系运算符&&和||赋值运算符例如：c=da+b&&ab等效于：c=((d(a+b))&&(ab))1.什么是逻辑表达式？3.7.3逻辑表达式用逻辑运算符将逻辑运算对象连结起来的式子。如：(ab)&&(bc)、!a||ab2.逻辑表达式的值运算结果∶逻辑值(只有假为0、真为1两种取值)如：53&&2||84‘b’&&’d’值为1值为１运算对象∶以数值非0为真、0为假注意事项：(1)代数式不等式0x5必须写成(x0)&&(x5),而不能直接写成0x5。(2)C语言允许直接对数或字符进行逻辑运算。例如！5，结果为0。5&&‘c’，结果为1。因为字符‘c’的ASCII为非0值，非0值与非0值作与运算，结果为真。3.7.4选择结构语句1.单分子选择if(表达式)语句3.7.4.1if语句执行过程：当表达式的值为“真”（非零）时，执行语句，否则，不执行语句。如:if(xy)z=x;2.双分子语句if(表达式)语句1else语句2执行过程：当表达式的值为“真”（非零）时，执行语句1，否则，执行语句2。如:if(xy)z=x;elsez=y;3.多分子语句if(表达式1)语句1elseif(表达式2)语句2elseif(表达式3)语句3:elseif(表达式m)语句melse语句n如：if(grade=85)level=‘A’;elseif(grade=70)level=‘B’;elseif(grade=60)level=‘C’;elselevel=‘D’;if语句说明：⑴if后面的表达式一般为逻辑表达式或关系表达式，也可以是任意数值类型表达式。该语句是合法的：if(3)printf(“ok!”);⑵if语句中的“语句”为一个简单语句或复合语句。如：下面程序段是否有错？if(x=0)printf(“Xispositive.”);x++;elseprintf(“Xisnegative.”);if(x=0){printf(“Xispositive.”);x++;}elseprintf(“Xisnegative.”);4.if语句的嵌套在if语句中又包含一个或多个if语句称为if语句的嵌套。一般形式：if(条件1）if(条件2)语句1else语句2elseif(条件3)语句3else语句4内嵌if内嵌if