摘要：循環(huán)結(jié)構(gòu)是結(jié)構(gòu)化程序設(shè)計(jì)中最為復(fù)雜的一種結(jié)構(gòu)，本文提出構(gòu)成循環(huán)結(jié)構(gòu)的三個(gè)要素，論述運(yùn)用循環(huán)結(jié)構(gòu)三要素進(jìn)行程序設(shè)計(jì)的方法，以及循環(huán)與遞歸的關(guān)系。

關(guān)鍵詞：算法；程序結(jié)構(gòu)；循環(huán)；遞歸

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1672-5913(2007)12-0083-05

1問題的提出

結(jié)構(gòu)化程序設(shè)計(jì)中，只有三種基本的結(jié)構(gòu)：順序、選擇和循環(huán)。

順序結(jié)構(gòu)是程序設(shè)計(jì)過程中自然形成的，也是三種結(jié)構(gòu)中最簡單的一種。選擇結(jié)構(gòu)與我們?nèi)粘Ｖ惺褂玫淖匀徽Z言“如果...則...否則...”十分相近，只是其嵌套時(shí)的二義性在形式上必須有一個(gè)明確的規(guī)定。

而循環(huán)結(jié)構(gòu)是三者中最為復(fù)雜的，也是使用最多的。一個(gè)算法往往要用循環(huán)結(jié)構(gòu)來描述，一個(gè)程序能否正確編寫又往往取決于對(duì)循環(huán)結(jié)構(gòu)的正確理解和使用。因此，有必要深入對(duì)循環(huán)結(jié)構(gòu)做一個(gè)分析。本文從循環(huán)結(jié)構(gòu)的三個(gè)要素、循環(huán)結(jié)構(gòu)與程序的閱讀、循環(huán)與遞歸的聯(lián)系等三個(gè)方面進(jìn)行分析與論述，而這些在目前的教學(xué)中往往很少提到，甚至是被忽略的。

2循環(huán)結(jié)構(gòu)的三要素

初學(xué)程序設(shè)計(jì)的人，對(duì)于如何在程序中使用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)算法，總覺得不知從何入手，有時(shí)即使編出程序，也不盡人意。下面我們從一個(gè)簡單的典型實(shí)例說起。為了說明問題，本文對(duì)有關(guān)編程的問題都以C語言函數(shù)的方式列出解答。

2.1一個(gè)典型實(shí)例及其兩種解答

例2.1雞兔同籠，有h個(gè)頭，f只腳，求雞兔各多少。這是我國古代一個(gè)典型的算術(shù)問題?，F(xiàn)在要設(shè)計(jì)一個(gè)函數(shù)，求出兔子的數(shù)目(求出兔子的數(shù)目，自然就可以得到雞的數(shù)目)。不妨設(shè)這個(gè)函數(shù)為：

int hab(int h， int f);

函數(shù)的定義如下：

int rabbit (int h， int f)// h為頭數(shù)， f為腳數(shù)

{

int i;

i=h;

while (i＞=0 )

{

if (i*4+(h-i)*2==f) break;

i--;

}

return i; //-1表示該該問題無解。

}

這個(gè)程序的運(yùn)行結(jié)果是正確的，但是很遺憾，這并不是一個(gè)完美的程序，盡管很多教科書也是這樣寫的。我們?cè)賮砜纯聪旅娴牧硪环N解法：

int rabbit (int h， int f)// h為頭數(shù)， f為腳數(shù)

{

int i;

i=h

while((i＞=0) (i*4+(h-i)*2!=f ))

i--;

return i;//-1表示該問題無解。

}

以上兩個(gè)程序都用到循環(huán)結(jié)構(gòu)，第一個(gè)程序在循環(huán)結(jié)構(gòu)中嵌套了一個(gè)選擇結(jié)構(gòu)，并且使用了break語句。而在第二個(gè)程序中，無需這樣做。無論從程序的結(jié)構(gòu)，還是從程序的可讀性來說，后者顯得比前者要好得多。那么問題出在哪里呢？

2.2深入分析

比較兩個(gè)程序可以發(fā)現(xiàn)，關(guān)鍵是對(duì)條件表達(dá)式(i*4+(h-i)*2!=l)的運(yùn)用。前者把條件表達(dá)式放在循環(huán)體中，后者把它作為循環(huán)條件?？磥恚斜匾獙?duì)循環(huán)結(jié)構(gòu)做深入的分析。

不管一個(gè)循環(huán)結(jié)構(gòu)有多復(fù)雜，都可以從以下三個(gè)方面來分析：

1) 初始狀態(tài)：所有參與循環(huán)的變量在循環(huán)之前都必須有一個(gè)確定的值。

2) 循環(huán)條件：當(dāng)條件滿足時(shí)，循環(huán)繼續(xù)，否則循環(huán)終止。循環(huán)條件應(yīng)是一個(gè)邏輯表達(dá)式。

3) 循環(huán)體：每次循環(huán)要執(zhí)行的語句。

這就是我們所講的循環(huán)結(jié)構(gòu)三要素。從這個(gè)角度再來分析上面的例子，就很容易找到問題的結(jié)癥：(i*4+(h-i)*2!=l)是循環(huán)條件之一，因此不應(yīng)放在循環(huán)體內(nèi)使用。第一種方法雖然也能得到正確的結(jié)果，但并不是好的方法，甚至是不正確的方法。

2.3一個(gè)應(yīng)用實(shí)例

例2.2 裴波那契序列數(shù)的遞歸表示如下：

f₀=0

f₁=1

f_n=f_n-2+f_n-1(n＞=2)

對(duì)于任意給定的正整數(shù)x，判別其是否在裴波那契序列中。

現(xiàn)在要求判別一個(gè)給定的正整數(shù)x是否在裴波那契序列中，一個(gè)直觀的判別方法是從f0和f1出發(fā)，不停地求后面的裴波那契序列數(shù)。每得到一個(gè)裴波那契序列數(shù)，就同這個(gè)待判別數(shù)進(jìn)行比較，直到相等時(shí)輸出“真”?；虍?dāng)?shù)玫揭粋€(gè)裴波那契序列數(shù)大于這個(gè)待判別數(shù)時(shí)，輸出“假”。

要實(shí)現(xiàn)這個(gè)算法，需用到循環(huán)結(jié)構(gòu)。我們來分析一下這個(gè)循環(huán)結(jié)構(gòu)的三個(gè)要素：

(1) 初始狀態(tài)：f0=0; f1=1，x=?；

(2) 循環(huán)條件：當(dāng)前求得的裴波那契序列數(shù) < 待判別數(shù)x；

(3) 循環(huán)體：計(jì)算一個(gè)新的裴波那契序列數(shù)。

根據(jù)以上的分析，判別一個(gè)給定的正整數(shù)x是否在求裴波那契序列中的C函數(shù)如下：

int in_fib(int x)

{

int f0=0， f1=1;

while (f1＜x)

{

t=f1+f0;

f0=f1;

f1=t;

}

return (x==f1|| x==f0);

}

3循環(huán)結(jié)構(gòu)與程序的閱讀

3.1閱讀的意義

對(duì)于計(jì)算機(jī)程序的閱讀，著名的計(jì)算機(jī)科學(xué)家克努特曾說過：閱讀他人的計(jì)算機(jī)程序獲得技巧是極其重要的，但在許許多多的計(jì)算機(jī)課程中這樣一種訓(xùn)練卻可悲地被忽視了，因此導(dǎo)致計(jì)算機(jī)極其低效率的使用。

學(xué)習(xí)一種計(jì)算機(jī)程序設(shè)計(jì)語言，不管是匯編語言還是高級(jí)語言，一個(gè)重要而又常用的方法就是閱讀：閱讀書中的例題，閱讀別人寫的程序，更多的是閱讀自已寫的程序。在某種意義上來說，一個(gè)程序是“被閱讀”的。首先是被計(jì)算機(jī)閱讀，這是毫無疑義的，但更多時(shí)候是被人閱讀。

3.2閱讀的方法

閱讀的目的是為了分析程序中的語句是如何實(shí)現(xiàn)算法的。對(duì)于一些較為復(fù)雜的程序，如果一開始就去分析每一個(gè)語句的功能，就很容易掉進(jìn)“迷宮”。因此在分析一個(gè)程序時(shí)應(yīng)該先分析程序的結(jié)構(gòu)，然后再對(duì)每個(gè)結(jié)構(gòu)中的語句逐一進(jìn)行跟蹤閱讀。

1. 程序結(jié)構(gòu)的分析

程序結(jié)構(gòu)的分析過程分為兩個(gè)步驟：第一是找出組成程序的各種結(jié)構(gòu)，第二是找出這些結(jié)構(gòu)之間的連接方式。

程序結(jié)構(gòu)的分析應(yīng)符合結(jié)構(gòu)化程序設(shè)計(jì)的原則。一種結(jié)構(gòu)化程序設(shè)計(jì)語言(如C語言，Pascal)，只包含三種基本結(jié)構(gòu)：順序、選擇和循環(huán)。每種結(jié)構(gòu)只有一個(gè)入口和一個(gè)出口。而各個(gè)結(jié)構(gòu)之間的連接方式有兩種：積木式和嵌套式。積木式的連接是一個(gè)結(jié)構(gòu)的出口與另一個(gè)結(jié)構(gòu)的入口的連接，而嵌套式的連接是在一個(gè)結(jié)構(gòu)的內(nèi)部嵌套另一個(gè)結(jié)構(gòu)。一般來說，我們應(yīng)先分析出程序中積木式連接的各個(gè)結(jié)構(gòu)，然后再找出這些結(jié)構(gòu)中的嵌套式連接的結(jié)構(gòu)。分析程序結(jié)構(gòu)時(shí)可以借用一些工具，如N-S圖、偽代碼等，即根據(jù)源程序畫出能反映程序結(jié)構(gòu)的Ｎ-Ｓ圖或?qū)懗龅刃У膫未a。這是一個(gè)與編程過程剛好相反的過程。

2. 語句的跟蹤閱讀

對(duì)于順序結(jié)構(gòu)的語句，閱讀是不成問題的。而對(duì)于選擇結(jié)構(gòu)的語句，由于與我們平時(shí)所用的自然語言比較一致，也不是太大的困難。關(guān)鍵在于，當(dāng)有兩個(gè)選擇結(jié)構(gòu)連接時(shí)，采用積木式的連接與采用嵌套式連接的差別是很大，有時(shí)甚至使得程序運(yùn)行的結(jié)果截然相反。

循環(huán)結(jié)構(gòu)是三種結(jié)構(gòu)中最為復(fù)雜的一種，對(duì)這種結(jié)構(gòu)的跟蹤閱讀可以用列表的方法，將循環(huán)過程中各語句執(zhí)行的結(jié)果一一列出。這個(gè)表包含了循環(huán)結(jié)構(gòu)的三個(gè)要素。

我們還是從著名的歐幾里德算法說起。

例3.1求兩個(gè)正整數(shù)的最大公約數(shù)。

【歐幾里德算法】

E1.[求余數(shù)] 以n除m并令r為所得余數(shù)(0＜=r＜n)。

E2.[余數(shù)為0?] 若r=0， 算法結(jié)束， n即為答案。

E3.[互換] 置m←n， n←r， 并返回步驟E1。

為了使計(jì)算過程更為緊湊，也考慮到當(dāng)n=0時(shí)，算法仍然有效，可將以上算法稍作改動(dòng)如下：

E'1.[n為0?] 若n=0， 算法結(jié)束， m即為答案。

E'2.[求余數(shù)] 以n除m并令r為所得余數(shù)(0＜=n＜n)。

E'3.[互換] 置m←n， n←r， 并返回步驟E'1。

根據(jù)以上所描述的算法，我們可以用C語言寫出相應(yīng)的函數(shù)：

int gcd(int m，int n)

{

int r;

while (n!=0)

{

r=m%n;

m=n;

n=r;

}

return m;

}

我們通過一組真實(shí)的數(shù)據(jù)(例如：m=20， n=12)分析循環(huán)結(jié)構(gòu)的執(zhí)行過程，即對(duì)循環(huán)體內(nèi)的語句逐一進(jìn)行跟蹤閱讀，直至循環(huán)條件不成立。分析程序執(zhí)行的過程如下：

閱讀的過程是艱苦的，初學(xué)者對(duì)此可能不十分習(xí)慣。但是這是學(xué)習(xí)一種計(jì)算機(jī)程序設(shè)計(jì)語言所必須掌握的方法，也是必須經(jīng)歷的過程。企圖繞開這個(gè)過程，尋找別的捷徑是不可能的。

4循環(huán)與遞歸

遞歸是計(jì)算科學(xué)中一個(gè)很重要的核心概念，它出現(xiàn)在計(jì)算科學(xué)的各門分支學(xué)科中，如計(jì)算理論基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)方法、程序設(shè)計(jì)語言等等。那么，遞歸與循環(huán)有什么聯(lián)系和區(qū)別呢？

在關(guān)于循環(huán)結(jié)構(gòu)三要素中，我們說循環(huán)結(jié)構(gòu)中的第一個(gè)要素是循環(huán)的初始狀態(tài)，那么每循環(huán)一次，參與循環(huán)的變量中至少有一個(gè)會(huì)發(fā)生變化(否則就會(huì)出現(xiàn)“死循環(huán)”)。因此，循環(huán)的過程就是從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)，在經(jīng)歷了若干個(gè)狀態(tài)之后，到達(dá)終結(jié)狀態(tài)，循環(huán)就結(jié)束。因此可以把一個(gè)循環(huán)結(jié)構(gòu)看成是一個(gè)有窮狀態(tài)機(jī)。在計(jì)算理論上，有窮狀態(tài)機(jī)能計(jì)算的問題，圖靈機(jī)必能計(jì)算，而圖靈機(jī)與遞歸函數(shù)是等價(jià)的。從這個(gè)意義上講，一個(gè)可以用循環(huán)結(jié)構(gòu)解決的問題必然也可以用遞歸方法來解決。對(duì)現(xiàn)在一般在大學(xué)一、二年級(jí)學(xué)習(xí)程序設(shè)計(jì)的學(xué)生來說，還不可能深入討論這個(gè)問題。但我們可以用一些典型的實(shí)例，通過循環(huán)與遞歸的對(duì)比，使得低年級(jí)的學(xué)生們對(duì)遞歸有一個(gè)初步的認(rèn)識(shí)。

4.1遞歸的意義與遞歸函數(shù)

我們來看一個(gè)簡單的例子。

例4.1求一個(gè)正整數(shù)n的階乘。

根據(jù)正整數(shù)階乘的定義ｎ！＝1×2×3×......×ｎ，用一個(gè)循環(huán)結(jié)構(gòu)即可很容易編寫出計(jì)算階乘的程序。如果用一個(gè)函數(shù)f(n)來表示n的階乘，也可以這樣來定義f(n)：

1 n=0

f(n)={

n·f(n-1)n＞0

在定義f(n)時(shí)又用到f這個(gè)函數(shù)，這就是遞歸。注意，在定義式中用到函數(shù)f，但它的自變量是n-1，計(jì)算n-1的階乘要比計(jì)算n的階乘容易一些。而且當(dāng)n=0時(shí)，可以直接得到答案f(0)=1。

例4.2求兩個(gè)正整數(shù)的最小公倍數(shù)。

歐幾里德算法(見例3.1)與以下的遞歸函數(shù)是等價(jià)的：

m n=0

gcd(m，n)= {

gcd(n，m%n)n＞0

在這里，當(dāng)n>0時(shí)，計(jì)算的是n和m%n的最小公倍數(shù)。顯然，這時(shí)的兩個(gè)正整數(shù)要比原來的兩個(gè)正整數(shù)(m， n)要小，計(jì)算也變得容易一些。

通過以上的例子，我們可以這樣來理解遞歸的意義：把一個(gè)復(fù)雜的、規(guī)模較大的問題轉(zhuǎn)化為簡單的、規(guī)模較小的同一個(gè)問題，直至可以直接得到問題的解。

4.2用遞歸函數(shù)取代循環(huán)結(jié)構(gòu)

一個(gè)程序如果可以用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)，那么也可以用一個(gè)遞歸函數(shù)來實(shí)現(xiàn)。我們先來看一個(gè)簡單的例子。

例4.3求一個(gè)有n個(gè)元素的數(shù)組中的最大元素。

用循環(huán)結(jié)構(gòu)的方法如下：

int max(int a[])

{

int i， m;

m=a[0]

for (i=1; i＜10，i++)

if(max＜a[i])m=a[i];

return m;

}

用遞歸函數(shù)。設(shè)一遞歸函數(shù)max(a，k)是求a數(shù)組中第ｋ個(gè)元素及其后所有元素的最大者：

a[k]k=n-1;

max(a，k)= {

a[k]＞max(a，k+1)?a[k]：max(a，k+1) k＜n-1

用C語言編寫的函數(shù)如下：

int max(int a[]， int k， int n)

{ int m;

if (k==n-1)return ( a[k] )

else {m=max(a，k+1);

return ( a[k]＞m?a[k]：m ); }

}

這是一個(gè)簡單的例子，下面再看一個(gè)較為復(fù)雜性的例子。

例4.4用遞歸函數(shù)求解例2.1。

用遞歸函數(shù)來求解例2.1，應(yīng)如何考慮呢？正如以上所說，遞歸的意義是把一個(gè)復(fù)雜的、規(guī)模較大的問題轉(zhuǎn)化為簡單的、規(guī)模較小的同一個(gè)問題，直至可以直接得到問題的解。因此我們可以這樣來考慮：把籠中的一只雞抓走，籠中的兔子的數(shù)目是不變的，顯然這仍然是雞兔同籠的問題，但少了一只雞，問題就變得簡單了一點(diǎn)。當(dāng)所有的雞都被抓走時(shí)，剩下的都是兔，這時(shí)就可以直接得到答案——腿數(shù)除以頭數(shù)就是兔子的數(shù)目。

我們用robb(h，g)這樣一個(gè)函數(shù)表示求兔子的數(shù)目，參數(shù)h、g分別表示頭數(shù)和腿數(shù)，因此有：

robb(x，y)=robb(x-1，y-2)

但在什么情況下能直接得到結(jié)果呢？顯然，當(dāng)雞全部抓走只留下兔子時(shí)，就可以直接得到答案，這時(shí)腿數(shù)應(yīng)是頭的4倍：

roob(x，y)=x當(dāng)4*x=y

另外還要考慮在什么情況下問題沒有解。顯然，當(dāng)4*h＜g時(shí)，這個(gè)問題無解。

x 4*x=y

robb(x，y)={ robb(x-1，y-2) 4*x＞y

-1 4*x＜y(-1表示問題無解)

在求得兔子的數(shù)目之后，只要用總數(shù)減去兔子的數(shù)目，就能求出雞的數(shù)目。

結(jié)束語

程序設(shè)計(jì)作為一門學(xué)科，經(jīng)歷了子程序、高級(jí)語言、結(jié)構(gòu)化程序設(shè)計(jì)三個(gè)里程碑[2]。近十幾年興起的面向?qū)ο蟪绦蛟O(shè)計(jì)可以說是第四個(gè)里程碑。程序設(shè)計(jì)在計(jì)算科學(xué)這門年輕的學(xué)科中，是一門“古老”的分支學(xué)科，又是一門久經(jīng)不衰的學(xué)科。計(jì)算科學(xué)中的許多新思想、新方法、新技術(shù)都首先體現(xiàn)在程序設(shè)計(jì)上。這種現(xiàn)象使我們不得不領(lǐng)悟到，這門課程中的許多知識(shí)反映了計(jì)算科學(xué)深刻的內(nèi)涵，程序設(shè)計(jì)的教學(xué)應(yīng)體現(xiàn)這一點(diǎn)。例如上述的循環(huán)結(jié)構(gòu)，就很值得我們?nèi)ヌ接憽１疚奶岢龅囊恍┯^點(diǎn)，確實(shí)很膚淺，希望能起到一個(gè)拋磚引玉的作用。

參考文獻(xiàn)：

[1] 蘇運(yùn)霖譯. 計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 第1卷 基本算法［M］. 北京：國防工業(yè)出版社，2002.

[2] 王選. 王選文集［M］.北京大學(xué)出版社，1997.

[3] 趙致琢. 計(jì)算科學(xué)導(dǎo)論(第二版)［M］. 北京：科學(xué)出版社，1998.

收稿日期：2006-5-27

通信地址：廣東省廣州市 華南師范大學(xué)計(jì)算機(jī)學(xué)院， 510631

E-mail：forest0504@sohu.com

電話：85215317(辦公) 87221177(家庭)