百度招聘的一道题
在烂叶的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], '
';
}
关于蒙特卡洛方法请猛击:蒙特卡洛方法