1.1 從素數(shù)問題看面向?qū)ο?/h2>

視頻講解

隨著C++、Java、C#等面向?qū)ο缶幊陶Z言的日益普及，面向?qū)ο蠹夹g(shù)已經(jīng)得到了廣泛的應(yīng)用。從面向?qū)ο蟮木幊陶Z言到面向?qū)ο筌浖こ谭椒ㄒ踩找姹蝗藗冎匾暺饋怼Ｃ嫦驅(qū)ο蟮母M一步應(yīng)用（如面向構(gòu)件、面向服務(wù)、面向模式等）也逐步發(fā)展起來，而這些新方法都是建立在面向?qū)ο蟮乃季S方式上的。由此可見，深入理解面向?qū)ο蟮乃季S方式不僅可以幫助我們理解當(dāng)前面臨的應(yīng)用模式，還是我們進一步學(xué)習(xí)和發(fā)展的必經(jīng)之路。

很多人都經(jīng)歷過傳統(tǒng)的結(jié)構(gòu)化思維方式，讓我們先通過一個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)中的算法問題來探討如何走出傳統(tǒng)的思維模式。利用面向?qū)ο蟮乃季S方式來解決問題，進而理解到底什么是面向?qū)ο笏季S方式，為后續(xù)的對象建模熱身。

1.1.1 問題的提出

這里，我們所面臨的是一個求素數(shù)的問題。素數(shù)（也叫質(zhì)數(shù)）是指除了1和它本身外，不能被其他正整數(shù)整除的數(shù)。按照習(xí)慣規(guī)定，1不算素數(shù)，最小的素數(shù)為2，其余的有3、5、7、11、13、17、19等。

根據(jù)上面的定義可以推導(dǎo)出判斷素數(shù)的算法：對于數(shù)n，判斷n能否被i（i=2,3,4, 5, ..., n—1）整除，如果全部不能被整除，則n是素數(shù)，只要有一個能除盡，則n不是素數(shù)。事實上，為了壓縮循環(huán)次數(shù)，可將判斷范圍從2～n—1改為2～sqrt（n）。

篩選法是一個經(jīng)典的求素數(shù)的算法，它的作用并不是判斷某個數(shù)是否為素數(shù)，而是求小于數(shù)n的所有素數(shù)。下面通過一個簡單的例子來說明篩選法的求解過程。

我們需要求解50以內(nèi)的所有素數(shù)i（2＜i＜n），為此需要進行如下的篩選（見圖1-1）。

圖1-1 篩選法求素數(shù)示意圖

為了利用程序?qū)崿F(xiàn)此算法，需要進行算法設(shè)計。考慮分別采用結(jié)構(gòu)化方法和面向?qū)ο蟮姆椒▽崿F(xiàn)此算法，并將設(shè)計方案以合適的方式記錄下來。下面將通過對兩種不同方法的比較，講解結(jié)構(gòu)化方法和面向?qū)ο蠓椒ㄔ诒举|(zhì)上的區(qū)別。

1.1.2 傳統(tǒng)的結(jié)構(gòu)化解決方案

按照傳統(tǒng)的結(jié)構(gòu)化方法，算法的執(zhí)行過程如下所示。

（1）以當(dāng)前最小的數(shù)（即2）作為因子，將后面所有可以被2整除的數(shù)去掉（因為它們肯定不是素數(shù)，參見圖1-1的第1行，去掉后面的4、6、8等，剩余結(jié)果見第2行）。

（2）取剩余序列中第二小的數(shù)（即3）作為因子，將后面所有可以被3整除的數(shù)去掉（參見圖1-1中的第2行，去掉后面的9、15、21等，剩余結(jié)果見第3行）。

（3）如此繼續(xù)，直到所取得最小數(shù)大于sqrt（n）（圖1-1中第4行為最后一次篩選，此時的因子為7，因為下一個因子即為11，大于sqrt（50））。

（4）剩余的序列即為n以內(nèi)的所有素數(shù)。

為了更清楚地描述該算法，可以采用流程圖來闡述算法流程，該算法的流程圖如圖1-2所示。

圖1-2 篩選法求素數(shù)流程圖

需要說明的是，上述的流程圖和前面描述的算法有所出入。在具體實現(xiàn)時，考慮到算法的執(zhí)行效率，并沒有將當(dāng)前因子的倍數(shù)直接刪除（因為如果采用數(shù)組存儲當(dāng)前數(shù)字序列，則刪除過程的算法復(fù)雜度都為O（n）），而是將相應(yīng)的位置設(shè)為0，表明該位置已經(jīng)沒有數(shù)據(jù)了。

設(shè)計出這樣一個算法后，后面的實現(xiàn)過程就是“水到渠成”的事了，我們可以選擇一種合適的編程語言來實現(xiàn)。下面列出了該算法的C語言實現(xiàn)。

    int main(){
        int ?sieve, n;
        int iCounter=2, iMax, i;
        printf("Please input max number:");
        scanf("%d", &n);
        sieve=(int?)malloc((n-1)?sizeof(int))
        for(i=0; i  n-1; i++){sieve[i]=i+2; }
        iMax=sqrt(n);
        while(iCounter =iMax){
            for(i=2?iCounter-2; i  n-1; i+=iCounter)
                sieve[i]=0;
            iCounter++; }
        for(i=0; i  n-1; i++)
            if sieve[i]! =0 printf("%d", sieve[i]);
        return 0;
    }

1.1.3 面向?qū)ο蟮慕鉀Q方案

在上面的問題中，可以很容易地從算法描述中構(gòu)造目標程序。很自然，這也似乎很符合人們的思維習(xí)慣。那么這種方法是面向?qū)ο蟮姆椒▎幔恳苍S讀者都會說不是。因為很明顯，我們采用的是C語言實現(xiàn)的，而C語言顯然是結(jié)構(gòu)化的。什么才算是面向?qū)ο蟮姆椒兀咳绻F(xiàn)在需要用面向?qū)ο蟮姆椒▉斫鉀Q這個問題，那么又應(yīng)該怎么做呢？

有人也許會說：“這很簡單，Java語言是一門真正的面向?qū)ο蟮恼Z言，用Java語言去實現(xiàn)這個算法是不是就是面向?qū)ο竽兀俊蹦敲矗旅婢涂纯丛撍惴ǖ腏ava語言實現(xiàn)。

    import java.lang.Math;
    public class PrimerNumber{
        public static void main(String args[]){
            int n=50;
            int sieve[]=new int[n-1];
            int iCounter=2, iMax, i;
            for(i=0; i  n-1; i++){sieve[i]=i+2; }
            iMax=(int)Math.sqrt(n);
            while(iCounter =iMax){
                for(i=2?iCounter-2; i  n-1; i+=iCounter)
                    sieve[i]=0;
                iCounter++;
            }
            for(i=0; i  n-1; i++)
            if(sieve[i]! =0)System.out.println(sieve[i]);
        }
    }

在這個程序中，可以看到一個面向?qū)ο蟮年P(guān)鍵特征——類。為了能夠使程序正確地通過編譯并運行，我們需要利用Java的關(guān)鍵字class定義一個類，并為該類定義相應(yīng)的成員函數(shù)（main（）函數(shù)），這不就是面向?qū)ο髥幔吭瓉磉@么簡單。

真的是這樣的嗎？我們再仔細看看程序的內(nèi)部實現(xiàn)，怎么這么面熟？這不是和前面的C程序很類似嗎？定義數(shù)組、利用for循環(huán)初始化、利用while循環(huán)控制因子，只不過將語法從C換成了Java。整個算法實現(xiàn)的思維方式完全沒有變化，這顯然不是面向?qū)ο螅@只不過是披著“面向?qū)ο蟆逼さ慕Y(jié)構(gòu)化程序，可把它稱為“偽面向?qū)ο蟆薄?/p>

那么怎樣才算面向?qū)ο蟮乃季S方式呢？到底要怎樣去做才是一個面向?qū)ο蟮某绦蚰兀吭谶@里暫不討論面向?qū)ο蟮母拍罨蚶碚摚ㄎ覀冊诤罄m(xù)章節(jié)中會陸續(xù)介紹這些內(nèi)容），先來看看這個例子如何通過面向?qū)ο蟮姆椒▽崿F(xiàn)。

人們都知道，在面向?qū)ο蟮姆椒ㄖ校钪匾母拍钍穷惡蛯ο螅@些算法所要求的功能是通過各個對象之間的交互實現(xiàn)的（這就像人們?nèi)粘Ｉ钜粯樱瑸榱送瓿赡骋患拢枰透鞣N不同的人、物打交道，這些人和物就是對象，而打交道的過程就是交互）。因此在面向?qū)ο蟮乃季S方法中，我們并不是關(guān)注算法本身，而需要關(guān)注為了完成這個算法，需要什么樣的“人”和“物”（即對象），再定義“人”和“物”之間的關(guān)系，從而明確兩者是如何“打交道”（即交互）的。把這個過程明確后，事就自然辦成了（即實現(xiàn)了算法）。

按照這種思維模式，再來看前面的篩選法求素數(shù)的問題是怎樣的一個過程。在這個算法中，我們看到了什么？

（1）看到了一堆需要處理的整數(shù)，這些整數(shù)構(gòu)成數(shù)據(jù)源，這個數(shù)據(jù)源就是一個待處理對象，針對這個對象即可抽象出一個類：篩子Sieve（存儲數(shù)據(jù)源）。

（2）看到了一個過濾因子，通過這個因子篩選后面的數(shù)，這個因子也是一個對象，針對這個對象即可抽象出一個類：過濾器Filter（記錄當(dāng)前的過濾因子）。

（3）還看到了一些其他方面，例如為了能夠?qū)?shù)據(jù)源進行遍歷，需要一個計數(shù)器記錄當(dāng)前正在訪問的數(shù)據(jù)值，這個計數(shù)器對象即可抽象成類：計數(shù)器Counter（記錄當(dāng)前正在篩選的數(shù)據(jù)）。

到此為止，就從業(yè)務(wù)場景中找出了為了實現(xiàn)該算法所需要的對象，這些對象就可以滿足基本的業(yè)務(wù)需求。然而，這還不是面向?qū)ο蠓椒ǖ娜浚€需要進行進一步的抽象。

如果僅僅找到具體的業(yè)務(wù)對象，還不算真正的面向?qū)ο螅@只不過是“基于對象”罷了。要做到真正的面向?qū)ο螅€需要執(zhí)行最關(guān)鍵的一步——抽象。這一步是面向?qū)ο蠹夹g(shù)中最難的一步，只有做好了這一步，程序（或軟件）才會獲得那些面向?qū)ο蟆皬V告語”中所謂的面向?qū)ο蟮母鞣N好處（如穩(wěn)定性、復(fù)用性等），否則這一切都是空談。至于如何對這個例子進行抽象，則是一個非常復(fù)雜的問題，在這里并不展開討論（關(guān)于抽象，后面會有專門的章節(jié)進行論述）。下面讓我們直接看結(jié)果，圖1-3即為篩選法求素數(shù)問題的類圖。

圖1-3 篩選法求素數(shù)的類圖

從圖1-3中可以看出，除了前面所找出的3個對象的類外，還定義了一個新的抽象類Item（在圖中類名用斜體字表示），作為這3個類的公有基類。通過該抽象層次，為成員函數(shù)out（）提供了多態(tài)（在3個子類中分別定義不同的實現(xiàn)）。

類圖用于描述系統(tǒng)所需要的類及它們之間的靜態(tài)關(guān)系。而為了實現(xiàn)具體的算法，還需要通過UML中的交互圖描述它們之間的交互過程（關(guān)于交互過程的描述，后面章節(jié)會詳細論述），從而實現(xiàn)算法所需要的操作。下面給出了該算法的面向?qū)ο蟮膶崿F(xiàn)（采用C++語法）。

    //基類：Item
     class Item{
    publ ic:
        Item? source;
        Item(Item? src){source=src; }
        virtual int out(){return 0; }
    };
    //計數(shù)器類：Counter
     class Counter:public Item{
        int value;
    publ ic:
        int out(){return value++; }
        Counter(int v):Item(0){value=v; }
    };
    //過濾器類：Filter
    class Filter:public Item{
        int factor;
    publ ic:
        int out(){
            while(1){
                int n=source- out();
                if(n%factor)return n;
            }
        }
        Filter(Item ?src, int f):Item(src){factor=f; }
    };
    //篩子類：Sieve
    class Sieve:public Item{
    publ ic:
        int out(){
            int n=source- out();
            source=new Filter(source, n);
            return n;
        }
        Sieve(Item ?src):Item(src){}
    };
    //主函數(shù)，構(gòu)造類的對象演繹應(yīng)用場景
    void main(){
        Counter c(2);
        Sieve s(&c);
        int next, n;
        cin   n;
        while(1){
            next=s.out();    //關(guān)鍵代碼只有一行，類知道自己的職責(zé)
            if(next  n)break;
            cout   next  "";
        }
        cout   endl;
    }

1.1.4 從結(jié)構(gòu)化到面向?qū)ο?/h3>

看完面向?qū)ο蟮慕Y(jié)果，有什么體會？

（1）程序更復(fù)雜了。的確，原來40多行的程序，用面向?qū)ο蠓椒▍s寫出了100多行。

（2）程序更難寫了。原來的思路很清楚，現(xiàn)在程序的結(jié)構(gòu)卻不是簡簡單單就可以寫出來的，它需要經(jīng)過一個復(fù)雜的分析和設(shè)計過程。

這是為什么呢？這樣做有必要嗎？目標是什么？

軟件工程思想的出現(xiàn)是為了解決軟件危機，而軟件危機出現(xiàn)的原因并不是寫不出程序，而是寫出來的程序無法修改、無法穩(wěn)定運行。因為社會在進步，軟件的需求也在不斷發(fā)展，這就要求程序也能夠隨著需求的變化而變化，而傳統(tǒng)的結(jié)構(gòu)化方法很難應(yīng)對此類問題。面向?qū)ο蠓椒ǖ某霈F(xiàn)就是為了解決變化的問題，使軟件能夠適應(yīng)變化。為了適應(yīng)變化，就需要為程序建立更合理、更穩(wěn)定的結(jié)構(gòu)，程序也就不可避免地變得更加復(fù)雜。不過，這種復(fù)雜性卻是很合理的，因為現(xiàn)實世界本身就具有這種復(fù)雜性，面向?qū)ο笤趯崿F(xiàn)功能的同時，還在模擬著這個現(xiàn)實世界。

當(dāng)然，用這樣一個算法問題來講解面向?qū)ο蟮膬?yōu)點是很笨拙的。因為算法是很穩(wěn)定的，它關(guān)注的是底層的實現(xiàn)，這些沒有必要、也不會隨著需求變化而變化。編者曾經(jīng)問過某計算機學(xué)院的一位非常有名的數(shù)據(jù)結(jié)構(gòu)方面的教師：“為什么到現(xiàn)在講解數(shù)據(jù)結(jié)構(gòu)時還是用C語言來實現(xiàn)，而不是面向?qū)ο蟮臄?shù)據(jù)結(jié)構(gòu)呢？”那位老師說：“因為數(shù)據(jù)結(jié)構(gòu)關(guān)注的是底層算法，并不是程序的高層結(jié)構(gòu)，用面向?qū)ο蟮姆椒〞沟贸绦蚋鼜?fù)雜，這樣編程人員必須投入更多的精力去關(guān)注程序結(jié)構(gòu)，而不是數(shù)據(jù)結(jié)構(gòu)。”

正是因為面向?qū)ο蠹夹g(shù)有這種復(fù)雜性，所以面向?qū)ο笤O(shè)計和開發(fā)的難度非常大，我們將面臨著對象的識別、職責(zé)分配等一系列問題。這就要求學(xué)習(xí)更多的知識和技術(shù)，并掌握一系列面向?qū)ο蟮脑O(shè)計原則和模式，同時靈活利用各種圖形化工具（如UML）來幫助我們表達和交流設(shè)計思想，從而簡化設(shè)計和實現(xiàn)過程。