第3章_控制语句.doc

第3章算法设计的基本方法教学目的：通过本章的学习，使学生掌握算法的基本知识，了解关系运算与逻辑运算，学会使用选择结构和循环型结构进行程序设计。知识点：1.算法的概念、特点及描述2.判断（关系运算与逻辑运算）3.选择型程序设计4.循环型程序设计重点：1.算法的描述2关系运算符和关系表达式3逻辑运算符和逻辑表达式4条件运算符及条件表达式5IF语句的格式使用难点：复杂条件的表示；IF语句的正确使用。3.1算法 程序是计算机的灵魂 算法是程序的灵魂一个程序应包括两个方面的内容: 著名计算机科学家沃思提出一个公式: 数据结构 + 算法 = 程序 对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm)完整的程序设计应该是:数据结构算法程序设计方法语言工具3.1.1 算法的组成要素和基本性质（1） 算法的概念解决问题的一种方法或过程的描述，（是对特定问题求解步骤的一种描述。）一个问题可能有多种算法对应。或算法是由一系列操作组成的。（2）算法的组成要素ü 操作：与问题和所用的工具有关。ü 控制结构：每一个算法都要由一系列的操作组成。同一操作序列，按不同的顺序执行，就会得出不同的结果。控制结构即如何控制组成算法的各操作的执行顺序。控制结构：顺序控制结构：语句是按照书写顺序执行的，也就是语句的执行顺序与书写顺序一致。只有这种结构不可能处理复杂问题。u 选择控制结构：当程序执行到某一条语句时，要进行某种判断，从两支或多分支选择其中一条执行。u 循环控制结构：将一条或多条语句重复执行若干次。有了选择和循环控制结构，就可以设计复杂大型的程序了。(3)算法的性质ü 效性：算法所规定的操作都应能有效执行的。ü 定性：描述的操作应当具有明确的含义；序列中只有一个初始动作，每一动作仅有一个后继动作；序列终止表示问题得到解答或问题没有解答，不能没有任何结论。ü 穷性：所规定的操作序列必须在允许的时间内结束。ü 输入ü 输出3.1.2算法的描述工具ü 1） 流程图方法：用一些图框表示各种类型的操作，用线表示这些操作的执行顺序。过程判断数据预定义过程起止流程线连接注释举例：用流程图描述从3个数据中取最大数的算法。a>=b输入a,b,cmax=a真假max=bmax>=c真假输出max输出c开始结束i<=3输入一个n假真假输出max开始结束max=0，i=1真i+n>=maxmax=nü 2） NS图l 方法：每一种基本结构都是一个矩形框，整个算法可以像堆积木一样堆成。S1S2S3PS1S2当PS假真（c）当型重复结构（a）顺序结构 （b）选择结构举例：用NS图描述从3个数据中取最大数的算法。算法1(使用选择结构)a>=bmax=amax=b输入a，b，c假真max>=c输出max输出c真假算法2(使用循环结构)当i<=3i+n>=maxmax=n真假输入n初始化：max=0，i=1输出maxü 3） 伪代码l 举例：用伪代码描述从3个数据中取最大数的算法。算法1(使用选择结构)输入a,b,c；if(a>=b)max=a;else max=bif(max>=c) 输出max;else 输出c；算法2(使用循环结构)初始化：max=-32768,i=1;当（i<=3）( 输入n; i+; if(n>=max) max=n;)输出max;3.1.3结构化程序设计方法由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。一个结构化程序 就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维护。结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。 构化程序设计方法的基本思路是：把一个复杂问题的求解过程 分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。 模块设计的方法：模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。模块一般不超过50行。分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。3.2判断3.2.1命题的“真”、“假”与C语言中的逻辑值ü 逻辑（布尔）值：“真”或“假”ü 早期的C语言不提供专门的逻辑（布尔）类型，规定用非0值表示“真”，用0值表示“假”。这样，不管任何表达式，只要其值为非0（包括负数），就说明其为“真”；只要其值为0，就说明其为“假”。ü 在C99中，增加了_Bool类型，并增加了头文件<stdbool.h>，在其中定义了宏bool、true和false，用true存储1，用false存储0。关系表达式和逻辑表达式是C语言中描述命题的两种基本形式。3.2.2关系运算与关系表达式ü 关系运算符 (左结合） > >= < <= = != 较高 较低ü 关系表达式u 用关系运算符将运算对象连接成的式子 例如：12< 'C'+1 （字符型数据比较ASCII值） a=b>=c 等价于 a = ( b>=c ) 与 (a=b)>=c 不等价ü 关系运算符优先于赋值，低于算术 说明：u 关系运算的结果应该是逻辑值。C语言用数值用 1 表示逻辑真， 0 表示逻辑假例如： 7>5 的值是 1，5>7 的值是 0 'a'>'b'的值是 0， 'a'<'b' 的值是1即关系表达式的值：0 或1 u 实型数可进行大于或小于比较，但通常不进行 = 或 != 的关系运算。void Msort(int SR,int s,int t)3.2.3逻辑运算与逻辑表达式ü 逻辑运算符 && | ！ ü 逻辑运算符的运算规则 运算对象逻辑运算结果aba&&ba | b!a非0非0110非000100非001100001u 逻辑表达式l 用逻辑运算符将运算对象连接成的式子。 例如：0&&'b' a &&b | c&&d a | b-5 | c/4 !x+y >= z u 逻辑运算符的优先级和结合性：l !是单目运算符，右结合，高于算术l && 和 | 是双目运算符，左结合，高于赋值运算符，低于关系运算符。逻辑运算规则从左到逻辑进行逻辑计算l 运算对象为非0表示逻辑真l 运算对象为 0 表示逻辑假逻辑运算的结果为 0 或 1例如设：a=15，b=0，c=-2 a && b && c 结果为0 a | b | c 结果为1 (a+c) | b && c 结果为1u 运算按照从左至右的顺序进行，一旦能够确定逻辑表达式的值，就立即结束运算关系与逻辑运算符的应用u 表示数学公式a>b>c ：a>b && b>cu 判断a, b, c三条线段能否组成一个三角形：a+b>c && a+c>b && b+c>au a, b不同时为负3.3选择型程序设计选择型程序描述了这样的求解规则：在不同的条件下所应进行的相应操作。3.3.1 ifelse结构1）双分支结构l 语句一般格式if （表达式） 语句1 else 语句2 l 功能：计算表达式的值，如果它的值是一个非0值（逻辑真），就执行内嵌语句1，之后跳过内嵌语句2，执行后续语句；否则跳过内嵌语句1，执行内嵌语句2，之后执行后续语句。 算法描述 表达式非0 T F 语句1 语句2N-S结构图 语句1 语句2流程图NY表达式非0？例求一个数的绝对值。2）单分支结构l 语句一般格式if （表达式） 语句l 功能：计算表达式的值，如果是一个非0值（即逻辑真），就执行内嵌语句，否则（即逻辑假）跳过内嵌语句，顺序执行后续语句。 l 算法描述 表达式非0 T F 语句N-S结构图语句流程图NY表达式非0？l 例如：u if (x>0) m+; u if ( a>b ) c=a; a=b; b=c; u 求3个数中最大数 z>xmax=z（空）max = x假真y>xmax=y（空）真假z>y真假return(max)3）if语句的嵌套如果if的内嵌语句中又使用了一个if语句，则构成if语句的嵌套。 比较两个整数的关系。 #include <stdio.h>main( ) int x, y; printf ("Enter integer X and Y:"); scanf ("%d%d", &x, &y); if ( x != y ) if ( x > y ) printf ("X>Yn"); else printf ("X<Yn"); else printf ("X=Yn");应该正确判断： if的内嵌语句 if和else的配对提倡缩格书写有利于阅读程序if语句嵌套的形式 简单if语句的嵌套形式 if (表达式) if 语句 双重（或多重）分支if语句的嵌套形式 if (表达式) if 语句 else if 语句 规则：在嵌套的ifelse语句中，else总是与上面的离它最近的尚未配对的if 配对。3.3.2 ifelse if结构l 语句一般格式if （表达式1） 语句1 else if （表达式2） 语句2 else if （表达式m） 语句m else 语句 nl 功能依次计算并判断表达式i，为非0时执行后面的语句，都为0时，执行语句n无论执行完那个语句分支，都转到后续语句l 流程图表达式2?表达式1?语句n 语句1 语句2 语句mYNYNNYl 例3.6 根据百分制分数决定成绩的等级： · 80分以上为A级； · 70分及以上，80分以下，B级； · 60分及以上，70分以下，C级； · 60分以下，D级。真假score>=80score>=70等级A真假输入scorescore>=60等级B等级D等级Cinclude <stdio.h>int main(void) float score; printf(“Input a scre:”); scanf(“%f”,&score); if (score >= 80) printf (%f is An,score); else if (score >= 70) printf (%f is Bn,score); else if (score >= 60) printf (%f is Cn,score); else printf (%f is Dn,score); return 0;3.3.3 switch结构l 语句一般格式switch （表达式） case 常量表达式1: 语句序列1 case 常量表达式2: 语句序列2 case 常量表达式n: 语句序列n default : 语句序列n+1 功能u 计算表达式的值，与常量表达式的值比较，等于第i个值时，顺序执行语句序列i、i+1、 、 n+1。u 若与所有常量表达式值都不相等，执行语句序列n+1。流程图表达式语句序列1常量表达式1:语句序列2常量表达式2:语句序列i常量表达式i:语句序列n常量表达式n:语句序列n+1default图3.16 switch控制结构1注意：u 一个switch结构的执行部分是一个由一些case子结构与一个可缺省的default子结构组成的复合语句，它们位于一对花括号之中。u switch的判断表达式只能对整数求值，可以使用字符或整数，但不能使用浮点表达式。case表达式应当是整型常数表达式，不能含有变量与函数的常数表达式u switch语句的书写格式：语句体本身必须用花括号括起；case和default后面如果有多条语句，则可以不必使用花括号；case和常量表达式之间必须有空格；default可以写在语句体的任何位置，也可以省略不写;u break语句可以改变case的语句标号作用，终止后续case语句序列的执行。 switch语句和break语句结合，可以实现程序的选择控制（break语句还可以在循环语句中使用）;u 允许switch嵌套使用，但同一个switch语句中，任意两个case的常量表达式值不能相同。u 一个switch结构中不可以出现两个具有相同值的常量表达式。u switch的匹配测试，只能测试是否相等，不能测试关系或逻辑。switch结构允许嵌套。3.3.4条件表达式l 语句一般格式表达式1？表达式2：表达式3功能若表达式的值为真(非0)，则以表达式2的值作为该条件表达式的值；否则取表达式3的值作为该条件表达式的值。3.4循环型程序设计3.4.1迭代与穷举算法（1）迭代是一个不断用新值取代变量的旧值，或由旧值递推出变量的新值的过程。例：人口增长问题。 按年0.2%的增长速度，现有13亿人，10年后将有多少人?分析：设现人口数为m，则第1年后人口变为： m = m*(1+0.2%) 即将m的值用m*(1+2%)替代。 兔子繁殖问题。Fibonacci曾提出一个有趣的问题：设有一对新生兔子，从第三个月开始它们每个月都生一对兔子。按此规律，并假设没有兔子死亡，一年后共有多少对兔子。 人们发现每月的兔子数组成如下数列： 1，1，2，3，5，8，13，21，34， 并把它称为Fibonacci数列。分析：每个月的兔子数由两部分组成：上一月的老兔子数，这一月刚生下的新兔子数。上一月的老兔子数即其前一个数。这一月刚生下的新兔子数恰好为上上月的兔子数。算法可以描述为 fib1=fib2=1 (1) fibn=fibn-1+fibn-2 (n=3) (2) 式(1)为赋初值，式(2)为迭代公式。用C语言来描述式(2)为：fib=fib1+fib2；fib1=fib2; /* 为下一次迭代作准备*/fib2= fib;一元方程的迭代解法。 一元方程f(x)=0， 5次以上的方程找不出通用的根的解析表达式。在这种情况下，人们不得不求助于一些近似解法。方法：· 二分迭代法· 牛顿迭代法（2）穷举ü 迭代是一个不断用新值取代变量的旧值，或由旧值递推出变量的新值的过程。ü 循环控制有两种办法：计数法与标志法。输入10个数，将最大的一个数打印出来。 S1：输入1个数，暂时作为擂主最大数。S2：输入9个数穷举这9个数，每输入一个，打一次擂台把最大数与刚输入的数据进行比较，把大者作为新擂主最大数。S3：输出最大数。例3.16 百钱买百鸡问题。 cocks+hens+chicks=100(1)5*cocks+3*hens+chicks/3=100(2)cocks: 019中的整数(因为每只鸡翁5钱，因此它不可能超过19只)hens: 033中的整数chicks: 0100中的整数3.4.2 while循环结构（1）格式while (表达式) 循环体语句（2） 执行流程循环体在执行while语句时，先对判断表达式进行计算，若其值为真(非0)，则执行循环体语句；否则跳过循环体，而执行该结构后面的语句。在进入循环体后，每执行完一次循环体语句后，再对判断表达式进行一次计算和判断。当发现判断表达式的值为0时，便立即退出循环。（3） 例 计算人口增长的C程序。例3.18 Fibonacci算法C语言的程序实现。例3.20 输入多个数，输出其中最大者的C程序。3.4.3 dowhile结构（1）格式do循环体while (表达式)；当流程到达do后，立即执行循环体一次，然后才对判断表达式进行计算、测试。若表达式的值为真(非0)，则重复执行一次循环体；否则退出。与while结构相比，dowhile结构至少要执行一次循环体。这样的结构应用在需要事先执行一次循环体的程序非常容易理解。（3）例 3.4.4 for结构（1）格式 for (表达式1；表达式2；表达式3)循环体for (初始化表达式；判断表达式；修正表达式) 循环体（2）执行流程 1) 先执行表达式1（初始化表达式）。注意在整个循环中它只执行一次。 2) 重复下面的过程：计算表达式2(判断表达式)，若为真(非0)，就执行一次循环体语句，然后再执行表达式3（修正表达式）；再计算表达式2(判断表达式)，判断是否为“真”，直至表达式2(判断表达式)的值为假(0)，就不再执行循环体了。3.4.5 循环嵌套一个循环体内又包含另一个完整的循环结构称为循环的嵌套。内嵌的循环中还可以嵌套循环，这就是多层循环。三种循环(while循环、do-while循环和for循环)可以互相嵌套。嵌套形式： 3.4.6循环结构的中途退出与重复周期的中途结束（1）break语句 break语句可以用来从循环体内跳出循环体，即提前结束循环，接着执行循环下面的语句 一般形式： break;注意:break语句不能用于循环语句和switch语句之外的任何其他语句中。 （2）continue语句提前结束一个循环周期continue语句3.4.7几种循环的比较(1)四种循环都可以用来处理同一问题。(2)在while和do-while循环中,应在循环体中包含使循环趋于结束的语句。for可以在表达式3中包含使循环趋于结束的操作。 (3) 循环变量初始化的操作应在while和do-while语句之前完成。而for可以在表达式1中实现循环变量的初始化(4)while、do-while和for循环，可以用break语句跳出循环，用continue语句结束本次循环。而对用goto构成的循环，不能用break语句和continue语句进行控制。