程序的控制结构及结构化程序设计方法.pptVIP

3.1 算法与算法的表示方法 3.2 顺序结构程序设计 3.3 选择结构程序设计 3.4 循环结构程序设计 第三章 程序的控制结构与 结构化程序设计方法 3.1 算法与算法的表示方法 本章主要内容： 1.了解算法的表示方法及其在程序设计中的重要地位. 2.掌握 C 语言的基本控制结构和基本控制语句. 3.掌握用 C 语言的基本控制语句进行顺序，选择和 循环结构程序的设计. 4.掌握一些常用的算法,如递推法,迭代法,穷举法等. 5.了解结构化程序设计的基本思想 算法分类： 数值运算算法：解决的是求数值解的问题。 非数值运算算法：主要解决关于分析推理、逻辑推理等 问题，如排序、查找等。 3.1.1 算法的概念 数据结构 + 算法 = 程序 数据结构：对数据的描述和组织形式， 算法：对操作或行为的描述，即操作步骤。 算法为解决一个具体问题而采取的确定的有限的操 作步骤。 2、控制结构：操作序列的顺序控制。 三种基本控制结构，即： 顺序结构、选择结构、循环结构。 3.1.1 算法的概念 算法的组成要素： 1、操作：各种运算。 如：算术运算、逻辑运算、关系运算等。 算法的特性： 1、有穷性：在有限的时间内，操作步骤能够终止。 2、确定性：每一步操作的含义必须明确。 3、有效性：每一步都应当能有效地进行并得到确定的结果。 4、有0个或多个输入。 5、有1个或多个输出。 3.1.1 算法的概念 例1：求12345。 算法一： S1：求12 ，得2； S2：将S1得的2再乘3，得6； S3：将S2得的6再乘4，得24； S4：将24再乘5，得120，结果。 算法二： S1：p=1 S2：i=2 S3：p =pi S4：i=i+1 S5：若i5，返回S3， 否则结束，得出结果 p为5！。 比较两个算法： 算法一：繁琐，数目大时步骤太多。 算法二：利用循环算法，借助两个变量，可求任意数的阶乘，提高通用性。 3.1.2 简单算法举例 3.1.2 简单算法举例 例2： 求1+2+3+4+100 算法： S1：n=1 S2：s=0 S3：s=s+n S4：n=n+1 S5：若n 100，返回到S3 ， 否则结束。 1+3+5+7+99 2+4+6+8+100 思考： S1：n=1 S2：s=0 S3：s=s+n S4：n=n+2 S5：若n 5为假 打印p main( ) int i,p; p=1; i=2; do p=p*i; i=i+1; while(i 注： 编译预处理命令不是C语 句，每条指令单独占一行， 同一行不能有其它的编译指 令或C语句。 3.2 顺序结构程序设计 C程序结构框架: 以#开始的编译预处理命令行 main( ) 局部变量说明语句; 执行语句序列; 包含头文件的方式：#include #include “文件名” 3.2 顺序结构程序设计 例3.2：任意从键盘输入一个三位整数，要求正确分离出它的 个位、十位、百位数，分别在屏幕上输出。 算法： Step 1：输入一个三位整数x； Step 2：计算最高位b2=x100； Step 4：计算最低位b0=x%10 或 b0=xb2100b110； Step 3：计算中间位b1=(xb2100) 10 或 b1=(x10)%10； Step 5：输出分离结果； 程序见eg3_2 3.2 顺序结构程序设计 例3.3：编程计算方程ax +bx+c=0的根，a，b，c 由键盘输入， 假设b -4ac 0。 2 2 分析： 一元二次方程的求根公式： 3.2 顺序结构程序设计 算法： Step 4：输出x1和x2； Step 1：输入a，b，c； 2 Step 2：计算判别式disc = b - 4ac； Step 3：由于以假设判别式0，所以可直接按求根公式 计算两个实根x1和x2； 程序见eg3_3 返回 n 选择结构的应用场合 n 计算一元二次方程 ax +bx+c=0的根 n b - 4ac0 有两个不相等的实根 n b - 4ac=0 有两个相等的实根 n b - 4ac 0 y= 1 x = 0 -e x 0 3.3 选择结构程序设计 n选择结构的流程图表示 P AB 真假 N-S 流程图 P AB 入口 出口 传统流程图 真假 3.3 选择结构程序设计 n选择结构种类 n单分支的选择结构 n双分支的选择结构 n多分支的选择结构 嵌套的if语句或switch语句 3.3 选择结构程序设计 nif else 形式 if（表达式）语句1 else 语句2 适合于解决双分支选择问 题 表达式 语句 假 真 表达式 语句2 真假 语句1 n 条件语句 n if 形式 if(表达式) 语句A 适合于解决单分支选择问题 3.3 选择结构程序设计 nelseif 形式 if（表达式1） 语句1 else if（表达式2） 语句2 else if（表达式m） 语句m else 语句m+1 适合于解决多分支选 择问题 表达式1 表达式2 表达式3 语句3语句2语句1语句4 真 真 真 假 假 假 3.3 选择结构程序设计 n例3.4 从键盘输入你和你朋友的年龄，编程判断谁的年龄 最大，并打印他的年龄。 N-S流程图： 读入 yours，his Y yours=his N 输出yours hisyours Y N 输出his 程序见eg3_4_1 n算法1: 用不带else子句的if语句编程。 3.3 选择结构程序设计 n算法2: 用带有else子句的if语句编程。 N-S流程图： 读入 yours，his Y yours=his N 输出yours 输出his 程序见eg3_4_2 3.3 选择结构程序设计 n算法3: 用条件表达式实现。 条件表达式： 表达式1 ? 表达式2 : 表达式3 N-S流程图： 读入 yours，his Y yours=his N max=yours max=his 输出max 程序见eg3_4_3 3.3 选择结构程序设计 n 例3.5 体型判断。判断某人是否属于肥胖，可根据身高 与体重等因素来判断，按照“体指数”对肥胖程度进行 划分： 体指数t = 体重w /（身高h ） （其中，w单位为kg，h单位为m） 当 t27 时，为肥胖。 2 3.3 选择结构程序设计 n算法1：用不带else子句的if语句编 程。 N-S流程图： 程序见eg3_5_1 n算法2：用在if子句中嵌入if语句的形式编程。 输入身高h和体重w 计算体指数t t0，则计算并输出两个不相等的实根： x1=p+q，x2=p-q； Step6：若disc=0，则计算并输出两个相等的实根： x1=x2=p； Step7：若discmagic，则给出提示：“Wrong！Too high！” Step4：如果guess100)printf(“input error.”); else if(score=90)printf(“%dAn”,score); else if(score=80)printf(“%dBn”,score); else if(score=70)printf(“%dCn”,score); else if(score=60) else printf(“%dDn”,score); printf(“%dEn”,score); 3.3 选择结构程序设计 方法二：用switch语句编写程序 main（） int score, mark； printf(“please enter score:”);scanf(“%d”, if(score 100)printf(“input error.”); else mark=score/10; switch( mark ) case 10: case 9: case 8: case 7: case 6: case 5: case 4: case 3: case 2: case 1: case 0:printf(“%dEn”,score); break; printf(“%dAn”,score); break; printf(“%dBn”,score); break; printf(“%dCn”,score); break; printf(“%dDn”,score); break; 3.3 选择结构程序设计 n例3.9 编程设计一个简单的计算器程序，要求根据用户从键 盘输入的表达式： 操作数1 运算符 操作数2 来计算表达式的值，指定的运算符为:加( + )、减( - )、 乘( * )、除( / )。 程序见eg3_9 返回 3.3 选择结构程序设计 3.4 循环结构程序设计 n循环结构的应用场合 用于需要重复执行的操作步骤和相应算法。 n 计算: 1+2+3+n n 计算: n! = 123n n 计算 e 的近似值 直到最后一项的绝对值小于10 时认为满足精度要求。 -5 n 以二维表形式打印乘法九九表 n循环结构的流程图表示 n直到型循环结构n当型循环结构 A P 假(0) 真(非0) 当 P 为 真 A A 直到 P 为真 3.4 循环结构程序设计 A P 假(0) 真(非0) n循环语句 循环语句在给定条件成立的情况下，重复执行某 个程序段。 当循环体是空语句（只有一个分号）时，表示在 循环体中什么也不做。 重复执行的程序段称为循环体，循环体可以是 单个C语句、空语句或复合语句。 n三种循环语句 while 语句、do-while 语句、for 语句 3.4 循环结构程序设计 nwhile 语句 （用来实现当型循环） 一般形式为： while（表达式） 循环体语句 ndo-while 语句 （用来实现直到型循环） 一般形式为： do 循环体语句 while（表达式）; 3.4 循环结构程序设计 nfor 语句 （用来实现当型循环结构） 一般形式为： for（表达式1；表达式2；表达式3） 循环体语句 其中： 1) 表达式1 的作用是初始化循环控制变量，即为循环控制变量赋 初值； 2) 表达式2 的作用是给出循环重复执行的判断条件，这个条件用 于决定什么时候结束循环的执行； 3) 表达式3 的作用是使循环控制变量发生变化，即通过循环变量 的变化使表达式2的条件趋于不成立。 3.4 循环结构程序设计 n注意 n for语句与while语句都用于实现当型循环结构，二者是完全等价的， 与for 语句等价的while语句形式为： 表达式1； while（表达式2） 循环体语句 表达式3 ； n 当需要使多个变量的值发生变化时，表达式3 也可以用逗号表达式。 例：for (i=1，j=100；i=j；i+，j-) sum=sum+i+j； n 当需要为多个变量赋初值时，表达式1 可以用逗号表达式顺序地执 行为多个变量赋初值的操作。 n 三个表达式可以是任何合法的C语言表达式。 n 表达式中的任何一个都可以省略不写，但分号不能省略不写。 n 三个表达式之间用分号隔开。 3.4 循环结构程序设计 n单重循环问题应用举例 单重循环问题常用于解决累加求和、累乘求积、统计求 和这类问题。 n循环次数已知 （一般用for语句实现） n循环次数未知 （一般用while语句或do-while语句实现） n例3.10: 将3.7的猜数游戏改为：先由计算机“想”一个1到 100之间的数请人猜，如果人猜对了，则游戏结束，否 则计算机给出提示，告诉人所猜的数是大还是小，直 到人猜对为止。计算机记录人猜的次数，以此来反映 猜数者“猜”的水平。 3.4 循环结构程序设计 n算法设计如下： 1. 通过调用随机函数任意“想”一个数magic; 2. 将记录人猜次数的计数器变量count初始化为0; 3. 输入人猜的数guess; 4. 计数器变量count加1; 5. 如果人猜的数guess大于计算机想的数magic,则给出 “错误,太大!”的提示信息;如果人猜的数guess小于计 算机想的数magic,则给出“错误,太小!”的提示信息; 6. 如果人猜的数guess不等于计算机想的数magic,则重 复执行步骤3到步骤5,直到guess等于magic为止,给出 “正确” 的提示信息后转去执行步骤7; 7. 打印人猜的次数count。 3.4 循环结构程序设计 程序见eg3_10 n例3.11 计算n!=123n 程序见eg3_11_1用while语句实现: 用do-while语句实现:程序见eg3_11_2 用for语句实现:程序见eg3_11_3 3.4 循环结构程序设计 n例3.12 国王的允诺。 问题分析： sum=12222 2363 算法1用for语句实现:程序见eg3_12_1 算法2用for语句实现:程序见eg3_12_2 3.4 循环结构程序设计 n 例3.13 利用/4=1-1/3+1/5-1/7+计算 的值，直到最后一项 的绝对值小于10 为止，要求统计总共累加了多少项。 - 4 用do-while语句实现:程序见eg3_13_1 用for语句实现: 程序见eg3_13_3 3.4 循环结构程序设计 n例3.14 从键盘输入一个班学生（人数不确定）一门课的五 分制成绩，统计并打印每种成绩的人数。 问题分析 采用符号#作为输入结束标志，并用switch语句对 成绩进行分类处理。 程序见eg3_14_e用while语句实现: 3.4 循环结构程序设计 改进程序：程序见eg3_14 3.4 循环结构程序设计 例3.15 水手分椰子。五个水手在一个岛上发现一堆椰子，现由 第一个水手把椰子分为等量的5堆，剩下的1个给猴子，并自 己藏起一堆，然后第二个水手把剩下的4堆混合后重新分为等 量的5堆，剩下的1个给猴子，自己藏起一堆。以后第三个、 第四个水手依次同样处理。最后，第五个水手把剩下的椰子 分为等量的5堆后，同样剩下1个椰子给猴子，问原来这堆椰 子至少有多少个？ 程序见eg3_15 n嵌套循环及其应用举例 n嵌套循环：将一个循环语句用于另一个循环语句的循环体。 n常用于：矩阵运算、报表打印等问题。 n注意事项： 1、在嵌套的各层循环体中,使用复合语句（即用一对大 括号将 循环体语句括起来）保证逻辑上的正确性。 2、内层和外层循环控制变量不应重名，以免造成混乱。 3、嵌套的循环最好采用右缩进格式书写，以保证层次的 清晰。 4、嵌套循环不能交叉，即在一个循环体内必须完整地包 含着 另一个循环。 3.4 循环结构程序设计 n例3.16 编程输出如下形式的乘法九九表。 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 2 4 6 8 10 12 14 16 18 3 6 9 12 15 18 21 24 27 4 8 12 16 20 24 28 32 36 5 10 15 20 25 30 35 40 45 6 12 18 24 30 36 42 48 54 7 14 21 28 35 42 49 56 63 8 16 24 32 40 48 56 64 72 9 18 27 36 45 54 63 72 81 3.4 循环结构程序设计 nN-S图 3.4 循环结构程序设计 程序见eg3_16 打印表头 被乘数n从1变化到9 乘数n从1变化到9 输出第m行n列中的m*n的值 输出换行符 n例3.17 将上例输出格式改写为如下的下三角格式打印。 1 2 3 4 5 6 7 8 9 - - - - - - - - - 1 2 4 3 6 9 4 8 12 16 5 10 15 20 25 6 12 18 24 30 36 7 14 21 28 35 42 49 8 16 24 32 40 48 56 64 9 18 27 36 45 54 63 72 81程序见eg3_17 3.4 循环结构程序设计 n介绍两种典型的算法迭代法和穷举法 一、迭代法：是一个不断用新值取代变量旧值或由旧值递 推出变量新值的过程。 用循环结构实现迭代，重复操作的内容是不断从一个 变量的旧值出发计算它的新值。 迭代与下列因素有关： 初值； 迭代公式； 迭代次数：精度 3.4 循环结构程序设计 n 迭代法举例 典型问题： （1）求两个数据的最大公约数； （2）Fibonacci数列； （3）一元方程的迭代解法：二分法 3.4 循环结构程序设计 定义 u , v , r, w 输入u,v 是 uv 否 w=u; u=v; v=w r=u%v 当 r!=0 u=v; v=r; r=u%v 输出 v main() int u,v,r,w; scanf (“%d %d“, if (u v) w=u; u=v; v=w; r=u%v; while (r != 0) u=v; v=r; r=u%v; printf (“%d n“, v); 例1: 求两个数u,v的最大公约数。 算法：辗转相除法。 3.4 循环结构程序设计 算法：迭代。 f1=1，f2=1 f3=f1+f2，f4=f2+f3， fn=fn-1+fn-2 迭代方法： f1=1 f2=1 f=f1+f2 f1=f2 f2=f 迭代 1 1 2 3 5 8. f1 f2 f1 f f f2 n例2: 求Fibonacci数列:1,1,2,3,5的前20个数。 数列中从第三项开始，每项为其前两项之和。 3.4 循环结构程序设计 程序见Fibonacci.c 例3: 用二分法求一元二次方程 2x3-4x2+3x-6=0 在(-10,10) 之间的根。 3.4 循环结构程序设计 算法：采用用迭代 x0 = (x1+x2)/2 若f(x1)与f(x0)同号：x1=x0 若f(x2)与f(x0)同号：x2=x0 x1 x2x0 x2 x0 x1 x yf(x) x2 x1 程序见half_separate.c 二、穷举法：是一种重复性算法，其基本思想是对问题所 有可能状态一一测试，直到找到解决或全部状态测试完 成为止。 两种控制方法： （1）计数法：用循环变量控制循环次数，完成指定次数， 循环结束。 （2）标志法：次数不定，达到某一目标（标志），循环 结束。如：遇到某个值、n、EOF等。 3.4 循环结构程序设计 常见问题： 1、不定方程求解问题：如百钱买百鸡，鸡免同笼等； 2、打印图形； n例1: 百钱买百鸡问题。 问题：100钱买100只鸡（包括公鸡、母鸡和小鸡）， 公鸡1只5钱，母鸡1只3钱，小鸡1只三分之一 钱，求公鸡、母鸡和小鸡的个数。 根据问题有：公鸡+母鸡+小鸡=100 5公鸡+3母鸡+1/3小鸡=100 3.4 循环结构程序设计 n算法： 定义 cocks,hens,chicks for cocks=0 to 19 for hens=0 to 33 chicks=100-cocks-hens 5*cocks+4*hens+chicks/3= =100 输出cocks,hens,chicks 是 否 程序见 cocks.c 3.4 循环结构程序设计 n例2:打印图形： * * * * 定义 i, j, k for i = 1 to 4 for j = 1 to 4-i 输出一个空格 for k = 1 to 2*i-1 输出一个* 换行 程序见triangle.c 3.4 循环结构程序设计 n 转移控制语句 用于控制流程转向的跳转语句。 1、goto语句 无条件转向语句。一般形式： goto 语句标号； 语句标号： 或 语句标号: goto 语句标号; 3.4 循环结构程序设计 2、break语句 用于switch结构和循环语句的结构体中。 当执行循环体遇到break语句时，循环将立即终止，从循 环语句后的第一条语句开始继续执行。 while（表达式1） for ( ; 表达式1 ;) if ( 表达式2 ) break ; if ( 表达式2 ) break ; 循环的下一条语句 循环的下一条语句 3.4 循环结构程序设计 3、continue语句 continue；（结束本次循环，进行下一次循环） while (表达式1) if (表达式2）continue； . while (表达式1) if (表达式2）break； . break； （跳出switch或跳出本次循环体） 3.4 循环结构程序设计 n使用break语句和continue语句时注意： n由 if 和 goto 语句构成的循环，不能用 break 和 continue 语句进行流程控制。 n在嵌套循环的情况下，break 语句和 continue 语句只对包 含它们的最内层的循环语句起作用。 for() while (表达式1) if (表达式2）break； . for() while (表达式1) if (表达式2）continue； . 3.4 循环结构程序设计 nbreak语句和continue语句的用法举例 例:break.c 例: contiue.c 3.4 循环结构程序设计 n例3.19 任意从键盘输入一个正整数，编程判断它是否是素数， 若是素数，输出“Yes！”，否则输出“No！”。 算法： Step 1：从键盘输入一个正整数。 Step 2：计算k= ； Step 3：i 从2变化到 k ，依次检查 m%i 是否为0； Step 4：若 m%i 为0，则判定 m 不是素数，并终止对其 余i值的检验，否则，令i=i+1；并继续对其余i值 进行检验，直到全部检验完毕为止，这时判定m 是素数。 3.4 循环结构程序设计 eg3_19_1 方法1：用goto语句实现。 eg3_19_2 eg3_19_3 方法2：用break语句实现。 方法3：采用设置变量并加强循环测试的方法。 3.4 循环结构程序设计 n例3.20 在上例的基础上，若m不是素数，则打印其所有因子， 否则，打印“没有因子，是素数”的提示信息。 程序见eg3_20 返回 3.4 循环结构程序设计 3.5 结构化程序设计简介 结构化程序设计（简称SP）的概念是由荷兰学者提出的。 现在人们已经认识到程序设计的任务不只是编写出一个能得到 正确结果的程序，还应考虑程序的质量。否则将会使程序质量 低下、可靠性差、开发周期长、维护费用高这就是我们常 说的“软件危机”，它严重地阻碍了计算机应用的发展。 结构化程序设计思想： 1、采用顺序结构、选择结构和循环结构作为程序设计的基 本单元，尽量避免使用goto语句。 2、三种基本结构应