一道笔试题,Ubi Soft的

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）。

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

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

assiss

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

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

assiss

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

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

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

assiss

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

assiss

原帖由 "yovn" 发表：

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

首先，你的方法不能保证一定会选中一行。

其次，根据楼主所说的，不定长的文件，每行不定长，

当且仅当如下情况时：
1-strlen(buf1)/MAX=1/lines_num
1-strlen(buf2)/MAX=1/(lines_num-1)
1-strlen(buf3)/MAX=1/(lines_num-2)
……
1-strlen(bufn)/MAX=1/(lines_num-n+1)

lines_num指的是总行数，buf1,buf2...bufn指的是第N行获得的字串


每行的概率才会相等。
而你的方法无法保证这种情况。

assiss

[quote]原帖由 "yovn"]一个文件里面每一行的字符数都不一样，也就是说strlen(buf)/MAX本身也是随机的。不知道一个随机数大于另一个随机数的概率等于多少。[/quote 发表：

正因为是随机的，所以才不可能相等。
如果要相等，一定要满足我上面证明的情况。

assiss

原帖由 "yzc2002"]这个是正确的，但不能break[/quote 发表：

请问你对我的理解如何看？

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

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

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

assiss

原帖由 "yzc2002" 发表：
第一行被选中的目的是保证至少有一行被选中，但有可能会被后来的赋值冲掉
(1)只有一行时，结果就是1
(2)有两行时，第一次得selelctLint=1，第二次循环有50%的机会转化成2，机率各50%
....
(n)若前n-1行的机率都�.........

rand()*i++在第一次的时候就始终是0,请问哪里来的第二次？

assiss

即使是没有BREAK，
那么BUF在后来的读取中已经被冲掉了，
selectLine指向的将始终是最后一行，
这样还有什么意义？

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);