作者归档：admin

猫狗大战

问题描述
【描述 Description】
　　新一年度的猫狗大战通过SC(星际争霸)这款经典的游戏来较量，野猫和飞狗这对冤家为此已经准备好久了，为了使战争更有难度和戏剧性，双方约定只能选择Terran(人族)并且只能造机枪兵。

　　比赛开始了，很快，野猫已经攒足几队机枪兵，试探性的发动进攻；然而，飞狗的机枪兵个数也已经不少了。野猫和飞狗的兵在飞狗的家门口相遇了，于是，便有一场腥风血雨和阵阵惨叫声。由于是在飞狗的家门口，飞狗的兵补给会很快，野猫看敌不过，决定撤退。这时飞狗的兵力也不足够多，所以没追出来。

　　由于不允许造医生，机枪兵没办法补血。受伤的兵只好忍了。555－
　　现在，野猫又攒足了足够的兵力，决定发起第二次进攻。为了使这次进攻给狗狗造成更大的打击，野猫决定把现有的兵分成两部分，从两路进攻。由于有些兵在第一次战斗中受伤了，为了使两部分的兵实力平均些，分的规则是这样的：1）两部分兵的个数最多只能差一个；2）每部分兵的血值总和必须要尽可能接近。现在请你编写一个程序，给定野猫现在有的兵的个数以及每个兵的血格值，求出野猫按上述规则分成两部分后每部分兵的血值总和。

【输入格式 Input Format】
第一行为一个整数n(1<=n<=200)，表示野猫现在有的机枪兵的个数。以下的n行每行一个整数，表示每个机枪兵的血格(1<=ai<=40)。 【输出格式 Output Format 】 只有一行，包含两个数，即野猫的每部分兵的血值总和，较小的一个值放在前面，两个数用空格分隔。 【样例输入 Sample Input 】 3 35 20 32 【样例输出 Sample Output】 35 52 【算法分析】 1 to n div 2为前一半数，n div 2+1 to n为后一半数之后枚举a[i],a[j]看是否可以交换 代码 方法一： 

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

#include <stdio.h>
 
int abs(int t)
{
 
       if (t < 0)
              return -t;
       else
              return t;
}
 
int main()
{
 
       int a[201], b[201];
       int n, i, j, l1, l2, sum1 , sum2, temp;
 
       scanf("%d", &n);
 
       l1 = n / 2;
       l2 = n - l1;
       sum1 = 0;
       sum2 = 0;
 
       for (i = 1; i <= l1; i++)
       {
              scanf("%d", &a[i]);
              sum1 += a[i];
       }
 
       for (i = 1; i <= l2; i++)
       {
              scanf("%d", &b[i]);
              sum2 += b[i];
       }
 
       for (i = 1; i <= l1; i++)
       {
              for (j = 1; j <= l2; j++)
              {
                     if (abs((sum1 + b[j] - a[i]) - (sum2 + a[i] - b[j])) < abs(sum1 - sum2))
                     {
                            sum1 = sum1 + b[j] - a[i];
                            sum2 = sum2 + a[i] - b[j];
                            temp = a[i];
                            a[i] = b[j];
                            b[j] = temp;
                     }
              }
       }
 
       if (sum1 < sum2)
              printf("%d %d\n", sum1, sum2);
       else
              printf("%d %d\n", sum2, sum1);
 
       return 0;
}

方法二：

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

Const
maxn=200;
maxm=8000;
Var
f:array[0..maxn,0..maxm] of boolean;
 
n,ans,mid:integer;
d:array[1..maxn] of integer;
 
Procedure Init;
var i:integer;
begin
　　fillchar(f,sizeof(f),false);
　　f[0,0]:=true;
　　ans:=0;
　　readln(n);
　　for i:=1 to n do readln(d[i]);
　　for i:=1 to n do ans:=ans+d[i];
　　mid:=ans div 2;
end;
 
Procedure Work;
var i,j,k:integer;
 
begin
　　for i:=1 to n do
　　  for k:=i downto 1 do
　　　　for j:=mid-d[i] downto 0 do
　　　　  if f[k-1,j] then f[k,j+d[i]]:=true;
end;
 
Procedure Print;
 
var i,j:integer;
begin
　　i:=0;j:=0;
　　while (not f[n div 2,mid+j]) do dec(j);
　　j:=mid+j;
　　writeln(j,' ',ans-j);
end;
 
BEGIN
init;
work;
print;
END.

PHP中的魔术方法总结 :__construct, __destruct , __call, __callStatic,__get, __set, __isset, __unset , __sleep, __wakeup, __toString, __set_state, __clone and __autoload

PHP中的魔术方法总结 :__construct, __destruct , __call, __callStatic,__get, __set, __isset, __unset , __sleep, __wakeup, __toString, __set_state, __clone and __autoload

1、__get、__set
这两个方法是为在类和他们的父类中没有声明的属性而设计的
__get( $property ) 当调用一个未定义的属性时访问此方法
__set( $property, $value ) 给一个未定义的属性赋值时调用
这里的没有声明包括当使用对象调用时，访问控制为proteced,private的属性（即没有权限访问的属性）

2、__isset、__unset
__isset( $property ) 当在一个未定义的属性上调用isset()函数时调用此方法
__unset( $property ) 当在一个未定义的属性上调用unset()函数时调用此方法
与__get方法和__set方法相同，这里的没有声明包括当使用对象调用时，访问控制为proteced,private的属性（即没有权限访问的属性）
3、__call
__call( $method, $arg_array ) 当调用一个未定义的方法是调用此访求
这里的未定义的方法包括没有权限访问的方法

4、__autoload
__autoload 函数，它会在试图使用尚未被定义的类时自动调用。通过调用此函数，脚本引擎在 PHP 出错失败前有了最后一个机会加载所需的类。
注意: 在 __autoload 函数中抛出的异常不能被 catch 语句块捕获并导致致命错误。

5、__construct、__destruct
__construct 构造方法，当一个对象创建时调用此方法，使用此方法的好处是：可以使构造方法有一个独一无二的名称,无论它所在的类的名称是什么.这样你在改变类的名称时,就不需要改变构造方法的名称
__destruct 析构方法，PHP将在对象被销毁前（即从内存中清除前）调用这个方法
默认情况下,PHP仅仅释放对象属性所占用的内存并销毁对象相关的资源.
析构函数允许你在使用一个对象之后执行任意代码来清除内存.
当PHP决定你的脚本不再与对象相关时,析构函数将被调用.
在一个函数的命名空间内,这会发生在函数return的时候.
对于全局变量,这发生于脚本结束的时候.如果你想明确地销毁一个对象,你可以给指向该对象的变量分配任何其它值.通常将变量赋值勤为NULL或者调用unset.

6、__clone
PHP5中的对象赋值是使用的引用赋值，如果想复制一个对象则需要使用clone方法，在调用此方法是对象会自动调用__clone魔术方法
如果在对象复制需要执行某些初始化操作，可以在__clone方法实现

7、__toString
__toString方法在将一个对象转化成字符串时自动调用，比如使用echo打印对象时
如果类没有实现此方法，则无法通过echo打印对象，否则会显示：Catchable fatal error: Object of class test could not be converted to string in
此方法必须返回一个字符串

在PHP 5.2.0之前，__toString方法只有结合使用echo() 或 print()时 才能生效。PHP 5.2.0之后，则可以在任何字符串环境生效（例如通过printf()，使用%s修饰符），但 不能用于非字符串环境（如使用%d修饰符）。从PHP 5.2.0，如果将一个未定义__toString方法的对象 转换为字符串，会报出一个E_RECOVERABLE_ERROR错误。

8、__sleep、__wakeup
__sleep 串行化的时候用
__wakeup 反串行化的时候调用
serialize() 检查类中是否有魔术名称 __sleep 的函数。如果这样，该函数将在任何序列化之前运行。它可以清除对象并应该返回一个包含有该对象中应被序列化的所有变量名的数组。
使用 __sleep 的目的是关闭对象可能具有的任何数据库连接，提交等待中的数据或进行类似的清除任务。此外，如果有非常大的对象而并不需要完全储存下来时此函数也很有用。
相反地，unserialize() 检查具有魔术名称 __wakeup 的函数的存在。如果存在，此函数可以重建对象可能具有的任何资源。
使用 __wakeup 的目的是重建在序列化中可能丢失的任何数据库连接以及处理其它重新初始化的任务。

9、__set_state
当调用var_export()时，这个静态 方法会被调用（自PHP 5.1.0起有效）。
本方法的唯一参数是一个数组，其中包含按array(‘property’ => value, …)格式排列的类属性。

10、__invoke
当尝试以调用函数的方式调用一个对象时，__invoke 方法会被自动调用。
PHP5.3.0以上版本有效
11、__callStatic
它的工作方式类似于 __call() 魔术方法，__callStatic() 是为了处理静态方法调用，
PHP5.3.0以上版本有效
PHP 确实加强了对 __callStatic() 方法的定义；它必须是公共的，并且必须被声明为静态的。同样，__call() 魔术方法必须被定义为公共的，所有其他魔术方法都必须如此。

PHP缓存 Cache Lite源码总结

PHP缓存 Cache Lite源码总结

1、【设置参数的方法】
在构造方法中调用对象方法setOption设置类私有变量的值，从而完成对象的初始化操作。
在setOption方法中通过判断$name是否为$availableOptions数组中的一员来设置初始值。
感觉有些坏味道

2、【缓存文件命名规则】
命名规则对fileNameProtection参数有两种设置方法
如果此参数为真，则对于$group和$id进行md5加密，否则直接使用这两个字段
默认情况下使用md5加密后的名称
如下所示代码：

1
2
3
4
5

 if ($this->_fileNameProtection) {
         $suffix = 'cache_'.md5($group).'_'.md5($id);
 } else {
         $suffix = 'cache_'.$group.'_'.$id;
  }

3、【缓存路径设置规则】
如果设置了hashedDirectoryLevel参数，则会在用户所给的缓存地址（cacheDir参数）后添加多层（hashedDirectoryLevel层）目录，所有的目录以cache_开头
默认hashedDirectoryLevel的值为0，即不添加嵌套目录
如下所示代码：

1
2
3
4
5
6
7

        $root = $this->_cacheDir;    //    用户所给的缓存地址
        if ($this->_hashedDirectoryLevel>0) {
            $hash = md5($suffix);
            for ($i=0 ; $i<$this->_hashedDirectoryLevel ; $i++) {
                $root = $root . 'cache_' . substr($hash, 0, $i + 1) . '/';
            }   
        }

4、【基于内存的缓存】
在缓存参数中我们可以看到有一个memoryCaching参数，此参数默认情况下为false，
对于这个内存缓存，我有些疑惑：

1、基于apache2服务器的PHP页面，每次访问都会有一个apache线程处理这个请求，而在每个线程中，这些内存缓存都是以对象属性的形式存在，则在各线程间如何共享？这样存在的意义是什么？
2、如果是在一次执行中进行缓存，那这样做的意义又有多大呢？


5、【过期时间的控制】
在每次读取缓存时间都会调用_setRefreshTime方法刷新此前时间，
$this->_refreshTime = time() – $this->_lifeTime;
然后在取数据时判断缓存文件的创建时间是否比_refreshTime大

1
2
3

     if ((file_exists($this->_file)) && (@filemtime($this->_file) > $this->_refreshTime)) {
                    $data = $this->_read();
               }

6、【_write函数中的坏味道】
在_write函数和_setFileName函数之间有重复代码
个人觉得可以将此提取出来。

7、【caching参数的必要性】
此参数控制全局的缓存的打开与关闭，在调试程序时十分有用

8、【自动清除旧缓存的控制】
automaticCleaningFactor参数控制是否自动清除旧缓存，
如果此参数的值大于1则会进行自动清除，只是在程序中针对自动清除有一个随机数，
可以理解为 1 / automaticCleaningFactor的机率进行自动清除旧缓存

9、【……】
很轻便的缓存类，如果是简单应用，值得一试！

EOF