程序设计C语言-预备知识.ppt

,第二级,第三级,第四级,第五级,程序设计,C,语言,第1,章 预备知识,第,1,章 预备知识,1.1,计算机内的数据表示,1.2,数的定点和浮点表示,1.3,简单的逻辑运算,1.4,程序的概念,1.5,算法,1.1,计算机内的数据表示,数据形态多种多样，凡是计算机能够处理的对象都称为数据，如文字数据、图形数据、声音数据等。但不管其表象多么复杂，多么千差万别，只要一归入计算机处理，都全部地统一为二进制数据，也就是说，数据在计算机内是以二进制,(,即用数字,0和1),来表示的。在计算机中为什么要用二进制,?,采用二进制有哪些优点,?,以下就是问题的答案。,(1),二进制表示数字在物理上容易实现。,计算机内部用电子器件的状态来表示数字信息。一种数制有多少种不同的数字，电子器件就需要多少种不同的状态。二进制只有数字,0和1,，因此它只需要由两个稳定状态的电子元件就,可以表示了，而十进制则需要由,10,个不同稳定状态的电子元件来表示。,(2),二进制运算规则简单。,二进制求和的规则有：,0+0=0,0+1=1+0=1,1+1=10,二进制求积的规则有：,00=0,01=10=0,11=1,(3),采用二进制可以用逻辑代数作为设计分析的工具。,二进制中用,0和1,可以表示是与非、高与低等，这恰恰是逻辑代数中的内容。,(4),用二进制可以节约存储设备。,比如要表示,0999这1000,个数时，十进制要用三位数，需,310=30,个状态设备量，,而用十位二进制数可表示,1024,个数，则只需,210=20,个状态设备量。,1.1.1,数的二进制、十进制、八进制和十六进制表示,常用的数制有二进制、十进制、八进制和十六进制，它们有共性也有差别。,1.,数码及进位法则,数码是构造一种数制所用的不同符号。各种进制的数码为：,二进制：,0，1,十进制：,0，1，2，3，4，5，6，7，8，9,八进制：,0，1，2，3，4，5，6，7,十六进制：,0，1，2，3，4，5，6，7，8，9，,A(a),B(b),C(c),D(d),E(e),F(f),2.,位置计数法,数据中各个数字所处的位置决定它的大小即权值，同样的数字在不同位置上代表的权值是不同的。比如：,22.2=210,1,+210,0,+210,-1,其中,10,1,10,0,10,-1,就是该位置的权值。,1.1.2,数制转换,我们日常习惯使用的是十进制，但在计算机中用的却是二进制，所以需要把十进制转换成二进制。但二进制书写麻烦，因此通常用八进制和十六进制表示，这样就存在各种数制之间的转换问题。,1.,将十进制转换成二进制,把十进制的整数和小数转换成二进制时所用的方法不同，因此应该分别进行转换。,(1),用余数法将十进制整数转换成二进制整数。把十进制整数不断地用,2,去除，将所得到的余数,0或1,依次记为,K,0,K,1,K,2,，,直到商是,0,为止，将最后一次所得的余数记为,K,n,，,则,K,n,K,n-1,K,1,K,0,即为该整数的二进制表示。在演算过程中可用竖式形式，也可用线图形式。,例,11 (59),10,=(),2,=(,K,n,K,1,K,0,),2,竖式演算如下：,2 59,余数,1=,K,0,2 29,余数,1=,K,1,2 14,余数,0=,K,2,2 7,余数,1=,K,3,2 3,余数,1=,K,4,2 1,余数,1=,K,5,0,(59),10,=(K,5,K,4,K,3,K,2,K,1,K,0,),2,=(111011),2,(2),用进位法将十进制小数转换成二进制小数。把十进制小数不断地用,2,去乘，将所得乘积的整数部分,0或1,依次记为,K,1,K,2,K,3,。,一般情况下十进制小数并不一定都能用有限位的二进制小数表示，可根据精度要求，转换成一定位数即可。,例,12 把0.47,转换成二进制。,用线图形式可演算如下：,0.470.940.880.760.520.04,2 ,整数,0 1 1 1 1,K,-1,K,-2,K,-3,K,-4,K,-5,在取,5,位小数时有,(0.47),10,=(,K,-1,K,-2,K,-3,K,-4,K,-5,),2,=(0.01111),2,(3),在把十进制转换成二进制时，熟记一些,2,的幂次的十进制及二进制值能加快转换速度,。表,11,中列出了一些,2,的幂次所对应的十进制和二进制数。,表11 2,的幂次所对应的二进制和十进制数,在转换时，可找出小于但最接近该十进制整数的某个,2,的幂次，减去这个幂次，再在减后的数中找小于且最接近该数的,2,的幂次,。2的,n,次方的二进制数的特点是,1,后跟有,n,个0,，利用这一点就能迅速地把二进制数的长度确定，然后在相应的位置上填上,1或0,即可。比如,(1287.25),10,=1024+256+4+2+1+0.25,=2,10,+2,8,+2,2,+2,1,+2,0,+2,-2,=(10000000000+100000000+100+10+1+0.01),2,=(10100000111.01),2,例,13 (30000),10,=(),2,;,计算,30000,除以,1024,得商,29,，余数为,304,，将商和余数分别用,2,的幂次之和的形式表示：,商：,29=16+8+4+1=2,4,+2,3,+2,2,+2,0,余数：,304=256+32+16=2,8,+2,5,+2,4,则(30000),10,=102429+304=2,10,(2,4,+2,3,+2,2,+2,0,)+2,8,+2,5,+2,4,=2,14,+2,13,+2,12,+2,10,+2,8,+2,5,+2,4,=(111010100110000),2,2.,将二进制转换成十进制,把二进制数按多项式展开求和即可。,(101.101),2,=(12,2,+02,1,+12,0,+12,-1,+02,-2,+12,-3,),10,=(14+11+10.5+10.125),10,=(5.625),10,1.1.3,原码、反码和补码,在计算机中，位,(,bit),是最小的单位，通常用来表示由二进制位组成的信息长度；把,8,位二进制位定义为一个字节,(,Byte)，,计算机中的存储量就是按字节来计算的；计算机内部数据处理的基本单位称为字,(,word)，,它通常也是输入,/,输出设备和存储器之间传递数据的基本单位，每个字所包含的位数称为字长。,在计算机中，不仅数值用,0和1,表示，而且正负号也用,0和1,表示。一般规定在一个存储单元的最高位,(,最左边的一位,),为符号位，如该位是,0,表示正，该位是,1,表示负。在计算机中，带符号的数通常有三种表示方法：原码、反码和补码。为简单起见，下,面我们只考虑用一个字节表示整数时的原码、反码和补码。,1.,原码,原码是一种机器数，原码表示法就是在机器中最高位用,0,表示正数，用,1,表示负数，而其余位表示数本身。例如：,+15,的原码为：,00001111,代表正,-15,的原码为：,10001111,代表负,+0,的原码为：,00000000,-0,的原码为：,10000000,2.,反码,在反码表示法中，正负数的表示是不同的。正数的反码和原码是一样的，如：,+15,的反码仍然是,00001111,负数的反码为：符号位为,1,，其他各位是对原码求反。如：,-15,的反码为,11110000,数值,0,的反码有两种：,+0,的反码为,00000000,-0,的反码为,11111111,即在反码表示法中，,0,的表示仍然不惟一。,图,11,时钟示例,3.,补码,鉴于以上情况，计算机内部采用补码方法来表示数值。采用补码方法的好处是简化设计与计算，能把减运算转变为加运算来进行。,我们以时钟为例来说明补码的原理。比如现在的标准时间是,6,点，而你的表停在,11,点的位置，如图,11,所示。要调准你的表可用两种方法：,向前拨,7,格；,向后拨,5,格。,不管采用哪种方法，都能达到目的，可谓殊途同归。但从算式上来看：,11+7=18(,向前拨,),11-5=6(,向后拨,),计算结果并不一样，那么操作结果为什么会一样呢,?,这是因为表盘的刻度是以,12,为周期的，超过,12,就又从头计数，因此上面的计算结果,18,因超过了,12,，再从头开始计数,后也就得到了,6,。,在计算机中是以一个有限长度的二进制位作为模，比如用一个字节表示一个数，则其模数为,2,+8,。如运算结果超过,2,+8,，就从中减去,2,+8,。反映在内存中，其情况为：,1,即把,8,位以外的数舍掉。,计算机中的补码是这样定义的：,正数：其补码与其原码、反码相同。例如：,+15,补,=+15,原,=+15,反,=00001111,+127,补,=,+127,原,=,+127,反,=01111111,00000000,负数：最高位为,1,，其余各位在原码的基础上取反，然后在最低位加,1,，简称“求反加,1”,。可用如下关系式 表示：,x,补,=,x,反,+1,注意各位取反时不包括符号位，即符号位不求反。例如：,-15,原,=10001111 -127,原,=11111111 -0,原,=10000000,-15,反,=11110000 -127,反,=10000000 -0,反,=11111111,-15,补,=11110001 -127,补,=10000001 -0,补,=00000000,表,12,补码的生成,1.2,数的定点和浮点表示,1.2.1,定点数的取值范围,定点数的表示格式是,.,符号占,1,位，数值可有多位，小数点的位置在符号位之后、数值部分的最高位之前，但不占实际位数，例如,:,01011,表示,0.1011,，是个正数,11011,表示,1.1011,，是个负数,符号,数 值,设定点计算机的字长是,9,位，其中一位是符号位，另,8,位是数值位，则该计算机所能表示的数的绝对值范围是：,0.000000010.11111111,或写成：,2,-8,1-2,-8,一般地，若定点计算机的字长是,n,位，其中一位是符号位，则它所能表示的数的绝对值范围是：,2,-(,n-1),1-2,-(n-1),(,数值位最低位为,1,，其余位皆为,0)(,数值位各位全是,1),1.2.2,浮点数的取值范围,在计算机中，浮点数由四部分表示：阶符、阶码、数符,(,尾符,),和数码,(,尾数,),。其格式为：,阶,符,阶,码,数,符,数码,对浮点机来说，总是规定数码部分的最高位是,1,，,也就是：,例,14,对用,32,位表示的浮点数，设阶码部分为,8,位，尾数部分为,24,位，各含,1,位符号位，求它所能表示的数的绝对值范围和有效数字位数。先标出取最大、最小值时在内存中各位的表示。,最小值：当阶码负最大、数码最小时，即,1,1 1 1 1 1 1 1,0,1 0 0 0 0,所表示的数值为：。,最大值：当阶码正最大、数码最大时，即,0,1 1 1 1 1 1 1,0,1 1 1 1 1 1,所表示的数值为：,。,由此知其范围为：,或,2,-128,2,127,(1-2,-23,),这是以,2,为基数的表示，如何表示成以,10,为基数的呢,?,因为尾数部分不大于,1,，所以数的大小主要是由阶码部分决定的。令阶码,2,127,等于十进制数,10,x,，,即设,2,127,=10,x,.,如能把,x,求出来，即可转换到十进制范围。对等式两边取对数：,127,lg2=x,因为,lg20.3，,所以,x0.312738,令2,-128,=10,y,，,则,y=-128lg2-1280.3-38,因此在十进制情况下，这种有,7,位阶码的浮点数的取值范围为：,10,-38,10,38,。,浮点数的尾数部分决定数的精度。,23,位数码的最大值为,2,24,-12,24,。,令,2,24,=10,x,(,二进制的,24,位相当于十进制的,x,位),，,则,x=24lg2240.37,一般情况下尾数达不到最大值，但也在,2,23,和2,24,之间，对,2,23,，设有,2,23,=10,y,可求出,y=23lg2230.3=6.9,取,y=6，,即相当于十进制的,6,位。因此对尾数是,24,位的浮点数，其有效数字为,67,位。,1.2.3,整数的取值范围,用一定位数表示整数，带符号位和不带符号位表示的数值范围是不同的。设用,8,位表示一个整数，其中最高位是符号位，则表示数值的位有,7,位，当,7,位全是,1,时绝对值最大：,符号,1,1,1,1,1,1,绝对值为,2,7,-1,一般地有,|,N|2,7,-1=127,对无符号数，最高位仍是数值位，则其最大值为,8,位全是,1,的时候：,1,1,1,1,1,1,1,数值为,2,8,-1,，一般地有,0,N2,8,-1=255,如有,n+1,位二进制数，则,带符号时，它所表示的绝对值范围为,|,N|2,n,-1,不带符号时，它所表示的数的范围为,0,N2,n+1,-1,1.3,简单的逻辑运算,1.3.1 “,或”、“与”、“非”运算,在逻辑演算中，逻辑连接词又称为逻辑运算符，它的运算对象都是真或假的命题。如果一个运算符需要两个运算对象，就称为双目运算符；如果只对一个运算对象进行运算，则称为单目运算符。逻辑运算符共有,4,个：逻辑“非”、逻辑“与”、逻辑“或”和逻辑“异或”。其中第一个是单目运算符，后三个是双目运算符。我们这里只介绍前三个运算符。,1.,逻辑“或”,(加),运算符,OR,逻辑或运算的情况类似于一个并联开关，如图,12,所示。只要有一个开关接通，电路就接通，电灯就会发亮。若灯泡亮用“,1”,表示，暗用“,0”,表示；,A、B,表示两个逻辑变量，接通用“,1”,表示，断开用“,0”,表示；结果用“,F”,表示，则可以写出如下函数关系：,F=A OR B,结果,F,的值也可能是,0,或,1,。,图12,逻辑或运算的物理示意图,变量,A、B,都可以取,0或1,中任一个值，这样当它们连接起来的时候就会有不同的组合，在各种组合情况下，结果值是什么呢,?,为了清楚地反映结果值与各变量取值间的关系，我们可以用一个表来显示，这样的表就称为“真值表”，真值表反映了因变量与自变量之间,的状态关系。逻辑或运算的真值表为：,A B,F,0 0,1 0,0 1,1 1,0,1,1,1,即：,0,OR 0=0,1 OR 0=1,0 OR 1=1,1 OR 1=1,2.,逻辑“与”,(乘),运算符,AND,与运算符的作用相当于一个串联开关，如图,13,所示。只有当两个开关同时连通时，电灯才会发亮，其关系式为：,F=A AND B,其真值表为：,A B,F,0 0,1 0,0 1,1 1,0,0,0,1,即：,0,AND 0=0,1 AND 0=0,0 AND 1=0,1 AND 1=1,图13,逻辑与运算的物理示意图,3.,逻辑“非”,(,否定,),运算符,NOT,逻辑“非”又称为逻辑否定，它把一个命题改换成相反的含义，其作用类似于反相开关电路，如图,14,所示。当开关接通时，电灯泡由亮变暗；断开时，电灯泡由暗变亮。其关系式为：,F=NOT A,A,F,0,1,1,0,即：,NOT 0=1,NOT 1=0,图14,逻辑非运算的物理示意图,1.3.2,真值表,上面我们介绍了三种逻辑运算符，逻辑运算符和逻辑运算对象相结合构成的式子称为逻辑表达式。在程序设计中我们需要的是逻辑表达式而不是一个孤零零的命题。然而在实际应用中，我们却往往不知道其逻辑表达式，只知道一些具体的要求。这时我们可以首先根据具体要求列出其真值表，然后再根据真值表写出逻辑表达式，这就是真值表的重要意义所在。,例,15,一个房间住了三个人：甲、乙、丙，求下列条件下房间内无人说话的表达式。,(1),甲从来不说话；,(2),当且仅当甲在场时乙才说话；,(3),丙在任何情况下都说话。,编程思路：首先用三个变量,A、B、C,表示甲、乙、丙三人以便于书写，并且规定其值为,1,时表示在房间，为,0,时表示不在房间。结果,F,为1,时表示房间内无,人说话，为,0,时表示有人说话。,第一步：根据条件，列出真值表：,A B C,F,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,1,0,1,0,1,0,0,0,第二步：根据真值表列出逻辑表达式。,关键是把,F,值为,1,的各种情况收集起来，用或运算符连接，表示只要有一种情况发生，就说明房间内无人说话。考虑,F=1,的各种取值：,(1),由真值表中第一行知，,A=B=C=0,时,F=1，,变量本身代表真，变量的否定代表假，则上述条件表示为：,(,NOT A)AND(NOT B)AND(NOT C),解释为：,A,不在场并且,B,不在场并且,C,也不在场，此时房间内无人说话。,(2),由真值表第三行知，,A=C=0,B=1,时,F=1，,这可以表示为：,(,NOT A)AND B AND(NOT C),解释为：,A,不在场但是,B,在场并且,C,不在场，此时房间内无人说话。,(3),由真值表第五行知，当,A=1,B=C=0,时,F=1，,这可表示为：,A AND（NOT B)AND (NOT C),解释为：,A,在场但,B,不在场并且,C,不在场，此时房间内无人说话。,逻辑运算符的优先级：,NOT,最高，,AND,次之，,OR,最低。,把上面三个表达式用,OR,运算符连接起来，即为所求的逻,表达式：,F=(NOT A)AND(NOT B)AND(NOT C)OR,(NOT A)AND B AND(NOT C)OR,(A AND (NOT B)AND(NOT C),1.4,程序的概念,一个程序是一个由指令组成的序列。指令就是行为或动作。从这个意义上说，程序在计算机发明以前很久就有了。比如弹奏乐曲的乐谱、厨师做菜的食谱、某项工程实施的计划等都可以说是程序，只是计算机的程序更复杂，更需要仔细而精细地进行编写而已。程序要由编程者来编写，并由执行者来实施。实现指令称为执行或运行程序。运行中的程序称为进程。程序是静态的概念，而进程是动态的概念。,1.4.1,程序的特性,所有程序,(,包括计算机程序,),都有一些共同的性质，这些性质主要包括以下几点：,(1),指令是顺序执行的。,(2),程序的执行都有一个结果。,(3),程序总是要对某些对象进行操作。,(4),有的程序要加入对操作对象的说明。,(5),有时指令要求执行者做出判断。,(6),一条或一组指令可能需要执行多次。,1.4.2,计算机程序的执行过程,程序是一种手段，程序的编写者利用程序来和执行者进行通信。通信就需要语言，不同的场合可以用不同的语言来表示程序。比如用自然语言交待任务、下达命令，但大多数程序设计需要一种特殊的语言。对计算机下达任务的语言就是计算机语言。,计算机语言有高级语言和低级语言之分，但这种高低之分并没有贵贱之别，有区分主要是因为它们对计算机硬件的接近程度不同。,低级语言主要是指机器语言,(,二进制语言,),和汇编语言，它们离计算机硬件最近。用机器语言写的指令都是由,0和1,组成的符号序列，计算机能直接识别和执行，因而速度很快。,但这种指令写起来繁琐复杂，非专业人士不能为之。汇编语言是符号化的二进制语言，它用英文单词或其缩写来表达指令，执行速度也很快，但却受具体机器系统的制约。,执行高级语言程序分为两个阶段：第一个阶段称为编译阶段，第二个阶段称为运行阶段。在程序执行的过程中可能会出现三种类型的错误：,(1),编译错误。这是在编译阶段发生的错误，主要是使用语言的语法不合规范所引起的错误。,(2),运行错误。这种错误在编译时发现不了，只在运行时才显现出来。如对负数开平方，除数为,0,，循环终止条件永远不能达到等，这种错误常会引起无限循环或死机。,(3),逻辑错误。这种错误即使在运行时也显示不出来，因程序能正常运行，但结果不对,。,图15,高级语言源程序的执行过程,1.5,算法,程序设计离不开算法，算法指导程序设计，算法是程序的灵魂。程序是语句的集合，但如何围绕所要解决的任务来安排这些语句的次序则是由算法决定的。因此程序设计的大致步骤如下：,(1),确定算法和数据结构。算法是和具体任务有关的，而数据结构则是程序要处理的数据的组织。,(2),把算法以明晰的方法表示出来，如用流程图、,NS,图、伪码等方法。,(3),在算法已明确表示出来的基础上用高级语言编制程序。,1.5.1,算法的特点,算法，简单地讲，就是解决问题的流程安排，即先做什么，后做什么。精确地讲，算法是被精确定义的一系列规则，这些规则规定了解决特定问题的一系列操作顺序，以便在有限步骤内产生出所求问题的解答。尽管算法因求解问题的不同而千变万化、简繁各异，但它们都必须具备以下五个特性。,1.,确定性,算法的每一步运算都必须有确切的定义，即每种运算所执行的操作都必须是确定的、无二义性的。,2.,能行性,算法中有待实现的运算方法都必须是可执行的，即在执行者,(,计算机,),能力范围之内并能在有限时间内完成。,3.,有穷性,一个算法必须在执行了有穷的步骤之后结束。,4.,输入,一个算法可以有,0,个或,0,个以上的输入，可提供算法操作的数据。,5.,输出,一个算法总能产生一个或多个输出，即算法的计算结果。,1.5.2,算法的表示,一个算法应该用明晰的方法展现在人们的面前，这样才易于用计算机语言写出体现算法的程序。,表示一个算法，通常有以下四种方法：,1.,自然语言描述法,比如求三个数的最大值问题，用自然语言可以描述为：先将两个数,a,和,b,进行比较，找出其最大者，然后再把它和第三个数,c,进行比较，如果它比第三个数大，则它就是最大数，,否则第三个数,c,就是最大数。,所谓伪码就是类似于程序设计语言的语句，但又不是任何一种真实的程序设计语言的语句，它不涉及程序设计的具体细节。比如求三个数的最大值问题，用伪码可表示为：,if ab,then,把,a,交给,max,else,把,b,交给,max,if maxc,then,输出最大值,max,else,输出最大值,c,3.,NS,图表示法,这是一种图语言表示法，其特点是在一个矩形框内完成算法的流程说明。比如求三个数最大值的问题，用,NS,图可描述为如图,16,所示的形式。,图16,求三个数的最大值问题,4.,流程图表示法,这也是一种图语言表示法，它用一些不同的图例来表示算法的流程。常用的图例主要有如图,17,中所示的几种。,图17,流程图表示法常用图例,图18,求三个数的最大值问题的流程图表示,1.5.3,结构化程序设计的三种基本结构,20,世纪,60,年代，在开发大型软件的过程中出现了所谓的“软件危机”，其主要表现是：开发进度被推迟；成本超出预算；软件产品不可靠。人们认识到软件开发要比想象的复杂得多。在如何克服“软件危机”的讨论和研究中，诞生了“结构化程序设计”的概,念，这是编写出清晰、正确和容易理解的程序的一种指导方针和严格方法。,结构化程序设计的基本方法是：在设计程序时，本着从上到下、逐步求精的原则，将一个大的原始问题分解为多个可独立进行编程的小问题,(,即小模块,),，如果某个模块还未精细到能直接进行编程的程度，则继续对它进行分解，直至能直接编程为止。每个模块只有一个入口和一个出口，这样不管编多大的程序，不管有多少人参加编写，都可以把他们,的模块很自然地连接起来。,在结构化程序设计方法中，有三种基本的控制结构。这三种基本结构是：顺序结构、选择结构和循环结构。,顺序结构是指语句的执行顺序和它在程序中出现的次序是一致的，即一条语句执行完后紧接着执行它下面的那条语句。,选择结构是根据一定的条件，把语句分成不同的分支，程序只执行其中一个分支，而不执行其他分支。,循环结构是根据一定的条件，对某些语句重复执行。被重复执行的语句称为循环体。重复执行的次数可以预指定，也可以不指定，而由循环体中的变化所决定。,这三种基本结构，可以用图表示法说明。,1.用,NS,图表示,(1),顺序结构：,A,执行完后接着执行,B。,(2),选择结构：,A,B,P,T,F,A,B,(3),循环结构：,循环结构有下面两种图示：,只要,P,为真就执行,A：,P,A,P,为条件。,执行,A,直到,P,为真为止：,A,P,2.,用流程图表示,(1),顺序结构，如图,19,所示。,(2),选择结构，这里又有如下三种形式：,if,结构,(,单路选择结构,),，如图,110,所示。,if/else,结构,(,双路选择结构,),，如图,111,所示。,switch,结构,(,多路选择结构,),，如图,112,所示。,图,112,的意思是：当某个,P,i,为真时，执行相应的语句,A,i,，,然后退出选择语句,(,通过,break,语句实现,),。,图19,顺序结构的,流程图,图110,if,结构的流,程图表示,图111,if/else,结构的,流程图表示,图112,switch,结构的流程图表示,(3),循环结构：,循环结构也有三种形式：,while,结构，如图,113,所示。,do/while,结构，如图,114,所示。,和,的区别在于，这里是先执行语句,A，,然后再判断条件,P。,for,结构，如图,115,所示。,图113,while,结构的,流程图表示,图114,do/while,结构的,流程图表示,图115,for,结构的流程图表示,从上面各图中可以看出，每一个结构只有一个入口和一个出口。按顺序来组织各种控制结构就能设计出结构化的程序，即只要把一个控制结构的出口点和另一个控制结构的入口点连接起来即可。,结构化程序设计的规则有,4,条：,(1),从最简单的流程图开始；,(2),任何矩形框都可以被两个按顺序放置的矩形框取代；,(3),任何矩形框都可以被任何结构取代；,(4),规则,(2),和规则,(3),可按任何顺序运用多次。,图116,从最简结构出发反复使用规则,(2),和规则,(4),图,117,中的虚线框就是对图,116,中一个矩形框的细化。用规则,(4),可以产生更大的、包含内容更丰富的、层次更深的嵌套式结构。运用规则所生成的流程图可以构造所有可能的结构化流程图，因而能够建立所有可能的结构化程序。,图117,对最简结构使用规则,(3),和规则,(4),注意：如果不按上面的基本结构来绘制流程图，就有可能产生非结构化的流程图，如图,118,所示。上面介绍了表示算法的四种方法，即：自然语言、伪码、,NS,图和流程图。下面举个例子，用四种不同的方法来表示其算法，以比较各方法的使用和方便程度。,图,118,非结构化流程图,例,16,用辗转相除法求两个正整数的最大公约数。,用自然语言描述：,S1.,输入两个正整数,m,和,n；,S2.,比较,m,和,n,如,m,小于,n，,则交换它们的值以保证,m,是最大数，,m,作相除时的分子；,S3.,求,m,除以,n,的余数,r,S4.,如余数,r=0，,转,S6；,S5.,把除数,n,作为新的分子,m,余数,r,作为新的分母,n,然后转,S3；,S6.,打印除数,n，,即为最大公约数。,用伪码描述：,input m,n,if mn then swap m and n,r=mod(m,n),While r0 do,m=n,n=r,r=mod(m,n),end do,print n,其中，符号,mod(m,n),代表,m,除以,n,的余数。,图119 例16的,NS,图描述,图120 例16,的流程图描述,从上面的描述可以看出，四种方法各有特色，读者可以根据自己的爱好和熟悉程度来决定使用哪一种方法。,说明：在按确定的算法编制程序前，并不一定非要把算法以某种形式写出来或画出来。根据求解问题的难易程度及程序员的编程经验，有时可以画一些简图，甚至,什么图都不画，而由算法直接编写程序。,1.5.4,程序设计中的几种常用算法,算法是解决问题的方法，在不同领域中都有各自的算法，但从算法所采用的方法或思路上来看，算法还是有一定的共性的。算法按其共性可以分成几大类，下面主要介绍穷举法、迭代法和递归法。,1.,穷举法,穷举法又称枚举法、试探法。如果问题解的值域是有限的、确定的和有序的，则可以把其中每一个值都拿来试一下，看是否符合所给条件。如果由人来采用该方法进行求解，则极为繁琐，尤其是当值域很大时；但该方法却特别适合于由计算机求解。对那些尚未,找到或不易找到用解析方法求解的问题，穷举法不失为一种行之有效的方法。,例,17,百鸡问题。用,100,元钱买,100,只鸡，已知一只公鸡,5,元，一只母鸡,3,元，,3,只小鸡,1,元，问能买的公鸡、母鸡和小鸡各是多少只,?,设 能买公鸡,x,只，母鸡,y,只，小鸡,z,只，按题意可列出下列方程组：,=100 (,总钱数,100),(,总只数,100),这个方程组有两个方程、,3,个未知数，因而是不定方程的求解问题，可用穷举法把每一种可能的组合方案都试一下。由题意可知，公鸡,x,的取值范围是,0到20(,可以一只公鸡都不买，也可以全买成公鸡，但最多买,20,只，当然这里还没有考虑鸡的总数的要求,),；同样母鸡,y,的取值范围是,0到33,；小鸡,z,没有取值的主动权，它只能在,x,和,y,的值确定之后来,决定自己的值，,z=100-x-y。,当,x,y,z,各取一值之后，还要验证是否符合总钱数的限制条件：,100=5,x+3y+(100-x-y)/3,共有多少种不同的组合呢,?,共有,2134=714,种。计算机把这,714,种可能性都测试一遍，最后求出符合条件的,4,组解。我们可以用流程图来描述这一算法，如图,121,所示。,图121 例17,的流程图,2.,迭代法,所谓迭代法就是根据问题的初始条件或迭代公式，先求出一个近似解，判断它是否符合要求，如不符合要求，则根据前一个近似解求出下一个更好的近似解，一步步向真实解逼近，直到解满足要求为止。,例,18,求正数,a,的平方根。,已知迭代公式为，,其中,a,为任意正数。当适当取,a,0,之后，则有,由迭代法求 的计算过程为：,取,a,0,=1.0，,然后根据迭代公式可求出,a,1,；,再由迭代公式和,a,1,而求出,a,2,显然,a,2,比,a,1,更接近真实结果；依次求出,a,3,a,4,a,n,，,直到,|,a,n,-a,n-1,|,小于预先给定的误差为止。其流程图如图,122,所示。,图122 例18,的流程图,例,19,用二分法求方程的解。,设在区间,a,b,内，函数,f(x),有一个根，则,f(a),和,f(b),必定异号。先求出该区间的中点,h,处的函数值,f(h)，,然后判断,f(h),和,f(a),是否同号，如果同号，则表示方程的根在,h,b,内，此时可取,h,为新的下界，,b,为新的上界，见图,123(,a)；,反之，若,f(h),和,f(a),异号，则说明方程的根在,a,h,内，此时可取,a,为新的下界，,h,为新的上界，见图,1-,23(,b)。,新的区间正好是原区间的一半，故称为二分法。继续在新的区间中做同样的判断，直至新区间的间隔小于给定的精度为止。,图,123,二分法求方程的解,(,a)f(h),与,f(a),同号时；,(,b)f(h),与,f(a),异号时,可写出其算法如下：,S1.,读入下界,a,上界,b,S2.,执行循环体：,2.1,取中点,2.2如,f(h),和,f(a),同号，则以,h,为新的下界,a,否则以,h,为新的上界,b；,2.3,如满足精度要求,|,a-b|0，,则以,h,为新的下界,a,否则以,h,为新的上界,b。,用流程图来描述算法，如图,124,所示。,例19,的流程图,3.,递归方法,直接或间接调用自身的算法称为递归算法。在算法的描述中，递归法往往比非递归法直观易懂。,例,110,阶乘函数的递归定义。,阶乘的数学定义为：,(N=0或N=1),(N2),第一式给出一个基本值，是非递归的；第二式是用较小的函数值,(,N-1)!,来计算较大的函数值,N!，,等号两边都用到了阶乘符号，因而是一个递归定义。,关于递归算法，后面有详细的讨论。,