一道笔试题,Ubi Soft的

hellhell

去Ubi Soft笔试了一次,可耻地失败了,但有道题目印象深刻,反正是以前没见过的:

有一个长度不定的文本文件,要从中随机选出一行,要求在一次遍历文件之内完成,而且每一行被选中的概率相等.

原题是填空,大概是这样子,不一定准确,但意思到堂了:

char* f(){
char* selectLine;
static char buf[MAX];

while( readline(buf, MAX))
{
        if ( 要填的地方) {
               selectLine = buf;
               break;
       }
}
}
return selectLine;

可以使用rand()函数,返回一个0-1的double型的随机数.

今天上网一次,下次大概是十天半个月以后,所以如果说明不清,只好望大家见谅,并自行揣摩意思,对不起

RedNax

我也参加过这个笔试，这个题目不算难，不过楼主记忆力不佳，基本上题目完全写错了（这也没办法，只有做出来才会详细记得什么样）。

最重要的是：这个考试最后必须签名申明不会泄露笔试内容的！我看版主还是把这贴删了吧。

jronald

同意javacool~~

jronald

if( (int)(rand()*i++) ==0 ) ?
i初值一定，不是不管多少行，同一行的概率都相同了吗？

jronald

错了，怎么不能删啊

jronald

static int i=1;
if( rand()<(1/i++) ){
}

这样行吗？
rand()<(1/i)的概率总是1/i

javacool

恩 对 我疏忽了 要去掉 BREAK
而且要转储字符串
不过这是个经典问题 其实肯定不应该有BREAK
因为最起码 程序要遍历文件一次 不然你怎么知道MAX_LINE
估计是楼主自己也没记清楚
据说MS 也出过这道题

assiss

原帖由 "javacool" 发表：
(int)(rand()*i++) ==0
保证每行的概率是1, 1/2, ....., 1/MAX
注意这个其实是条件概率
我们从第MAX行考虑 他被选中的概率为1/MAX
如果他没被选中 则按平均分布的概念 应该在MAX-1种选一个
设第MAX-1元素被选�.........

这样的算法，楼主的题目要改两个地方：
1、把BREAK去掉
2、
selectLine=buf;
改为
char selectLine[MAX];
……
strcpy(selectLine, buf);

javacool

(int)(rand()*i++) ==0
保证每行的概率是1, 1/2, ....., 1/MAX
注意这个其实是条件概率
我们从第MAX行考虑 他被选中的概率为1/MAX
如果他没被选中 则按平均分布的概念 应该在MAX-1种选一个
设第MAX-1元素被选中为A 第MAX元素没有被选中为B
因此P(A|B) = P(AB)/P(B) = 1/(MAX-1)
P(AB)从概念上理解就是P(A) 因为B情况包含A因此
P(A)/P(B) = 1/(MAX-1)  P(B) = 1 - 1/MAX = (MAX-1)/MAX
因此P(A)的概率也是1/MAX
由此往前推 其实所有元素的概率都是1/MAX 及满足均匀分布
其实最需要注意的是真实概率其实并不是1/n ,这是一个条件概率

严密的证明我也给不出
程序设计实践上说The art of programming 上有完整证明

yzc2002

唔~~~这个说得还有道理
也就是说这个selectLine不能是个char *，而应该是个string