[技术]讨论一个选择算法

[Johnbin]

给定一个数组X，大小为N。 要求设计这样一个选择函数select, 使得经过如下代码运行后，返回的结果elem为数组X中随机的一个元素（即概率
相等）。

ElementType elem = X[0];
for(int i=1; i<N; i++){
elem = select(elem, X[i]);// 返回两个参数其中之一
}
return elem;

[Shuo Chen]

select 以 1/(i+1) 的概率返回 X[i].
程序设计实践上举过这个例子。

[Lucas Zhang]

可以去看看编程珠玑2，里面有关于随机选择的讨论~

2009/10/23 Shuo Chen <gian...@gmail.com>

--
=============
Thank you
Zhang Qing

[赵立]

记得编程珠玑里就有这题

2009/10/23 Lucas Zhang <zhangq...@gmail.com>

[xueqiang pan]

和轮盘赌差不多吧

2009/10/22 Johnbin <johnbi...@gmail.com>

[Johnbin]

刚才证明了一下，果然应该是以1/i+1的概率选取i。但是不知道答案事先应该怎么思考呢。

[Johnbin]

嗯，研究了一下编程珠玑2里面的随机选择算法，他给出的算法可以返回一个随机排列的数组。

On 10月23日, 下午3时12分, Lucas Zhang <zhangqing1...@gmail.com> wrote:
> 可以去看看编程珠玑2，里面有关于随机选择的讨论~
>

> 2009/10/23 Shuo Chen <giantc...@gmail.com>

[Johnbin]

嗯，研究了一下编程珠玑2里面的随机选择算法，他给出的算法可以返回一个随机排列的数组。

On 10月23日, 下午3时12分, Lucas Zhang <zhangqing1...@gmail.com> wrote:

> 可以去看看编程珠玑2，里面有关于随机选择的讨论~
>
> 2009/10/23 Shuo Chen <giantc...@gmail.com>

[Johnbin]

嗯，研究了一下编程珠玑2里面的随机选择算法，他给出的算法可以返回一个随机排列的数组。

On 10月23日, 下午3时12分, Lucas Zhang <zhangqing1...@gmail.com> wrote:

> 可以去看看编程珠玑2，里面有关于随机选择的讨论~
>
> 2009/10/23 Shuo Chen <giantc...@gmail.com>

[Shuo Chen]

我不懂，我碰巧知道答案。