Chinaunix

标题: 一道笔试题,Ubi Soft的 [打印本页]
作者: hellhell    时间: 2005-08-27 18:56
标题: 一道笔试题,Ubi Soft的
去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    时间: 2005-08-27 21:47
标题: 一道笔试题,Ubi Soft的
int i = 1;

(int) (rand() * i++) == 0
具体可以程序设计实践 C专家编程都有涉及
art of programming 上据说有证明
作者: assiss    时间: 2005-08-28 10:56
标题: 一道笔试题,Ubi Soft的
原帖由 "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    时间: 2005-08-28 11:15
标题: 一道笔试题,Ubi Soft的
假设搂主的rand()是[0-1]（好像是0~RAND_MAX）
if(rand()*MAX>;=strlen(buf))
这样对于每一行，都有机会符合这个表达式。
作者: assiss    时间: 2005-08-28 11:24
标题: 一道笔试题,Ubi Soft的
原帖由 "yovn" 发表：
像是0~RAND_MAX）
if(rand()*MAX>;=strlen(buf))
这样对于每一行，都有机会符合这个表达式。

但是每一行被选中的概率并不相等，
而且更要命的是：你无法保证一定能选中其中一行。
极有可能一行都不选。
作者: Arghawk    时间: 2005-08-28 11:33
标题: 一道笔试题,Ubi Soft的
(int) (rand() * 2) == 0呢？
作者: assiss    时间: 2005-08-28 11:39
标题: 一道笔试题,Ubi Soft的
[quote]原帖由 "Arghawk"](int) (rand() * 2) == 0呢？[/quote 发表：

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

同样不能保证一定会选到某行
作者: Arghawk    时间: 2005-08-28 11:58
标题: 一道笔试题,Ubi Soft的
没明白，为什么概率以n次方增长！第1次循环完了，第2次循环的rand()同样是产生一个在0到1之间的任何一个数，rand()可能产生和第1次同样的数啊！怎么概率就减少呢？
作者: assiss    时间: 2005-08-28 12:06
标题: 一道笔试题,Ubi Soft的
只有第一次循环完了第二次才有可能被选中，
第一次不被选中，1/2,第二次被选中，又是1/2,是：1/2×1/2
作者: yovn    时间: 2005-08-28 12:08
标题: 一道笔试题,Ubi Soft的
原帖由 "assiss" 发表：

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

这个你说的被选中概率不一样恐怕是毫无根据。
作者: yzc2002    时间: 2005-08-28 12:18
标题: 一道笔试题,Ubi Soft的
原帖由 "yovn" 发表：

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

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

这个除了说明遇到空行一定会成立以外，不能说明任何问题。
作者: assiss    时间: 2005-08-28 12:21
标题: 一道笔试题,Ubi Soft的
原帖由 "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    时间: 2005-08-28 12:22
标题: 一道笔试题,Ubi Soft的
一个文件里面每一行的字符数都不一样，也就是说strlen(buf)/MAX本身也是随机的。不知道一个随机数大于另一个随机数的概率等于多少。
作者: assiss    时间: 2005-08-28 12:24
标题: 一道笔试题,Ubi Soft的
[quote]原帖由 "yovn"]一个文件里面每一行的字符数都不一样，也就是说strlen(buf)/MAX本身也是随机的。不知道一个随机数大于另一个随机数的概率等于多少。[/quote 发表：

正因为是随机的，所以才不可能相等。
如果要相等，一定要满足我上面证明的情况。
作者: Arghawk    时间: 2005-08-28 12:47
标题: 一道笔试题,Ubi Soft的
原帖由 "assiss" 发表：
只有第一次循环完了第二次才有可能被选中，
第一次不被选中，1/2,第二次被选中，又是1/2,是：1/2×1/2

不好意思，没注意break语句！
作者: yzc2002    时间: 2005-08-28 12:58
标题: 一道笔试题,Ubi Soft的
  1. if(rand() * i++ == 0)
  2.     selectLine = buf;
复制代码

这个是正确的，但不能break
作者: assiss    时间: 2005-08-28 13:01
标题: 一道笔试题,Ubi Soft的
原帖由 "yzc2002"]这个是正确的，但不能break[/quote 发表：

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

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

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

不会出现每行被选中概率相同的情况。
作者: yzc2002    时间: 2005-08-28 13:10
标题: 一道笔试题,Ubi Soft的
第一行被选中的目的是保证至少有一行被选中，但有可能会被后来的赋值冲掉
(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    时间: 2005-08-28 13:12
标题: 一道笔试题,Ubi Soft的
原帖由 "yzc2002" 发表：
第一行被选中的目的是保证至少有一行被选中，但有可能会被后来的赋值冲掉
(1)只有一行时，结果就是1
(2)有两行时，第一次得selelctLint=1，第二次循环有50%的机会转化成2，机率各50%
....
(n)若前n-1行的机率都�.........

rand()*i++在第一次的时候就始终是0,请问哪里来的第二次？
作者: yzc2002    时间: 2005-08-28 13:15
标题: 一道笔试题,Ubi Soft的
说了不能break
作者: assiss    时间: 2005-08-28 13:15
标题: 一道笔试题,Ubi Soft的
即使是没有BREAK，
那么BUF在后来的读取中已经被冲掉了，
selectLine指向的将始终是最后一行，
这样还有什么意义？
作者: yzc2002    时间: 2005-08-28 13:19
标题: 一道笔试题,Ubi Soft的
唔~~~这个说得还有道理
也就是说这个selectLine不能是个char *，而应该是个string
作者: javacool    时间: 2005-08-28 13:26
标题: 一道笔试题,Ubi Soft的
(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 上有完整证明
作者: assiss    时间: 2005-08-28 13:28
标题: 一道笔试题,Ubi Soft的
原帖由 "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    时间: 2005-08-28 13:37
标题: 一道笔试题,Ubi Soft的
恩 对 我疏忽了 要去掉 BREAK
而且要转储字符串
不过这是个经典问题 其实肯定不应该有BREAK
因为最起码 程序要遍历文件一次 不然你怎么知道MAX_LINE
估计是楼主自己也没记清楚
据说MS 也出过这道题
作者: jronald    时间: 2005-08-28 15:08
标题: 一道笔试题,Ubi Soft的
static int i=1;
if( rand()<(1/i++) ){
}

这样行吗？
rand()<(1/i)的概率总是1/i
作者: jronald    时间: 2005-08-28 15:14
标题: 一道笔试题,Ubi Soft的
错了，怎么不能删啊
作者: jronald    时间: 2005-08-28 15:35
标题: 一道笔试题,Ubi Soft的
if( (int)(rand()*i++) ==0 ) ?
i初值一定，不是不管多少行，同一行的概率都相同了吗？
作者: jronald    时间: 2005-08-28 16:46
标题: 一道笔试题,Ubi Soft的
同意javacool~~
作者: RedNax    时间: 2005-08-31 00:44
标题: 一道笔试题,Ubi Soft的
我也参加过这个笔试，这个题目不算难，不过楼主记忆力不佳，基本上题目完全写错了（这也没办法，只有做出来才会详细记得什么样）。

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



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2