《程序设计与C语言》课件第1章

第1章预备知识1.1计算机内的数据表示

1.2数的定点和浮点表示1.3简单的逻辑运算1.4程序的概念1.5算法习题11.1计算机内的数据表示数据形态多种多样，凡是计算机能够处理的对象都称为数据，如文字数据、图形数据、声音数据等。但不管其表象多么复杂，多么千差万别，只要一归入计算机处理，都全部地统一为二进制数据，也就是说，数据在计算机内是以二进制(即用数字0和1)来表示的。在计算机中为什么要采用二进制?采用二进制有哪些优点?以下就是问题的答案。

(1)用二进制表示数字在物理上容易实现。计算机内部用电子器件的状态来表示数字信息。一种数制有多少种不同的数字，电子器件就需要多少种不同的状态。二进制只有数字0和1，因此它只需要由两个稳定状态的电子元件来表示，而十进制则需要由10个不同稳定状态的电子元件来表示。显然对电子元件的制造来讲，用二进制要简单，如开关的接通与断开，晶体管的导通与截止，都可以由0和1两个数字表示。因此用二进制表示数字，数字的状态少，工作可靠。

(2)二进制运算规则简单。二进制求和的规则有：

0+0=0 0+1=1+0=1 1+1=10二进制求积的规则有：

0×0=0 0×1=1×0=0 1×1=1一般地，若一种数制中有n个不同的数字，则根据排列组合的法则可知，其求和与求积各需要n(n+1)/2条不同的规则。按这一公式计算，对十进制求和与求积就需要55条规则。

(3)采用二进制可以用逻辑代数作为设计分析的工具。二进制中用0和1可以表示是与非、高与低等，这恰恰是逻辑代数中的内容。

(4)用二进制可以节约存储设备。比如要表示0~999这1000个数时，十进制要用3位数，需3×10=30个状态设备量，而用10位二进制数表示时，只需2×10=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)在十六进制中有16个数码，但自10起就没有相应的阿拉伯数字可以使用了，所以用字母A、B、C、D、E、F(大小写均可)来表示10、11、12、13、14、15。各种数制的共性是：N进制中的最大数码比N少1；在N进制中，逢N进1，借1当N。

2.位置计数法数据中各个数字所处的位置决定它的大小(即权值)，同样的数字在不同位置上代表的权值是不同的。比如：22.2=2×101+2×100+2×10－1

其中，101、100、10－1就是各位置的权值。采用位置计数法的任何数制都可以表示成多项式的形式。如有数据N=KnKn-1…K1K0K－1K－2…K－m

可以表示成：这里，Ni为整数部分；Nf为小数部分；x为基数，可以是2、8、10、16等。二进制、十进制、八进制和十六进制都采用位置计数法。1.1.2数制转换我们日常习惯使用的是十进制，但在计算机中使用的却是二进制，所以需要把十进制转换成二进制。但二进制书写麻烦，因此通常用八进制和十六进制表示，这样就存在各种数制之间的转换问题。

1.将十进制转换成二进制把十进制的整数和小数转换成二进制时所用的方法不同，因此应该分别进行转换。

(1)用余数法将十进制整数转换成二进制整数。把十进制整数不断地用2去除，将所得到的余数0或1依次记为K0,K1,K2,…，直到商是0为止，将最后一次所得的余数记为Kn，则KnKn-1…K1K0即为该整数的二进制表示。在演算过程中可用竖式形式，也可用线图形式。

【例1-1】(59)10=()2=(Kn…K1K0)2。①竖式演算如下：

259 余数1=K0

229 余数1=K1

214 余数0=K2

27 余数1=K3

23 余数1=K4

21 余数1=K5

0最后得到的余数在最高位，所以有(59)10=(K5K4K3K2K1K0)2=(111011)2②线图演算如下： →29→14→7→3→1→0 ÷2↓↓↓↓↓↓

余数110111 K0K1K2K3K4K5

同样有(59)10=(K5K4K3K2K1K0)2=(111011)2

(2)用进位法将十进制小数转换成二进制小数。把十进制小数不断地用2去乘，将所得乘积的整数部分(0或1)依次记为K－1,K－2,K－3,…。一般情况下，十进制小数并不一定都能用有限位的二进制小数表示，可根据精度要求，转换到一定位数即可。

【例1-2】把0.47转换成二进制。用线图形式可演算如下：

0.47→0.94→0.88→0.76→0.52→0.04 ×2↓↓↓↓↓

整数01111 K－1K－2K－3K－4K－5

在取5位小数时有(0.47)10=(0.K－1K－2K－3K－4K－5)2=(0.01111)2

(3)在把十进制转换成二进制时，熟记一些2的幂次的十进制及二进制值能加快转换速度。表1-1中列出了一些2的幂次所对应的十进制和二进制数。在转换时，可找出小于但最接近于该十进制整数的某个2的幂次，减去这个幂次，再在减后的数中找小于且最接近于该数的2的幂次……。2的n次方的二进制数的特点是1后跟有n个0，利用这一点就能迅速地确定二进制数的长度，然后在相应的位置上填上1或0即可。例如：

(1287.25)10=1024+256+4+2+1+0.25=210+28+22+21+20+2－2

=(10000000000+100000000+100+10+1+0.01)2

=(10100000111.01)2如果一个数比1024大很多，则可求出该数对1024的倍数，把倍数用2的幂次之和的形式表示，再与210相乘。

【例1-3】(30000)10=()2。计算30000除以1024得商29，余数为304，将商和余数分别用2的幂次之和的形式表示： 商：29=16+8+4+1=24+23+22+20

余数：304=256+32+16=28+25+24

则(30000)10=1024×29+304=210(24+23+22+20)+28+25+24

=214+213+212+210+28+25+24=(111010100110000)2

2.将二进制转换成十进制把二进制数按多项式展开求和即可得到其十进制表示。例如：

(101.101)2=(1×22+0×21+1×20+1×2-1+0×2-2+1×2-3)10

=(1×4+1×1+1×0.5+1×0.125)10

=(5.625)101.1.3原码、反码和补码在计算机中，位(bit)是最小的单位，通常用来表示由二进制位组成的信息长度；把8位二进制位定义为一个字节(byte)，计算机中的存储量就是按字节来计算的；计算机内部数据处理的基本单位称为字(word)，它通常也是输入/输出设备和存储器之间传递数据的基本单位，每个字所包含的位数称为字长。在计算机中，不仅数值用0和1表示，而且正负号也用0和1表示。一般规定一个存储单元的最高位(最左边的一位)为符号位，如该位是0表示正，该位是1表示负。在计算机中，带符号的数通常有三种表示方法：原码、反码和补码。为简单起见，下面我们只考虑用一个字节表示整数时的原码、反码和补码。

1.原码原码是一种机器数，原码表示法就是在机器中最高位用0表示正数，用1表示负数，而其余位表示数本身。例如：

+15的原码为：00001111 ↑

代表正 －15的原码为：10001111 ↑

代表负

+0的原码为：00000000

－0的原码为：10000000同一个0在计算机中有不同的表示，这不适合计算机的运算。

2.反码在反码表示法中，正、负数的表示是不同的。正数的反码和原码是一样的，如+15的反码仍然是00001111。负数的反码为符号位是1、其他各位是对原码求反，如－15的反码为11110000。数值0的反码有两种：+0的反码为00000000，－0的反码为11111111。即在反码表示法中，0的表示仍然不惟一。

3.补码鉴于以上情况，计算机内部采用补码方法来表示数值。采用补码方法的好处是可以简化设计与计算，把减运算转变为加运算来进行。我们以时钟为例来说明补码的原理。比如现在的标准时间是6点，而你的表停在11点的位置，如图1-1所示。要调准你的表可用两种方法：①向前拨7格；②向后拨5格。图1-1时钟示例不管采用哪种方法，都能达到目的，可谓殊途同归，但从算式上来看：

11+7=18(向前拨) 11－5=6(向后拨)计算结果并不一样，那么操作结果为什么会一样呢?这是因为表盘的刻度是以12为周期的，超过12就又从头计数，因此上面的计算结果18因超过了12，再从头开始计数后也就得到了6。这个12就称为系统的模数，7和5相对于模数12来说称做是互补的，即一个数是另一个数的补码。从上面的计算可以看出，减一个数就等于加上它的补码，效果是相同的，这就是把减法变成加法的原理。在计算机中以一个有限长度的二进制位作为模。比如用一个字节表示一个数，则其模数为28，如运算结果超过28，就从中减去28。反映在内存中，其情况为

100000000即把8位以外的数舍掉。计算机中的补码是这样定义的：正数：其补码与其原码、反码相同。例如： ［+15］补=［+15］原=［+15］反=00001111

［+127］补=［+127］原=［+127］反=01111111负数：最高位为1，其余各位在原码的基础上取反，然后在最低位加1，简称“求反加1”。可用如下关系式表示：［x］补=［x］反+1

注意：各位取反时不包括符号位，即符号位不求反。例如： ［-15］原=10001111 ［-127］原=11111111

［-0］原=10000000 ［-15］反=11110000

［-127］反=10000000 ［-0］反=11111111

［-15］补=11110001 ［-127］补=10000001

［-0］补=00000000因为［-0］反+1=100000000，把超过8位的部分舍掉，则［-0］补的结果就是00000000，而+0的补码也是00000000，即在补码表示法中，0的表示是惟一的。在8位字长情况下，-128是一个特殊的数，计算机中规定它的表示为10000000，即它的补码为［-128］补=10000000我们也可以这样来看一个补码的生成，如表1-2所示。

-127以前各数的补码既可以按［x］补=［x］反+1的公式得到，也可以按在前一个负数补码的基础上减1的规则来得到，而按这个规则求出-128的补码为10000000也就很自然了。1.2数的定点和浮点表示对任意一个二进制数N，都可以表示成下面的形式：N=2j×S其中，j是二进制整数，称为数N的阶码，S为二进制小数，称为数N的尾数。尾数表示数N的全部有效数字,阶码指明小数点的位置。对任意一个数，如阶码j是固定不变的，则这种表示方法称为数的定点表示，这样的数称为定点数；如阶码j可以取不同的值，则称为浮点表示，这样的数称为浮点数。如果j=0，则这样的定点数只能表示小数，这是一种常用的表示小数的方法。采用定点表示的计算机称为定点机，其中数的小数点的位置是固定的。而采用浮点表示的计算机称为浮点机，其中数的小数点的位置是变化的、浮动的。浮点机通用性强，但复杂；定点机制造简单，但精度受到影响。1.2.1定点数的取值范围定点数的表示格式如下： 符号·

数值其中，符号占1位，数值可有多位，小数点的位置在符号位之后、数值部分的最高位之前，但不占实际位数，例如:

01011表示0.1011，是个正数；

11011表示1.1011，是个负数。设定点计算机的字长是9位，其中一位是符号位，另8位是数值位，则该计算机所能表示的数的绝对值范围是：

0.00000001~0.11111111或写成：

2－8~1－2－8

一般地，若定点计算机的字长是n位，其中一位是符号位，则它所能表示的数的绝对值范围是：

2－(n－1)~1－2－(n－1)

(数值位最低位为1，其余位皆为0)(数值位各位全是1)1.2.2浮点数的取值范围在计算机中，浮点数由四部分表示：阶符、阶码、数符(尾符)和数码(尾数)。其格式如下： 阶符阶码数符·数码对浮点机来说，总是规定数码部分的S是纯小数且最高位是1，即

例如，浮点数110011.101的机器表示格式如下：因为110011.101=26×0.110011101,即小数点向左移6位，等于减小到原来的1/2-6，所以为保持原值大小不变，还应乘以26。移动时应保证小数点后的位上是1(小数点的位置也是隐含的)。这里阶符和数符全为正，故用0表示，阶码6写成二进制形式即为(110)2。注意：浮点数的正负号是由数码位的正负号决定的，而阶码的正负号只决定小数点的位置，即决定浮点数的绝对值大小。对给定一定位数的浮点机，如何决定它的取值范围呢?设有一台浮点机，数码位有8位，阶码有3位，另外各有一位符号位，则它所能表示的数的绝对值范围是：最小值：数码部分最小，阶码部分负绝对值最大(即阶符、阶码全为1)，即所以最小值为2-7×2-1。最大值：数码部分最大，阶码部分正最大(即阶符为0，阶码全为1)，即阶码7=23-1，2的幂次正好是阶码的位数。则取值范围(绝对值)为

2-7×2-1~27×(1-2-8)或一般地，若数码位有n-1位，阶码位有m位，则所能表示的数的绝对值范围为

【例1-4】对于用32位表示的浮点数，设阶码部分为8位，尾数部分为24位，各含1位符号位，求它所能表示的数的绝对值范围和有效数字位数。先标出取最大、最小值时在内存中各位的表示。最小值：当阶码负绝对值最大、数码最小时，即所表示的数值为：最大值：当阶码正最大、数码最大时，即所表示的数值为：由此知其范围为或

2-128~2127×(1-2-23)这是以2为基数的表示，如何表示成以10为基数的呢?因为尾数部分不大于1，所以数的大小主要是由阶码部分决定的。令阶码2127等于十进制数10x，即设

2127=10x

如能把x求出来，即可转换到十进制范围。对等式两边取对数：

127×lg2=x因为lg2≈0.3，所以

x≈0.3×127≈38令2-128=10y，则

y=-128×lg2≈-128×0.3≈-38因此在十进制情况下，这种有7位阶码的浮点数的取值范围为10-38~1038。浮点数的尾数部分决定数的精度。23位数码的最大值为224-1≈224。令224=10x(二进制的24位相当于十进制的x位)，则

x=24×lg2≈24×0.3≈7一般情况下尾数达不到最大值，但也在223和224之间，对于223，设有

223=10y

可求出

y=23×lg2≈23×0.3=6.9取y=6，即相当于十进制的6位。因此对尾数是二进制的24位的浮点数，其有效数字为十进制的6~7位。1.2.3整数的取值范围对于由一定位数表示的整数N的取值范围，可因带符号位和不带符号位、是原码表示还是补码表示而不同。设用8位表示一个有符号的整数，其中最高位是符号位，则表示数值的有7位。

(1)若用原码表示，则当数值的7位全是1时，整数N的绝对值最大，即此绝对值为27-1,即

0≤|N|≤27-1=127则

-127≤N≤127符号1111111

(2)若用补码表示，则最小的负数表示为该数值为-128。最大的正数表示为该数值为127。则

-128≤N≤1271000000001111111对于用8位表示的无符号整数，它表示的数全为正数，故当其8位全部是1时表示的数值最大，即该数值为28-1，则

0≤N≤28-1=255一般地，对由n+1位二进制数表示的整数：不带符号时，它所表示的数的范围为

0≤N≤2n+1-1带符号时：·用原码表示时，它所表示的整数的范围为

-(2n-1)≤N≤2n-1·用补码表示时，它所表示的整数的范围为

-2n≤N≤2n-1111111111.3简单的逻辑运算在程序设计中往往要根据某些条件是否成立来决定程序的走向：条件为真执行某个动作，条件为假则执行另外的动作。真和假，这两个值被称为逻辑值，逻辑值也只有这两个值。真假逻辑值在不同的环境下有不同的表示，有的地方用TRUE和FALSE表示，有的地方用非0和0来表示，C语言中就是用后者来表示的。条件也有简单条件和复杂条件之分。在逻辑学中，具有真假意义的句子称为命题，简单命题可以表示简单条件，而由逻辑连接词连接起来的复合命题就可以表示复杂条件。下面简单介绍一下逻辑连接词及其使用情况。1.3.1“或”、“与”、“非”运算在逻辑演算中，逻辑连接词又称为逻辑运算符，它的运算对象都是真或假的命题。如果一个运算符需要两个运算对象，就称为双目运算符；如果一个运算符只对一个运算对象进行运算，则称为单目运算符。逻辑运算符共有四个：逻辑“非”、逻辑“与”、逻辑“或”和逻辑“异或”。其中第一个是单目运算符，后三个是双目运算符。我们这里只介绍前三个运算符。

1.逻辑或(加)运算符OR逻辑或运算的情况类似于一个并联开关，如图1-2所示。只要有一个开关接通，电路就接通，电灯就会发亮。若灯泡亮用1表示，暗用0表示；A、B表示两个逻辑变量，接通用1表示，断开用0表示；结果用F表示，则可以写出如下函数关系：

F=AORB结果F的值也可能是0或1。图1-2逻辑或运算的物理示意图逻辑变量A、B都可以取0或1中任一个值，这样当它们连接起来的时候就会有不同的组合，在各种组合情况下，结果值是什么呢?为了清楚地反映逻辑结果值与各逻辑变量取值间的关系，我们可以用一个表来显示，这样的表就称为“真值表”。真值表反映了因变量与自变量之间的状态关系。逻辑或运算的真值表为或运算符还可以是+、∪、∨等。ABF000101011111即：0OR0=01OR0=10OR1=11OR1=1

2.逻辑与(乘)运算符AND逻辑与运算符的作用相当于一个串联开关，如图1-3所示。只有当两个开关同时连通时，电灯才会发亮，其关系式为F=AANDB其真值表为与运算符还可以是×、∩、∧等。ABF000100010111即：0AND0=01AND0=00AND1=01AND1=1图1-3逻辑与运算的物理示意图即：NOT0=1NOT1=0AF0110

3.逻辑非(否定)运算符NOT逻辑非又称为逻辑否定，它把一个命题改换成相反的含义，其作用类似于反相开关电路，如图1-4所示。当开关接通时，电灯泡由亮变暗；断开时，电灯泡由暗变亮。其关系式为F=NOTA其真值表为逻辑非运算符还可以是~、］、上划线(如)等。图1-4逻辑非运算的物理示意图1.3.2真值表上面我们介绍了三种逻辑运算符，逻辑运算符和逻辑运算对象相结合构成的式子称为逻辑表达式。在程序设计中我们需要的是逻辑表达式而不是一个孤零零的命题。然而在实际应用中，我们却往往不知道其逻辑表达式，只知道一些具体的要求。这时我们可以首先根据具体要求列出其真值表，然后再根据真值表写出逻辑表达式，这就是真值表的重要意义所在。

【例1-5】一个房间住了三个人：甲、乙、丙，求下列条件下房间内无人说话的表达式：

(1)甲从来不说话；

(2)当且仅当甲在场时乙才说话；

(3)丙在任何情况下都说话。

编程思路：首先用三个变量A、B、C表示甲、乙、丙三人以便于书写，并且规定其值为1时表示在房间，为0时表示不在房间。结果F为1时表示房间内无人说话，为0时表示有人说话。第一步：根据条件，列出真值表：第二步：根据真值表列出逻辑表达式。关键是把F值为1的各种情况收集起来，用或运算符连接，表示只要有一种情况发生，就说明房间内无人说话。ABCF00010010010101101001101011001110考虑F=1的各种取值：

(1)由真值表中第一行知，A=B=C=0时F=1，变量本身代表真，变量的否定代表假，则上述条件表示为(NOTA)AND(NOTB)AND(NOTC)解释为：A不在场并且B不在场并且C也不在场，此时房间内无人说话。

(2)由真值表第三行知，A=C=0,B=1时F=1，这可以表示为(NOTA)ANDBAND(NOTC)解释为：A不在场但是B在场并且C不在场，此时房间内无人说话。

(3)由真值表第五行知，当A=1,B=C=0时F=1，这可表示为

AAND(NOTB)AND(NOTC)解释为：A在场但B不在场并且C不在场，此时房间内无人说话。

说明：逻辑运算符AND、OR和NOT有不同的优先级：NOT最高，AND次之，OR最低。因此上面的括号可以不要，加上是为了清晰。把上面三个表达式用OR运算符连接起来，即为所求得的逻辑表达式：((NOTA)AND(NOTB)AND(NOTC))OR((NOTA)ANDBAND(NOTC))OR(AAND(NOTB)AND(NOTC))如果逻辑或运算符用“+”表示，逻辑与运算符省略，上划线表示否定，则可以把上面的表达式写成：

如果把这个表达式作为条件，则可以写出语句：

THEN打印输出“房间内无人说话”1.4程序的概念一个程序是一个由指令组成的序列。指令就是行为或动作。从这个意义上说，程序在计算机发明以前很久就有了。比如弹奏乐曲的乐谱、厨师做菜的食谱、某项工程实施的计划等都可以说是程序，只是计算机的程序更复杂，更需要仔细而精细地进行编写而已。程序要由编程者来编写，并由执行者来实施。实现指令称为执行或运行程序。运行中的程序称为进程。程序是静态的概念，而进程是动态的概念。1.4.1程序的特性所有程序(包括计算机程序)都有一些共同的性质，这些性质主要包括以下几点：

(1)指令是顺序执行的。除非有特别的声明，一般情况下程序总是从第一条指令起依次向后执行每一条指令，直至结束。

(2)程序的执行都有一个结果。厨师按食谱做菜最后可作出一道好菜；乐师按乐谱弹奏就会有一首美妙悦耳的乐曲；工程师按规划施工可建造出一座漂亮的楼房；用户按计算机程序执行可以完成相应的任务。

(3)程序总是要对某些对象进行操作。厨师做菜要用各种肉类或蔬菜等；演奏家要弹奏乐器；建筑师设计要用建筑材料；计算机程序操作的对象则是数据。

(4)有的程序要加入对操作对象的说明。比如一个食谱，基本上由两部分组成，第一部分说明所用的配料，第二部分才是操作的过程。计算机程序中有时也要先对操作数据的属性加以说明。

(5)有时指令要求执行者作出判断。指令的编写者在编制时并不知道在一次具体实现中执行者会做些什么。但他可以建立一个执行者用以作出判定的标准，比如“朋友来了，端出好酒；豺狼来了，拿出猎枪”。

(6)一条或一组指令可能需要执行多次。比如在中草药炮制过程中，对某种药材要经过“九蒸九晒”才符合要求，这种重复必须指明重复的次数。有时重复执行某些指令不一定有明确的次数，但可以以是否达到某个目标作为重复终止的判断依据。比如在把假分数化成真分数时，可以从分子中不断地减去分母，直到分子小于分母为止。人工重复执行某些指令也许是很繁琐枯燥的事情，但由于计算机执行速度很快，因此重复执行对它来说就不算什么问题了。1.4.2计算机程序的执行过程程序是一种手段，程序的编写者利用程序来和执行者进行通信。通信就需要语言，不同的场合可以用不同的语言来表示程序。比如用自然语言交待任务、下达命令，但大多数程序设计需要一种特殊的语言。对计算机下达任务的语言就是计算机语言。计算机语言有高级语言和低级语言之分，但这种高低之分并没有贵贱之别，其区分主要是因为它们对计算机硬件的接近程度不同。低级语言主要是指机器语言(二进制语言)和汇编语言，它们离计算机硬件最近。用机器语言写的指令都是由0和1组成的符号序列，计算机能直接识别和执行，因而速度很快。但这种指令写起来繁琐复杂，非专业人士不能为之。汇编语言是符号化的二进制语言，它用英文单词或其缩写来表达指令，执行速度也很快，但却受具体机器系统的制约。高级语言又称为算法语言，它用类似于自然语言和数学公式的指令编写程序。这样编写、阅读程序都很方便，并且还不受限于某种机器系统。高级语言的出现大大促进了计算机的普及，使计算机从少数人才能涉足的象牙塔中走出来面向大众。但是计算机并不认识高级语言程序，计算机只认识二进制代码。因此在高级语言程序和计算机之间就需要一个翻译，由这个翻译把高级语言程序翻译成计算机能懂的程序。这个翻译常被称为编译程序或编译器。不同的高级语言有不同的编译器。用高级语言写的程序又称为源程序，它的执行过程是这样的：把源程序输入给计算机，然后编译器工作，把源程序翻译成目标程序，目标程序即是用二进制表示的机器指令，机器指令再对输入的数据进行操作，最后得到结果数据并输出。可以看出，执行高级语言程序分为两个阶段：第一个阶段称为编译阶段，第二个阶段称为运行阶段。在程序执行的过程中可能会出现三种类型的错误：

(1)编译错误。这是在编译阶段发生的错误，主要是使用语言的语法不合规范所引起的错误。需要把这种错误全部排除后才能进入运行阶段。

(2)运行错误。这种错误在编译时发现不了，只在运行时才显现出来。如对负数开平方，除数为0，循环终止条件永远不能达到等，这种错误常会引起无限循环或死机。

(3)逻辑错误。这种错误即使在运行时也显示不出来，因程序能正常运行，但结果不对。比如把求平方根的函数sqrt(x)写成了求平方的函数sqr(x)，把表达式中的加号“+”写成了乘号“*”等。前两种错误计算机都会有提示或不正常表象，它会迫使你进行修改，但对逻辑错误计算机并不提醒，全靠程序员仔细检查予以排除。我们可以用一简图来显示一个高级语言源程序的执行过程，如图1-5所示。图1-5高级语言源程序的执行过程1.5算法程序设计离不开算法，算法指导程序设计，算法是程序的灵魂。程序是语句的集合，但如何围绕所要解决的任务来安排这些语句的次序则是由算法决定的。因此程序设计的大致步骤如下：

(1)确定算法和数据结构。算法是和具体任务有关的，而数据结构则是程序要处理的数据的组织。

(2)把算法以明晰的方法表示出来，如用流程图、N-S图、伪码等方法。

(3)在算法已明确表示出来的基础上用高级语言编制程序。1.5.1算法的特点算法，简单地讲，就是解决问题的流程安排，即先做什么，后做什么。精确地讲，算法是被精确定义的一系列规则，这些规则规定了解决特定问题的一系列操作顺序，以便在有限步骤内产生出所求问题的解答。尽管算法因求解问题的不同而千变万化、简繁各异，但它们都必须具备以下五个特性。

1.确定性算法的每一步运算都必须有确切的定义，即每种运算所执行的操作都必须是确定的、无二义性的。比如在配制某种溶液时，应明确指出“5升水加100克药粉”，而不能是“一桶水加适量的药粉”这种不确定的说法。

2.能行性算法中有待实现的运算方法都必须是可执行的，即在执行者(计算机)能力范围之内并能在有限时间内完成。

3.有穷性一个算法必须在执行了有穷的步骤之后结束。如果一个计算不具有有穷性，但具有算法的其他特性，则称之为计算方法。比如对无穷调和级数的计算就不是一个算法，而是一个计算方法。但是在确定了项数或精度之后，再进行的计算就是有穷的了，这时对调和级数的计算如求和，就变成了算法。

4.输入一个算法可以有0个或0个以上的输入，可提供算法操作的数据。

5.输出一个算法总能产生一个或多个输出，即算法的计算结果。1.5.2算法的表示一个算法应该用明晰的方法展现在人们的面前，这样才易于用计算机语言写出体现算法的程序。表示一个算法的方法，通常有以下四种。

1.自然语言描述法比如求三个数的最大值问题，用自然语言可以描述为：先将两个数a和b进行比较，找出其最大者，然后再把它和第三个数c进行比较，如果它比第三个数大，则它就是最大数，否则第三个数c就是最大数。

2.伪码表示法所谓伪码，就是类似于程序设计语言的语句，但又不是任何一种真实的程序设计语言的语句，它不涉及程序设计的具体细节。比如求三个数的最大值问题，用伪码可表示为：ifa>b then把a交给maxelse把b交给maxifmax>c then输出最大值maxelse输出最大值c说明：用伪码表示的详细程度没有一定的标准，可以很详细，也可以很简略。

3.N-S图表示法这是一种图语言表示法，其特点是在一个矩形框内完成算法的流程说明。比如求三个数的最大值问题，用N-S图可描述为如图1-6所示的形式。图1-6求三个数的最大值问题

4.流程图表示法这也是一种图语言表示法，它用一些不同的图例来表示算法的流程。常用的图例主要有如图1-7中所示的几种。比如求三个数的最大值问题，用流程图法可表示为如图1-8所示的形式。图1-7流程图表示法常用图例图1-8求三个数的最大值问题的流程图表示1.5.3结构化程序设计的三种基本结构

20世纪60年代，在开发大型软件的过程中出现了所谓的“软件危机”，其主要表现是：开发进度被推迟；成本超出预算；软件产品不可靠。人们认识到软件开发要比想象的复杂得多。在如何克服“软件危机”的讨论和研究中，诞生了“结构化程序设计”的概念，这是编写出清晰、正确和容易理解的程序的一种指导方针和严格方法。结构化程序设计的基本方法是：在设计程序时，本着从上到下、逐步求精的原则，将一个大的原始问题分解为多个可独立进行编程的小问题(即小模块)，如果某个模块还未精细到能直接进行编程的程度，则继续对它进行分解，直至能直接编程为止。每个模块只有一个入口和一个出口，这样不管编多大的程序，不管有多少人参加编写，都可以把他们的模块很自然地连接起来。与非结构化程序设计方法相比，采用结构化方法能够设计出更易理解的程序，因此也更容易测试、调试和修改，甚至从数学的意义上讲，这种设计方法也是正确的。在结构化程序设计方法中，有三种基本的控制结构。这三种基本结构是：顺序结构、选择结构和循环结构。顺序结构是指语句的执行顺序和它在程序中出现的次序是一致的，即一条语句执行完后紧接着执行它下面的那条语句。选择结构是根据一定的条件，把语句分成不同的分支，程序只执行其中一个分支，而不执行其他分支。循环结构是根据一定的条件，对某些语句重复执行。被重复执行的语句称为循环体。重复执行的次数可以预指定，也可以不指定，而由循环体中的变化所决定。这三种基本结构，可以用图表示法说明。ABTFAB

1.用N-S图表示

(1)顺序结构：

A执行完后接着执行B。

(2)选择结构：

P为条件，当P为真(T)时执行A，当P为假(F)时执行B。P

(3)循环结构：循环结构又分为以下两种。①while结构：P为条件，只要P为真就执行A。PA②repeat-until结构：执行A直到P变为真为止。以上各图中的A和B，可以是一个简单语句，也可以是以上三种结构语句之一，这种嵌套代入方式也表明了从上到下、逐步求精的设计方法。AP

2.用流程图表示

(1)顺序结构，如图1-9所示。图1-9顺序结构的流程图表示

(2)选择结构，这里又有如下三种形式：①if结构(单路选择结构)，如图1-10所示。②if/else结构(双路选择结构)，如图1-11所示。图1-10if结构的流程图表示图1-11if/else结构的流程图表示③switch结构(多路选择结构)，如图1-12所示。图中，当某个Pi为真时，执行相应的语句Ai，然后退出选择语句(通过break语句实现)。图1-12switch结构的流程图表示

(3)循环结构，也有三种形式：①while结构，如图1-13所示。②do-while结构，如图1-14所示。和①的区别在于，这里是先执行语句A，然后再判断条件P。图1-13while结构的流程图表示图1-14do-while结构的流程图表示③for结构，如图1-15所示。图1-15for结构的流程图表示从上面各图中可以看出，每一个结构只有一个入口和一个出口。按顺序来组织各种控制结构就能设计出结构化的程序，即只要把一个控制结构的出口点和另一个控制结构的入口点连接起来即可。结构化程序设计的规则有4条：

(1)从最简单的流程图开始。

(2)任何矩形框都可以被两个按顺序放置的矩形框取代。

(3)任何矩形框都可以被任何结构取代。

(4)规则(2)和规则(3)可按任何顺序运用多次。规则(2)又称为“栈式控制规则”，规则(3)又称为“嵌套式控制规则”。下面用图示方法展示一下结构程序设计的原则，如图

1-16、图1-17所示。图1-16从最简结构出发反复使用规则(2)和规则(4)图1-17对最简结构使用规则(3)和规则(4)图1-17中的虚线框就是对图1-16中一个矩形框的细化。用规则(4)可以产生更大的、包含内容更丰富的、层次更深的嵌套式结构。运用规则所生成的流程图可以构造所有可能的结构化流程图，因而能够建立所有可能的结构化程序。

注意：如果不按上面的基本结构来绘制流程图，就有可能产生非结构化的流程图，如图1-18所示。上面介绍了表示算法的四种方法，即自然语言、伪码、N-S图和流程图。下面举个例子，用四种不同的方法来表示其算法，以比较各方法的使用和方便程度。图1-18非结构化的流程图

【例1-6】用辗转相除法求两个正整数的最大公约数。①用自然语言描述：

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，即为最大公约数。例如，设最初取m为74，n为108。首先将它们调整为m=108,n=74，则有如下示意性的操作：

mnr

第一遍1087434

第二遍74346

第三遍3464

第四遍642

第五遍420当执行五遍之后，余数r=0，则此时的除数n=2即为m和n的最大公约数。②用伪码描述：inputm,nifm<nthenswapmandnr<=mod(m,n)whiler≠0domnnrrmod(m,n)enddoprintn其中，符号mod(m,n)代表m除以n的余数。③用N-S图描述，如图1-19所示。④用流程图描述，如图1-20所示。图1-19例1-6的N-S图描述图1-20例1-6的流程图描述从上面的描述可以看出，四种方法各有特色，读者可以根据自己的爱好和熟悉程度来决定使用哪一种方法。

说明：在按确定的算法编制程序前，并不一定非要把算法以某种形式写出来或画出来。根据求解问题的难易程度及程序员的编程经验，有时可以画一些简图，甚至什么图都不画，而由算法直接编写程序。1.5.4程序设计中的几种常用算法算法是解决问题的方法，在不同领域中都有各自的算法，但从算法所采用的方法或思路上来看，算法还是有一定共性的。算法按其共性可以分成几大类，下面主要介绍穷举法、迭代法和递归法。

1.穷举法穷举法又称枚举法、试探法。如果问题解的值域是有限的、确定的和有序的，则可以把其中每一个值都拿来试一下，看是否符合所给条件。如果由人来采用该方法进行求解，则极为繁琐，当值域很大时尤其如此；但该方法却特别适合于由计算机求解。对那些尚未找到或不易找到用解析方法求解的问题，穷举法不失为一种行之有效的方法。

【例1-7】百鸡问题。用100元钱买100只鸡，已知一只公鸡5元，一只母鸡3元，3只小鸡1元，问能买的公鸡、母鸡和小鸡各是多少只?设能买公鸡x只，母鸡y只，小鸡z只，按题意可列出下列方程组：这个方程组有两个方程、3个未知数，因而是不定方程的求解问题，可用穷举法把每一种可能的组合方案都试一下。由题意可知，公鸡x的取值范围是0~20(可以一只公鸡都不买，也可以全买成公鸡，但最多买20只，当然这里还没有考虑鸡的总数的要求)；同样，母鸡y的取值范围是0~33；小鸡z没有取值的主动权，它只能在x和y的值确定之后来决定自己的值，即z=100-x-y。当x、y、z各取一值之后，还要验证是否符合总钱数的限制条件：100=5x+3y+(100-x-y)/3共有多少种不同的组合呢?共有21×34=714种。计算机把这714种可能性都测试一遍，最后求出符合条件的4组解。我们可以用流程图来描述这一算法，如图1-21所示。图1-21例1-7的流程图

2.迭代法所谓迭代法，就是根据问题的初始条件或迭代公式，先求出一个近似解，判断它是否符合要求，如不符合要求，则根据前一个近似解求出下一个更好的近似解，一步步向真实解逼近，直到解满足要求为止。

【例1-8】求正数a的平方根。已知迭代公式为，其中a为任意正数。当适当取a0之后，则有。由迭代法求的计