第3章算法和基本程序设计PPT讲稿.ppt

《第3章算法和基本程序设计PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第3章算法和基本程序设计PPT讲稿.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章算法和基本程序设计第1页，共44页，编辑于2022年，星期一3.1算法的概念1.定义:做任何事情都有一定的步骤。为解决一个问题而采取的方法和步骤，就称为算法。2.计算机算法可分为两大类：数值运算算法：求解数值；非数值运算算法：事务管理领域。第2页，共44页，编辑于2022年，星期一一个著名的公式一个著名的公式 数据结构数据结构+算法算法=程序程序数据：计算机所能识别、存储和处理的数据：计算机所能识别、存储和处理的对象。数据的动态性。对象。数据的动态性。数据结构：确定数据对象及其存储方式，数据结构：确定数据对象及其存储方式，并定义在这些数据对象上的运算集合。并定义在这些数据对象上的运算集合

2、。算法：为解决一个问题而采取的方法和算法：为解决一个问题而采取的方法和步骤。步骤。第3页，共44页，编辑于2022年，星期一算法的特性1 1 有穷性有穷性 操作步骤是有限的，不是无限的操作步骤是有限的，不是无限的。2 2 确定性确定性 每个步骤是确定的，无歧义性。每个步骤是确定的，无歧义性。3 3 有零个或多个输入有零个或多个输入4 4 有一个或多个输出有一个或多个输出5 5 有效性有效性 每一步骤能有效执行，并得到确定结果每一步骤能有效执行，并得到确定结果。第4页，共44页，编辑于2022年，星期一3.1.2算法的评价标准1.正确性对任何合法的输入，算法都会得出正确的结果。2.可读性可读性指

3、算法被理解的难易程度。3.健壮性（鲁棒性）健壮性即对非法输入的抵抗能力。4.高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。二者往往是一对矛盾，常常可以用空间换时间，也可以用时间换空间。第5页，共44页，编辑于2022年，星期一 怎样表示一个算法用自然语言表示算法用自然语言表示算法用流程图表示算法用流程图表示算法用用N-S流程图表示算法流程图表示算法用伪代码表示算法用伪代码表示算法用计算机语言表示算法用计算机语言表示算法 歧义性，描述分支、循环算法不方便歧义性，描述分支、循环算法不方便第6页，共44页，编辑于2022年，星

4、期一第7页，共44页，编辑于2022年，星期一起止框起止框输入输出框输入输出框处理框处理框判断框判断框流程线流程线连接点连接点第8页，共44页，编辑于2022年，星期一【例3.1】求三个整数的和。求三个整数和的算法流程图如图所示。开始x+y+z=sum输出sum的值结束输入x,y,z图3.2求三个整数和的算法第9页，共44页，编辑于2022年，星期一【例3.2】求最大公约数。m,n为正整数开始结束输入m,n求m/n的余数rr=0?n=m,r=n输出n是否第10页，共44页，编辑于2022年，星期一最大公因数的算法求最大公因数的最普遍的算法是欧几里得算法，它最初是公元前由欧几里得提出来的，有时也

5、称它为辗转相除法表述如下：设给定m，n(mn)，令r0=m，r1=n，有则得rk=gcd(rk-1，rk)=gcd(rk-2，rk-1)=gcd(r2，r3)=gcd(r1，r2)=gcd(r0，r1)=gcd(m，n)b|a表示b整除a或者a整除以b则a是b的倍数，b是a的约数rk-2=qk-1 qkrk+rk=(qk-1 qk+1)rk第11页，共44页，编辑于2022年，星期一S1:求求12=2S2:求求23=6S3:求求64=24 天啊！共需天啊！共需999个步骤，太可个步骤，太可怕了。怕了。案例案例 求求12341000S1:1 p (p:被乘数被乘数)S2:2 i (i:乘数乘数)

6、S3:pi pS4:i+1 iS5:若若i1000,返回返回S3；否则，结束。；否则，结束。只需只需5个步骤，简单。个步骤，简单。第12页，共44页，编辑于2022年，星期一3.2结构化程序设计的方法结构化程序设计思想采用了模块分解与功能抽象和自顶向下、分而治之的方法，从而有效地将一个较复杂的程序系统设计任务分解成许多易于控制和处理的子程序，便于开发和维护，减少程序的出错概率和提高软件的开发效率。采用结构化程序设计方法应遵循以下原则。1.自顶向下即在程序设计时，先考虑总体，做出全局设计，然后再考虑细节进行局部设计，逐步实现精细化。这种方法称为“自顶向下，逐步细化”的方法。2.模块化就是将一个大

7、任务分成若干个较小的部分，每一部分承担一定的功能，称为“功能模块”。每个模块可以分别编程和调试，然后组成一个完整的程序。模块的划分应遵循一些基本原则，如模块内部联系要紧密，关联程度要高；模块间的接口要尽可能简单，以减少模块间的数据传递。3.限制使用GOTO语句第13页，共44页，编辑于2022年，星期一 结构化的程序设计方法结构化的程序设计方法基本思路基本思路:把一个复杂问题的求解过把一个复杂问题的求解过程分阶段进行程分阶段进行,每个阶段处理的问题每个阶段处理的问题都控制在人们容易理解和处理的范围都控制在人们容易理解和处理的范围内内.采用的方法采用的方法:1 1 自顶而下自顶而下2 2 逐步细

8、化逐步细化3 3 模块化设计模块化设计4 4 结构化编码结构化编码第14页，共44页，编辑于2022年，星期一三种基本结构三种基本结构1 1 顺序结构顺序结构 2 2 选择结构选择结构3 3 循环结构循环结构3.3 程序的基本结构程序的基本结构第15页，共44页，编辑于2022年，星期一三种基本结构的特点三种基本结构的特点1 1 只有一个入口只有一个入口2 2 只有一个出口只有一个出口pA3 3 结构内的每一部分都有机会被执行到结构内的每一部分都有机会被执行到AB4 4 结构内没有死循环结构内没有死循环第16页，共44页，编辑于2022年，星期一顺序结构的流程图符号顺序结构的流程图符号ABab

9、AB传统流程图传统流程图N-S流程图流程图第17页，共44页，编辑于2022年，星期一选择结构的流程图符号选择结构的流程图符号Ap成立不成立BAp成立不成立传统流程图传统流程图第18页，共44页，编辑于2022年，星期一选择结构的流程图符号（续）选择结构的流程图符号（续）成立不成立ApBN-S流程图流程图第19页，共44页，编辑于2022年，星期一循环结构的流程图符号循环结构的流程图符号Ap1成立不成立ab不成立Ap2成立ab传统流程图传统流程图While型型Until型型第20页，共44页，编辑于2022年，星期一循环结构的流程图符号（续）循环结构的流程图符号（续）直到直到p1成立成立A当当

10、p1成立成立AWhile型型Until型型N-S流程图流程图第21页，共44页，编辑于2022年，星期一一个有用的结论一个有用的结论已经证明：已经证明：三种基本结构的三种基本结构的顺序组成顺序组成可以表示任何复杂的算法结构。可以表示任何复杂的算法结构。由基本结构构成的算法，属于由基本结构构成的算法，属于“结结构化构化”算法。算法。第22页，共44页，编辑于2022年，星期一有关结构化算法的总结有关结构化算法的总结一个结构化的算法是由一些基本结构顺一个结构化的算法是由一些基本结构顺序组成的；基本结构之间不存在向前或序组成的；基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个向后的跳转，流

11、程的转移只存在于一个基本结构的范围之内（如循环中的流程基本结构的范围之内（如循环中的流程跳转）；跳转）；一个非结构化算法可以用一个等价的结构化一个非结构化算法可以用一个等价的结构化算法代替，其功能不变。算法代替，其功能不变。如果一个算法不能分解为若干个节本结构，如果一个算法不能分解为若干个节本结构，则它必然不是一个结构化算法。则它必然不是一个结构化算法。第23页，共44页，编辑于2022年，星期一3.4顺序结构程序设计1.表达式语句表达式语句是在各种表达式后加一个分号(；)形成一个表达式语句。2.空语句空语句直接由分号(；)组成，常用于控制语句中必须出现语句之处。它不做任何操作，只在逻辑上起到

12、有一个语句的作用。例如：;空语句也是一个语句，不产生任何动作。空语句常用于构成标号语句，标识程序中相关位置；循环语句中空循环体；模块化程序中未实现的模块及暂不链入的模块。第24页，共44页，编辑于2022年，星期一3.函数调用语句由函数调用加上分号组成。4.复合语句是由一对花括号括起的若干个语句，语法上可以看成是一个语句。复合语句中最后一个语句的分号不能省略。例如下面是一个复合语句：z=x；x=y；y=z;凡是单一语句可以存在的位置，均可以使用复合语句。复合语句用在语法上是单一语句，而相应操作需多条语句描述的情况。第25页，共44页，编辑于2022年，星期一5.控制语句控制语句有条件判断语句(

13、if、switch)，循环语句(for、while、do-while)，转移语句(goto、continue、break、return)。控制语句根据控制条件决定程序的执行流程，控制语句不是顺序执行的。顺序结构是C语言的基本结构，除非指示转移，否则计算机自动以语句编写的顺序一句一句地执行C语句。第26页，共44页，编辑于2022年，星期一C语言无I/O语句，I/O操作由函数实现#include字符输出函数3.5数据的输入与输出格式格式:putchar(c):putchar(c)参数参数:c:c为字符常量、变量或表达式为字符常量、变量或表达式功能：把字符功能：把字符c c输出到显示器上输出到显示

14、器上返值：正常，为显示的代码值；出错，为返值：正常，为显示的代码值；出错，为EOF(-1EOF(-1)第27页，共44页，编辑于2022年，星期一【例3.3】字符数据的输出。#include main()char a,b;a=r;b=e;putchar(a);putchar(b);putchar(d);putchar(n)；运行后，在屏幕上显示：red 第28页，共44页，编辑于2022年，星期一 数据输入数据输入字符输入函数格式格式:getchar():getchar()功能：从键盘读一字符功能：从键盘读一字符返值：正常，返回读取的代码值；出错返值：正常，返回读取的代码值；出错,返回返回EO

15、F(-1)EOF(-1)注意：getchar()函数的括号中没有参数，该函数的输入一直到“回车”才结束。回车前的所有输入字符都会逐个显示在屏幕上，但只有第只有第一个字符作为函数的返回值一个字符作为函数的返回值。第29页，共44页，编辑于2022年，星期一运行时，输入xxx，在屏幕上显示：x【例3.4】单个字符的输入和输出。#include main()char ch;/*从键盘上读入字符直到从键盘上读入字符直到“回车回车”结束结束*/ch=getchar();/*显示输入的第一个字符显示输入的第一个字符*/putchar(ch);putchar(n);/*换行换行*/第30页，共44页，编辑于

16、2022年，星期一【例3.5】将小写字母转换成大写。#include main()char ch;ch=getche();putchar(ch-32);若输入b，在屏幕上显示：bB第31页，共44页，编辑于2022年，星期一3.字符串输入/输出函数字符串输入函数gets()用来从键盘读入一串字符。函数的调用形式：gets(字符串变量名字符串变量名)；在输入字符串后，必须用用回回车车作作为为输输入入结结束束。该回车符并不属于这串字符，由一个“空操作字符(0)”在串的最后来代替它。此时空格不能结束字符串的输入，gets函数返回一个指针。字符串输出函数puts()，将字符串数据(可以是字字符符串串常

17、常量量、字符指针或字符数组名字符指针或字符数组名)显示在屏幕上并换行。函数的调用形式是：puts(字符串数据字符串数据)；第32页，共44页，编辑于2022年，星期一【例3.6】字符串的输入和输出。#include main()char str80;gets(str);puts(str);当输入为“How are you?”，则输出为：How are you?第33页，共44页，编辑于2022年，星期一格式：格式：printf(printf(“格式控制串格式控制串”，输出表，输出表)功能：按指定格式向显示器输出数据功能：按指定格式向显示器输出数据返值：正常，返回输出字节数；出错，返回返值：正常

18、，返回输出字节数；出错，返回EOF(-1)EOF(-1)3.5.3格式输入与输出_格式输出函数输出表：要输出的数据（可以没有，多个时以输出表：要输出的数据（可以没有，多个时以“,”分隔）分隔）格式控制串：包含两种信息格式控制串：包含两种信息格式说明：格式说明：%修饰符修饰符格式字符格式字符 ，用于指定输出格，用于指定输出格式式普通字符或转义序列：原样输出普通字符或转义序列：原样输出格式字符格式字符第34页，共44页，编辑于2022年，星期一d,ix,Xoucse,Efg%格式字符：十六进制无符号整数不带符号十进制整数十进制整数指数形式浮点小数单一字符字符串八进制无符号整数小数形式浮点小数e和f

19、中较短一种百分号本身inta=567;printf(“%d”,a);inta=255;printf(“%x”,a);inta=65;printf(“%o”,a);inta=567;printf(“%u”,a);chara=65;printf(“%c”,a);printf(“%s”,“ABC”);floata=567.789;printf(“%e”,a);floata=567.789;printf(“%f”,a);floata=567.789;printf(“%g”,a);printf(“%”);567ff101567AABC5.677890e+02567.789000567.789%说明格式字

20、符要用小写格式字符与输出项个数应相同，按先后顺序一一对应输出转换:格式字符与输出项类型不一致,自动按指定格式输出例 main()unsignedintu=65535;printf(”u=%dn,u);输出结果：u=-1例 int a=3,b=4;printf(“%d%dn”,a,b);printf(“a=%d,b=%dn”,a,b);例inta=3,b=4;printf(“%d%dn”,a,b);printf(“a=%d,b=%dn”,a,b);输出结果:34a=3,b=411 11 11 11 11 11 11 1165535第35页，共44页，编辑于2022年，星期一格式输入函数格式格式:

21、scanf(:scanf(“格式控制串格式控制串”，地址表），地址表）功能：按指定格式从键盘读入数据，存入地址表指定的功能：按指定格式从键盘读入数据，存入地址表指定的 存储单元中存储单元中,并按回车键结束并按回车键结束返值：正常，返回输入数据个数返值：正常，返回输入数据个数地址表：变量的地址，常用取地址运算符&格式字符:d,i,o,x,u,c,s,f,e例scanf(“%d”,&a);输入：10则a=10例scanf(“%x”,&a);输入：11则a=17第36页，共44页，编辑于2022年，星期一附加格式说明符（修饰符）例scanf(“%4d%2d%2d”,&yy,&mm,&dd);输入19

22、991015则1999yy,10mm,15dd例scanf(“%3d%*4d%f”,&k,&f);输入12345678765.43则123k,8765.43f例scanf(“%2d%*3d%2d”,&a,&b);输入1234567则12a,67b例scanf(“%3c%2c”,&c1,&c2);输入abcde则ac1,dc2l修饰符功能hm*用于d,o,x前，指定输入为short型整数用于d,o,x前，指定输入为long型整数用于e,f前，指定输入为double型实数指定输入数据宽度，遇空格或不可转换字符则结束抑制符，指定输入项读入后不赋给变量第37页，共44页，编辑于2022年，星期一输入分

23、隔符的指定一般以空格、TAB或回车键作为分隔符其它字符做分隔符：格式串中两个格式符间字符例scanf(“%d%o%x”,&a,&b,&c);printf(“a=%d,b=%d,c=%dn”,a,b,c);输入123123123输出a=123,b=83,c=291例scanf(“%d:%d:%d”,&h,&m,&s);输入12:30:45则12h,30m,45s例scanf(“%d,%d”,&a,&b)输入3,4则3a,4b例scanf(“a=%d,b=%d,c=%d”,&a,&b,&c);输入a=12,b=24,c=36第38页，共44页，编辑于2022年，星期一说明：用“%c”格式符时，空格

24、和转义字符作为有效字符输入如 scanf(“%c%c%c”,&c1,&c2,&c3);若输入abc 则ac1,c2,bc3输入数据时，遇以下情况认为该数据结束：遇空格、TAB、或回车遇宽度结束遇非法输入如scanf(“%d%c%f”,&a,&b,&c);若输入1234a123o.26则1234a,ab,123c输入函数留下的“垃圾”：例intx;charch;scanf(“%d”,&x);ch=getchar();printf(“x=%d,ch=%dn”,x,ch);执行：123输出：x=123,ch=10例intx;charch;scanf(“%d”,&x);scanf(“%c”,&ch);

25、printf(“x=%d,ch=%dn”,x,ch);执行：123输出：x=123,ch=10解决方法：（1）用getchar()清除（2）用函数fflush(stdin)清除全部剩余内容(3)用格式串中空格或“%*c”来“吃掉”例intx;charch;scanf(“%d”,&x);getchar();scanf(“%c”,&ch);或scanf(“%*c%c”,&ch);第39页，共44页，编辑于2022年，星期一注意:scanf()函数没有输出功能(即不会向屏幕显示任何字符)也不能规定小数位数(m.n)典型错误:scanf(“a=%d,b=%d,c=%d n”,&a,&b,&c);sca

26、nf(“%5.2f“,&x);正确语句:printf(“Input a,b,c=“);scanf(“%d,%d,%d”,&a,&b,&c);printf(“n”);/*不必要,因为x为实数格式输入*/scanf(“%5f“,&x);第40页，共44页，编辑于2022年，星期一/*求圆的面积和周长*/#define PI 3.14159#include stdio.hmain()float r;float s,l;printf（请输请输入入圆圆的半径的半径:）;scanf（%f,&r）;s=PI*r*r;l=2*PI*r;printf（面面积积=%6.3f,周周长长=%6.3fn,s,l）;输入

27、数据：3 运行结果为：面积=28.274,周长=18.850第41页，共44页，编辑于2022年，星期一【例3.10】编写显示如下界面的程序:学生管理程序 Add追加数据 Modify修改数据 Delete删除数据 Print打印数据 Sort成绩排序 Quit退出程序第42页，共44页，编辑于2022年，星期一/*学生管理程序界面显示学生管理程序界面显示*/#include stdio.hmain()clrscr();printf（%sn,学生管理程序学生管理程序”）;printf（%sn,Add追加数据追加数据 Modify修改数据修改数据”）;printf（%sn,Delete删删除数据除数据 Print打印数据打印数据”）;printf（%sn,Sort成成绩绩排序排序 Quit退出程序退出程序”）;第43页，共44页，编辑于2022年，星期一一个程序应包括两方面内容：1.对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构。2.对操作的描述。即操作步骤，也叫做算法。第44页，共44页，编辑于2022年，星期一