循環結構的三要素及其他

摘要：循環結構是結構化程序設計中最為復雜的一種結構，本文提出構成循環結構的三個要素，論述運用循環結構三要素進行程序設計的方法，以及循環與遞歸的關系。

關鍵詞：算法；程序結構；循環；遞歸

中圖分類號：TP391文獻標識碼：B

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

1問題的提出

結構化程序設計中，只有三種基本的結構：順序、選擇和循環。

順序結構是程序設計過程中自然形成的，也是三種結構中最簡單的一種。選擇結構與我們日常中使用的自然語言“如果...則...否則...”十分相近，只是其嵌套時的二義性在形式上必須有一個明確的規定。

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

2循環結構的三要素

初學程序設計的人，對于如何在程序中使用循環結構實現算法，總覺得不知從何入手，有時即使編出程序，也不盡人意。下面我們從一個簡單的典型實例說起。為了說明問題，本文對有關編程的問題都以C語言函數的方式列出解答。

2.1一個典型實例及其兩種解答

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

int hab(int h， int f);

函數的定義如下：

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

{

int i;

i=h;

while (i＞=0 )

{

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

i--;

}

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

}

這個程序的運行結果是正確的，但是很遺憾，這并不是一個完美的程序，盡管很多教科書也是這樣寫的。我們再來看看下面的另一種解法：

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

{

int i;

i=h

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

i--;

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

}

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

2.2深入分析

比較兩個程序可以發現，關鍵是對條件表達式(i*4+(h-i)*2!=l)的運用。前者把條件表達式放在循環體中，后者把它作為循環條件。看來，有必要對循環結構做深入的分析。

不管一個循環結構有多復雜，都可以從以下三個方面來分析：

1) 初始狀態：所有參與循環的變量在循環之前都必須有一個確定的值。

2) 循環條件：當條件滿足時，循環繼續，否則循環終止。循環條件應是一個邏輯表達式。

3) 循環體：每次循環要執行的語句。

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

2.3一個應用實例

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

f₀=0

f₁=1

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

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

現在要求判別一個給定的正整數x是否在裴波那契序列中，一個直觀的判別方法是從f0和f1出發，不停地求后面的裴波那契序列數。每得到一個裴波那契序列數，就同這個待判別數進行比較，直到相等時輸出“真”。或當得到一個裴波那契序列數大于這個待判別數時，輸出“假”。

要實現這個算法，需用到循環結構。我們來分析一下這個循環結構的三個要素：

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

(2) 循環條件：當前求得的裴波那契序列數 < 待判別數x；

(3) 循環體：計算一個新的裴波那契序列數。

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

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循環結構與程序的閱讀

3.1閱讀的意義

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

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

3.2閱讀的方法

閱讀的目的是為了分析程序中的語句是如何實現算法的。對于一些較為復雜的程序，如果一開始就去分析每一個語句的功能，就很容易掉進“迷宮”。因此在分析一個程序時應該先分析程序的結構，然后再對每個結構中的語句逐一進行跟蹤閱讀。

1. 程序結構的分析

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

程序結構的分析應符合結構化程序設計的原則。一種結構化程序設計語言(如C語言，Pascal)，只包含三種基本結構：順序、選擇和循環。每種結構只有一個入口和一個出口。而各個結構之間的連接方式有兩種：積木式和嵌套式。積木式的連接是一個結構的出口與另一個結構的入口的連接，而嵌套式的連接是在一個結構的內部嵌套另一個結構。一般來說，我們應先分析出程序中積木式連接的各個結構，然后再找出這些結構中的嵌套式連接的結構。分析程序結構時可以借用一些工具，如N-S圖、偽代碼等，即根據源程序畫出能反映程序結構的Ｎ-Ｓ圖或寫出等效的偽代碼。這是一個與編程過程剛好相反的過程。

2. 語句的跟蹤閱讀

對于順序結構的語句，閱讀是不成問題的。而對于選擇結構的語句，由于與我們平時所用的自然語言比較一致，也不是太大的困難。關鍵在于，當有兩個選擇結構連接時，采用積木式的連接與采用嵌套式連接的差別是很大，有時甚至使得程序運行的結果截然相反。

循環結構是三種結構中最為復雜的一種，對這種結構的跟蹤閱讀可以用列表的方法，將循環過程中各語句執行的結果一一列出。這個表包含了循環結構的三個要素。

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

例3.1求兩個正整數的最大公約數。

【歐幾里德算法】

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

E2.[余數為0?] 若r=0， 算法結束， n即為答案。

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

為了使計算過程更為緊湊，也考慮到當n=0時，算法仍然有效，可將以上算法稍作改動如下：

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

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

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

根據以上所描述的算法，我們可以用C語言寫出相應的函數：

int gcd(int m，int n)

{

int r;

while (n!=0)

{

r=m%n;

m=n;

n=r;

}

return m;

}

我們通過一組真實的數據(例如：m=20， n=12)分析循環結構的執行過程，即對循環體內的語句逐一進行跟蹤閱讀，直至循環條件不成立。分析程序執行的過程如下：

閱讀的過程是艱苦的，初學者對此可能不十分習慣。但是這是學習一種計算機程序設計語言所必須掌握的方法，也是必須經歷的過程。企圖繞開這個過程，尋找別的捷徑是不可能的。

4循環與遞歸

遞歸是計算科學中一個很重要的核心概念，它出現在計算科學的各門分支學科中，如計算理論基礎、數據結構、程序設計方法、程序設計語言等等。那么，遞歸與循環有什么聯系和區別呢？

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

4.1遞歸的意義與遞歸函數

我們來看一個簡單的例子。

例4.1求一個正整數n的階乘。

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

1 n=0

f(n)={

n·f(n-1)n＞0

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

例4.2求兩個正整數的最小公倍數。

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

m n=0

gcd(m，n)= {

gcd(n，m%n)n＞0

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

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

4.2用遞歸函數取代循環結構

一個程序如果可以用循環結構來實現，那么也可以用一個遞歸函數來實現。我們先來看一個簡單的例子。

例4.3求一個有n個元素的數組中的最大元素。

用循環結構的方法如下：

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;

}

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

a[k]k=n-1;

max(a，k)= {

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

用C語言編寫的函數如下：

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 ); }

}

這是一個簡單的例子，下面再看一個較為復雜性的例子。

例4.4用遞歸函數求解例2.1。

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

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

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

但在什么情況下能直接得到結果呢？顯然，當雞全部抓走只留下兔子時，就可以直接得到答案，這時腿數應是頭的4倍：

roob(x，y)=x當4*x=y

另外還要考慮在什么情況下問題沒有解。顯然，當4*h＜g時，這個問題無解。

x 4*x=y

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

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

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

結束語

程序設計作為一門學科，經歷了子程序、高級語言、結構化程序設計三個里程碑[2]。近十幾年興起的面向對象程序設計可以說是第四個里程碑。程序設計在計算科學這門年輕的學科中，是一門“古老”的分支學科，又是一門久經不衰的學科。計算科學中的許多新思想、新方法、新技術都首先體現在程序設計上。這種現象使我們不得不領悟到，這門課程中的許多知識反映了計算科學深刻的內涵，程序設計的教學應體現這一點。例如上述的循環結構，就很值得我們去探討。本文提出的一些觀點，確實很膚淺，希望能起到一個拋磚引玉的作用。

參考文獻：

[1] 蘇運霖譯. 計算機程序設計藝術 第1卷 基本算法［M］. 北京：國防工業出版社，2002.

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

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

收稿日期：2006-5-27

通信地址：廣東省廣州市 華南師范大學計算機學院， 510631

E-mail：forest0504@sohu.com

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