一道笔试题,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型的随机数.

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

javacool

int i = 1;

(int) (rand() * i++) == 0
具体可以程序设计实践 C专家编程都有涉及
art of programming 上据说有证明

assiss

原帖由 "javacool" 发表：
int i = 1;

(int) (rand() * i++) == 0
具体可以程序设计实践 C专家编程都有涉及
art of programming 上据说有证明

i=1,
rand()根据楼主的意思是0~1.
如果不包括1,那(int)(rand()*1)就是0了。
第一行必被选中。

如果rand()是[0,1]，那么
第一行被选中的概率是[0,1)/[0,1]，
还是必被选中（一个点在一个区间里出现的的概率极限值为0）。

不会出现每行被选中概率相同的情况。

不知道我的理解是不是对的，
请大家指正。

yovn

假设搂主的rand()是[0-1]（好像是0~RAND_MAX）
if(rand()*MAX>;=strlen(buf))
这样对于每一行，都有机会符合这个表达式。

assiss

原帖由 "yovn" 发表：
像是0~RAND_MAX）
if(rand()*MAX>;=strlen(buf))
这样对于每一行，都有机会符合这个表达式。

但是每一行被选中的概率并不相等，
而且更要命的是：你无法保证一定能选中其中一行。
极有可能一行都不选。

Arghawk

(int) (rand() * 2) == 0呢？

assiss

[quote]原帖由 "Arghawk"](int) (rand() * 2) == 0呢？[/quote 发表：

第一行被 选中的概率是1/2
第二行是1/2×1/2
第三行是1/2×1/2×1/2
……
第N行是（1/2）的N次方

同样不能保证一定会选到某行

Arghawk

没明白，为什么概率以n次方增长！第1次循环完了，第2次循环的rand()同样是产生一个在0到1之间的任何一个数，rand()可能产生和第1次同样的数啊！怎么概率就减少呢？

assiss

只有第一次循环完了第二次才有可能被选中，
第一次不被选中，1/2,第二次被选中，又是1/2,是：1/2×1/2

yovn

原帖由 "assiss" 发表：

但是每一行被选中的概率并不相等，
而且更要命的是：你无法保证一定能选中其中一行。
极有可能一行都不选。

这个你说的被选中概率不一样恐怕是毫无根据。