一道笔试题,Ubi Soft的

yzc2002

原帖由 "yovn" 发表：

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

？？？

原帖由 "yovn" 发表：
if(rand()*MAX>;=strlen(buf))

这个除了说明遇到空行一定会成立以外，不能说明任何问题。

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行获得的字串


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

yovn

一个文件里面每一行的字符数都不一样，也就是说strlen(buf)/MAX本身也是随机的。不知道一个随机数大于另一个随机数的概率等于多少。

assiss

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

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

Arghawk

原帖由 "assiss" 发表：
只有第一次循环完了第二次才有可能被选中，
第一次不被选中，1/2,第二次被选中，又是1/2,是：1/2×1/2

不好意思，没注意break语句！

yzc2002

1. if(rand() * i++ == 0)
   
2.     selectLine = buf;
   

复制代码

这个是正确的，但不能break

assiss

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

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

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

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

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

yzc2002

第一行被选中的目的是保证至少有一行被选中，但有可能会被后来的赋值冲掉
(1)只有一行时，结果就是1
(2)有两行时，第一次得selelctLint=1，第二次循环有50%的机会转化成2，机率各50%
....
(n)若前n-1行的机率都有1/(n-1)，再看这一行：if(rand() * i++ == 0)这个成立的机率是1/n，不成立的机率是(n-1)/n，即取第n行的机率是1/n，取前n-1行的机率是(n-1)/n，由前面的假设，得到前n-1任一行的机率都是(n-1)/n*(1/(n-1)) = 1/n
证毕

assiss

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

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

yzc2002

说了不能break