一道笔试题,Ubi Soft的

javacool

int i = 1;

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

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 上有完整证明

javacool

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