百度的一道试题…

Jessica     PHP     PHP, 算法

下面是百度招聘的一道试题，有兴趣的同学可以研究一下，要求用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多的if..真真涉及到算法的语句很少…= =||

不说了.直接贴给大家把..谁有更好的方法欢迎提供..:)

<?php  
class BaiduTest {  
    protected $fileName = "";  
    protected $num;  
    protected $array = array();  
    public function __construct($fileName, $num) {  
        if (is_file($fileName)) {  
            $this->fileName = $fileName;  
            $this->num = $num;  
            $this->readFile();  
        } else {  
            $this->throwException('找不到文件');  
        }  
    }  
 
    protected function readFile() {  
        $handle = fopen($this->fileName, "r");  
        if ($handle) {  
            for ($i=1;$i<=6 && !feof($handle);$i++) {  
                if ($buffer = fgets($handle)) {  
                    if (strlen($buffer) > 15) {  
                        $this->throwException('字符长度超过15个字节');  
                    } else {  
                        list($key, $value) = sscanf($buffer, "%s\t%d");  
                        if (emptyempty($key) || $value > 100) {  
                            $this->throwException('格式不正确');  
                        }  
                        $array[] = array($key => $value);  
                    }  
                }  
            }  
            if (!feof($handle) && fgets($handle) && $i>6) {  
                $this->throwException('文件超过6行');  
            }  
            //重点是这里.组合数组  
            foreach ($array as $v) {  
                foreach ($v as $k => $v2) {  
                    for ($i=1; $i<=$v2; $i++) {  
                        $this->array[] = $k;  
                    }  
                }  
            }  
            if (count($this->array) != 100) {  
                $this->throwException('总概率不等于100');  
            }  
            fclose($handle);  
        } else {  
            $this->throwException('无法打开文件');  
        }  
    }  
 
    public function outPut() {  
        //这个地方不能使用array_rand的第二个参数.不然出来的都是连续的  
        while ($this->num--) {  
            echo $this->array[array_rand($this->array)]."\n";  
        }  
    }  
 
    protected function throwException($str) {  
        throw new Exception($str);  
    }  
}  
$bt = new BaiduTest('a.txt', 10);  
$bt->outPut(); 

 还有一个a.txt..我直接打包给大家下载吧..

点我下载