C语言程序设计-C2-1课件

有符号数(int)-1无符号数(unsignedint)28－1=255浮点数(float)11111111符号整数符号纯小数阶码尾数

（补）（原）（-1）2（-0.1111)2=-0.93752-1×-0.9375=-0.4687511111111内存中同样的数据,类型不同,其值不相同!注意:补码的概念值=?

瑞士科学家沃思（NikiklausWirth)提出（1976）,程序应包括两方面的内容1.数据的描述

—在计算机中表示数据(数据结构datastructure）

问题:一个内存单元(即1Byte,共8个二进制位)的所有位均为1。第二章计算机算法有符号数(int)11).

数据结构定义数据类型2).算法程序的骨架3).程序设计方法

遵循科学有效的方法—“结构化程序设计方法”4.语言工具及运行环境借助于程序设计语言和操作系统2.计算步骤—算法。

解决“做什么”“怎么做”，是程序的“骨架”

在高级语言中,用户可通过定义变量的类型来实现数据描述,而不必关心数据在内存中的具体存放形式。程序设计的含义1).数据结构定义数据2一.概念

算法——为解决一个实际问题而采取的方法和有限的计算（操作）步骤。

例：

输入100个数，求总和。

算法1：

(1)第1个数输入计算机a1(2)第2个数输入计算机a2(3)以上两数相加sum←a1+a2(4)输入第3个数a3

(5)第3个数与前两数之和相加sum←sum+a3…………..(198)将第100个数输入a←100(199)与前99个数之和相加sum←sum+a100(200)打印输出总和

问题:书写太长。如输入1000个数，更长。不具有普遍意义§2.1算法的概念一.概念§2.1算法的概念3

算法2(1)设一个“计数变量”N，令初值N=0(2)设一个“累加变量”sum，令初值sum=0(3)输入一个数给变量a(4)sum←sum+a(5)N的值加1，（表示已经加了一个数）N←N+1(6)如N＜100则返回(3),否则执行(7)或:如N≥100则执行(7),否则返回(3)(7)打印输出sum优点:

算法精练,有一定的通用性。二.算法的分类

1.数值运算算法

如：求线性方程组,求非性线方根的根,计算定积分等《计算方法》研究本类问题

2.非数值运算算法

如：资料检索,调度,人工智能等,有待于进一步完善二.算法的分类4三.对算法的要求

1.正确性2.容易阅读理解3.计算机执行时具有较高的效率1)得到结果的时间少(步骤不能太多)2)占用内存少(程序不能太长,变量不能太多)尤其重要三.对算法的要求尤其重要5s1:i←1s6:输出ps2:p←1s3:p←p*is4:i←i+2s5如i≤11T转向s3F转向s6例2.1求1×2×3×4×5

(1)设一个“计数变量”i,初值i=1

(2)设一个“积”p,初值p=1(注p≠0)(3)计算p×i,结果仍赋给ppp×i(4)i自加1ii+1(为下一次计算作准备)(5)判i≤5?成立,返回(3)不成立,转入(6)(6)输出p

问题:

求1×3×5×7×9×11?§2.2简单算法举例s1:i←16例2.2求：

思考：算法:B

s1:sign=-1s2:和sum=0s3:分母deno=1(第一项分母)s4:sign=(-1)*signs5:项term=sign*(1/deno)s6:sum=sum+terms7:deno=deno+1(下一个分母）s8:deno≤100?T转s4F输出sum符号：初值sign=1sign(-1)*sign算法：A

s1:sign=1s2:和sum=1(将第一项直接纳入总和)s3:分母deno=2(第二项分母)s4:sign=(-1)*signs5:项term=sign*(1/deno)s6:sum=sum+terms7:deno=deno+1(下一个分母）s8:deno≤100?T转s4F输出sum例2.2求：算法:B符号：初值sign=17思考:1)2)例2.4

对一个大于或等于3的正整数,判断它是否为素数。

思考：对于正整数n,用2至n-1的各个整数作除数与n相除，若都不能整除（即余数≠0)，则n为素数;否则只要有一个数能与n整除，则n不为素数。

s1:

输入n

s2:除数i←2

s3:计算r=nMODi(MOD——求余数运算）

s4:判r=0?T则输出“n不是素数”,结束F转入s5

s5:i=i+1

s6:判i≤n-1?T返回S3F则输出“n是素数”,结束思考:1)例2.4对一个大于或等于3的正8§2.3算法的特性1.有穷性

有限的计算(操作)步骤2.确定性确切的数据参加运算，得确切的结果。3.有零个、1个、多个输入；4.有一个、多个输出。如无解也要明确指出“无解”5.有效性每一步都要能有效执行如：有语句a=b-3;c=sqrt(a);必须考虑a有可能小于0的情况d=5/a;a不能为0故:a>0,b>3

§2.3算法的特性1.有穷性9§2.4算法的描述

如何表示算法一.用自然语言表示算法——用文字叙述来表示算法问题：描述不够准确，有“歧义性”，只用于简单的算法。如：a、b相除，结果赋给c

c=a/bc=b/a?二.用流程图表示算法用图形符号计算或操作带箭头线条执行顺序由ANSI规定，国标GB1526—89引用起止框输入、输出框处理框，计算§2.4算法的描述一.用自然语言表示算法c10判断框流程线连接点注释框求1×2×3×4×5

(1)设一个“计数变量”i,初值i=1

(2)设一个“积”p,初值p=1(3)pp×i(4)i自加1,ii+1(5)判i≤5?成立,返回(3)不成立,转入(6)(6)输出pbegini=1;p=1p=p*ii=i+1i≤5T输出pendF判断框流程线连接点注释框求1×2×3×4×5begini=111s1:sign=1s2:和sum=1s3:分母deno=2s4:sign=(-1)*signs5:项term=sign*(1/deno)s6:sum=sum+terms7:deno=deno+1(下一个分母）s8:deno≤100?T转s4F输出sum例NoorFbeginsign=1;sum=1;deno=2sign=(-1)*signterm=sign*(1/deno)sum=sum+termdeno=deno+1deno≤100endYesorT输出sums1:sign=1例NoorFbeginsign=12判素数一题s1:输入ns2:除数i←2s3:计算r=nMODis4:判r=0?T则输出“n不是素数”,结束F转入s5s5:i=i+1s6:判i≤n-1?T返回S3F则输出“n是素数”,结束输出“非素数begin输入ni=2r=nMODir=0?i=i+1i≤n-1输出“是素数”endTTFF判素数一题s1:输入n输出“非素数begin输入ni=213例:求n!n≥0,n!=1*2*3*...*nn=0,n!=1n<0,n!无意义,重输入子程序cul调用传nn=0r=1r=1;i=1r=r*ii=i+1i≤nT输出:r返回FFT主程序begin输入:nn<0调culendTNCul为子程序例:求n!n≥0,n!=1*214

总结:

1)直观,容易理解;2)程序的转向无限制,复杂程序难以阅读，BS程序（算法）(abowlofspaghetti),不符合结构化程序设计的要求。三.结构化程序设计及三种基本程序结构

三种基本程序结构1.顺序结构按先后顺序执行AB荷兰学者Dijkstra提出结构化程序设计的概念。目的：使程序具有良好的结构，以便于设计、理解和调试、修改，从而提高设计和维护程序工作的效率。1966年Bohra和Jacopin提出了三种基本程序结构，作为程序的组成单元。总结:三.结构化程序设计及三种基本程序结构15

2.选择结构根据某种条件（状态），选择下一步操作，控制程序流向。条件PAB3.循环结构重复执行（有限次）某一系列计算或操作(1)当型循环条件PA成立a.当条件成立，反复执行Ab.当条件不成立，停止循环即：当条件为真时，才执行循环。成立不成立2.选择结构条件PAB3.循环结构(1)当16(2)直到型循环A条件P不成立先执行A，判P,不成立→执行A成立→停止循环即：一直执行A,直到条件成立为止。A条件P成立先执行A，判P,成立→执行A不成立→停止循环即：一直执行A,直到条件不成立为止。成立不成立注意:两种类型循环的异同点

1.当型循环:先判断条件,后执行循环体中内容;

直到型循环:先执行循环体中内容,后判断条件。2.当第一次条件判断成立时,两种循环等效(2)直到型循环A条件P不成立先执行A，判P,不成立→执行17四.用N—S图表示算法

1973年美国I.Nassi和B.Shneiderman提出1）顺序结构执行：A→B→CABC2）选择结构执行：P→成立→A不成立→BPAB成立不成立3）循环结构当P成立A直到P成立(或不成立）为止当型直到型A四.用N—S图表示算法1）顺序结构ABC2）选择结构PA18例:求n!n≥0,n!=1*2*3*...*nn=0,n!=1n<0,n!无意义,重输入主程序begin输入:nn>=0调culendTNCul为子程序主程序输入nbegin直到n>=0调用culEnd例:求n!n≥0,n!=1*219例:求n!

子程序cul传nn=0?TFr=1i=1r=r*ii=i+1直到i>n输出r返回r=1子程序cul调用传nn=0r=1r=1;i=1r=r*ii=i+1i≤nT输出:r返回FFT例:求n!子程序cul传nn=0?TFr=1i=1r=20begin输入ni=2r=nMODir=0?i=i+1i≤n-1输出“是素数”endTTFF判素数一题输出“非素数？begin输入ni=2r=nMODir=0?i=i+1i≤n-1且w≠1TTFFW=0W—标志,如：W=0，“素数”如：W=1，

“非素数”W=0?“素”“非素”TFendw=1begin输入ni=2r=nMODir=0?i21N-S图输入nw=0i=2r=nMODir=0FTW=1i=i+1直到i>n-1或W=1W=0?TF是素数非素数begin输入ni=2r=nMODir=0?i=i+1i≤n-1且W≠1TTFFW=0W—标志,如：W=0，“素数”如：W=1，

“非素数”W=0?“素”“非素”TFendw=1N-S图输入nw=0i=2r=nMODir=0FTW=22求：5!（两种循环的比较）i=1当型循环：p=1i=p*ii=i+1直到i>5为止直到型循环：输出pi=1p=1i=p*ii=i+1当i≤5时输出p当第一次循环能进行时,“当型”与“直到型”可互换求：5!（两种循环的比较）i=1当型循环：p=1i=p*23五.用伪代码表示算法——用与程序设计语言相近的文字、符号表示算法

持点：无严格规定，以表示清楚为原则

文字：中文、英文、或程序设计语言中的部分内容例：求n!

Begini=1p=1

当i<=5执行{p=p*ii=i+1}输出：tend必须遵循“结构化程序设计”原则当型循环五.用伪代码表示算法例：求n!Begin24Beginsign=-1sum=0deno=1

执行下列内容{sign=(-1)*signterm=sign*(1/deno)sum=sum+termdeno=deno+1}直到deno>100输出：sumendBeginsign=-1sum=0deno=1

当deno<=100时执行：{sign=(-1)*signterm=sign*(1/deno)sum=sum+termdeno=deno+1}输出：sumend当型直到求：方法1方法2BeginBegin当型直到求：方法1方法225六.用计算机语言表示算法

——用某一种程序设计语言来编程序。main(){inti,p;i=1;p=1;

while(i<=5){p=p*i;i++;}printf(“5!=%d”,p);}main(){inti,p;i=1;p=1;

do{p=p*i;i++;}while(i<=5)printf(“5!=%d”,p);}法1（用当型循）法2（用直到型循）1.求：5！六.用计算机语言表示算法main()main()法26main(){intsign;floatsum,deno,term;sign=-1;sum=0.0;deno=1.0;

do{sign=(-1)*sign;term=sign/deno;sum=sum+term;deno=deno+1.0;}while(deno<=100);

printf(“sum=%f\n”,sum);}main(){intsign;floatsum,deno,term;sign=-1;sum=0.0;deno=1.0;

while(deno<=100){sign=(-1)*sign;term=sign/deno;sum=sum+term;deno=deno+1.0;}printf(“sum=%f\n”,sum);}求法1（用当型循）法2（用直到型循）main()main()求法1（用当型循）法2（用直到型循27有符号数(int)-1无符号数(unsignedint)28－1=255浮点数(float)11111111符号整数符号纯小数阶码尾数

（补）（原）（-1）2（-0.1111)2=-0.93752-1×-0.9375=-0.4687511111111内存中同样的数据,类型不同,其值不相同!注意:补码的概念值=?

瑞士科学家沃思（NikiklausWirth)提出（1976）,程序应包括两方面的内容1.数据的描述

—在计算机中表示数据(数据结构datastructure）

问题:一个内存单元(即1Byte,共8个二进制位)的所有位均为1。第二章计算机算法有符号数(int)281).

数据结构定义数据类型2).算法程序的骨架3).程序设计方法

遵循科学有效的方法—“结构化程序设计方法”4.语言工具及运行环境借助于程序设计语言和操作系统2.计算步骤—算法。

解决“做什么”“怎么做”，是程序的“骨架”

在高级语言中,用户可通过定义变量的类型来实现数据描述,而不必关心数据在内存中的具体存放形式。程序设计的含义1).数据结构定义数据29一.概念

算法——为解决一个实际问题而采取的方法和有限的计算（操作）步骤。

例：

输入100个数，求总和。

算法1：

(1)第1个数输入计算机a1(2)第2个数输入计算机a2(3)以上两数相加sum←a1+a2(4)输入第3个数a3

(5)第3个数与前两数之和相加sum←sum+a3…………..(198)将第100个数输入a←100(199)与前99个数之和相加sum←sum+a100(200)打印输出总和

问题:书写太长。如输入1000个数，更长。不具有普遍意义§2.1算法的概念一.概念§2.1算法的概念30

算法2(1)设一个“计数变量”N，令初值N=0(2)设一个“累加变量”sum，令初值sum=0(3)输入一个数给变量a(4)sum←sum+a(5)N的值加1，（表示已经加了一个数）N←N+1(6)如N＜100则返回(3),否则执行(7)或:如N≥100则执行(7),否则返回(3)(7)打印输出sum优点:

算法精练,有一定的通用性。二.算法的分类

1.数值运算算法

如：求线性方程组,求非性线方根的根,计算定积分等《计算方法》研究本类问题

2.非数值运算算法

如：资料检索,调度,人工智能等,有待于进一步完善二.算法的分类31三.对算法的要求

1.正确性2.容易阅读理解3.计算机执行时具有较高的效率1)得到结果的时间少(步骤不能太多)2)占用内存少(程序不能太长,变量不能太多)尤其重要三.对算法的要求尤其重要32s1:i←1s6:输出ps2:p←1s3:p←p*is4:i←i+2s5如i≤11T转向s3F转向s6例2.1求1×2×3×4×5

(1)设一个“计数变量”i,初值i=1

(2)设一个“积”p,初值p=1(注p≠0)(3)计算p×i,结果仍赋给ppp×i(4)i自加1ii+1(为下一次计算作准备)(5)判i≤5?成立,返回(3)不成立,转入(6)(6)输出p

问题:

求1×3×5×7×9×11?§2.2简单算法举例s1:i←133例2.2求：

思考：算法:B

s1:sign=-1s2:和sum=0s3:分母deno=1(第一项分母)s4:sign=(-1)*signs5:项term=sign*(1/deno)s6:sum=sum+terms7:deno=deno+1(下一个分母）s8:deno≤100?T转s4F输出sum符号：初值sign=1sign(-1)*sign算法：A

s1:sign=1s2:和sum=1(将第一项直接纳入总和)s3:分母deno=2(第二项分母)s4:sign=(-1)*signs5:项term=sign*(1/deno)s6:sum=sum+terms7:deno=deno+1(下一个分母）s8:deno≤100?T转s4F输出sum例2.2求：算法:B符号：初值sign=134思考:1)2)例2.4

对一个大于或等于3的正整数,判断它是否为素数。

思考：对于正整数n,用2至n-1的各个整数作除数与n相除，若都不能整除（即余数≠0)，则n为素数;否则只要有一个数能与n整除，则n不为素数。

s1:

输入n

s2:除数i←2

s3:计算r=nMODi(MOD——求余数运算）

s4:判r=0?T则输出“n不是素数”,结束F转入s5

s5:i=i+1

s6:判i≤n-1?T返回S3F则输出“n是素数”,结束思考:1)例2.4对一个大于或等于3的正35§2.3算法的特性1.有穷性

有限的计算(操作)步骤2.确定性确切的数据参加运算，得确切的结果。3.有零个、1个、多个输入；4.有一个、多个输出。如无解也要明确指出“无解”5.有效性每一步都要能有效执行如：有语句a=b-3;c=sqrt(a);必须考虑a有可能小于0的情况d=5/a;a不能为0故:a>0,b>3

§2.3算法的特性1.有穷性36§2.4算法的描述

如何表示算法一.用自然语言表示算法——用文字叙述来表示算法问题：描述不够准确，有“歧义性”，只用于简单的算法。如：a、b相除，结果赋给c

c=a/bc=b/a?二.用流程图表示算法用图形符号计算或操作带箭头线条执行顺序由ANSI规定，国标GB1526—89引用起止框输入、输出框处理框，计算§2.4算法的描述一.用自然语言表示算法c37判断框流程线连接点注释框求1×2×3×4×5

(1)设一个“计数变量”i,初值i=1

(2)设一个“积”p,初值p=1(3)pp×i(4)i自加1,ii+1(5)判i≤5?成立,返回(3)不成立,转入(6)(6)输出pbegini=1;p=1p=p*ii=i+1i≤5T输出pendF判断框流程线连接点注释框求1×2×3×4×5begini=138s1:sign=1s2:和sum=1s3:分母deno=2s4:sign=(-1)*signs5:项term=sign*(1/deno)s6:sum=sum+terms7:deno=deno+1(下一个分母）s8:deno≤100?T转s4F输出sum例NoorFbeginsign=1;sum=1;deno=2sign=(-1)*signterm=sign*(1/deno)sum=sum+termdeno=deno+1deno≤100endYesorT输出sums1:sign=1例NoorFbeginsign=39判素数一题s1:输入ns2:除数i←2s3:计算r=nMODis4:判r=0?T则输出“n不是素数”,结束F转入s5s5:i=i+1s6:判i≤n-1?T返回S3F则输出“n是素数”,结束输出“非素数begin输入ni=2r=nMODir=0?i=i+1i≤n-1输出“是素数”endTTFF判素数一题s1:输入n输出“非素数begin输入ni=240例:求n!n≥0,n!=1*2*3*...*nn=0,n!=1n<0,n!无意义,重输入子程序cul调用传nn=0r=1r=1;i=1r=r*ii=i+1i≤nT输出:r返回FFT主程序begin输入:nn<0调culendTNCul为子程序例:求n!n≥0,n!=1*241

总结:

1)直观,容易理解;2)程序的转向无限制,复杂程序难以阅读，BS程序（算法）(abowlofspaghetti),不符合结构化程序设计的要求。三.结构化程序设计及三种基本程序结构

三种基本程序结构1.顺序结构按先后顺序执行AB荷兰学者Dijkstra提出结构化程序设计的概念。目的：使程序具有良好的结构，以便于设计、理解和调试、修改，从而提高设计和维护程序工作的效率。1966年Bohra和Jacopin提出了三种基本程序结构，作为程序的组成单元。总结:三.结构化程序设计及三种基本程序结构42

2.选择结构根据某种条件（状态），选择下一步操作，控制程序流向。条件PAB3.循环结构重复执行（有限次）某一系列计算或操作(1)当型循环条件PA成立a.当条件成立，反复执行Ab.当条件不成立，停止循环即：当条件为真时，才执行循环。成立不成立2.选择结构条件PAB3.循环结构(1)当43(2)直到型循环A条件P不成立先执行A，判P,不成立→执行A成立→停止循环即：一直执行A,直到条件成立为止。A条件P成立先执行A，判P,成立→执行A不成立→停止循环即：一直执行A,直到条件不成立为止。成立不成立注意:两种类型循环的异同点

1.当型循环:先判断条件,后执行循环体中内容;

直到型循环:先执行循环体中内容,后判断条件。2.当第一次条件判断成立时,两种循环等效(2)直到型循环A条件P不成立先执行A，判P,不成立→执行44四.用N—S图表示算法

1973年美国I.Nassi和B.Shneiderman提出1）顺序结构执行：A→B→CABC2）选择结构执行：P→成立→A不成立→BPAB成立不成立3）循环结构当P成立A直到P成立(或不成立）为止当型直到型A四.用N—S图表示算法1）顺序结构ABC2）选择结构PA45例:求n!n≥0,n!=1*2*3*...*nn=0,n!=1n<0,n!无意义,重输入主程序begin输入:nn>=0调culendTNCul为子程序主程序输入nbegin直到n>=0调用culEnd例:求n!n≥0,n!=1*246例:求n!

子程序cul传nn=0?TFr=1i=1r=r*ii=i+1直到i>n输出r返回r=1子程序cul调用传nn=0r=1r=1;i=1r=r*ii=i+1i≤nT输出:r返回FFT例:求n!子程序cul传nn=0?TFr=1i=1r=47begin输入ni=2r=nMODir=0?i=i+1i≤n-1输出“是素数”endTTFF判素数一题输出“非素数？begin输入ni=2r=nMODir=0?i=i+1i≤n-1且w≠1TTFFW=0W—标志,如：W=0，“素数”如：W=1，

“非素数”W=0?“素”“非素”TFendw=1begin输入ni=2r=nMODi