随机数算法
tcsong
posted @ Fri, 13 Aug 2010 09:56:28 -1100
in Others
, 1300 readers
本文参考more programming pearls的相关章节，表说我抄袭……
假设你有一个随机函数RandInt(L,U)，如何产生1..N中的M个不重复的随机数？
正常人想到的算法是类似这样的：
//initialize set s to empty
int size = 0;
while (size < M) {
int t = RandInt(1,N);
if (t not in s){
s.insert(t);
size=size+1;
}
}
但是这个算法有一个致命缺陷，当M值与N值很接近时，在获得最后几个随机数时它需要猜测太多次以至于这将严重降低程序的运行速度，对于特定的随机数列，它甚至不会停止。那么，有没有一种只需要运行M次RandInt函数即可获得M个不重复随机数的算法呢？有的。Floyd大神给出了他的答案：
int sample(int M, int N){
if (M=0) return new Set();
else{
Set s=sample(M-1,N-1);
int t=RandInt(1,N);
if(t not in s) s.insert(t);
else s.insert(N);
return s;
}
}
这个算法为了从1..N中产生M个随机数，先从1..N-1中产生M-1个随机数，然后加上N去产生第M个随机数。很神奇吧？
Tue, 27 Sep 2022 20:08:43 -1100
Each 6th class student who wants to give their best in every Geography examination conducted by the any Central Education Board in Term-1 & Term-2 such as SA1, SA2, FA1, FA2, FA3, FA4 and Assignments and other types of exams can download NCERT 6th Class Geography Sample Paper 2023 with answers for regular practising by mock tests and revisions. NCERT Geography Question Paper Class 6 Each 6th class student who wants to give their best in every Geography examination conducted by the any Central Education Board in Term-1 & Term-2 such as SA1, SA2, FA1, FA2, FA3, FA4 and Assignments and other types of exams can download NCERT 6th Class Geography Sample Paper 2023 with answers for regular practising by mock tests and revisions.
Sat, 26 Nov 2022 00:55:01 -1100
Accidentally i have come across this website and little bit confused real estate services Avondale about the details shared here. This post deals with the details regarding some random number algorithm details. It refers to the relevant chapters of more programming pearls. Keep sharing more updates over here.
Wed, 17 Jan 2024 02:44:36 -1100
The affordability of 오피타임's services is truly commendable.
Wed, 17 Jan 2024 09:59:58 -1100
제주출장마사지 offers an array of therapies that cater to diverse needs.