1.1 从素数问题看面向对象

视频讲解

随着C++、Java、C#等面向对象编程语言的日益普及，面向对象技术已经得到了广泛的应用。从面向对象的编程语言到面向对象软件工程方法也日益被人们重视起来。面向对象的更进一步应用（如面向构件、面向服务、面向模式等）也逐步发展起来，而这些新方法都是建立在面向对象的思维方式上的。由此可见，深入理解面向对象的思维方式不仅可以帮助我们理解当前面临的应用模式，还是我们进一步学习和发展的必经之路。

很多人都经历过传统的结构化思维方式，让我们先通过一个经典的数据结构中的算法问题来探讨如何走出传统的思维模式。利用面向对象的思维方式来解决问题，进而理解到底什么是面向对象思维方式，为后续的对象建模热身。

1.1.1 问题的提出

这里，我们所面临的是一个求素数的问题。素数（也叫质数）是指除了1和它本身外，不能被其他正整数整除的数。按照习惯规定，1不算素数，最小的素数为2，其余的有3、5、7、11、13、17、19等。

根据上面的定义可以推导出判断素数的算法：对于数n，判断n能否被i（i=2,3,4, 5, ..., n—1）整除，如果全部不能被整除，则n是素数，只要有一个能除尽，则n不是素数。事实上，为了压缩循环次数，可将判断范围从2～n—1改为2～sqrt（n）。

筛选法是一个经典的求素数的算法，它的作用并不是判断某个数是否为素数，而是求小于数n的所有素数。下面通过一个简单的例子来说明筛选法的求解过程。

我们需要求解50以内的所有素数i（2＜i＜n），为此需要进行如下的筛选（见图1-1）。

图1-1 筛选法求素数示意图

为了利用程序实现此算法，需要进行算法设计。考虑分别采用结构化方法和面向对象的方法实现此算法，并将设计方案以合适的方式记录下来。下面将通过对两种不同方法的比较，讲解结构化方法和面向对象方法在本质上的区别。

1.1.2 传统的结构化解决方案

按照传统的结构化方法，算法的执行过程如下所示。

（1）以当前最小的数（即2）作为因子，将后面所有可以被2整除的数去掉（因为它们肯定不是素数，参见图1-1的第1行，去掉后面的4、6、8等，剩余结果见第2行）。

（2）取剩余序列中第二小的数（即3）作为因子，将后面所有可以被3整除的数去掉（参见图1-1中的第2行，去掉后面的9、15、21等，剩余结果见第3行）。

（3）如此继续，直到所取得最小数大于sqrt（n）（图1-1中第4行为最后一次筛选，此时的因子为7，因为下一个因子即为11，大于sqrt（50））。

（4）剩余的序列即为n以内的所有素数。

为了更清楚地描述该算法，可以采用流程图来阐述算法流程，该算法的流程图如图1-2所示。

图1-2 筛选法求素数流程图

需要说明的是，上述的流程图和前面描述的算法有所出入。在具体实现时，考虑到算法的执行效率，并没有将当前因子的倍数直接删除（因为如果采用数组存储当前数字序列，则删除过程的算法复杂度都为O（n）），而是将相应的位置设为0，表明该位置已经没有数据了。

设计出这样一个算法后，后面的实现过程就是“水到渠成”的事了，我们可以选择一种合适的编程语言来实现。下面列出了该算法的C语言实现。

    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 面向对象的解决方案

在上面的问题中，可以很容易地从算法描述中构造目标程序。很自然，这也似乎很符合人们的思维习惯。那么这种方法是面向对象的方法吗？也许读者都会说不是。因为很明显，我们采用的是C语言实现的，而C语言显然是结构化的。什么才算是面向对象的方法呢？如果现在需要用面向对象的方法来解决这个问题，那么又应该怎么做呢？

有人也许会说：“这很简单，Java语言是一门真正的面向对象的语言，用Java语言去实现这个算法是不是就是面向对象呢？”那么，下面就看看该算法的Java语言实现。

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

在这个程序中，可以看到一个面向对象的关键特征——类。为了能够使程序正确地通过编译并运行，我们需要利用Java的关键字class定义一个类，并为该类定义相应的成员函数（main（）函数），这不就是面向对象吗？原来这么简单。

真的是这样的吗？我们再仔细看看程序的内部实现，怎么这么面熟？这不是和前面的C程序很类似吗？定义数组、利用for循环初始化、利用while循环控制因子，只不过将语法从C换成了Java。整个算法实现的思维方式完全没有变化，这显然不是面向对象，这只不过是披着“面向对象”皮的结构化程序，可把它称为“伪面向对象”。

那么怎样才算面向对象的思维方式呢？到底要怎样去做才是一个面向对象的程序呢？在这里暂不讨论面向对象的概念或理论（我们在后续章节中会陆续介绍这些内容），先来看看这个例子如何通过面向对象的方法实现。

人们都知道，在面向对象的方法中，最重要的概念是类和对象，这些算法所要求的功能是通过各个对象之间的交互实现的（这就像人们日常生活一样，为了完成某一件事，需要和各种不同的人、物打交道，这些人和物就是对象，而打交道的过程就是交互）。因此在面向对象的思维方法中，我们并不是关注算法本身，而需要关注为了完成这个算法，需要什么样的“人”和“物”（即对象），再定义“人”和“物”之间的关系，从而明确两者是如何“打交道”（即交互）的。把这个过程明确后，事就自然办成了（即实现了算法）。

按照这种思维模式，再来看前面的筛选法求素数的问题是怎样的一个过程。在这个算法中，我们看到了什么？

（1）看到了一堆需要处理的整数，这些整数构成数据源，这个数据源就是一个待处理对象，针对这个对象即可抽象出一个类：筛子Sieve（存储数据源）。

（2）看到了一个过滤因子，通过这个因子筛选后面的数，这个因子也是一个对象，针对这个对象即可抽象出一个类：过滤器Filter（记录当前的过滤因子）。

（3）还看到了一些其他方面，例如为了能够对数据源进行遍历，需要一个计数器记录当前正在访问的数据值，这个计数器对象即可抽象成类：计数器Counter（记录当前正在筛选的数据）。

到此为止，就从业务场景中找出了为了实现该算法所需要的对象，这些对象就可以满足基本的业务需求。然而，这还不是面向对象方法的全部，还需要进行进一步的抽象。

如果仅仅找到具体的业务对象，还不算真正的面向对象，这只不过是“基于对象”罢了。要做到真正的面向对象，还需要执行最关键的一步——抽象。这一步是面向对象技术中最难的一步，只有做好了这一步，程序（或软件）才会获得那些面向对象“广告语”中所谓的面向对象的各种好处（如稳定性、复用性等），否则这一切都是空谈。至于如何对这个例子进行抽象，则是一个非常复杂的问题，在这里并不展开讨论（关于抽象，后面会有专门的章节进行论述）。下面让我们直接看结果，图1-3即为筛选法求素数问题的类图。

图1-3 筛选法求素数的类图

从图1-3中可以看出，除了前面所找出的3个对象的类外，还定义了一个新的抽象类Item（在图中类名用斜体字表示），作为这3个类的公有基类。通过该抽象层次，为成员函数out（）提供了多态（在3个子类中分别定义不同的实现）。

类图用于描述系统所需要的类及它们之间的静态关系。而为了实现具体的算法，还需要通过UML中的交互图描述它们之间的交互过程（关于交互过程的描述，后面章节会详细论述），从而实现算法所需要的操作。下面给出了该算法的面向对象的实现（采用C++语法）。

    //基类：Item
     class Item{
    publ ic:
        Item∗ source;
        Item(Item∗ src){source=src; }
        virtual int out(){return 0; }
    };
    //计数器类：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){}
    };
    //主函数，构造类的对象演绎应用场景
    void main(){
        Counter c(2);
        Sieve s(&c);
        int next, n;
        cin   n;
        while(1){
            next=s.out();    //关键代码只有一行，类知道自己的职责
            if(next  n)break;
            cout   next  "";
        }
        cout   endl;
    }

1.1.4 从结构化到面向对象

看完面向对象的结果，有什么体会？

（1）程序更复杂了。的确，原来40多行的程序，用面向对象方法却写出了100多行。

（2）程序更难写了。原来的思路很清楚，现在程序的结构却不是简简单单就可以写出来的，它需要经过一个复杂的分析和设计过程。

这是为什么呢？这样做有必要吗？目标是什么？

软件工程思想的出现是为了解决软件危机，而软件危机出现的原因并不是写不出程序，而是写出来的程序无法修改、无法稳定运行。因为社会在进步，软件的需求也在不断发展，这就要求程序也能够随着需求的变化而变化，而传统的结构化方法很难应对此类问题。面向对象方法的出现就是为了解决变化的问题，使软件能够适应变化。为了适应变化，就需要为程序建立更合理、更稳定的结构，程序也就不可避免地变得更加复杂。不过，这种复杂性却是很合理的，因为现实世界本身就具有这种复杂性，面向对象在实现功能的同时，还在模拟着这个现实世界。

当然，用这样一个算法问题来讲解面向对象的优点是很笨拙的。因为算法是很稳定的，它关注的是底层的实现，这些没有必要、也不会随着需求变化而变化。编者曾经问过某计算机学院的一位非常有名的数据结构方面的教师：“为什么到现在讲解数据结构时还是用C语言来实现，而不是面向对象的数据结构呢？”那位老师说：“因为数据结构关注的是底层算法，并不是程序的高层结构，用面向对象的方法会使得程序更复杂，这样编程人员必须投入更多的精力去关注程序结构，而不是数据结构。”

正是因为面向对象技术有这种复杂性，所以面向对象设计和开发的难度非常大，我们将面临着对象的识别、职责分配等一系列问题。这就要求学习更多的知识和技术，并掌握一系列面向对象的设计原则和模式，同时灵活利用各种图形化工具（如UML）来帮助我们表达和交流设计思想，从而简化设计和实现过程。