a****n
发帖数: 1887 | 1 面试考得随机算法
from我的blog, http://www.cnblogs.com/asuran/
1. 要求从N个元素中随机的抽取1个元素。
2. 要求从N个元素中随机的抽取K个元素。
int remain = N
int select = K
for (int i = 0; i < N; ++i){
if (rand()% remain < select){
cout<
--select;
}
--remain;
}
第一个元素被选中的概率为 K/N
第二个元素被选中的概率为(K/N)*((K-1)/(N-1)) + ((N-K)/N) * (K/(N-1)) = K/N
.........
证明略（参看The Art of Computer Programming III）
3. 要求从N个元素中随机的抽取1个元素, 其中N无法确定(数据流)。
int Num;
int i = 0;
int choose = 0;
while(scanf("%d", &Num)&& Num != 0){
if (((double |
g*******y
发帖数: 1930 | |
w********p
发帖数: 948 | |
k***e
发帖数: 556 | 4 首先，感谢你的share，敬佩你码了这么多字
以下我只是列出一点事实，并不是想打击你的积极性。
1。programming pearl chap12基本包含了你写的内容。
2。那个证明完全不用refer到knuth的书，用归纳法就可以了。
3。在线n choose one can be extended to n choose k for general k
【在 a****n 的大作中提到】
: 面试考得随机算法
: from我的blog, http://www.cnblogs.com/asuran/
: 1. 要求从N个元素中随机的抽取1个元素。
: 2. 要求从N个元素中随机的抽取K个元素。
: int remain = N
: int select = K
: for (int i = 0; i < N; ++i){
: if (rand()% remain < select){
: cout<: --select;
|
a********a
发帖数: 219 | 5 这些题实在太难了。。。。
【在 a****n 的大作中提到】
: 面试考得随机算法
: from我的blog, http://www.cnblogs.com/asuran/
: 1. 要求从N个元素中随机的抽取1个元素。
: 2. 要求从N个元素中随机的抽取K个元素。
: int remain = N
: int select = K
: for (int i = 0; i < N; ++i){
: if (rand()% remain < select){
: cout<: --select;
|
a****l
发帖数: 245 | |
m*****f
发帖数: 1243 | 7 面试要考随机就考这些阿
知道了还难么..
【在 a********a 的大作中提到】
: 这些题实在太难了。。。。
|
r**u
发帖数: 1567 | 8 很不错，谢谢。
【在 a****n 的大作中提到】
: 面试考得随机算法
: from我的blog, http://www.cnblogs.com/asuran/
: 1. 要求从N个元素中随机的抽取1个元素。
: 2. 要求从N个元素中随机的抽取K个元素。
: int remain = N
: int select = K
: for (int i = 0; i < N; ++i){
: if (rand()% remain < select){
: cout<: --select;
|
Z*****Z
发帖数: 723 | 9 补充一个变体
Write a function that given a list of items and weights return a random item
in the list taking the weights into account.
【在 a****n 的大作中提到】
: 面试考得随机算法
: from我的blog, http://www.cnblogs.com/asuran/
: 1. 要求从N个元素中随机的抽取1个元素。
: 2. 要求从N个元素中随机的抽取K个元素。
: int remain = N
: int select = K
: for (int i = 0; i < N; ++i){
: if (rand()% remain < select){
: cout<: --select;
|
