标签归档：PHP应用

百度招聘的一道题

1条回复

在烂叶的blog上看到一篇关于百度招聘的一道题
地址：百度招聘的一道试题

有些兴趣，自己实现了下，使用了类蒙地卡罗方法实现。

【题目】
2009百度实习笔试题
要求用PHP，shell或c完成
输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
文件格式如下：
字符串\t数字\n

说明：
每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。

要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机地输出字符串，输出N条记录

例如：
输入文件A.txt
abc20
a30
de50
输入为：10

即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记录
以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
de
de
abc
de
a
de
a
de

【算法】
先将数据从文件中取出存放到数组，然后将概率空间分割为所给字符串个数个部分，然后生成N个1-100的随机数，然后看每个随机数落在哪一个区间，就将该区间对应的字符串输出。

【程序】

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

 
$filename = "A.txt";
 
/**
* 数据初始化 读取文件内容，拆分字符串形成数据，
* @param <type> $filename  数据文件名
* @return <type> 如果文件打开错误或文件错误返回FALSE                                                      
*/
function data_init($filename) {
    $lines = file($filename);
 
    if ($lines === FALSE) {
       return FALSE;
    }
 
    $data = array();
    foreach ($lines as $row) {
       $row = rtrim($row, "\r\n");
 
       $index = strpos($row, "\t");
       $key = substr($row, 0, $index);
 
       if (strlen($key) > 15) {
           return FALSE;
       }
 
       $data[$key] = (int) substr($row, $index + 1);
    }
 
    return $data;
}
 
$data = data_init($filename);
 
if ($data === FALSE) {  //  输入文件错误
    die('Input File Error!');
}
 
if (array_sum($data) != 100) {  //  输入数据错误
    die('Input Data Error!');
}
 
/* 以类蒙地卡罗方法实现 */
$map = array();
$k = 0;
 
/* 概率空间分割 */
foreach ($data as $key => $row) {                                                 
    $i = $row;
    for ($i = 1; $i <= $row; $i++) {
       $map[$k + $i] = $key;
    }
    $k += $row;
}
 
/* 随机输出 */
$count = 10;
for ($i = 0; $i < $count; $i++) {
    $rand_num = rand(1, 100);
    echo $map[$rand_num], '<br />';
}

关于蒙特卡洛方法请猛击：蒙特卡洛方法

PHP5.2.0之前版本使用JSON函数的方法

1条回复

PHP5.2.0之前版本使用JSON函数的方法
我们知道PHP在其版本5.2.0之后才支持 JSON相关函数，在此版本之前如果我们要使用JSON函数则需要自己实现
JSON的算法已经有人实现了，其下载地址为：http://pear.php.net/pepr/pepr-proposal-show.php?id=198

但是它是一个类这与我们的使用习惯不同，于是我们需要将它包装下，其代码如下：

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

/**
* 对象转换成数组 递归函数
* @param <type> $value 需要转换的值                                
* @return <type>
*/
function object2array($value) {
   if (!(is_array($value) || is_object($value))) {
       return $value;
   }
 
   $array = array();
   foreach ($value as $key => $row) {
       $array[$key] = object2array($row);
   }
 
   return $array;
}
 
/**
* 替换JSON方法
*/
if (!function_exists("json_encode")) {
   include_once("JSON.php");
 
   function json_encode($array) {
       $json = new Services_JSON();
       $json_array = $json->encode($array);
       return $json_array;
   }
 
   /**
    * 解析JSON数据
    * @param string $json_data 需要解析的JSON数据                                                      
    * @param bool $toarray 是否需要解析成数组                                      
    * @return array 返回解析后的数组
    */
   function json_decode($json_data, $toarray = TRUE) {
       $json = new Services_JSON();
       $array = $json->decode($json_data);
 
       if ($toarray) { //  需要转换成数组
           $array = object2array($array);
       }
       return $array;
   }
 
}

不过以上的递归实现在效率上有一些慢，它需要遍历这个数组的所有元素，
如果只限于实现二维数组，可以考虑直接使用循环+类型强制转化来做
【EOF】

PHP中大整数相乘的2种实现方式

发表回复

PHP中大整数相乘的2种实现方式
1、【通过调用BCMath实现】
PHP 为任意精度数学计算提供了二进制计算器（Binary Calculator），它支持任意大小和精度的数字，以字符串形式描述。
示例代码如下：

1
2
3
4
5
6

<?PHP
$op_left = '123456789123456789';                                                                                  
$op_right = '123456789123456789';
$rs = bcmul($op_left, $op_right);
var_dump($rs);
die();

2、【通过字符串数组相乘实现】
将乘数和被乘数分别按指定的位数存放到数组中，然后再模拟乘法，将结果加起来，最后在返回的时候针对不够位数的进行补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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

<?PHP
define('DEPTH', 10000);
define('LEN', strlen(DEPTH) - 1);
 
/**
 * 格式化数组元素，如果单个元素的值不够LEN的长度，前面补0
 * @param string $input
 */
function item_format(&$input) {
    $input = str_pad($input, LEN, "0", STR_PAD_LEFT);
}
 
/**
 * 初始化相乘的字符串，将其转化成数组
 * @param string $input 需要相乘的操作数
 * @return array 已经分好块，并且逆转了的数组
 */
function init_array($input) {
    $begin_len = strlen($input) % LEN;
    $a = array();
    if ($begin_len > 0) {
        $a[0] = substr($input, 0, $begin_len);                                                                         
        $input = substr($input, $begin_len);
    }
    $a = array_merge($a, str_split($input, LEN));
    return array_reverse($a);
}
/**
 * 大整数相乘的数组实现
 * @param string $left_operand  左边的操作数
 * @param string $right_operand 右边的操作数
 * @return string   相乘的结果
 */
function mul($left_operand, $right_operand) {
    if (empty($left_operand) || empty($right_operand)) {
        return FALSE;
    }
 
    /* 初始化相乘的数组 */
    $a = init_array($left_operand);
    $b = init_array($right_operand);
    $len_a = strlen($a);
    $len_b = strlen($b);
 
    for ($i = 0; $i < $len_a; $i++) {
        for ($j = 0; $j < $len_b; $j++) {
            $c[$i + $j] += $a[$i] * $b[$j];
            if ($c[$i + $j] >= DEPTH) { //  进位操作
                $c[$i + $j + 1] += floor($c[$i + $j] / DEPTH);
                $c[$i + $j] %= DEPTH;
            }
        }
    }
 
    $c = array_reverse($c);
    array_walk(&$c, 'item_format');
    return ltrim(implode('', $c), '0');
}
$left_operand = '123456789123456789';
$right_operand = '123456789123456789';
$rs = mul($left_operand, $right_operand);
var_dump($rs);

EOF