《程序設(shè)計(jì)與C語言》課件第1章

第1章預(yù)備知識(shí)1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示

1.2數(shù)的定點(diǎn)和浮點(diǎn)表示1.3簡單的邏輯運(yùn)算1.4程序的概念1.5算法習(xí)題11.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示數(shù)據(jù)形態(tài)多種多樣，凡是計(jì)算機(jī)能夠處理的對(duì)象都稱為數(shù)據(jù)，如文字?jǐn)?shù)據(jù)、圖形數(shù)據(jù)、聲音數(shù)據(jù)等。但不管其表象多么復(fù)雜，多么千差萬別，只要一歸入計(jì)算機(jī)處理，都全部地統(tǒng)一為二進(jìn)制數(shù)據(jù)，也就是說，數(shù)據(jù)在計(jì)算機(jī)內(nèi)是以二進(jìn)制(即用數(shù)字0和1)來表示的。在計(jì)算機(jī)中為什么要采用二進(jìn)制?采用二進(jìn)制有哪些優(yōu)點(diǎn)?以下就是問題的答案。

(1)用二進(jìn)制表示數(shù)字在物理上容易實(shí)現(xiàn)。計(jì)算機(jī)內(nèi)部用電子器件的狀態(tài)來表示數(shù)字信息。一種數(shù)制有多少種不同的數(shù)字，電子器件就需要多少種不同的狀態(tài)。二進(jìn)制只有數(shù)字0和1，因此它只需要由兩個(gè)穩(wěn)定狀態(tài)的電子元件來表示，而十進(jìn)制則需要由10個(gè)不同穩(wěn)定狀態(tài)的電子元件來表示。顯然對(duì)電子元件的制造來講，用二進(jìn)制要簡單，如開關(guān)的接通與斷開，晶體管的導(dǎo)通與截止，都可以由0和1兩個(gè)數(shù)字表示。因此用二進(jìn)制表示數(shù)字，數(shù)字的狀態(tài)少，工作可靠。

(2)二進(jìn)制運(yùn)算規(guī)則簡單。二進(jìn)制求和的規(guī)則有：

0+0=0 0+1=1+0=1 1+1=10二進(jìn)制求積的規(guī)則有：

0×0=0 0×1=1×0=0 1×1=1一般地，若一種數(shù)制中有n個(gè)不同的數(shù)字，則根據(jù)排列組合的法則可知，其求和與求積各需要n(n+1)/2條不同的規(guī)則。按這一公式計(jì)算，對(duì)十進(jìn)制求和與求積就需要55條規(guī)則。

(3)采用二進(jìn)制可以用邏輯代數(shù)作為設(shè)計(jì)分析的工具。二進(jìn)制中用0和1可以表示是與非、高與低等，這恰恰是邏輯代數(shù)中的內(nèi)容。

(4)用二進(jìn)制可以節(jié)約存儲(chǔ)設(shè)備。比如要表示0~999這1000個(gè)數(shù)時(shí)，十進(jìn)制要用3位數(shù)，需3×10=30個(gè)狀態(tài)設(shè)備量，而用10位二進(jìn)制數(shù)表示時(shí)，只需2×10=20個(gè)狀態(tài)設(shè)備量。1.1.1數(shù)的二進(jìn)制、十進(jìn)制、八進(jìn)制和十六進(jìn)制表示常用的數(shù)制有二進(jìn)制、十進(jìn)制、八進(jìn)制和十六進(jìn)制，它們有共性也有差別。

1.數(shù)碼及進(jìn)位法則數(shù)碼是構(gòu)造一種數(shù)制所用的不同符號(hào)。各種進(jìn)制的數(shù)碼為：二進(jìn)制：0，1十進(jìn)制：0，1，2，3，4，5，6，7，8，9八進(jìn)制：0，1，2，3，4，5，6，7十六進(jìn)制：0，1，2，3，4，5，6，7，8，9，A(a),B(b),C(c),D(d),E(e),F(f)在十六進(jìn)制中有16個(gè)數(shù)碼，但自10起就沒有相應(yīng)的阿拉伯?dāng)?shù)字可以使用了，所以用字母A、B、C、D、E、F(大小寫均可)來表示10、11、12、13、14、15。各種數(shù)制的共性是：N進(jìn)制中的最大數(shù)碼比N少1；在N進(jìn)制中，逢N進(jìn)1，借1當(dāng)N。

2.位置計(jì)數(shù)法數(shù)據(jù)中各個(gè)數(shù)字所處的位置決定它的大小(即權(quán)值)，同樣的數(shù)字在不同位置上代表的權(quán)值是不同的。比如：22.2=2×101+2×100+2×10－1

其中，101、100、10－1就是各位置的權(quán)值。采用位置計(jì)數(shù)法的任何數(shù)制都可以表示成多項(xiàng)式的形式。如有數(shù)據(jù)N=KnKn-1…K1K0K－1K－2…K－m

可以表示成：這里，Ni為整數(shù)部分；Nf為小數(shù)部分；x為基數(shù)，可以是2、8、10、16等。二進(jìn)制、十進(jìn)制、八進(jìn)制和十六進(jìn)制都采用位置計(jì)數(shù)法。1.1.2數(shù)制轉(zhuǎn)換我們?nèi)粘Ａ?xí)慣使用的是十進(jìn)制，但在計(jì)算機(jī)中使用的卻是二進(jìn)制，所以需要把十進(jìn)制轉(zhuǎn)換成二進(jìn)制。但二進(jìn)制書寫麻煩，因此通常用八進(jìn)制和十六進(jìn)制表示，這樣就存在各種數(shù)制之間的轉(zhuǎn)換問題。

1.將十進(jìn)制轉(zhuǎn)換成二進(jìn)制把十進(jìn)制的整數(shù)和小數(shù)轉(zhuǎn)換成二進(jìn)制時(shí)所用的方法不同，因此應(yīng)該分別進(jìn)行轉(zhuǎn)換。

(1)用余數(shù)法將十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制整數(shù)。把十進(jìn)制整數(shù)不斷地用2去除，將所得到的余數(shù)0或1依次記為K0,K1,K2,…，直到商是0為止，將最后一次所得的余數(shù)記為Kn，則KnKn-1…K1K0即為該整數(shù)的二進(jìn)制表示。在演算過程中可用豎式形式，也可用線圖形式。

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

259 余數(shù)1=K0

229 余數(shù)1=K1

214 余數(shù)0=K2

27 余數(shù)1=K3

23 余數(shù)1=K4

21 余數(shù)1=K5

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

余數(shù)110111 K0K1K2K3K4K5

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

(2)用進(jìn)位法將十進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)。把十進(jìn)制小數(shù)不斷地用2去乘，將所得乘積的整數(shù)部分(0或1)依次記為K－1,K－2,K－3,…。一般情況下，十進(jìn)制小數(shù)并不一定都能用有限位的二進(jìn)制小數(shù)表示，可根據(jù)精度要求，轉(zhuǎn)換到一定位數(shù)即可。

【例1-2】把0.47轉(zhuǎn)換成二進(jìn)制。用線圖形式可演算如下：

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

整數(shù)01111 K－1K－2K－3K－4K－5

在取5位小數(shù)時(shí)有(0.47)10=(0.K－1K－2K－3K－4K－5)2=(0.01111)2

(3)在把十進(jìn)制轉(zhuǎn)換成二進(jìn)制時(shí)，熟記一些2的冪次的十進(jìn)制及二進(jìn)制值能加快轉(zhuǎn)換速度。表1-1中列出了一些2的冪次所對(duì)應(yīng)的十進(jìn)制和二進(jìn)制數(shù)。在轉(zhuǎn)換時(shí)，可找出小于但最接近于該十進(jìn)制整數(shù)的某個(gè)2的冪次，減去這個(gè)冪次，再在減后的數(shù)中找小于且最接近于該數(shù)的2的冪次……。2的n次方的二進(jìn)制數(shù)的特點(diǎn)是1后跟有n個(gè)0，利用這一點(diǎn)就能迅速地確定二進(jìn)制數(shù)的長度，然后在相應(yīng)的位置上填上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如果一個(gè)數(shù)比1024大很多，則可求出該數(shù)對(duì)1024的倍數(shù)，把倍數(shù)用2的冪次之和的形式表示，再與210相乘。

【例1-3】(30000)10=()2。計(jì)算30000除以1024得商29，余數(shù)為304，將商和余數(shù)分別用2的冪次之和的形式表示： 商：29=16+8+4+1=24+23+22+20

余數(shù)：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.將二進(jìn)制轉(zhuǎn)換成十進(jìn)制把二進(jìn)制數(shù)按多項(xiàng)式展開求和即可得到其十進(jìn)制表示。例如：

(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原碼、反碼和補(bǔ)碼在計(jì)算機(jī)中，位(bit)是最小的單位，通常用來表示由二進(jìn)制位組成的信息長度；把8位二進(jìn)制位定義為一個(gè)字節(jié)(byte)，計(jì)算機(jī)中的存儲(chǔ)量就是按字節(jié)來計(jì)算的；計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位稱為字(word)，它通常也是輸入/輸出設(shè)備和存儲(chǔ)器之間傳遞數(shù)據(jù)的基本單位，每個(gè)字所包含的位數(shù)稱為字長。在計(jì)算機(jī)中，不僅數(shù)值用0和1表示，而且正負(fù)號(hào)也用0和1表示。一般規(guī)定一個(gè)存儲(chǔ)單元的最高位(最左邊的一位)為符號(hào)位，如該位是0表示正，該位是1表示負(fù)。在計(jì)算機(jī)中，帶符號(hào)的數(shù)通常有三種表示方法：原碼、反碼和補(bǔ)碼。為簡單起見，下面我們只考慮用一個(gè)字節(jié)表示整數(shù)時(shí)的原碼、反碼和補(bǔ)碼。

1.原碼原碼是一種機(jī)器數(shù)，原碼表示法就是在機(jī)器中最高位用0表示正數(shù)，用1表示負(fù)數(shù)，而其余位表示數(shù)本身。例如：

+15的原碼為：00001111 ↑

代表正 －15的原碼為：10001111 ↑

代表負(fù)

+0的原碼為：00000000

－0的原碼為：10000000同一個(gè)0在計(jì)算機(jī)中有不同的表示，這不適合計(jì)算機(jī)的運(yùn)算。

2.反碼在反碼表示法中，正、負(fù)數(shù)的表示是不同的。正數(shù)的反碼和原碼是一樣的，如+15的反碼仍然是00001111。負(fù)數(shù)的反碼為符號(hào)位是1、其他各位是對(duì)原碼求反，如－15的反碼為11110000。數(shù)值0的反碼有兩種：+0的反碼為00000000，－0的反碼為11111111。即在反碼表示法中，0的表示仍然不惟一。

3.補(bǔ)碼鑒于以上情況，計(jì)算機(jī)內(nèi)部采用補(bǔ)碼方法來表示數(shù)值。采用補(bǔ)碼方法的好處是可以簡化設(shè)計(jì)與計(jì)算，把減運(yùn)算轉(zhuǎn)變?yōu)榧舆\(yùn)算來進(jìn)行。我們以時(shí)鐘為例來說明補(bǔ)碼的原理。比如現(xiàn)在的標(biāo)準(zhǔn)時(shí)間是6點(diǎn)，而你的表停在11點(diǎn)的位置，如圖1-1所示。要調(diào)準(zhǔn)你的表可用兩種方法：①向前撥7格；②向后撥5格。圖1-1時(shí)鐘示例不管采用哪種方法，都能達(dá)到目的，可謂殊途同歸，但從算式上來看：

11+7=18(向前撥) 11－5=6(向后撥)計(jì)算結(jié)果并不一樣，那么操作結(jié)果為什么會(huì)一樣呢?這是因?yàn)楸肀P的刻度是以12為周期的，超過12就又從頭計(jì)數(shù)，因此上面的計(jì)算結(jié)果18因超過了12，再從頭開始計(jì)數(shù)后也就得到了6。這個(gè)12就稱為系統(tǒng)的模數(shù)，7和5相對(duì)于模數(shù)12來說稱做是互補(bǔ)的，即一個(gè)數(shù)是另一個(gè)數(shù)的補(bǔ)碼。從上面的計(jì)算可以看出，減一個(gè)數(shù)就等于加上它的補(bǔ)碼，效果是相同的，這就是把減法變成加法的原理。在計(jì)算機(jī)中以一個(gè)有限長度的二進(jìn)制位作為模。比如用一個(gè)字節(jié)表示一個(gè)數(shù)，則其模數(shù)為28，如運(yùn)算結(jié)果超過28，就從中減去28。反映在內(nèi)存中，其情況為

100000000即把8位以外的數(shù)舍掉。計(jì)算機(jī)中的補(bǔ)碼是這樣定義的：正數(shù)：其補(bǔ)碼與其原碼、反碼相同。例如： ［+15］補(bǔ)=［+15］原=［+15］反=00001111

［+127］補(bǔ)=［+127］原=［+127］反=01111111負(fù)數(shù)：最高位為1，其余各位在原碼的基礎(chǔ)上取反，然后在最低位加1，簡稱“求反加1”?？捎萌缦玛P(guān)系式表示：［x］補(bǔ)=［x］反+1

注意：各位取反時(shí)不包括符號(hào)位，即符號(hào)位不求反。例如： ［-15］原=10001111 ［-127］原=11111111

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

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

［-15］補(bǔ)=11110001 ［-127］補(bǔ)=10000001

［-0］補(bǔ)=00000000因?yàn)椋?0］反+1=100000000，把超過8位的部分舍掉，則［-0］補(bǔ)的結(jié)果就是00000000，而+0的補(bǔ)碼也是00000000，即在補(bǔ)碼表示法中，0的表示是惟一的。在8位字長情況下，-128是一個(gè)特殊的數(shù)，計(jì)算機(jī)中規(guī)定它的表示為10000000，即它的補(bǔ)碼為［-128］補(bǔ)=10000000我們也可以這樣來看一個(gè)補(bǔ)碼的生成，如表1-2所示。

-127以前各數(shù)的補(bǔ)碼既可以按［x］補(bǔ)=［x］反+1的公式得到，也可以按在前一個(gè)負(fù)數(shù)補(bǔ)碼的基礎(chǔ)上減1的規(guī)則來得到，而按這個(gè)規(guī)則求出-128的補(bǔ)碼為10000000也就很自然了。1.2數(shù)的定點(diǎn)和浮點(diǎn)表示對(duì)任意一個(gè)二進(jìn)制數(shù)N，都可以表示成下面的形式：N=2j×S其中，j是二進(jìn)制整數(shù)，稱為數(shù)N的階碼，S為二進(jìn)制小數(shù)，稱為數(shù)N的尾數(shù)。尾數(shù)表示數(shù)N的全部有效數(shù)字,階碼指明小數(shù)點(diǎn)的位置。對(duì)任意一個(gè)數(shù)，如階碼j是固定不變的，則這種表示方法稱為數(shù)的定點(diǎn)表示，這樣的數(shù)稱為定點(diǎn)數(shù)；如階碼j可以取不同的值，則稱為浮點(diǎn)表示，這樣的數(shù)稱為浮點(diǎn)數(shù)。如果j=0，則這樣的定點(diǎn)數(shù)只能表示小數(shù)，這是一種常用的表示小數(shù)的方法。采用定點(diǎn)表示的計(jì)算機(jī)稱為定點(diǎn)機(jī)，其中數(shù)的小數(shù)點(diǎn)的位置是固定的。而采用浮點(diǎn)表示的計(jì)算機(jī)稱為浮點(diǎn)機(jī)，其中數(shù)的小數(shù)點(diǎn)的位置是變化的、浮動(dòng)的。浮點(diǎn)機(jī)通用性強(qiáng)，但復(fù)雜；定點(diǎn)機(jī)制造簡單，但精度受到影響。1.2.1定點(diǎn)數(shù)的取值范圍定點(diǎn)數(shù)的表示格式如下： 符號(hào)·

數(shù)值其中，符號(hào)占1位，數(shù)值可有多位，小數(shù)點(diǎn)的位置在符號(hào)位之后、數(shù)值部分的最高位之前，但不占實(shí)際位數(shù)，例如:

01011表示0.1011，是個(gè)正數(shù)；

11011表示1.1011，是個(gè)負(fù)數(shù)。設(shè)定點(diǎn)計(jì)算機(jī)的字長是9位，其中一位是符號(hào)位，另8位是數(shù)值位，則該計(jì)算機(jī)所能表示的數(shù)的絕對(duì)值范圍是：

0.00000001~0.11111111或?qū)懗桑?/p>

2－8~1－2－8

一般地，若定點(diǎn)計(jì)算機(jī)的字長是n位，其中一位是符號(hào)位，則它所能表示的數(shù)的絕對(duì)值范圍是：

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

(數(shù)值位最低位為1，其余位皆為0)(數(shù)值位各位全是1)1.2.2浮點(diǎn)數(shù)的取值范圍在計(jì)算機(jī)中，浮點(diǎn)數(shù)由四部分表示：階符、階碼、數(shù)符(尾符)和數(shù)碼(尾數(shù))。其格式如下： 階符階碼數(shù)符·數(shù)碼對(duì)浮點(diǎn)機(jī)來說，總是規(guī)定數(shù)碼部分的S是純小數(shù)且最高位是1，即

例如，浮點(diǎn)數(shù)110011.101的機(jī)器表示格式如下：因?yàn)?10011.101=26×0.110011101,即小數(shù)點(diǎn)向左移6位，等于減小到原來的1/2-6，所以為保持原值大小不變，還應(yīng)乘以26。移動(dòng)時(shí)應(yīng)保證小數(shù)點(diǎn)后的位上是1(小數(shù)點(diǎn)的位置也是隱含的)。這里階符和數(shù)符全為正，故用0表示，階碼6寫成二進(jìn)制形式即為(110)2。注意：浮點(diǎn)數(shù)的正負(fù)號(hào)是由數(shù)碼位的正負(fù)號(hào)決定的，而階碼的正負(fù)號(hào)只決定小數(shù)點(diǎn)的位置，即決定浮點(diǎn)數(shù)的絕對(duì)值大小。對(duì)給定一定位數(shù)的浮點(diǎn)機(jī)，如何決定它的取值范圍呢?設(shè)有一臺(tái)浮點(diǎn)機(jī)，數(shù)碼位有8位，階碼有3位，另外各有一位符號(hào)位，則它所能表示的數(shù)的絕對(duì)值范圍是：最小值：數(shù)碼部分最小，階碼部分負(fù)絕對(duì)值最大(即階符、階碼全為1)，即所以最小值為2-7×2-1。最大值：數(shù)碼部分最大，階碼部分正最大(即階符為0，階碼全為1)，即階碼7=23-1，2的冪次正好是階碼的位數(shù)。則取值范圍(絕對(duì)值)為

2-7×2-1~27×(1-2-8)或一般地，若數(shù)碼位有n-1位，階碼位有m位，則所能表示的數(shù)的絕對(duì)值范圍為

【例1-4】對(duì)于用32位表示的浮點(diǎn)數(shù)，設(shè)階碼部分為8位，尾數(shù)部分為24位，各含1位符號(hào)位，求它所能表示的數(shù)的絕對(duì)值范圍和有效數(shù)字位數(shù)。先標(biāo)出取最大、最小值時(shí)在內(nèi)存中各位的表示。最小值：當(dāng)階碼負(fù)絕對(duì)值最大、數(shù)碼最小時(shí)，即所表示的數(shù)值為：最大值：當(dāng)階碼正最大、數(shù)碼最大時(shí)，即所表示的數(shù)值為：由此知其范圍為或

2-128~2127×(1-2-23)這是以2為基數(shù)的表示，如何表示成以10為基數(shù)的呢?因?yàn)槲矓?shù)部分不大于1，所以數(shù)的大小主要是由階碼部分決定的。令階碼2127等于十進(jìn)制數(shù)10x，即設(shè)

2127=10x

如能把x求出來，即可轉(zhuǎn)換到十進(jìn)制范圍。對(duì)等式兩邊取對(duì)數(shù)：

127×lg2=x因?yàn)閘g2≈0.3，所以

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

y=-128×lg2≈-128×0.3≈-38因此在十進(jìn)制情況下，這種有7位階碼的浮點(diǎn)數(shù)的取值范圍為10-38~1038。浮點(diǎn)數(shù)的尾數(shù)部分決定數(shù)的精度。23位數(shù)碼的最大值為224-1≈224。令224=10x(二進(jìn)制的24位相當(dāng)于十進(jìn)制的x位)，則

x=24×lg2≈24×0.3≈7一般情況下尾數(shù)達(dá)不到最大值，但也在223和224之間，對(duì)于223，設(shè)有

223=10y

可求出

y=23×lg2≈23×0.3=6.9取y=6，即相當(dāng)于十進(jìn)制的6位。因此對(duì)尾數(shù)是二進(jìn)制的24位的浮點(diǎn)數(shù)，其有效數(shù)字為十進(jìn)制的6~7位。1.2.3整數(shù)的取值范圍對(duì)于由一定位數(shù)表示的整數(shù)N的取值范圍，可因帶符號(hào)位和不帶符號(hào)位、是原碼表示還是補(bǔ)碼表示而不同。設(shè)用8位表示一個(gè)有符號(hào)的整數(shù)，其中最高位是符號(hào)位，則表示數(shù)值的有7位。

(1)若用原碼表示，則當(dāng)數(shù)值的7位全是1時(shí)，整數(shù)N的絕對(duì)值最大，即此絕對(duì)值為27-1,即

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

-127≤N≤127符號(hào)1111111

(2)若用補(bǔ)碼表示，則最小的負(fù)數(shù)表示為該數(shù)值為-128。最大的正數(shù)表示為該數(shù)值為127。則

-128≤N≤1271000000001111111對(duì)于用8位表示的無符號(hào)整數(shù)，它表示的數(shù)全為正數(shù)，故當(dāng)其8位全部是1時(shí)表示的數(shù)值最大，即該數(shù)值為28-1，則

0≤N≤28-1=255一般地，對(duì)由n+1位二進(jìn)制數(shù)表示的整數(shù)：不帶符號(hào)時(shí)，它所表示的數(shù)的范圍為

0≤N≤2n+1-1帶符號(hào)時(shí)：·用原碼表示時(shí)，它所表示的整數(shù)的范圍為

-(2n-1)≤N≤2n-1·用補(bǔ)碼表示時(shí)，它所表示的整數(shù)的范圍為

-2n≤N≤2n-1111111111.3簡單的邏輯運(yùn)算在程序設(shè)計(jì)中往往要根據(jù)某些條件是否成立來決定程序的走向：條件為真執(zhí)行某個(gè)動(dòng)作，條件為假則執(zhí)行另外的動(dòng)作。真和假，這兩個(gè)值被稱為邏輯值，邏輯值也只有這兩個(gè)值。真假邏輯值在不同的環(huán)境下有不同的表示，有的地方用TRUE和FALSE表示，有的地方用非0和0來表示，C語言中就是用后者來表示的。條件也有簡單條件和復(fù)雜條件之分。在邏輯學(xué)中，具有真假意義的句子稱為命題，簡單命題可以表示簡單條件，而由邏輯連接詞連接起來的復(fù)合命題就可以表示復(fù)雜條件。下面簡單介紹一下邏輯連接詞及其使用情況。1.3.1“或”、“與”、“非”運(yùn)算在邏輯演算中，邏輯連接詞又稱為邏輯運(yùn)算符，它的運(yùn)算對(duì)象都是真或假的命題。如果一個(gè)運(yùn)算符需要兩個(gè)運(yùn)算對(duì)象，就稱為雙目運(yùn)算符；如果一個(gè)運(yùn)算符只對(duì)一個(gè)運(yùn)算對(duì)象進(jìn)行運(yùn)算，則稱為單目運(yùn)算符。邏輯運(yùn)算符共有四個(gè)：邏輯“非”、邏輯“與”、邏輯“或”和邏輯“異或”。其中第一個(gè)是單目運(yùn)算符，后三個(gè)是雙目運(yùn)算符。我們這里只介紹前三個(gè)運(yùn)算符。

1.邏輯或(加)運(yùn)算符OR邏輯或運(yùn)算的情況類似于一個(gè)并聯(lián)開關(guān)，如圖1-2所示。只要有一個(gè)開關(guān)接通，電路就接通，電燈就會(huì)發(fā)亮。若燈泡亮用1表示，暗用0表示；A、B表示兩個(gè)邏輯變量，接通用1表示，斷開用0表示；結(jié)果用F表示，則可以寫出如下函數(shù)關(guān)系：

F=AORB結(jié)果F的值也可能是0或1。圖1-2邏輯或運(yùn)算的物理示意圖邏輯變量A、B都可以取0或1中任一個(gè)值，這樣當(dāng)它們連接起來的時(shí)候就會(huì)有不同的組合，在各種組合情況下，結(jié)果值是什么呢?為了清楚地反映邏輯結(jié)果值與各邏輯變量取值間的關(guān)系，我們可以用一個(gè)表來顯示，這樣的表就稱為“真值表”。真值表反映了因變量與自變量之間的狀態(tài)關(guān)系。邏輯或運(yùn)算的真值表為或運(yùn)算符還可以是+、∪、∨等。ABF000101011111即：0OR0=01OR0=10OR1=11OR1=1

2.邏輯與(乘)運(yùn)算符AND邏輯與運(yùn)算符的作用相當(dāng)于一個(gè)串聯(lián)開關(guān)，如圖1-3所示。只有當(dāng)兩個(gè)開關(guān)同時(shí)連通時(shí)，電燈才會(huì)發(fā)亮，其關(guān)系式為F=AANDB其真值表為與運(yùn)算符還可以是×、∩、∧等。ABF000100010111即：0AND0=01AND0=00AND1=01AND1=1圖1-3邏輯與運(yùn)算的物理示意圖即：NOT0=1NOT1=0AF0110

3.邏輯非(否定)運(yùn)算符NOT邏輯非又稱為邏輯否定，它把一個(gè)命題改換成相反的含義，其作用類似于反相開關(guān)電路，如圖1-4所示。當(dāng)開關(guān)接通時(shí)，電燈泡由亮變暗；斷開時(shí)，電燈泡由暗變亮。其關(guān)系式為F=NOTA其真值表為邏輯非運(yùn)算符還可以是~、］、上劃線(如)等。圖1-4邏輯非運(yùn)算的物理示意圖1.3.2真值表上面我們介紹了三種邏輯運(yùn)算符，邏輯運(yùn)算符和邏輯運(yùn)算對(duì)象相結(jié)合構(gòu)成的式子稱為邏輯表達(dá)式。在程序設(shè)計(jì)中我們需要的是邏輯表達(dá)式而不是一個(gè)孤零零的命題。然而在實(shí)際應(yīng)用中，我們卻往往不知道其邏輯表達(dá)式，只知道一些具體的要求。這時(shí)我們可以首先根據(jù)具體要求列出其真值表，然后再根據(jù)真值表寫出邏輯表達(dá)式，這就是真值表的重要意義所在。

【例1-5】一個(gè)房間住了三個(gè)人：甲、乙、丙，求下列條件下房間內(nèi)無人說話的表達(dá)式：

(1)甲從來不說話；

(2)當(dāng)且僅當(dāng)甲在場時(shí)乙才說話；

(3)丙在任何情況下都說話。

編程思路：首先用三個(gè)變量A、B、C表示甲、乙、丙三人以便于書寫，并且規(guī)定其值為1時(shí)表示在房間，為0時(shí)表示不在房間。結(jié)果F為1時(shí)表示房間內(nèi)無人說話，為0時(shí)表示有人說話。第一步：根據(jù)條件，列出真值表：第二步：根據(jù)真值表列出邏輯表達(dá)式。關(guān)鍵是把F值為1的各種情況收集起來，用或運(yùn)算符連接，表示只要有一種情況發(fā)生，就說明房間內(nèi)無人說話。ABCF00010010010101101001101011001110考慮F=1的各種取值：

(1)由真值表中第一行知，A=B=C=0時(shí)F=1，變量本身代表真，變量的否定代表假，則上述條件表示為(NOTA)AND(NOTB)AND(NOTC)解釋為：A不在場并且B不在場并且C也不在場，此時(shí)房間內(nèi)無人說話。

(2)由真值表第三行知，A=C=0,B=1時(shí)F=1，這可以表示為(NOTA)ANDBAND(NOTC)解釋為：A不在場但是B在場并且C不在場，此時(shí)房間內(nèi)無人說話。

(3)由真值表第五行知，當(dāng)A=1,B=C=0時(shí)F=1，這可表示為

AAND(NOTB)AND(NOTC)解釋為：A在場但B不在場并且C不在場，此時(shí)房間內(nèi)無人說話。

說明：邏輯運(yùn)算符AND、OR和NOT有不同的優(yōu)先級(jí)：NOT最高，AND次之，OR最低。因此上面的括號(hào)可以不要，加上是為了清晰。把上面三個(gè)表達(dá)式用OR運(yùn)算符連接起來，即為所求得的邏輯表達(dá)式：((NOTA)AND(NOTB)AND(NOTC))OR((NOTA)ANDBAND(NOTC))OR(AAND(NOTB)AND(NOTC))如果邏輯或運(yùn)算符用“+”表示，邏輯與運(yùn)算符省略，上劃線表示否定，則可以把上面的表達(dá)式寫成：

如果把這個(gè)表達(dá)式作為條件，則可以寫出語句：

THEN打印輸出“房間內(nèi)無人說話”1.4程序的概念一個(gè)程序是一個(gè)由指令組成的序列。指令就是行為或動(dòng)作。從這個(gè)意義上說，程序在計(jì)算機(jī)發(fā)明以前很久就有了。比如彈奏樂曲的樂譜、廚師做菜的食譜、某項(xiàng)工程實(shí)施的計(jì)劃等都可以說是程序，只是計(jì)算機(jī)的程序更復(fù)雜，更需要仔細(xì)而精細(xì)地進(jìn)行編寫而已。程序要由編程者來編寫，并由執(zhí)行者來實(shí)施。實(shí)現(xiàn)指令稱為執(zhí)行或運(yùn)行程序。運(yùn)行中的程序稱為進(jìn)程。程序是靜態(tài)的概念，而進(jìn)程是動(dòng)態(tài)的概念。1.4.1程序的特性所有程序(包括計(jì)算機(jī)程序)都有一些共同的性質(zhì)，這些性質(zhì)主要包括以下幾點(diǎn)：

(1)指令是順序執(zhí)行的。除非有特別的聲明，一般情況下程序總是從第一條指令起依次向后執(zhí)行每一條指令，直至結(jié)束。

(2)程序的執(zhí)行都有一個(gè)結(jié)果。廚師按食譜做菜最后可作出一道好菜；樂師按樂譜彈奏就會(huì)有一首美妙悅耳的樂曲；工程師按規(guī)劃施工可建造出一座漂亮的樓房；用戶按計(jì)算機(jī)程序執(zhí)行可以完成相應(yīng)的任務(wù)。

(3)程序總是要對(duì)某些對(duì)象進(jìn)行操作。廚師做菜要用各種肉類或蔬菜等；演奏家要彈奏樂器；建筑師設(shè)計(jì)要用建筑材料；計(jì)算機(jī)程序操作的對(duì)象則是數(shù)據(jù)。

(4)有的程序要加入對(duì)操作對(duì)象的說明。比如一個(gè)食譜，基本上由兩部分組成，第一部分說明所用的配料，第二部分才是操作的過程。計(jì)算機(jī)程序中有時(shí)也要先對(duì)操作數(shù)據(jù)的屬性加以說明。

(5)有時(shí)指令要求執(zhí)行者作出判斷。指令的編寫者在編制時(shí)并不知道在一次具體實(shí)現(xiàn)中執(zhí)行者會(huì)做些什么。但他可以建立一個(gè)執(zhí)行者用以作出判定的標(biāo)準(zhǔn)，比如“朋友來了，端出好酒；豺狼來了，拿出獵槍”。

(6)一條或一組指令可能需要執(zhí)行多次。比如在中草藥炮制過程中，對(duì)某種藥材要經(jīng)過“九蒸九曬”才符合要求，這種重復(fù)必須指明重復(fù)的次數(shù)。有時(shí)重復(fù)執(zhí)行某些指令不一定有明確的次數(shù)，但可以以是否達(dá)到某個(gè)目標(biāo)作為重復(fù)終止的判斷依據(jù)。比如在把假分?jǐn)?shù)化成真分?jǐn)?shù)時(shí)，可以從分子中不斷地減去分母，直到分子小于分母為止。人工重復(fù)執(zhí)行某些指令也許是很繁瑣枯燥的事情，但由于計(jì)算機(jī)執(zhí)行速度很快，因此重復(fù)執(zhí)行對(duì)它來說就不算什么問題了。1.4.2計(jì)算機(jī)程序的執(zhí)行過程程序是一種手段，程序的編寫者利用程序來和執(zhí)行者進(jìn)行通信。通信就需要語言，不同的場合可以用不同的語言來表示程序。比如用自然語言交待任務(wù)、下達(dá)命令，但大多數(shù)程序設(shè)計(jì)需要一種特殊的語言。對(duì)計(jì)算機(jī)下達(dá)任務(wù)的語言就是計(jì)算機(jī)語言。計(jì)算機(jī)語言有高級(jí)語言和低級(jí)語言之分，但這種高低之分并沒有貴賤之別，其區(qū)分主要是因?yàn)樗鼈儗?duì)計(jì)算機(jī)硬件的接近程度不同。低級(jí)語言主要是指機(jī)器語言(二進(jìn)制語言)和匯編語言，它們離計(jì)算機(jī)硬件最近。用機(jī)器語言寫的指令都是由0和1組成的符號(hào)序列，計(jì)算機(jī)能直接識(shí)別和執(zhí)行，因而速度很快。但這種指令寫起來繁瑣復(fù)雜，非專業(yè)人士不能為之。匯編語言是符號(hào)化的二進(jìn)制語言，它用英文單詞或其縮寫來表達(dá)指令，執(zhí)行速度也很快，但卻受具體機(jī)器系統(tǒng)的制約。高級(jí)語言又稱為算法語言，它用類似于自然語言和數(shù)學(xué)公式的指令編寫程序。這樣編寫、閱讀程序都很方便，并且還不受限于某種機(jī)器系統(tǒng)。高級(jí)語言的出現(xiàn)大大促進(jìn)了計(jì)算機(jī)的普及，使計(jì)算機(jī)從少數(shù)人才能涉足的象牙塔中走出來面向大眾。但是計(jì)算機(jī)并不認(rèn)識(shí)高級(jí)語言程序，計(jì)算機(jī)只認(rèn)識(shí)二進(jìn)制代碼。因此在高級(jí)語言程序和計(jì)算機(jī)之間就需要一個(gè)翻譯，由這個(gè)翻譯把高級(jí)語言程序翻譯成計(jì)算機(jī)能懂的程序。這個(gè)翻譯常被稱為編譯程序或編譯器。不同的高級(jí)語言有不同的編譯器。用高級(jí)語言寫的程序又稱為源程序，它的執(zhí)行過程是這樣的：把源程序輸入給計(jì)算機(jī)，然后編譯器工作，把源程序翻譯成目標(biāo)程序，目標(biāo)程序即是用二進(jìn)制表示的機(jī)器指令，機(jī)器指令再對(duì)輸入的數(shù)據(jù)進(jìn)行操作，最后得到結(jié)果數(shù)據(jù)并輸出。可以看出，執(zhí)行高級(jí)語言程序分為兩個(gè)階段：第一個(gè)階段稱為編譯階段，第二個(gè)階段稱為運(yùn)行階段。在程序執(zhí)行的過程中可能會(huì)出現(xiàn)三種類型的錯(cuò)誤：

(1)編譯錯(cuò)誤。這是在編譯階段發(fā)生的錯(cuò)誤，主要是使用語言的語法不合規(guī)范所引起的錯(cuò)誤。需要把這種錯(cuò)誤全部排除后才能進(jìn)入運(yùn)行階段。

(2)運(yùn)行錯(cuò)誤。這種錯(cuò)誤在編譯時(shí)發(fā)現(xiàn)不了，只在運(yùn)行時(shí)才顯現(xiàn)出來。如對(duì)負(fù)數(shù)開平方，除數(shù)為0，循環(huán)終止條件永遠(yuǎn)不能達(dá)到等，這種錯(cuò)誤常會(huì)引起無限循環(huán)或死機(jī)。

(3)邏輯錯(cuò)誤。這種錯(cuò)誤即使在運(yùn)行時(shí)也顯示不出來，因程序能正常運(yùn)行，但結(jié)果不對(duì)。比如把求平方根的函數(shù)sqrt(x)寫成了求平方的函數(shù)sqr(x)，把表達(dá)式中的加號(hào)“+”寫成了乘號(hào)“*”等。前兩種錯(cuò)誤計(jì)算機(jī)都會(huì)有提示或不正常表象，它會(huì)迫使你進(jìn)行修改，但對(duì)邏輯錯(cuò)誤計(jì)算機(jī)并不提醒，全靠程序員仔細(xì)檢查予以排除。我們可以用一簡圖來顯示一個(gè)高級(jí)語言源程序的執(zhí)行過程，如圖1-5所示。圖1-5高級(jí)語言源程序的執(zhí)行過程1.5算法程序設(shè)計(jì)離不開算法，算法指導(dǎo)程序設(shè)計(jì)，算法是程序的靈魂。程序是語句的集合，但如何圍繞所要解決的任務(wù)來安排這些語句的次序則是由算法決定的。因此程序設(shè)計(jì)的大致步驟如下：

(1)確定算法和數(shù)據(jù)結(jié)構(gòu)。算法是和具體任務(wù)有關(guān)的，而數(shù)據(jù)結(jié)構(gòu)則是程序要處理的數(shù)據(jù)的組織。

(2)把算法以明晰的方法表示出來，如用流程圖、N-S圖、偽碼等方法。

(3)在算法已明確表示出來的基礎(chǔ)上用高級(jí)語言編制程序。1.5.1算法的特點(diǎn)算法，簡單地講，就是解決問題的流程安排，即先做什么，后做什么。精確地講，算法是被精確定義的一系列規(guī)則，這些規(guī)則規(guī)定了解決特定問題的一系列操作順序，以便在有限步驟內(nèi)產(chǎn)生出所求問題的解答。盡管算法因求解問題的不同而千變?nèi)f化、簡繁各異，但它們都必須具備以下五個(gè)特性。

1.確定性算法的每一步運(yùn)算都必須有確切的定義，即每種運(yùn)算所執(zhí)行的操作都必須是確定的、無二義性的。比如在配制某種溶液時(shí)，應(yīng)明確指出“5升水加100克藥粉”，而不能是“一桶水加適量的藥粉”這種不確定的說法。

2.能行性算法中有待實(shí)現(xiàn)的運(yùn)算方法都必須是可執(zhí)行的，即在執(zhí)行者(計(jì)算機(jī))能力范圍之內(nèi)并能在有限時(shí)間內(nèi)完成。

3.有窮性一個(gè)算法必須在執(zhí)行了有窮的步驟之后結(jié)束。如果一個(gè)計(jì)算不具有有窮性，但具有算法的其他特性，則稱之為計(jì)算方法。比如對(duì)無窮調(diào)和級(jí)數(shù)的計(jì)算就不是一個(gè)算法，而是一個(gè)計(jì)算方法。但是在確定了項(xiàng)數(shù)或精度之后，再進(jìn)行的計(jì)算就是有窮的了，這時(shí)對(duì)調(diào)和級(jí)數(shù)的計(jì)算如求和，就變成了算法。

4.輸入一個(gè)算法可以有0個(gè)或0個(gè)以上的輸入，可提供算法操作的數(shù)據(jù)。

5.輸出一個(gè)算法總能產(chǎn)生一個(gè)或多個(gè)輸出，即算法的計(jì)算結(jié)果。1.5.2算法的表示一個(gè)算法應(yīng)該用明晰的方法展現(xiàn)在人們的面前，這樣才易于用計(jì)算機(jī)語言寫出體現(xiàn)算法的程序。表示一個(gè)算法的方法，通常有以下四種。

1.自然語言描述法比如求三個(gè)數(shù)的最大值問題，用自然語言可以描述為：先將兩個(gè)數(shù)a和b進(jìn)行比較，找出其最大者，然后再把它和第三個(gè)數(shù)c進(jìn)行比較，如果它比第三個(gè)數(shù)大，則它就是最大數(shù)，否則第三個(gè)數(shù)c就是最大數(shù)。

2.偽碼表示法所謂偽碼，就是類似于程序設(shè)計(jì)語言的語句，但又不是任何一種真實(shí)的程序設(shè)計(jì)語言的語句，它不涉及程序設(shè)計(jì)的具體細(xì)節(jié)。比如求三個(gè)數(shù)的最大值問題，用偽碼可表示為：ifa>b then把a(bǔ)交給maxelse把b交給maxifmax>c then輸出最大值maxelse輸出最大值c說明：用偽碼表示的詳細(xì)程度沒有一定的標(biāo)準(zhǔn)，可以很詳細(xì)，也可以很簡略。

3.N-S圖表示法這是一種圖語言表示法，其特點(diǎn)是在一個(gè)矩形框內(nèi)完成算法的流程說明。比如求三個(gè)數(shù)的最大值問題，用N-S圖可描述為如圖1-6所示的形式。圖1-6求三個(gè)數(shù)的最大值問題

4.流程圖表示法這也是一種圖語言表示法，它用一些不同的圖例來表示算法的流程。常用的圖例主要有如圖1-7中所示的幾種。比如求三個(gè)數(shù)的最大值問題，用流程圖法可表示為如圖1-8所示的形式。圖1-7流程圖表示法常用圖例圖1-8求三個(gè)數(shù)的最大值問題的流程圖表示1.5.3結(jié)構(gòu)化程序設(shè)計(jì)的三種基本結(jié)構(gòu)

20世紀(jì)60年代，在開發(fā)大型軟件的過程中出現(xiàn)了所謂的“軟件危機(jī)”，其主要表現(xiàn)是：開發(fā)進(jìn)度被推遲；成本超出預(yù)算；軟件產(chǎn)品不可靠。人們認(rèn)識(shí)到軟件開發(fā)要比想象的復(fù)雜得多。在如何克服“軟件危機(jī)”的討論和研究中，誕生了“結(jié)構(gòu)化程序設(shè)計(jì)”的概念，這是編寫出清晰、正確和容易理解的程序的一種指導(dǎo)方針和嚴(yán)格方法。結(jié)構(gòu)化程序設(shè)計(jì)的基本方法是：在設(shè)計(jì)程序時(shí)，本著從上到下、逐步求精的原則，將一個(gè)大的原始問題分解為多個(gè)可獨(dú)立進(jìn)行編程的小問題(即小模塊)，如果某個(gè)模塊還未精細(xì)到能直接進(jìn)行編程的程度，則繼續(xù)對(duì)它進(jìn)行分解，直至能直接編程為止。每個(gè)模塊只有一個(gè)入口和一個(gè)出口，這樣不管編多大的程序，不管有多少人參加編寫，都可以把他們的模塊很自然地連接起來。與非結(jié)構(gòu)化程序設(shè)計(jì)方法相比，采用結(jié)構(gòu)化方法能夠設(shè)計(jì)出更易理解的程序，因此也更容易測試、調(diào)試和修改，甚至從數(shù)學(xué)的意義上講，這種設(shè)計(jì)方法也是正確的。在結(jié)構(gòu)化程序設(shè)計(jì)方法中，有三種基本的控制結(jié)構(gòu)。這三種基本結(jié)構(gòu)是：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。順序結(jié)構(gòu)是指語句的執(zhí)行順序和它在程序中出現(xiàn)的次序是一致的，即一條語句執(zhí)行完后緊接著執(zhí)行它下面的那條語句。選擇結(jié)構(gòu)是根據(jù)一定的條件，把語句分成不同的分支，程序只執(zhí)行其中一個(gè)分支，而不執(zhí)行其他分支。循環(huán)結(jié)構(gòu)是根據(jù)一定的條件，對(duì)某些語句重復(fù)執(zhí)行。被重復(fù)執(zhí)行的語句稱為循環(huán)體。重復(fù)執(zhí)行的次數(shù)可以預(yù)指定，也可以不指定，而由循環(huán)體中的變化所決定。這三種基本結(jié)構(gòu)，可以用圖表示法說明。ABTFAB

1.用N-S圖表示

(1)順序結(jié)構(gòu)：

A執(zhí)行完后接著執(zhí)行B。

(2)選擇結(jié)構(gòu)：

P為條件，當(dāng)P為真(T)時(shí)執(zhí)行A，當(dāng)P為假(F)時(shí)執(zhí)行B。P

(3)循環(huán)結(jié)構(gòu)：循環(huán)結(jié)構(gòu)又分為以下兩種。①while結(jié)構(gòu)：P為條件，只要P為真就執(zhí)行A。PA②repeat-until結(jié)構(gòu)：執(zhí)行A直到P變?yōu)檎鏋橹?。以上各圖中的A和B，可以是一個(gè)簡單語句，也可以是以上三種結(jié)構(gòu)語句之一，這種嵌套代入方式也表明了從上到下、逐步求精的設(shè)計(jì)方法。AP

2.用流程圖表示

(1)順序結(jié)構(gòu)，如圖1-9所示。圖1-9順序結(jié)構(gòu)的流程圖表示

(2)選擇結(jié)構(gòu)，這里又有如下三種形式：①if結(jié)構(gòu)(單路選擇結(jié)構(gòu))，如圖1-10所示。②if/else結(jié)構(gòu)(雙路選擇結(jié)構(gòu))，如圖1-11所示。圖1-10if結(jié)構(gòu)的流程圖表示圖1-11if/else結(jié)構(gòu)的流程圖表示③switch結(jié)構(gòu)(多路選擇結(jié)構(gòu))，如圖1-12所示。圖中，當(dāng)某個(gè)Pi為真時(shí)，執(zhí)行相應(yīng)的語句Ai，然后退出選擇語句(通過break語句實(shí)現(xiàn))。圖1-12switch結(jié)構(gòu)的流程圖表示

(3)循環(huán)結(jié)構(gòu)，也有三種形式：①while結(jié)構(gòu)，如圖1-13所示。②do-while結(jié)構(gòu)，如圖1-14所示。和①的區(qū)別在于，這里是先執(zhí)行語句A，然后再判斷條件P。圖1-13while結(jié)構(gòu)的流程圖表示圖1-14do-while結(jié)構(gòu)的流程圖表示③for結(jié)構(gòu)，如圖1-15所示。圖1-15for結(jié)構(gòu)的流程圖表示從上面各圖中可以看出，每一個(gè)結(jié)構(gòu)只有一個(gè)入口和一個(gè)出口。按順序來組織各種控制結(jié)構(gòu)就能設(shè)計(jì)出結(jié)構(gòu)化的程序，即只要把一個(gè)控制結(jié)構(gòu)的出口點(diǎn)和另一個(gè)控制結(jié)構(gòu)的入口點(diǎn)連接起來即可。結(jié)構(gòu)化程序設(shè)計(jì)的規(guī)則有4條：

(1)從最簡單的流程圖開始。

(2)任何矩形框都可以被兩個(gè)按順序放置的矩形框取代。

(3)任何矩形框都可以被任何結(jié)構(gòu)取代。

(4)規(guī)則(2)和規(guī)則(3)可按任何順序運(yùn)用多次。規(guī)則(2)又稱為“棧式控制規(guī)則”，規(guī)則(3)又稱為“嵌套式控制規(guī)則”。下面用圖示方法展示一下結(jié)構(gòu)程序設(shè)計(jì)的原則，如圖

1-16、圖1-17所示。圖1-16從最簡結(jié)構(gòu)出發(fā)反復(fù)使用規(guī)則(2)和規(guī)則(4)圖1-17對(duì)最簡結(jié)構(gòu)使用規(guī)則(3)和規(guī)則(4)圖1-17中的虛線框就是對(duì)圖1-16中一個(gè)矩形框的細(xì)化。用規(guī)則(4)可以產(chǎn)生更大的、包含內(nèi)容更豐富的、層次更深的嵌套式結(jié)構(gòu)。運(yùn)用規(guī)則所生成的流程圖可以構(gòu)造所有可能的結(jié)構(gòu)化流程圖，因而能夠建立所有可能的結(jié)構(gòu)化程序。

注意：如果不按上面的基本結(jié)構(gòu)來繪制流程圖，就有可能產(chǎn)生非結(jié)構(gòu)化的流程圖，如圖1-18所示。上面介紹了表示算法的四種方法，即自然語言、偽碼、N-S圖和流程圖。下面舉個(gè)例子，用四種不同的方法來表示其算法，以比較各方法的使用和方便程度。圖1-18非結(jié)構(gòu)化的流程圖

【例1-6】用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)的最大公約數(shù)。①用自然語言描述：

S1.輸入兩個(gè)正整數(shù)m和n；

S2.比較m和n,如m小于n，則交換它們的值以保證m是最大數(shù)，m作相除時(shí)的分子；

S3.求m除以n的余數(shù)r;

S4.如余數(shù)r=0，轉(zhuǎn)S6；

S5.把除數(shù)n作為新的分子m,余數(shù)r作為新的分母n,然后轉(zhuǎn)S3；

S6.打印除數(shù)n，即為最大公約數(shù)。例如，設(shè)最初取m為74，n為108。首先將它們調(diào)整為m=108,n=74，則有如下示意性的操作：

mnr

第一遍1087434

第二遍74346

第三遍3464

第四遍642

第五遍420當(dāng)執(zhí)行五遍之后，余數(shù)r=0，則此時(shí)的除數(shù)n=2即為m和n的最大公約數(shù)。②用偽碼描述：inputm,nifm<nthenswapmandnr<=mod(m,n)whiler≠0domnnrrmod(m,n)enddoprintn其中，符號(hào)mod(m,n)代表m除以n的余數(shù)。③用N-S圖描述，如圖1-19所示。④用流程圖描述，如圖1-20所示。圖1-19例1-6的N-S圖描述圖1-20例1-6的流程圖描述從上面的描述可以看出，四種方法各有特色，讀者可以根據(jù)自己的愛好和熟悉程度來決定使用哪一種方法。

說明：在按確定的算法編制程序前，并不一定非要把算法以某種形式寫出來或畫出來。根據(jù)求解問題的難易程度及程序員的編程經(jīng)驗(yàn)，有時(shí)可以畫一些簡圖，甚至什么圖都不畫，而由算法直接編寫程序。1.5.4程序設(shè)計(jì)中的幾種常用算法算法是解決問題的方法，在不同領(lǐng)域中都有各自的算法，但從算法所采用的方法或思路上來看，算法還是有一定共性的。算法按其共性可以分成幾大類，下面主要介紹窮舉法、迭代法和遞歸法。

1.窮舉法窮舉法又稱枚舉法、試探法。如果問題解的值域是有限的、確定的和有序的，則可以把其中每一個(gè)值都拿來試一下，看是否符合所給條件。如果由人來采用該方法進(jìn)行求解，則極為繁瑣，當(dāng)值域很大時(shí)尤其如此；但該方法卻特別適合于由計(jì)算機(jī)求解。對(duì)那些尚未找到或不易找到用解析方法求解的問題，窮舉法不失為一種行之有效的方法。

【例1-7】百雞問題。用100元錢買100只雞，已知一只公雞5元，一只母雞3元，3只小雞1元，問能買的公雞、母雞和小雞各是多少只?設(shè)能買公雞x只，母雞y只，小雞z只，按題意可列出下列方程組：這個(gè)方程組有兩個(gè)方程、3個(gè)未知數(shù)，因而是不定方程的求解問題，可用窮舉法把每一種可能的組合方案都試一下。由題意可知，公雞x的取值范圍是0~20(可以一只公雞都不買，也可以全買成公雞，但最多買20只，當(dāng)然這里還沒有考慮雞的總數(shù)的要求)；同樣，母雞y的取值范圍是0~33；小雞z沒有取值的主動(dòng)權(quán)，它只能在x和y的值確定之后來決定自己的值，即z=100-x-y。當(dāng)x、y、z各取一值之后，還要驗(yàn)證是否符合總錢數(shù)的限制條件：100=5x+3y+(100-x-y)/3共有多少種不同的組合呢?共有21×34=714種。計(jì)算機(jī)把這714種可能性都測試一遍，最后求出符合條件的4組解。我們可以用流程圖來描述這一算法，如圖1-21所示。圖1-21例1-7的流程圖

2.迭代法所謂迭代法，就是根據(jù)問題的初始條件或迭代公式，先求出一個(gè)近似解，判斷它是否符合要求，如不符合要求，則根據(jù)前一個(gè)近似解求出下一個(gè)更好的近似解，一步步向真實(shí)解逼近，直到解滿足要求為止。

【例1-8】求正數(shù)a的平方根。已知迭代公式為，其中a為任意正數(shù)。當(dāng)適當(dāng)取a0之后，則有。由迭代法求的計(jì)