月度归档：2009年10月

迎春舞会之三人组舞

发表回复

【问题描述】
背景 Background
　　HNSDFZ的同学们为了庆祝春节，准备排练一场舞

【描述 Description】
　　n个人选出3*m人，排成m组，每组3人。
　　站的队形——较矮的2个人站两侧，最高的站中间。
　　从对称学角度来欣赏，左右两个人的身高越接近，则这一组的“残疾程度”越低。
　　计算公式为 h=(a-b)^2 (a、b为较矮的2人的身高)
　　那么问题来了。
　　现在候选人有n个人，要从他们当中选出3*m个人排舞蹈，要求总体的“残疾程度”最低。

【输入格式 Input Format】
　　第一排为m，n。
　　第二排n个数字，保证升序排列。

【输出格式 Output Format】
　　输出最小“残疾程度”。

【样例输入 Sample Input】
9 40
1 8 10 16 19 22 27 33 36 40 47 52 56 61 63 71 72 75 81 81 84 88 96 98 103 110 113 118 124 128 129 134 134 139 148 157 157 160 162 164

【样例输出 Sample Output】
23

注释 Hint
m<=1000,n<=5000 数据保证3*m<=n 【算法分析】 从大到小排序 a[i] f[i,j] 表示前i个数中有j对跳舞组合时的最优解 应为要最优就必须是排序时相邻两数的在两边才最好 而中间的人最高，记 f[i,j]=f[i-2,j-1]+(a[i]-a[i-1])^2 如果不取a[j]就 记 f[i,j]=f[i-1,j] 所以 f[i,j]=min{f[i,j]=f[i-2,j-1]+(a[i]-a[i-1])^2 | f[i,j]=f[i-1,j]} huyichen 摘自一大牛语录: 首先将筷子长度从短到长排序。 F[i,j,0]表示i个人使用前j双筷子，且第j根筷子不用，所需要长度差的平方和的最小值。 F[i,j,1]表示i个人使用前j双筷子，且使用第j根筷子，所需要长度差的平方和的最小值。 则F[i,j,0]=min{f[i,j-1,1]，f[i,j-1,0]}，F[i,j,1]=F[i-1,j-1,0]+(l[j]-l[j-1])^2 ans=min{F[k,n,1]，F[k,n,0]} 算法复杂度为O(NK)。 算法正确性的简单证明： 因为筷子配对的时候要求是长度平方差最小，所以每根筷子的配对的时候总是希望和长度差最小的配对，即排序后相邻两根筷子是可以配对的。l[a]，l，l[c]，l[d]表示4根排序好的筷子。因为(l-l[a])^2+(l[d]-l[c])^2<(l-l[c])^2+(l[d]-l[a])^2，所以上述配对方法是正确的。 本题同样可以把模型直接转变为二分图最小权匹配。 将两根筷子相连的边权值标记为两根筷子长度平方差，然后对二分图求一次最小权匹配。可以使用网络流的最小费用K流的算法，寻找K次最短路的增广轨。 算法复杂度为O(KN^3)。 非常显然，动态规划的复杂度远远低于二分图最小权匹配的复杂度。 【代码】 

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

#include <stdio.h>
#include <string.h>
 
int a[1001][5001];
int b[5001];
 
int main()
{
       int n, m, i, j, k, temp;
 
       scanf("%d%d", &m, &n);
       memset(b, 0, sizeof(b));
 
       for (i = 1; i <= n; i++)
              scanf("%d", &b[i]);
 
       for (i = 0; i <= m; i++)
       {
              for (j = 0; j <= n; j++)
                     a[i][j] = 2000000000;
       }
 
       for (i = 0; i <= n; i++)
              a[0][i] = 0;
 
       for (i = 1; i <= m; i++)
       {
              for (j = i + i; j <= n - (m - i) * 3; j++)
              {
                     a[i][j] = a[i][j - 1];
                     temp = a[i - 1][j - 2] + (b[j] - b[j - 1]) * (b[j] - b[j - 1]);
                     if ( j < n - (m - i) * 3 && temp < a[i][j])
                            a[i][j] = temp;
              }
       }
 
       printf("%d\n", a[m][n]);
       return 0;
}

JSON格式总结

发表回复

【JSON是什么】
JSON，JavaScript Object Notation，一种更轻、更友好的用于接口(AJAX、REST等)数据交换的格式。JSON是结构化数据串行化的文本格式，作为XML的一种替代品，用于表示客户端与服务器间数据交换有效负载的格式。它是从ECMAScript语言标准衍生而来的。JSON的设计目标是使它成为小的、轻便的、文本的，而且是JavaScript的一个子集。
JSON能够描述四种简单的类型（字符串、数字、布尔值和null）和两种结构化类型（对象和数组）。

字符串(string)是零个或多个Unicode字符的序列。除了字符 “、\、/和一些控制符（\b，\f，\n，\r，\t）需要编码外，其他 Unicode 字符可以直接输出

对象(Object)是无次序的零个或多个名/值(name/value)对的集合，使用｛｝包含包含所有元素。这里的name是string类型，value则可以是string、number、boolean、null、Object或Array类型。

数组(Array)是零个或多个value的有序序列。JSON 还可以表示一个数组对象，使用 [] 包含所有元素，每个元素用逗号分隔，元素可以是任意的 Value。

Object 对象在 JSON 中是用 {} 包含一系列无序的 Key-Value 键值对表示的，key是string类型，value则可以是string、number、boolean、null、Object或Array类型。

“Object”和”Array”这两个术语来自JavaScript规范。

【JSON的优点】

  1. 数据格式比较简单, 易于读写, 格式都是压缩的, 占用带宽小
  2. 易于解析, 客户端JavaScript可以简单的通过eval()进行JSON数据的读取
  3. 支持多种语言, 包括ActionScript, C, C#, ColdFusion, Java, JavaScript, Perl, PHP, Python, Ruby等语言服务器端语言, 便于服务器端的解析

【JSON的缺点】

  1. 没有XML格式这么推广的深入人心和使用广泛, 没有XML那么通用性
  2. JSON格式目前在Web Service中推广还属于初级阶段

【在PHP中使用JSON】
PHP中的json直接相关的函数只有json_encode和json_decode。其中json_encode只能接受 UTF-8 编码的字符串类型数据，所以此处我们可能用到iconv等编码转换函数。

在PHP５.2.0之后，可以使用json_encode直接操作服务器端的对象、数组等，能够直接生JSON格式, 便于客户端的访问提取。
另外，由于PHP中的数组是以HASH链表存在，可以使用非数字的关键字作为下标，所以，如果我们需要生成的数据是数组而不是对象时，需要数据的下标满足如下要求：

  • 必须是数字索引，
  • 必须从0开始，
  • 必须从小到依次增加，
  • 中间不可以弹跳下,
  • 位置不可变动.

这是由于在JS中数组是0开始的顺序序列，其余都只能是哈希表对象。如果要使用数组，可以使用array_values()函数。

【小结】
JSON 已经是 JavaScript. 标准的一部分。目前，主流的浏览器对 JSON 支持都非常完善。应用 JSON，我们可以从 XML 的解析中摆脱出来，对那些应用 Ajax 的 Web 2.0 网站来说，JSON 确实是目前最灵活的轻量级方案。

【参考资料】

http://ssgemail.javaeye.com/blog/36776

http://blog.csdn.net/kinglino520/archive/2009/03/30/4036449.aspx

http://hi.baidu.com/zhaofei299/blog/item/79ba4bf3473012c30b46e0d3.html

PHP遍历文件的4种方法

6条回复

【常规遍历方法】
常规遍历方法是指从PHP4开始就可以使用的方法，它是结合使用opendir()函数和readdir()函数，通过打开目录，读取目录和关闭目录，逐一判断列出所有的文件。简单实现代码如下：

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

/**
 * 获取当前目录及子目录下的所有文件
 * @param string $dir 路径名
 * @return array 所有文件的路径数组
 */
function get_files1($dir) {
    $files = array();
 
    if(!is_dir($dir)) {
        return $files;
    }
 
    $handle = opendir($dir);
    if($handle) {
        while(false !== ($file = readdir($handle))) {
            if ($file != '.' && $file != '..') {
                $filename = $dir . "/"  . $file;
                if(is_file($filename)) {
                    $files[] = $filename;
                }else {
                    $files = array_merge($files, get_files($filename));
                }
            }
        }   //  end while
        closedir($handle);
    }
    return $files;
}   //  end function

【使用glob】
glob() 函数依照 libc glob() 函数使用的规则寻找所有与 pattern 匹配的文件路径，类似于一般 shells 所用的规则一样。不进行缩写扩展或参数替代。
返回一个包含有匹配文件／目录的数组。如果出错返回 FALSE。
此函数不能作用于远程文件，被检查的文件必须通过服务器的文件系统访问。

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

<?PHP
/**
 * 获取当前目录下的所有文件
 * @param string $dir 路径名
 * @return array 所有文件的路径数组
 */
function get_files($dir) {
    $dir = realpath($dir) . "/";
    $files  = array();
 
    if (!is_dir($dir)) {
        return $files;
    }
 
    $pattern =  $dir . "*";
    $file_arr = glob($pattern);
 
    foreach ($file_arr as $file) {
        if (is_dir($file)) {
            $temp = get_files($file);
 
            if (is_array($temp)) {
                $files = array_merge($files, $temp);
            }
        }else {
            $files[] = $file;
        }   //  end if
    }
    return $files;
}   //  end function
?>

【使用directory 类】
这是个仿冒面向对象的机制来读取一个目录。
dir() 函数打开一个目录句柄，并返回一个对象。这个对象包含三个方法：read() , rewind() 以及 close()。并且有两个属性可用。handle 属性可以用在其它目录函数例如 readdir()，rewinddir() 和 closedir() 中。path 属性被设为被打开的目录路径。
若成功，则该函数返回一个目录流，否则返回 false 以及一个 error。可以通过在函数名前加上 “@” 来隐藏 error 的输出。

注意: read 方法返回的目录项的顺序依赖于系统。
注意: 本函数定义了内部类 Directory，意味着不能再用同样的名字定义用户自己的类。

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

/**
 * 递归显示当前指定目录下所有文件
 * 使用dir函数
 * @param string $dir 目录地址
 * @return array $files 文件列表
 */
function get_files($dir) {
    $files = array();
 
    if (!is_dir($dir)) {
        return $files;
    }
 
    $d = dir($dir);
    while (false !== ($file = $d->read())) {
        if ($file != '.' && $file != '..') {
            $filename = $dir . "/"  . $file;
 
            if(is_file($filename)) {
                $files[] = $filename;
            }else {
                $files = array_merge($files, get_files($filename));
            }
        }
    }
    $d->close();
    return $files;
}

【RecursiveDirectoryIterator类】
此方法自PHP 5.0有效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * 使用RecursiveDirectoryIterator遍历文件，列出所有文件路径
 * @param RecursiveDirectoryIterator $dir 指定了目录的RecursiveDirectoryIterator实例
 * @return array $files 文件列表
 */
function get_files($dir) {
    $files = array();
 
    for (; $dir->valid(); $dir->next()) {
        if ($dir->isDir() && !$dir->isDot()) {
            if ($dir->haschildren()) {
                $files = array_merge($files, get_files($dir->getChildren()));
            };
        }else if($dir->isFile()){
            $files[] = $dir->getPathName();
        }
    }
    return $files;
}
 
$path = "/var/www";
$dir = new RecursiveDirectoryIterator($path);
print_r(get_files($dir));

需要了解此类的其它信息请移步 http://www.php.net/~helly/php/ext/spl/