月度归档:2015年10月

程序设计之状态机PHP版本

状态机

把复杂的控制逻辑分解成有限个稳定状态,在每个状态上判断事件,变连续处理为离散数字处理,符合计算机的工作特点。
同时,因为有限状态机具有有限个状态,所以可以在实际的工程上实现。但这并不意味着其只能进行有限次的处理,相反,有限状态机是闭环系统,有限无穷,可以用有限的状态,处理无穷的事务。

状态机可归纳为4个要素,即 现态条件动作次态。这样的归纳,主要是出于对状态机的内在因果关系的考虑。“现态”和“条件”是因,“动作”和“次态”是果。详解如下:

  1. 现态:是指当前所处的状态。
  2. 条件:又称为“事件”,当一个条件被满足,将会触发一个动作,或者执行一次状态的迁移。
  3. 动作:条件满足后执行的动作。动作执行完毕后,可以迁移到新的状态,也可以仍旧保持原状态。动作不是必需的,当条件满足后,也可以不执行任何动作,直接迁移到新状态。
  4. 次态:条件满足后要迁往的新状态。“次态”是相对于“现态”而言的,“次态”一旦被激活,就转变成新的“现态”了。

举个最简单的例子。
人有三个状态健康,感冒,康复中。
触发的条件有淋雨(t1),吃药(t2),打针(t3),休息(t4)。

所以状态机就是

  • 健康-(t4)->健康;
  • 健康-(t1)->感冒;
  • 感冒-(t3)->健康;
  • 感冒-(t2)->康复中;
  • 康复中-(t4)->健康,

就是这样状态在不同的条件下跳转到自己或不同状态的图。

举个例子:找出一个文本文件中所有符合条件的字符串(文本文件都是字母可能有回车,换行)

文本文件str.txt如下:

sdfasdfAAAsAAAdfasddllfadsBBBsBBBdfdfdfsdfdf dfadfsfaHHHsKKKsaddfkkslslAAAAhBBBddfFFhMMM

条件格式:
1. 左边三个大写字母
2. 中间一个小写字母
3. 右边三个大写字母

解决这个问题可能涉及栈结构
栈(stack)
后进先出

++++++++++++++++++++++++++++++解题思路++++++++++++++++++++++++++++++

定义状态:对栈的情况定义相关的状态

  • 栈空状态: stat0,
  • 栈中一个有效数据:stat1
  • 栈中两个有效数据:stat2
  • 栈中三个有效数据:stat3
  • 栈中四个有效数据:stat4
  • 栈中五个有效数据:stat5
  • 栈中六个有效数据:stat6
  • 栈中七个有效数据:stat7

单个字符扫描文件让符合条件的字符入栈,根据栈的状态做出相应动作
0.初始状态栈空,即$curState=0,遇到大写字母入栈,栈中一个有效字母,修改栈状态:$curState=1

  1. 当栈状态为1时,下一个字母必须为大写,才能入栈,否则置空栈,恢复栈状态:$curState=0
  2. 当栈状态为2时,下一个字母必须为大写,才能入栈,否则置空栈,恢复栈状态:$curState=0
  3. 当栈状态为3时,下一个字母必须为小写,才能入栈,否则置空栈,恢复栈状态:$curState=0
  4. 当栈状态为4时,下一个字母必须为大写,才能入栈,否则置空栈,恢复栈状态:$curState=0
  5. 当栈状态为5时,下一个字母必须为大写,才能入栈,否则置空栈,恢复栈状态:$curState=0
  6. 当栈状态为6时,下一个字母必须为大写,才能入栈,否则置空栈,恢复栈状态:$curState=0
  7. 当栈状态为7时,下一个字母必须为小写,此时栈中元素符合了有效条件格式,把栈中元素传给$box数组,然后置空栈,恢复栈状态:$curState=0;否则置空栈,恢复栈状态:$curState=0

必须考虑栈的当前状态与下一个状态成立间的关系,即现态与次态
$box数组中就是文本文件中所有符合条件格式的字符串

(PS:例子从别处抄来的,觉得很好理解,所以码在这里)

面向对象的S.O.L.I.D 原则

面向对象的S.O.L.I.D 原则

一般来说这是面向对象的五大设计原则,但是,我觉得这些原则可适用于所有的软件开发。

Single Responsibility Principle (SRP) – 职责单一原则

关于单一职责原则,其核心的思想是:一个类,只做一件事,并把这件事做好,其只有一个引起它变化的原因。单一职责原则可以看作是低耦合、高内聚在面向对象原则上的引申,将职责定义为引起变化的原因,以提高内聚性来减少引起变化的原因。职责过多,可能引起它变化的原因就越多,这将导致职责依赖,相互之间就产生影响,从而极大的损伤其内聚性和耦合度。单一职责,通常意味着单一的功能,因此不要为一个模块实现过多的功能点,以保证实体只有一个引起它变化的原因。

Unix/Linux是这一原则的完美体现者。各个程序都独立负责一个单一的事。
Windows是这一原则的反面示例。几乎所有的程序都交织耦合在一起。

Open/Closed Principle (OCP) – 开闭原则

关于开发封闭原则,其核心的思想是:模块是可扩展的,而不可修改的。也就是说,对扩展是开放的,而对修改是封闭的。

对扩展开放,意味着有新的需求或变化时,可以对现有代码进行扩展,以适应新的情况。
对修改封闭,意味着类一旦设计完成,就可以独立完成其工作,而不要对类进行任何修改。

对于面向对象来说,需要你依赖抽象,而不是实现,23个经典设计模式中的“策略模式”就是这个实现。对于非面向对象编程,一些API需要你传入一个你可以扩展的函数,比如我们的C 语言的qsort()允许你提供一个“比较器”,STL中的容器类的内存分配,ACE中的多线程的各种锁。对于软件方面,浏览器的各种插件属于这个原则的实践。

Liskov substitution principle (LSP) – 里氏代换原则

软件工程大师Robert C. Martin把里氏代换原则最终简化为一句话:“Subtypes must be substitutable for their base types”。也就是,子类必须能够替换成它们的基类。即:子类应该可以替换任何基类能够出现的地方,并且经过替换以后,代码还能正常工作。另外,不应该在代码中出现if/else之类对子类类型进行判断的条件。里氏替换原则LSP是使代码符合开闭原则的一个重要保证。正是由于子类型的可替换性才使得父类型的模块在无需修改的情况下就可以扩展。

这么说来,似乎有点教条化,我非常建议大家看看这个原则个两个最经典的案例——“正方形不是长方形”和“鸵鸟不是鸟”。通过这两个案例,你会明白《墨子 小取》中说的 ——“娣,美人也,爱娣,非爱美人也….盗,人也;恶盗,非恶人也。”——妹妹虽然是美人,但喜欢妹妹并不代表喜欢美人。盗贼是人,但讨厌盗贼也并不代表就讨厌人类。这个原则让你考虑的不是语义上对象的间的关系,而是实际需求的环境。

在很多情况下,在设计初期我们类之间的关系不是很明确,LSP则给了我们一个判断和设计类之间关系的基准:需不需要继承,以及怎样设计继承关系。

Interface Segregation Principle (ISP) – 接口隔离原则

接口隔离原则意思是把功能实现在接口中,而不是类中,使用多个专门的接口比使用单一的总接口要好。

举个例子,我们对电脑有不同的使用方式,比如:写作,通讯,看电影,打游戏,上网,编程,计算,数据等,如果我们把这些功能都声明在电脑的抽类里面,那么,我们的上网本,PC机,服务器,笔记本的实现类都要实现所有的这些接口,这就显得太复杂了。所以,我们可以把其这些功能接口隔离开来,比如:工作学习接口,编程开发接口,上网娱乐接口,计算和数据服务接口,这样,我们的不同功能的电脑就可以有所选择地继承这些接口。

这个原则可以提升我们“搭积木式”的软件开发。对于设计来说,Java中的各种Event Listener和Adapter,对于软件开发来说,不同的用户权限有不同的功能,不同的版本有不同的功能,都是这个原则的应用。

Dependency Inversion Principle (DIP) – 依赖倒置原则

高层模块不应该依赖于低层模块的实现,而是依赖于高层抽象

举个例子,墙面的开关不应该依赖于电灯的开关实现,而是应该依赖于一个抽象的开关的标准接口,这样,当我们扩展程序的时候,我们的开关同样可以控制其它不同的灯,甚至不同的电器。也就是说,电灯和其它电器继承并实现我们的标准开关接口,而我们的开关产商就可不需要关于其要控制什么样的设备,只需要关心那个标准的开关标准。这就是依赖倒置原则。

这就好像浏览器并不依赖于后面的web服务器,其只依赖于HTTP协议。这个原则实在是太重要了,社会的分工化,标准化都是这个设计原则的体现。

参考:http://en.wikipedia.org/wiki/Solid_(object-oriented_design)