第3章算法与程序设计基础

1、第第3章章 算法与程序设计基础算法与程序设计基础 3.1算法概述 3.2算法的常用表示方法 3.3结构化程序设计方法结构化程序设计方法 3.4C语句概述 3.5选择结构程序设计 3.6循环程序设计 3.7综合程序应用举例3.13.1算法概述算法概述 3.1.1算法的概念算法的概念 为解决一个实际问题而采取的方法和步骤，称之为为解决一个实际问题而采取的方法和步骤，称之为“算法算法” 。例3.1: 求1+2+3+4+100=?算法1 步骤1：1+2=3 步骤2：3+3=6 步骤3：6+4=10 步骤99：4950+100=5050算法3 步骤步骤1：k=1，s=0 步骤步骤2：如果k100,则算法

2、结束，s即为所求的和，输出s；否则转向步骤3. 步骤步骤3：s=s+k，k=k+1 步骤步骤4：转向步骤23.1.2 算法的特性算法的特性 1.有穷性有穷性 2.确定性确定性 3.可行性可行性 4.有零个或多个输入有零个或多个输入 5.有一个或多个输出有一个或多个输出3 32 2算法的常用表示方法算法的常用表示方法3.2.1自然语言表示法自然语言表示法例例3.2: 3.2: 求求m m！如果如果m=6,m=6,即求即求1 12 23 34 45 56 6。我们先设我们先设s s 代表累乘之积，以代表累乘之积，以t t代表乘数，自然代表乘数，自然语言表示语言表示m m！的算法为：！的算法为：(1

3、)(1)使使s=1,t=1s=1,t=1。(2)(2)使使s st, t, 得到的积仍放在得到的积仍放在s s中。中。(3) (3) 使使t t的值加的值加1 1。(4) (4) 如果如果tmtm，返回第，返回第步重新执行。否则循环步重新执行。否则循环结束，此时结束，此时s s中的值就是中的值就是m!m!，输出，输出s s。 3.2.2流程图流程图结构化程序设计中采用三种基结构化程序设计中采用三种基本结构，即顺序结构、选本结构，即顺序结构、选择结构和循环结构，这三择结构和循环结构，这三种基本结构有以下共同特种基本结构有以下共同特点：点：只有一个入口。只有一个入口。只有一个出口。只有一个出口。结

4、构内的每一部分都有机结构内的每一部分都有机会被执行到。会被执行到。 结构内不存在结构内不存在“死循环死循环”（无终止的循环）。（无终止的循环）。 3.2.3 N-S结构流程图结构流程图3.2.4 伪代码表示法伪代码表示法伪代码伪代码（pseudo codepseudo code）是用介于自然语言和是用介于自然语言和计算机语言之间的文计算机语言之间的文字和符号来表示算法字和符号来表示算法即计算机程序设计语即计算机程序设计语言中具有的语句关键言中具有的语句关键字用英文表示，其他字用英文表示，其他的可用汉字，也可用的可用汉字，也可用英文，只要便于书写英文，只要便于书写和阅读就可。和阅读就可。 例例3

5、.3: 求求m!,用伪代码表示用伪代码表示的算法如下：的算法如下：开始开始 从键盘输入一个正整数给从键盘输入一个正整数给m 置置s的初值为的初值为1 置置i的初值为的初值为1 当当i=m，重复执行下面的，重复执行下面的操作：操作： 使使s=si 使使i=i+1 （循环体到此结束）（循环体到此结束） 打印打印s的值的值结束结束3.2.5 用计算机语言表示算法用计算机语言表示算法例例3.4: 将例将例3.2求求m!的算法用的算法用C语言表示。语言表示。#include main()int j,s,m;printf(“n Please input a integer to m:”);scanf(“%

6、d”,&m);s=1;j=1;while (j5) x=y; j+;4. 空语句空语句仅由一个分号构成的语句就是空语句。仅由一个分号构成的语句就是空语句。5. 复合语句复合语句复合语句是由大括号括起来的在逻辑上相复合语句是由大括号括起来的在逻辑上相关的一组语句。如上例中的：关的一组语句。如上例中的： s=s+i; i=i+2; 6. 控制语句控制语句 控制语句用来规定语句执行的顺序控制语句用来规定语句执行的顺序,共共有有9种控制语句种控制语句: if (条件) else 条件语句 for (条件) 循环语句 while (条件) 循环语句 do while(条件); 循环语句 continue

7、; 结束本次循环语句 break; 结束循环语句或结束switch语句 switch (表达式) 多分支选择语句 goto 标号; 转向语句 return (表达式); 从函数返回语句3.5 3.5 选择结构程序设计选择结构程序设计3.5.1 关系运算符和关系表达式关系运算符和关系表达式1关系运算符关系运算符及优先次序及优先次序2关系表达式关系表达式 用关系运算符连接起来的表达式称为关用关系运算符连接起来的表达式称为关系表达式，关系表达式的结果为逻辑值真（用系表达式，关系表达式的结果为逻辑值真（用“1”表示）和假（用表示）和假（用“0”表示）。表示）。例如：例如：ca+b 若：若：a=3,b=

8、4,c=9 则结果为：则结果为：1a=bc 若：若： b=4,c=9 则则a的值为：的值为：0 3.5.2 逻辑运算符和逻辑表达式逻辑运算符和逻辑表达式 1逻辑运算符及优先次序逻辑运算符及优先次序 2. 逻辑表达式逻辑表达式用逻辑运算符将关系表达式或逻辑表达式连接起用逻辑运算符将关系表达式或逻辑表达式连接起来的式子称逻辑表达式。来的式子称逻辑表达式。例如：若例如：若a=4,b=2,x=6,y=7,则：则：ab&xy 表达式的结果为：表达式的结果为：0a=b|x=y 表达式的结果为：表达式的结果为：0!a|ab 表达式的结果为：表达式的结果为：1 注意：注意：（1） 在在C语言中规定：非零为语言

9、中规定：非零为“真真”，“真真”用用1表示；零为表示；零为“假假”，“假假”用用0表示。表示。（2） 对逻辑表达式的求解，并不是所有的逻对逻辑表达式的求解，并不是所有的逻辑运算符都被执行，只是在必须执行下一个逻辑运算符都被执行，只是在必须执行下一个逻辑运算符才能求出表达式的解时，才执行该运辑运算符才能求出表达式的解时，才执行该运算符。算符。 例3.6： 运行下面的程序四次，若分别输入0 0 0，1 1 1，4 5 6，0 1 0，分别写出其对应的输出结果。#includemain() int a,b,c; scanf(%d%d%d,&a,&b,&c); printf(e=%d,a=%d,b=%

10、d,c=%dn, +a & b- & +c,a,b,c); printf(a=%d,b=%d,c=%d,e=%d,n, a,b,c,+a & b- & +c); c=a|(a=c)b); printf(a=%d,b=%d,c=%dn,a,b,c); printf(e=%d,a=%d,b=%d,c=%dn, -c | b-|+a,a,b,c); printf(a=%d,b=%d,c=%d,e=%dn,a,b,c,-c | b-|+a); 3.5.3 if语句语句 C语言提供了两种格式： 格式格式1: if (表达式表达式) 语句语句; 该语句的功能是该语句的功能是:首先计算表达式的值首先计算表达

11、式的值,然然后判断表达式的值是否为非零后判断表达式的值是否为非零(真真)，若为非零，若为非零(真真)，则执行语句。其执行过程见图，则执行语句。其执行过程见图3-22所所示示 例例3.7: 输入一个字符，若是字母，则输出输入一个字符，若是字母，则输出“Yes!”。#include main() char x; x=getchar();if (x=a&x=z|x=A&xb)?a:b 相当于相当于 max=(ab)? a:b) ab? a:b+1 相当于相当于 ab?a : (b+1)3.条件运算符的结合方向为条件运算符的结合方向为“自右至左自右至左”。如：如：ab?a:cd?c:d 相当于相当于

12、ab?a: (cd?c:d)表达式表达式1？表达式？表达式2：表达式：表达式33.5.6 switch 语句语句其一般形式如下：其一般形式如下：switch (表达式表达式) case 常量表达式常量表达式1： 语句语句1； case 常量表达式常量表达式2： 语句语句 2； case 常量表达式常量表达式n： 语句语句n; default: 语句语句n+1; 例例3.14: 某幼儿园只收某幼儿园只收2至至6岁的小孩。岁的小孩。23岁入小岁入小班，班，4岁入中班，岁入中班，56岁入大班。输入年龄，要求输岁入大班。输入年龄，要求输出应入什么班？出应入什么班？ #includemain() int

13、 age; printf(nInput a age:); scanf(%d,&age); switch (age) case 2: case 3: printf(n Enter Lower class!); break; case 4: printf(n Enter Middle class!); break; case 5: case 6: printf(n Enter Higher class!); break; default: printf(n Cant enter!); 说明：说明：（1 1）switch switch 后的表达式，可以是整型或字符型，也可以是枚后的表达式，可以是整型

14、或字符型，也可以是枚举类型，不能是上述三种类型以外的类型。举类型，不能是上述三种类型以外的类型。 （2 2）每个）每个casecase后的常量表达式只能是常量组成的表达式，当后的常量表达式只能是常量组成的表达式，当switchswitch后的表达式的值与某一个常量表达式的值一致时。程后的表达式的值与某一个常量表达式的值一致时。程序就转到此序就转到此casecase后的语句开始执行。如果没有一个常量表达后的语句开始执行。如果没有一个常量表达式的值与式的值与switchswitch后的值一致，就执行后的值一致，就执行defaultdefault后的语句。后的语句。 （3 3）每个）每个caseca

15、se后的常量表达式的值必须互不相同，否则程序后的常量表达式的值必须互不相同，否则程序就无法判断应该执行哪个语句了。就无法判断应该执行哪个语句了。 （4 4）casecase的次序不影响执行结果，一般情况下，尽量将使用的次序不影响执行结果，一般情况下，尽量将使用几率大的几率大的casecase放在前面，放在前面，defaultdefault部分也不一定要放在最后。部分也不一定要放在最后。5 5）在执行完一个）在执行完一个casecase后面的语句后，程序流程转到下一个后面的语句后，程序流程转到下一个casecase后的语句开始执行，直至整个后的语句开始执行，直至整个switchswitch语句结

16、束。千万不语句结束。千万不要理解成执行完一个要理解成执行完一个 casecase后程序就转到后程序就转到switchswitch后的语句去后的语句去执行了。若要执行完一个执行了。若要执行完一个casecase的语句后，转到的语句后，转到switchswitch后的语后的语句去执行，则要在该句去执行，则要在该casecase语句的最后加上语句的最后加上breakbreak语句（跳转语句（跳转语句，在下一节做详细讲解），跳转到语句，在下一节做详细讲解），跳转到switchswitch后的语句去执后的语句去执行。行。switchswitch语句与语句与breakbreak语句的执行过程的流程图如图语

17、句的执行过程的流程图如图3-293-29所示。所示。 3.5.7 选择结构程序设计举例选择结构程序设计举例#include #include main() float x,y,z; printf(nx=); scanf(%f,&x); printf(ny=); scanf(%f,&y); if(x0)&(y=0)&(x=0) z=exp(2*x-y); if(x=1) z=log(x); printf(z=%5.2fn,z); 例例3.18： 假设个人所得税的计征办法是月收入低于假设个人所得税的计征办法是月收入低于1000元者，不计税，高于元者，不计税，高于1000元低于元低于2000元者，高

18、元者，高出部分征收出部分征收5%；高于；高于2000元低于元低于5000元者，高出部元者，高出部分征收分征收10%；高于；高于5000元低于是元低于是10000元元,高出部分高出部分征收征收15%,高于高于10000元的征收元的征收35%。输入一个人的。输入一个人的月收入，求出其应交的个人所得税。月收入，求出其应交的个人所得税。#includemain()long int r; float f; printf(Input a integer to r:); scanf(%ld,&r); if (r0) switch(r/1000) case 0:f=0;break; case 1:f=(r-1

19、000)*0.05;break; case 2: case 3: case 4:f=1000*0.05+(r-2000)*0.1;break; case 5: case 6: case 7: case 8: case 9:f=1000*0.05+3000*0.1+(r-5000)*0.15;break; default:f=1000*0.05+3000*0.1+5000*0.15+(r-10000)*0.35; printf(f=%f,f); else printf(Input a data error!); 3.6 3.6 循环程序设计循环程序设计 在C语言中提供了四种实现循环结构的四种实现

20、循环结构的方法方法：（1）goto语句以及用goto语句构成的循环（2）用while 语句（3）用do-while 语句（4）用for 语句3.6.1 goto语句以及用语句以及用goto语句构成的循环语句构成的循环 goto语句为无条件转向语句，它的一般形语句为无条件转向语句，它的一般形式为式为 goto 语句标号；语句标号；一般情况下，使用一般情况下，使用goto语句有两种情况：语句有两种情况：与与if语句一起构成循环结构；语句一起构成循环结构；从循环体中跳转到循环体外，但在从循环体中跳转到循环体外，但在C语言中语言中可以用可以用break语句和语句和continue语句跳出本层语句跳出本

21、层循环和结束本次循环。循环和结束本次循环。3.6.2 while 语句语句 while 语句又称当循环语句，其一般的语句又称当循环语句，其一般的形式如下：形式如下： while (表达式表达式) 循环体语句；循环体语句； 例3.22: 用while语句来实现求m!，m的值由键盘输入。 其算法用N-S流程图表示见图3-32。#includemain() int m,i=1; long factorial=1; printf(nInput a integer to m:); scanf(%d,&m); while (i=m) factorial=factorial*i; i+; printf(%d

22、!=%ld,m,factorial); 说明：说明：(1)while(1)while语句一般用于事先不知道循环次数，语句一般用于事先不知道循环次数，在循环执行的过程中，根据条件来决定循环是在循环执行的过程中，根据条件来决定循环是否结束。否结束。(2)(2)在循环体语句中可以是一条简单的语句，也在循环体语句中可以是一条简单的语句，也可以是复合语句，若为复合语句则要用花括号可以是复合语句，若为复合语句则要用花括号括起来。括起来。(3)(3)在循环体语句中，一定要有改变循环条件的在循环体语句中，一定要有改变循环条件的语句，使循环能终止。语句，使循环能终止。如上例中的如上例中的i+;i+;语句，语句，

23、其就是使循环变量其就是使循环变量i i自增自增1 1，改变循环条件的语，改变循环条件的语句，若没有该语句，则句，若没有该语句，则i i的值永远不会改变，的值永远不会改变，条件条件i=mi=m永远为真，这样的循环称为死循环。永远为真，这样的循环称为死循环。 3.6.3 do-while 语句语句 do-while循环语句又称直到型循环语句，循环语句又称直到型循环语句，其一般形式如下：其一般形式如下： do 循环体语句；循环体语句； while (表达式表达式)； 例3.24： 用do-while语句来实现求m!，m的值由键盘输入。程序清单如下：程序清单如下：#includemain() int

24、m,i=1; long factorial=1; printf(nInput a integer to m:); scanf(%d,&m); do factorial=factorial*i; i+; while (i=m); printf(%d!=%ld,m,factorial); 说明：说明：(1)dowhile语句也是一般用于事先不知道循环次数的语句也是一般用于事先不知道循环次数的情况下，在循环执行的过程中，根据条件来决定循环情况下，在循环执行的过程中，根据条件来决定循环是否结束。是否结束。(2)在循环体语句中可以是一条简单的语句，也可以是复在循环体语句中可以是一条简单的语句，也可以是复

25、合语句，若为复合语句则要用花括号括起来。合语句，若为复合语句则要用花括号括起来。(3)在循环体语句中，一定要有改变循环条件的语句，使在循环体语句中，一定要有改变循环条件的语句，使循环能终止。如上例中的循环能终止。如上例中的i+;语句，其就是使循环变语句，其就是使循环变量量i自增自增1，改变循环条件的语句，若没有该语句，则，改变循环条件的语句，若没有该语句，则i的值永远不会改变，循环就是一个死循环。的值永远不会改变，循环就是一个死循环。(4)在在while（表达式）的后面一定要有一个分号，它用（表达式）的后面一定要有一个分号，它用来表示来表示do-while语句的结束。语句的结束。(5)do-w

26、hile语句和语句和while语句最大的差别就是语句最大的差别就是do-while语句至少要执行一次循环体语句，而语句至少要执行一次循环体语句，而while语句可以一语句可以一次都不执行。请看例次都不执行。请看例3.25。 例例3.25： while 循环和循环和do-while循环的比较。循环的比较。程序如下：（1） main() (2) main() int m,n=1; int m,n=1; scanf(“%d”,&m); scanf(“%d”,&m); do while(m=10) n+=m; n+=m; m+; m+; while(m=10); printf(“n=%d,m=%d”,

27、n,m); printf(“n=%d,m=%d”,n,m); 程序运行结果： 程序运行结果： 5 5 n=46, m=11 n=46, m=11 再运行一次的结果： 再运行一次的结果： 11 11 n=12,m=12 n=1,m=11 3.6.4 for 语句语句 for语句的一般形式为： for(for(表达式表达式1 1；表达式；表达式2 2；表达式；表达式3)3) 循环体语句循环体语句 说明：说明： (1) for(1) for语句可用如下易理解的形式来描述：语句可用如下易理解的形式来描述： forfor（循环变量初值；循环条件；循环变量增值）循环体语句（循环变量初值；循环条件；循环变量

28、增值）循环体语句 （2 2）forfor语句的一般形式中的语句的一般形式中的“表达式表达式1”1”可以省略，此时应在可以省略，此时应在forfor语句之前给循环变量赋初值。表达式语句之前给循环变量赋初值。表达式1 1省略，其后的分号不能省略。省略，其后的分号不能省略。执行时跳过执行时跳过“求解表达式求解表达式1”1”这一步，其它不变。这一步，其它不变。 （3 3）“表达式表达式2”2”也可省略，其后的分号不能省略。此时等于没有也可省略，其后的分号不能省略。此时等于没有循环条件，执行循环条件，执行forfor语句时，就不要判断循环条件，也就认为表达语句时，就不要判断循环条件，也就认为表达式式2

29、2始终为真。此时循环体中一定要有一条语句能够跳出循环，否始终为真。此时循环体中一定要有一条语句能够跳出循环，否则就是一个死循环。则就是一个死循环。 （4 4）“表达式表达式3”3”也可省略，但前面的分号不能省略，此时应在循也可省略，但前面的分号不能省略，此时应在循环体中要有语句可以改变循环变量的值，否则循环也会变成死循环体中要有语句可以改变循环变量的值，否则循环也会变成死循环。环。 （5 5）表达式）表达式1 1，表达式，表达式2 2，表达式，表达式3 3可以省略一个或两个，也可同时可以省略一个或两个，也可同时全部省略，但分号不能省略。全部省略，但分号不能省略。 （6 6）表达式）表达式1 1

30、，2 2，3 3可以是任何类型的表达式，包括逗号表达式。可以是任何类型的表达式，包括逗号表达式。可以是与循环变量有关的表达式，也可以是与循环变量无关的表可以是与循环变量有关的表达式，也可以是与循环变量无关的表达式。达式。 例例3.28: 中国剩中国剩余定理：余定理：“有物有物不知几何，三三不知几何，三三数余一，五五数数余一，五五数余二，七七数余余二，七七数余三，问：物有几三，问：物有几何？何？”。编程求。编程求1000以内所有解。以内所有解。程序清单如下：程序清单如下：#include main()int m,count=0;for(m=1;m=1000;m+) if(m%3=1&m%5=2&

31、m%7=3) printf(“%5d”,m);count+; if(count%5=0) printf(“n”); 3.6.5 循环的嵌套循环的嵌套程序清单如下：程序清单如下：#include main() int i,j; for(i=1;i=9;i+) for(j=1;j=9;j+) printf(“%d*%d=%dt”,I,j,I*j); printf(“n”); 打印如书打印如书P94图图3-36所示的所示的“九九-九九”乘法表。乘法表。打印如下图形：用循环的嵌套如何设计？打印如下图形：用循环的嵌套如何设计？*或或 * * * * 3.6.6 break语句语句break语句的一般格式为： break； 例3.31 求s=1+2+3+4+，直到s的值不小于28888，求此时n的值为多少？#includemain() int i=1,s=0; while(1) s+=i; if (s=28888) break; i+; printf(n i=%d,i); 3.6.7 continue语句语句 continue语句的一般形式如下：continue;例3.32： 从键盘输入整数，显示出其中的正整数，若输入的是100，则退出。程序清单如下：#includ