月度归档：2010年09月

PHP设计模式笔记：使用PHP实现模板方法模式

2条回复

PHP设计模式笔记：使用PHP实现模板方法模式

【意图】
定义一个操作中的算法的骨架，而将一些步骤延迟到子类中。Template Method 使得子类可以在不改变一个算法的结构的情况下重定义该算法的某些特定的步骤【GOF95】

【模板方法模式结构图】

Template Method

Template Method

【模板方法模式中主要角色】
抽象模板(AbstractClass)角色: 定义一个或多个抽象方法让子类实现。这些抽象方法叫做基本操作，它们是顶级逻辑的组成部分。
定义一个模板方法。这个模板方法一般是一个具体方法，它给出顶级逻辑的骨架，而逻辑的组成步骤在对应的抽象操作中，这些操作将会推迟到子类中实现。同时，顶层逻辑也可以调用具体的实现方法

具体模板(ConcrteClass)角色：实现父类的一个或多个抽象方法，作为顶层逻辑的组成而存在。

每个抽象模板可以有多个具体模板与之对应，而每个具体模板有其自己对抽象方法（也就是顶层逻辑的组成部分）的实现，从而使得顶层逻辑的实现各不相同。

【模板方法模式适用场景】
1、一次性实现一个算法的不变的部分，并将可变的行为留给子类来实现。
2、各子类中公共的行为应被提取出来并集中到一个公共父类中以避免代码重复。
3、控制子类扩展。

【模板方法模式与其它模式】
1、策略模式(strategy模式)：模板方法使用继承来改变算法的部分，策略模式使用委托来改变整个算法。区别在于封闭的变化不同，一个变化的部分，一个变化的是整体。
2、工厂方法模式(factory method模式)：Factory Method模式常被模板方法调用。
【模板方法模式PHP示例】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

<?php
/**
 * 模板方法模式简单示例 2010-09-12 sz
 * @author phppan.p#gmail.com  http://www.phppan.com                                                       
 * 哥学社成员（http://www.blog-brother.com/）
 * @package design pattern
 */
 
/**
 * 抽象模板角色
 * 定义抽象方法作为顶层逻辑的组成部分，由子类实现
 * 定义模板方法作为顶层逻辑的架子，调用基本方法组装顶层逻辑
 */
abstract class AbstractClass {
 
    /**
     * 模板方法 调用基本方法组装顶层逻辑
     */
    public function templateMethod() {
        echo 'templateMethod begin.<br />';
        $this->primitiveOperation1();
        $this->primitiveOperation2();
        echo 'templateMethod end.<br />';
    }
 
    /**
     * 基本方法1
     */
    abstract protected function primitiveOperation1();
 
     /**
     * 基本方法2
     */
    abstract protected function primitiveOperation2();
}
 
/**
 * 具体模板角色
 * 实现父类的抽象方法
 */
class ConcreteClass extends AbstractClass{
    /**
     * 基本方法1
     */
    protected function primitiveOperation1() {
        echo 'primitiveOperation1<br />';
    }
 
     /**
     * 基本方法2
     */
    protected function primitiveOperation2(){
        echo 'primitiveOperation2<br />';
    }
 
}
 
/**
 * 客户端
 */
class Client {
 
     /**
     * Main program.
     */
    public static function main() {
        $class = new ConcreteClass();
        $class->templateMethod();
    }
}
 
Client::main();
?>

【模板方法模式】
模板方法是一种代码复用的基本技术，模板方法导致一种反射的控制结构，这指的是一个父类调用子类的操作。
其实现过程：准备一个抽象类，将部分逻辑以具体方法以及具体构造子的形式实现，然后声明一些抽象方法来迫使子类实现剩余的逻辑。不同子类可以以不同的方式实现这些抽象方法，从而对剩余的逻辑有不同的实现。

【重构的原则】
重构时应当遵守的原则是：将行为以是移到结构的高端，而将状态尽量移动到结构的低端。
Auer曾在文献【AUER95】中指出：
1、应当要所行为而不是状态定义一个类。
2、在实现行为是，是用抽象状态而不是用具体状态。
3、给操作划分层次。
4、将状态的确认推迟到子类中。在父类中，如果需要状态属性的话，可以调用抽象的取值方法，而将抽象的取值方法的实现放到具体子类中。
如果可以遵守以上的而，那么就可以在等级结构中将接口与实现分离，将抽象与具体分离，从而保证代码可以最大限度的被复用。

PHP帮助手册拾遗三：类与对象

4条回复

PHP帮助手册拾遗：类与对象

1、__autoload函数
__autoload函数定义时必须包含一个参数，否则会显示如下错误：
Fatal error: __autoload() must take exactly 1 argument

在 __autoload 函数中抛出的异常不能被 catch 语句块捕获并导致致命错误。

2、父类的构造方法调用
如果子类中定义了构造函数则不会暗中调用其父类的构造函数。要执行父类的构造函数，需要在子类的构造函数中调用 parent::__construct()。这里python和php一样

3、父类的析构方法调用
和构造函数一样，父类的析构函数不会被引擎暗中调用。要执行父类的析构函数，必须在子类的析构函数体中显式调用 parent::__destruct()。
析构函数在脚本关闭时调用，此时所有的头信息已经发出。
试图在析构函数中抛出一个异常会导致致命错误。

4、访问限制
var与public在类中的变量定义相同，但是在php5的php5.1.3会生成一个E_STRICT警告
方法如果没有设置访问控制，则将默认设置为public

5、构造方法
PHP提交两种构造方法，以类名和__construct，当类中没有__construct方法时，PHP会调用类名函数，但是如果存在__construct时，不管其访问控制是什么，都不会调用类名函数。
如下所示代码：

1
2
3
4
5
6
7
8
9
10
11

class Demo {
    public function Demo() {
       echo 'Demo function';
    }
 
    private function __construct() {
       echo '__construct function';
    }
}
 
$demo = new Demo();

运行会报错：Fatal error: Call to private Demo::__construct() from invalid context
ps:上面的这个问题是ben前辈提出的，感谢ben前辈昨天的指导

6、静态变量
PHP5.3以后，可以使用变量引用类，但是这个变量不能是关键字（如self,parent,static等）。如下所示代码：

1
2
3
4
5
6

class Demo {
    public static $my_static = 'Demo';
}
 
$classname = 'Demo';
print $classname::$my_static . "\n"; // As of PHP 5.3.0

7、接口
接口可以有常量，不能有变量，并且常量在其子类中无法重载
如下所示代码：

1
2
3
4
5
6
7
8
9
10
11

interface Base {
    const constant = 'constant value';
    public $var = "test var";
}
 
class Foo implements Base {
 
}
 
echo Base::constant;
echo Base::$var;

以上代码报错为：Fatal error: Interfaces may not include member variables
注释掉对变量的操作后可以正常打印常量中存放的值。
8、对象迭代
在PHP5中，使用foreach，遍历一个对象，可以访问这个对象的所有可以访问的属性
如果要自定义迭代器，可以通过实现一个叫Iterator的接口来实现
9、单例模式
单例模式(singleton模式)在实现过程中，需要考虑__clone方法。
10、对象与引用
PHP5之后，对象在默认情况下是以引用的方式传递的。

最小矩阵和

2条回复

很久很久以前的代码，在某个角落找到，贴了上来，
在杭电acm1081上可以ac，来源应该是Greater New York 2001
貌似作为中南赛区ACM竞赛题

问题描述
【Description】

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.

As an example, the maximal sub-rectangle of the array:

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

is in the lower left corner:

9 2
-4 1
-1 8
and has a sum of 15.

【Input】

The input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N^2 integers separated by whitespace (spaces and newlines). These are the N^2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].

【Output】

Output the sum of the maximal sub-rectangle.

【Sample Input】
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2

【Sample Output】
15

下面的中文来自：http://blog.csdn.net/hym666/archive/2010/08/17/5818591.aspx
此文章处有C++的解答

题目描述：
在一个大的方阵中找出一个子方阵，这个子方阵是所有子方阵和中的最大的一个
问题分析：
问题可以回归到一个数列中的连续字数列的和的最大值。
即把每一行看成一个数列。把每一列转换成一个数。
当然每一列也是一个数列，有很多的连续子数列。所有会有很多中情况。可穷举各种数列来构造一个行向的数列。
再用动态规划计算每一行的最大值，再在各行中选取最大的作为题目的解。

【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

import java.util.*;
 
public class Main {
 
       /**
        * @param args
        */
 
       public static int maxSum(int[] b, int n){
 
              int max = b[0], sum = 0;
 
              for (int i = 1; i < n ; i++ ){
                     if (max > 0)
                            max += b[i];
                     else
                            max = b[i];
 
                     if (max > sum)
                            sum = max;
              }
              return sum;
       }
 
       public static int maxTotal(int[][] a, int n){
 
              int max = 0;
              int[] b = new int[n];
 
              for (int i = 0; i < n; i++){
                     for (int j = 0; j < n; j++)
                            b[j] = a[i][j];
 
                     int sum = maxSum(b, n);
 
                     if (sum > max)
                            max = sum;
 
                     for (int j = i + 1; j < n; j++){
                            for (int k = 0; k < n; k++)
                                   b[k] += a[j][k];
 
                            sum = maxSum(b, n);
                            if (sum > max)
                                  max = sum;
                     }
              }
              return max;
       }
 
       public static void main(String[] args) {
              // TODO Auto-generated method stub
 
              Scanner cin = new Scanner(System.in);
              int n;
 
              while (cin.hasNext()){
                     n = cin.nextInt();
                     int[][] a = new int[n][n];
                     for (int i = 0; i < n; i++){
                            for (int j = 0; j < n; j++){
                                   a[i][j] = cin.nextInt();                                  
                            }
                     }
                     System.out.println(maxTotal(a, n));
              }
       }
}