标题: 从素数问题看对象思维方式
作者: dnawo
日期: 2010-05-31 05:44 PM
分类: 其他
内容: 1.引言
随着C++、Java、C#等面向对象的编程语言的日益普及，面向对象概念已经深入人心；从面向对象的编程语言到面向对象软件工程方法也日益得到广泛的应用；关于面向对象的更进一步的应用如：面向构件、面向服务、面向模式等新思维也逐步发展起来，而这些新方法都是建立在面向对象的思维方式上的。由此可见，深入理解面向对象的思维方式不仅可以帮助我们理解目前面临的应用模式，还是我们进一步学习和发展的必经之路。
我们很多人都是传统的结构化思维方式中走过来的，本文即通过一个经典数据结构中的算法问题来探讨如何走出传统的思维模式，而通过对象思维方式来解决问题，进而理解到底什么是对象思维方式。从而为后续的对象课程热身。
2.传统思维方式
我们所面临的是一个求素数的问题，素数(也叫质数)是指除了1与本身之外，不能被其他正整数整除的数。按照习惯规定，1不算素数，最小的素数是2，其余的是3、5、7、11、13、17、19……等等。
根据上面的定义我们可以推导出判断素数的算法：对于数n，从i=2,3,4,5…到 n-1 判断 n能否被i整除，如果全部不能整除，则n是素数，只要有一个能除尽，则n不是素数；事实上，为了压缩循环次数,可将判断范围从2 ~ n-1改为2 ~ sqrt(n)。
筛选法是一个经典的求素数的算法，它的作用并不是判定某个数是否是素数，而是求小于数n的所有素数，下面通过一个简单的例子来说明筛选法的求解过程。
我们需要求解50以内的所有素数i(2<i<n)，为此我们需要进行如下的筛选：
算法的执行过程是这样的：
1)首先，拿当前最小的数(即2)作为因子，将后面所有可以被2整除的数去掉(因为它们肯定不是素数，参见图中的第1行，去掉后面的4、6、8…，剩余结果见第2行)；
2)之后，取剩余序列中第二小的数(即3)作为因子，将后面所有可以被3整除的数去掉(参见图中的第2行，去掉后面的4、6、8…，剩余结果见第3行)；
3)如此继续，直到所取得最小数大于sqrt(n)(图中第4行为最后一次筛选，此时的因子为7，因为下一个因子即为11大于sqrt(50))；
4)剩余的序列即为n以内的所有素数。
为了更清楚地描述该算法，我们可以采取传统软件工程中的流程图来阐述上面的流程，下图即为该算法的流程图：
注意：上述的流程图和前面描述的算法有所出入；在具体实现时，考虑到算法的执行效率并没有将当前因子的倍数直接删除(因为，如果采用数组来存储当前数字序列，则删除过程的算法复杂度都为O(n))，而是将相应的位置零，表明该位置已经没有数据了。
设计出这样一个算法后，后面的实现过程就是水到渠成了，我们可以随便采用一种编程语言来实现，这里我们采用C语言来实现，其源代码如下(PrimerNumber.c)：
复制内容到剪贴板 程序代码void main(){
int *sieve, n;
int iCounter=2, iMax, i;
printf("Please input max number:");
scanf(“%d", &n);
sieve=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]);
}
3.是对象思维吗？
在上面的问题中，我们可以很容易的从算法描述中构造目标程序，很自然，也似乎很符合我们的思维习惯；那么这种方法是面向对象的方法吗？也许大家都会说不是！因为很明显我们采用是C语言实现的，而C语言显然是结构化的！
那么怎样才算面向对象的方法呢？如果我现在需要大家用面向对象的方法去解决这个问题，那么我们又会怎么去做呢？
有人也许会说，这很简单，Java是一门真正的面向对象的语言，我用Java去实现这个算法是不是就是面向对象呢？好，下面我们就看看该算法的Java实现(PrimerNumber.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函数)，这不就是面向对象吗？原来就这么简单？！
4.上升到对象思维
那么真的是这样的吗？我们再仔细看看程序的内部实现，怎么这么面熟？这不和前面的C程序很类似吗？定义数组、利用for循环初始化，利用while循环控制因子；只不过将语法从C换成了Java，换汤不换药；这不是面向对象，这只不过是披着“面向对象皮”的结构化程序，我把它称为“伪面向对象”。
那么怎样才算面向对象的思维方式呢？到底要怎样去做才是一个面向对象的程序呢？在这里我先不讨论关于面向对象的概念或理论(这些内容后续章节会陆续介绍)，我们先来看看这个例子如何通过面向对象的方法来实现。
我们都知道，在面向对象的方法中，最重要的概念是类和对象，至于这些算法所要求的功能是通过各个对象来之间的交互实现的(这就像我们日常生活一样，为了完成某一件事，我们需要和各种不同的人、物打交道，这些人和物就是对象，而打交道的过程就是交互)。因此在面向对象的思维方法中，我们并不是关注算法本身，而需要关注为了完成这个算法，我们需要怎么的“人”和“物”(即对象)，之后再定义这些“人”和“物”之间的关系，从而明确它们是如何“打交道”的(即交互)；把这个过程明确后，事就自然办成了(即算法实现了)。
按照这种思维模式，我们再来看前面的筛选法求素数的问题是怎样的一个过程。在这个算法中，我们看到了什么？
1)首先，我们看到了一堆需要处理的数字，这些数字构成数据源，这个数据源就是一个对象，针对这个对象即可抽象出一个类：筛子Seive(存储数据源)；
2)其次，我们看到了一个过滤因子，通过这个因子来筛选后面的数，这个因子就是一个对象，针对这个对象即可抽象出一个类：过滤器Factor(记录当前的过滤因子)；
3)此外，我们还看到一些东西，比如为了能够对数据源进行遍历，我们需要一个计数器来记录当前正在访问的数据值，这个计数器对象即可抽象成类：计数器Counter(记录当前正在筛选的数据)。
具体的过程如下图所示：
好了，到这我们基本上把所要求的对象都找出来啦，是不是工作就做完了？
没有，如果仅到这一步还不是面向对象，这只不过是“基于对象”罢了，要做到真正的面向对象，还需要最关键的一步：抽象！这一步是面向对象领域最难的一步，这一步做好了我们程序(或软件)才会获得那些面向对象“广告语”中所谓的面向对象各种好处(什么稳定性、复用性等等)，否则这一切都是空谈。至于这个例子如何进行抽象，这是一个非常复杂的问题，我们并不展开(关于抽象，后面会有专门的章节进行论述)；我们直接看结果，下图即为筛选法求素数问题的类图：
在这个类图中，除了前面所找出来的三个对象之外，我们还看到了一个新的类Item，这个类的类名是一个斜体字，表明它是一个抽象类；通过该抽象类为其成员函数out()提供了多态的特型。
通过上面的类图即可描述我们所需要的类以及它们之间的关系；此外，为了能够实现具体的算法，我们还需要通过UML中的交互图描述它们之间的交互过程(关于交互过程的描述，后面章节会详细论述)，此处由于这个过程比较简单，我们可以直接实现；下面是该算法的面向对象的实现(采用C++语法)：
复制内容到剪贴板 程序代码//基类：Item
class Item{
public:
Item* source;
Item (Item* src) {source=src;}
virtual int out() {return 0;}
};
//计数器类：Counter
class Counter: public Item{
int value;
public:
int out() {return value++;}
Counter(int v):Item(0){value=v;}
};
//过滤器类：Filter
class Filter:public Item{
int factor;
public:
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{
public:
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;
}
5.总结
看完面向对象的结果，我们有什么体会？
1)程序更复杂了！的确，原来40多行的程序，用面向对象的方法却写出了100多行。
2)程序更写难了！原来的思路很清楚，但现在程序的结构却不是简简单单就可以写出来的，它需要我们经过一个复杂的分析和设计过程。
这是为什么呢？这样做有必要吗？我们的目标是什么？
软件工程思想的出现是为了解决软件危机，而软件危机出现的原因并不是写不出程序了，而是写出来的程序无法修改、无法稳定运行！因为社会在进步，软件的需求也在不断的发展，这就要求我们的程序也能够随着需求的变化而变化，而传统的方法是无法解决这些问题的。面向对象技术的出现就是为了解决变化的问题，使软件能够适应变化。而为了这个变化，就需要程序建立更合理、稳定的结构；程序也就不可避免的变得更加复杂；不过这种复杂性却是很合理的，因为我们的现实世界本身就具有这种复杂性，面向对象在实现功能的时候，还在模拟着这个现实世界。
当然，用这样一个算法问题来讲解面向对象的优点是很愚蠢的！因为算法是很稳定的，它关注的是底层的实现，这些没有必要也不会随着需求而变化。我曾经问过计算机学院一位非常有名的数据结构老师，为什么到现在讲解数据结构时还是用C语言来实现，而不是面向对象的数据结构呢？那位老师就说，因为数据结构关注的是底层算法，并不是程序的高层结构，用面向对象的方法使得程序更复杂，这样必须投入更多地精力去关注程序结构，而不是数据结构，舍本逐末了。
正是因为面向对象技术有这种复杂性的存在，使得面向对象设计和开发的难度更大，因为我们将面临着对象的识别、职责分配等一系列问题；而这就要求我们学习更多知识和技术，并掌握一系列面向对象的设计原则和模式，同时灵活利用各种图形化工具(如UML)来帮助我们表达和交流设计思想，并简化实现的过程。
+ 查看当前日志评论 (0)
────────────
PJBlog3 v3.2.9.518 Inside.
Processed In 0.078 ms
标题: 从素数问题看对象思维方式
你没有权限发表评论
────────────
PJBlog3 v3.2.9.518 Inside.
Processed In 0.078 ms
暂无评论
────────────
PJBlog3 v3.2.9.518 Inside.
Processed In 0.078 ms