r*****t
发帖数: 286 | 1 ☆─────────────────────────────────────☆
yogaII (...) 于 (Wed Jan 31 15:24:18 2007) 提到:
不是finance company. 就问了一个问题。 就算一个brainteaser吧：
一个设备一直读进objects。 每次进来一个object
要求设计一个算法， 在任何时候都有10个objects， 并且所有读进来的objects被选中
的概率一样。
原题略略有点不同， 但是基本上差不多。
☆─────────────────────────────────────☆
bigbendan (LoveforeverLong) 于 (Thu Feb 1 12:59:13 2007) 提到:
ambiguous.
re-write.
random(1,10) ? random(1,N)?
☆─────────────────────────────────────☆
wusuowei (wuxuowei) 于 (Thu Feb 1 18:06:11 2007) | t*****l
发帖数: 121 | 2 看到精华区的这个贴子,觉得按这样的解法,当进来的object数目很大的时候,设备里
的10个object是不会变化了的.也就是说,每个进来的object被选中的概率是不同的.
正确的选择应该是10个以后进来的 object,如果是第k个,就按10/k的概率选择这个
object留下,然后再在10个保留的object里面选一个替换.这样可以保证每个object被留
在设备中的概率是10/k
选中
the
【在 r*****t 的大作中提到】
: ☆─────────────────────────────────────☆
: yogaII (...) 于 (Wed Jan 31 15:24:18 2007) 提到:
: 不是finance company. 就问了一个问题。 就算一个brainteaser吧：
: 一个设备一直读进objects。 每次进来一个object
: 要求设计一个算法， 在任何时候都有10个objects， 并且所有读进来的objects被选中
: 的概率一样。
: 原题略略有点不同， 但是基本上差不多。
: ☆─────────────────────────────────────☆
: bigbendan (LoveforeverLong) 于 (Thu Feb 1 12:59:13 2007) 提到:
:
|
|
