第章算法和基本程序设计ppt课件

1、第3章 算法和根本程序设计 3.1 算法的概念算法的概念 3.2 构造化程序设计方法构造化程序设计方法 3.3 程序的根本构造程序的根本构造 3.4 顺序构造程序设计顺序构造程序设计 3.5 数据的输入输出数据的输入输出 3.6 C程序的上机步骤程序的上机步骤3.1 算法的概念 1.定义: 做任何事情都有一定的步骤。为处理一个问题而采取的方法和步骤，就称为算法。 2.计算机算法可分为两大类： 数值运算算法：求解数值； 非数值运算算法：事务管理领域。一个著名的公式一个著名的公式 数据构造数据构造+ +算法算法= =程序程序 数据：计算机所能识别、存储和数据：计算机所能识别、存储和处置的对象。数据

2、的动态性。处置的对象。数据的动态性。 数据构造：确定数据对象及其存数据构造：确定数据对象及其存储方式，并定义在这些数据对象储方式，并定义在这些数据对象上的运算集合。上的运算集合。 算法：为处理一个问题而采取的算法：为处理一个问题而采取的方法和步骤。方法和步骤。 算法的特性 1 1 有穷性有穷性 操作步骤是有限的，不是无限的。操作步骤是有限的，不是无限的。 2 2 确定性确定性 每个步骤是确定的，无歧义性。每个步骤是确定的，无歧义性。 3 3 有零个或多个输入有零个或多个输入 4 4 有一个或多个输出有一个或多个输出 5 5 有效性有效性 每一步骤能有效执行，并得到确定结果。每一步骤能有效执行，

3、并得到确定结果。 3.1.2 算法的评价规范 1. 正确性 对任何合法的输入，算法都会得出正确的结果。 2. 可读性 可读性指算法被了解的难易程度。 3. 强壮性鲁棒性 强壮性即对非法输入的抵抗才干。 4. 高效率与低存储量需求 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。二者往往是一对矛盾，经常可以用空间换时间，也可以用时间换空间。 怎样表示一个算法用自然言语表示算法用自然言语表示算法用流程图表示算法用流程图表示算法用用N-S流程图表示算法流程图表示算法用伪代码表示算法用伪代码表示算法用计算机言语表示算法用计算机言语表示算法 歧义性，描

4、画分支、循环算法不方便歧义性，描画分支、循环算法不方便起止框起止框输入输出框输入输出框处置框处置框判别框判别框流程线流程线衔接点衔接点 【例3.1】 求三个整数的和。 求三个整数和的算法流程图如下图。开场x+y+z = sum输出sum 的值终了输入x,y,z图3.2 求三个整数和的算法【例3.2】 求最大公约数。m,n为正整数开场终了输入m,n求m/n的余数rr = 0 ?n =m, r =n输出n是否最大公因数的算法求最大公因数的最普遍的算法是欧几里得算法，它最初是公元前由欧几里得提出来的，有时也称它为辗转相除法表述如下：设给定m，n(mn)，令r0=m，r1=n，有 那么得rk=gcd(

5、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 qk rk + rk =(qk-1 qk +1) rk S1: 求求12=2 S2: 求求23=6 S3: 求求64=24 天啊！共需天啊！共需999个步骤，太可个步骤，太可怕了。怕了。案例案例 求求12341000 S1: 1 p (p:被乘数被乘数) S2: 2 i (i:乘数乘数) S3: pi p S4: i+1 i S5: 假设假设i1000,前往前往S3；否那么，

6、终了。；否那么，终了。 只需只需5个步骤，简单。个步骤，简单。3.2 构造化程序设计的方法 构造化程序设计思想采用了模块分解与功能笼统和自顶向下、分而治之的方法，从而有效地将一个较复杂的程序系统设计义务分解成许多易于控制和处置的子程序，便于开发和维护，减少程序的出错概率和提高软件的开发效率。 采用构造化程序设计方法应遵照以下原那么。 1. 自顶向下 即在程序设计时，先思索总体，做出全局设计，然后再思索细节进展部分设计，逐渐实现精细化。这种方法称为“自顶向下，逐渐细化的方法。 2. 模块化 就是将一个大义务分成假设干个较小的部分，每一部分承当一定的功能，称为“功能模块。每个模块可以分别编程和调试

7、，然后组成一个完好的程序。模块的划分应遵照一些根本原那么，如模块内部联络要严密，关联程度要高；模块间的接口要尽能够简单，以减少模块间的数据传送。 3. 限制运用GOTO语句 构造化的程序设计方法构造化的程序设计方法 根本思绪根本思绪: 把一个复杂问题的求解过程把一个复杂问题的求解过程分阶段进展分阶段进展,每个阶段处置的问题都控制每个阶段处置的问题都控制在人们容易了解和处置的范围内在人们容易了解和处置的范围内. 采用的方法采用的方法: 1 自顶而下自顶而下 2 逐渐细化逐渐细化 3 模块化设计模块化设计 4 构造化编码构造化编码三种根本构造三种根本构造 1 1 顺序构造顺序构造 2 2 选择构造

8、选择构造 3 3 循环构造循环构造3.3 程序的根本构造程序的根本构造三种根本构造的特点三种根本构造的特点 1 1 只需一个入口只需一个入口 2 2 只需一个出口只需一个出口pA 3 3 构造内的每一部分都有时机被执行到构造内的每一部分都有时机被执行到AB 4 4 构造内没有死循环构造内没有死循环顺序构造的流程图符号顺序构造的流程图符号ABabAB传统流程图传统流程图N-S流程图流程图选择构造的流程图符号选择构造的流程图符号Ap成立不成立BAp成立不成立传统流程图传统流程图选择构造的流程图符号续选择构造的流程图符号续成立不成立ApBN-S流程图流程图循环构造的流程图符号循环构造的流程图符号Ap

9、1成立不成立ab不成立Ap2成立ab传统流程图传统流程图While型型Until型型循环构造的流程图符号续循环构造的流程图符号续直到直到p1成立成立A当当p1成立成立AWhile型型Until型型N-S流程图流程图一个有用的结论一个有用的结论 曾经证明：曾经证明： 三种根本构造的顺序组成可以三种根本构造的顺序组成可以表示任何复杂的算法构造。表示任何复杂的算法构造。 由根本构造构成的算法，属于由根本构造构成的算法，属于“构造化算法。构造化算法。有关构造化算法的总结有关构造化算法的总结 一个构造化的算法是由一些根本构造顺一个构造化的算法是由一些根本构造顺序组成的；根本构造之间不存在向前或序组成的；

10、根本构造之间不存在向前或向后的跳转，流程的转移只存在于一个向后的跳转，流程的转移只存在于一个根本构造的范围之内如循环中的流程根本构造的范围之内如循环中的流程跳转；跳转； 一个非构造化算法可以用一个等价的构一个非构造化算法可以用一个等价的构造化算法替代，其功能不变。造化算法替代，其功能不变。 假设一个算法不能分解为假设干个节本假设一个算法不能分解为假设干个节本构造，那么它必然不是一个构造化算法。构造，那么它必然不是一个构造化算法。3.4 顺序构造程序设计 1. 表达式语句 表达式语句是在各种表达式后加一个分号(；)构成一个表达式语句。 2. 空语句 空语句直接由分号(；)组成，常用于控制语句中必

11、需出现语句之处。它不做任何操作，只在逻辑上起到有一个语句的作用。例如： ; 空语句也是一个语句，不产生任何动作。空语句常用于构成标号语句，标识程序中相关位置；循环语句中空循环体；模块化程序中未实现的模块及暂不链入的模块。 3. 函数调用语句 由函数调用加上分号组成。 4.复合语句是由一对花括号 括起的假设干个语句，语法上可以看成是一个语句。复合语句中最后一个语句的分号不能省略。例如下面是一个复合语句： z = x； x = y； y =z; 凡是单一语句可以存在的位置，均可以运用复合语句。复合语句用在语法上是单一语句，而相应操作需多条语句描画的情况。 5. 控制语句 控制语句有条件判别语句(i

12、f、switch)，循环语句(for、while、do-while)，转移语句(goto、continue、break、return)。控制语句根据控制条件决议程序的执行流程，控制语句不是顺序执行的。 顺序构造是C言语的根本构造，除非指示转移，否那么计算机自动以语句编写的顺序一句一句地执行C语句。 5C言语无I/O语句，I/O操作由函数实现5 #include 5字符输出函数3.5 数据的输入与输出 格式格式: putchar( c ): putchar( c )参数参数: c: c为字符常量、变量或表达式为字符常量、变量或表达式功能：把字符功能：把字符c c输出到显示器上输出到显示器上返值：

13、正常，为显示的代码值；出错，为返值：正常，为显示的代码值；出错，为EOF(-1)EOF(-1)【例3.3】 字符数据的输出。#include main( ) char a, b; a=r; b=e; putchar(a); putchar(b); putchar(d); putchar(n)；运转后，在屏幕上显示：red 数据输入数据输入字符输入函数字符输入函数 格式格式:getchar( ):getchar( )功能：从键盘读一字符功能：从键盘读一字符返值：正常，前往读取的代码值；出错返值：正常，前往读取的代码值；出错, ,前往前往EOF(-1)EOF(-1)留意：getchar()函数的括

14、号中没有参数，该函数的输入不断到“回车才终了。回车前的一切输入字符都会逐个显示在屏幕上，但只需第一个字符作为函数的前往值。 运转时，输入xxx ，在屏幕上显示：x【例3.4】 单个字符的输入和输出。#include main() char ch; /*从键盘上读入字符直到“回车终了*/ ch= getchar(); /*显示输入的第一个字符*/ putchar(ch); putchar(n); /*换行*/【例3.5】 将小写字母转换成大写。#include main( ) char ch; ch=getche( ); putchar(ch-32);假设输入b，在屏幕上显示： bB 3. 字符

15、串输入/输出函数 字符串输入函数gets() 用来从键盘读入一串字符。函数的调用方式： gets(字符串变量名)；在输入字符串后，必需用回车作为输入终了。该回车符并不属于这串字符，由一个“空操作字符( 0 )在串的最后来替代它。此时空格不能终了字符串的输入，gets函数前往一个指针。字符串输出函数puts()，将字符串数据(可以是字符串常量、字符指针或字符数组名)显示在屏幕上并换行。函数的调用方式是： puts(字符串数据)；【例3.6】 字符串的输入和输出。#include main( ) char str80; gets(str); puts(str);当输入为“How are you?，

16、那么输出为：How are you?格式：格式：printf(printf(“格式控制串，输出表格式控制串，输出表) )功能：按指定格式向显示器输出数据功能：按指定格式向显示器输出数据返值：正常，前往输出字节数；出错，前往返值：正常，前往输出字节数；出错，前往EOF(-1)EOF(-1)3.5.3 格式输入与输出_格式输出函数 输出表：要输出的数据可以没有，多个时以输出表：要输出的数据可以没有，多个时以“,分隔分隔 格式控制串：包含两种信息格式控制串：包含两种信息 格式阐明：格式阐明： %修饰符修饰符格式字符格式字符 ，用于指定输，用于指定输出格式出格式 普通字符或本义序列：原样输出普通字符或

17、本义序列：原样输出 格式字符格式字符d,ix,Xoucse,Efg%格式字符：十六进制无符号整数不带符号十进制整数十进制整数指数方式浮点小数单一字符字符串八进制无符号整数小数方式浮点小数e和f中较短一种百分号本身int a=567;printf ( “%d,a);int a=255;printf(“%x,a);int a=65;printf(“%o,a);int a=567;printf(“%u,a);char a=65;printf(“%c,a);printf(“%s,“ABC);float a=567.789;printf(“%e,a);float a=567.789;printf(“%f

18、,a);float a=567.789;printf(“%g,a);printf(“%);567ff101567AABC5.677890e+02567.789000567.789% 阐明 格式字符要用小写 格式字符与输出项个数应一样，按先后顺序一一对应 输出转换:格式字符与输出项类型不一致,自动按指定格式输出例 main() unsigned int u=65535; printf(u=%dn,u); 输出结果：u=-1例 int a=3,b=4; printf(“%d %dn,a,b); printf(“a=%d , b=%dn,a,b); 例 int a=3,b=4; printf(“%d

19、 %dn,a,b); printf(“a=%d , b=%dn,a,b);输出结果: 3 4 a=3, b=411 11 11 11 11 11 11 1165535 格式输入函数格式格式: scanf(: scanf(“格式控制串，地址表格式控制串，地址表功能：按指定格式从键盘读入数据，存入地址表指定的功能：按指定格式从键盘读入数据，存入地址表指定的 存储单元中存储单元中, ,并按回车键终了并按回车键终了返值：正常，前往输入数据个数返值：正常，前往输入数据个数 地址表：变量的地址，常用取地址运算符& 格式字符:d,i,o,x,u,c,s,f,e例 scanf(“%d,&a);

20、 输入：10 那么 a=10例 scanf(“%x,&a); 输入：11 那么 a=17 附加格式阐明符修饰符例 scanf(“%4d%2d%2d,&yy,&mm,&dd); 输入 20191015 那么2019yy, 10 mm, 15 dd例 scanf(“%3d%*4d%f,&k,&f); 输入 12345678765.43 那么123k, 8765.43f例 scanf(“%2d %*3d %2d,&a,&b); 输入 12 345 67 那么12a, 67b例 scanf(“%3c%2c,&c1,&c2)

21、; 输入 abcde 那么ac1, d c2l修饰符功 能hm*用于d,o,x前，指定输入为short型整数用于d,o,x前，指定输入为long型整数用于e,f前，指定输入为double型实数指定输入数据宽度，遇空格或不可转换字符那么终了抑制符，指定输入项读入后不赋给变量 输入分隔符的指定 普通以空格、TAB或回车键作为分隔符 其它字符做分隔符：格式串中两个格式符间字符例 scanf(“%d%o%x,&a,&b,&c); printf(“a=%d,b=%d,c=%dn,a,b,c); 输入 123 123 123 输出 a=123,b=83,c=291例 scanf(“

22、%d:%d:%d,&h,&m,&s); 输入 12:30:45 那么12 h, 30 m, 45 s例 scanf(“%d,%d,&a,&b) 输入 3,4 那么3a, 4 b例 scanf(“a=%d,b=%d,c=%d,&a,&b,&c); 输入 a=12,b=24,c=36 阐明： 用“%c格式符时，空格和本义字符作为有效字符输入如 scanf(“%c%c%c,&c1,&c2,&c3); 假设输入a b c 那么ac1, c2, b c3 输入数据时，遇以下情况以为该数据终了： 遇空格、TAB、或回车

23、 遇宽度终了 遇非法输入如 scanf(“%d%c%f,&a,&b,&c); 假设输入1234a123o.26 那么 1234 a, a b, 123 c 输入函数留下的“渣滓：例 int x; char ch; scanf(“%d,&x); ch=getchar(); printf(“x=%d,ch=%dn,x,ch);执行：123输出：x=123,ch=10例 int x; char ch; scanf(“%d,&x); scanf(“%c,&ch); printf(“x=%d,ch=%dn,x,ch);执行：123输出：x=123,ch=10处理方法：1用getchar()去除2用函数fflush(stdin)去除全部剩余内容 (3) 用格式串中空格或“%*c来“吃掉例 int x; char ch; scanf(“%d,&x); getchar(); scanf(“ %c,&ch);或 scanf(“%*c%c,&ch); 留意: scanf( )函数没有输出功能(即不会向