← 回到文章

百度招聘的一道题

在烂叶的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的随机数,然后看每个随机数落在哪一个区间,就将该区间对应的字符串输出。 【程序】
$filename = "A.txt";

/**
* 数据初始化 读取文件内容,拆分字符串形成数据,
* @param  $filename  数据文件名
* @return  如果文件打开错误或文件错误返回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], '
'; }
关于蒙特卡洛方法请猛击:蒙特卡洛方法
最后更新于 2010-06-24 11:52:00