在烂叶的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 />'; } |
关于蒙特卡洛方法请猛击：蒙特卡洛方法
Pingback引用通告： PATRICK