首页 > 试题广场 >

下面的程序可以从0....n-1中随机等概率的输出m个不重复

[单选题]

下面的程序可以从0....n-1中随机等概率的输出m个不重复的数。这里我们假设n远大于m

knuth(int n, int m)
{ 
    srand((unsigned int)time(0)); 
    for (int i = 0; i < n; i++) { 
        if ( ) { 
            cout << i << endl; 
            ( ); 
        } 
     } 
}

```
rand()%(n-i) <= m    m--
```
```
rand()%(n-i) < m    m--
```
```
rand()%(n-i) >= m    m++
```
```
rand()%(n-i) > m    m++
```

查看正确选项

dwj411024

上面有的回答思路很正确，但概率表述有问题，在这跟大家分享下

由这个for循环循环n次，且在满足条件时才输出i,可知，输出m个不同值的要求已满足，因为每次输出的都是i值，而i值每次都是不一样的，m--保证了程序在输出了m个值后就停止循环。

在i=0时，rand()%(n-i)的取值范围为0到n-1，共n个数，此时要输出0只需要rand()%(n-i)小于m，故i=0被输出的概率为m/n;

在i=1时，rand()%(n-i)的取值范围为0到n-2，共n-1个数，若i=0没有被输出，则m--未被执行，此时i=1被输出的概率为m/(n-1)，若i=0已经被输出了，则m变为m-1，此时i=1被输出的概率为(m-1)/(n-1)；由概率论的知识，可知此时i=1被输出的概率为

P=(1-m/n)*(m/(n-1))+m/n*((m-1)/(n-1))=m/n；以此类推，可知每个数被输出的概率都为m/n

发表于 2016-03-23 18:14:27 回复(41)

zhaol233

第一次循环，i=0，随机数输出概率m/n；

第二次循环，i=1，若0已经输出，则m=m-1，此时1输出的概率为(m-1)/(n-1)；若0没有输出，1输出的概率为m/(n-1),,则1输出的概率为(1-m/n)*(m/(n-1))+m/n*((m-1)/(n-1))=m/n

第三次循环，i=2，共四种情况，证明同上。

具体类比抽签，rand()%(n-i)，为控制概率，i为签值。要使抽中i的概率为m/n,直到抽出m个不同的值.

....

发表于 2020-12-28 19:00:55 回复(0)

LiamJin

循环执行了n次。

发表于 2018-09-06 21:18:51 回复(0)

AresGao

很有意思，注意三点：
第一：任意一个整数n作为除数，所能取到余数的范围是(0~n-1)
第二：每个数被输出的概率都是n/m
第三：N远大于M......

发表于 2017-03-23 20:17:26 回复(0)

火星01

本来奇怪rand()%n一直是大于等于m的怎么办？那样最后可能得不到m个数。。。结果发现远大于这三个字。。。

编辑于 2016-08-25 14:14:28 回复(0)

huixieqingchun

答案A正确，这样寻找的m个数相当于数学概率上的抽签式得到的，每次得到的概率相等。

发表于 2016-05-18 19:57:01 回复(0)

冬

#include <iostream>
#include<ctime>
#include<cstdlib>

using namespace std;

void knuth(int n, int m)
{ 
    srand((unsigned int)time(0)); 
    for (int i = 0; i < n; i++) { 
      //rand() % (n-i)通过对（n-i）取模，获得了一个从n-i的随机数，就是说
	 //如果i=0;就是随机产生1到n的数，与m作比较是限制在m个数据中不会
	 //有相同的数重复出现，同时确保等概率性
		  if ( rand() % (n-i) < m) 
		{ 
            cout << i << endl;
            m--;
        }
     }
}

int main()
{
//本题一个比较关键的条件是n远远大于m，这样满足这个条件才能确保
//每次都会得到m个数据
	knuth(10000000,5);
	system("pause");
	return 0;
}

编辑于 2015-08-13 20:10:51 回复(1)

ABCD

我也不明白，之前生成不重复的n个随机数，都是把生成的随机数作为一个数组的下标来处理的 #include <time.h>

#include <iostream>

#include <ctime>

int main()

{

srand(time(0));

int N; int m;//需要产生m个在0~N之间的不重复随机数

int arr[N];//生成的随机数在0-N之间

int k=0;

for(int i=0;i<N;i++)

{

arr[i]=i;//将数组赋给初值

}

for(int j=0;j<m;)

{

k=rand()%200;

if(arr[k]==-1)

{

k=rand()%200;//如果随机产生的这个数已经被用了就重新产生

}

else{

b[j]=arr[k];

arr[k]=-1;//每选出数组中的一个数，将其标记为-1

j++;//随机产生的数没有被用，才随机产生下一个数

}

return 0;

}

发表于 2015-05-26 16:31:54 回复(0)

been

不太明白题目意思。。。晦涩

发表于 2015-05-22 11:36:23 回复(1)

PacoVirus

rand()%(n-i)<m 和 m--;

发表于 2014-11-15 10:18:50 回复(0)

不想编程你还读个毛计算机

为了方便解释假设n等于10，m等于5：
第一次rand()%(n-0)的余数范围是0~9,有可能小于m(=5)，可以输出i=0；随后i++,m--
第二次rand()%(n-1)的余数范围是0~8,有可能小于m(=4)，可以输出i=1；随后i++,m--
...
第五次rand()%(n-4)的余数范围是0~5,有可能小于m(=1)，可以输出i=4；随后i++,m--得到i=5,m=0

第六次rand()%(n-5)的余数范围是0~4,不可能小于m(=0)，算法结束。

倘若rand()%(n-i)<=m，则第六次还满足条件，意味着多输出的一次；

而rand()%(n-i)>=m，将会因为判断条件不满足而提早退出。因此选B

发表于 2015-03-11 15:56:16 回复(7)

xcwqr

代码【没有问题】。算出来的数是等概率的！！！！

为了方便解释假设n等于10，m等于5：

第一次rand()%(n-0)的余数范围是0~9,有可能小于m(=5)，可以输出i=0；随后i++,m--
第二次rand()%(n-1)的余数范围是0~8,有可能小于m(=4)，可以输出i=1；随后i++,m--
...

i=0这个数被选中的概率为：5/10

i=1这个数被选中的概率为：（5/10）*（4/9 ）+ （5/10）*（ 5/9 ）=5/10

……

发表于 2016-04-14 17:09:56 回复(0)

Kris_z

/********************************************************************************************************

需满足三个条件：

(1)输出m个数,即cout<<i<<endl;语句执行m次

rand()%(n-i)>0,故当m<0时,rand()%(n-1)<m不成立,循环结束,所以第二个空应为m--

(2)不重复

由于i一直增长,所以不会输出重复值

(3)随机等概率

rand()函数保证随机

   当i=0时，rand%(n-i)取值范围为0~n-1，总共n个数，只要rand()%(n-i)<m输出i=0的概率就为m/n。（小于号的原因是从0开始，取到m-1就总共m个数）。  
   当i=1时，rand%(n-i)取值范围为0~n-2，总共n-1个数，当i=0输出时，执行m--，当i=0未输出时，m的值不变，根据条件概率公式，输出i=1的概率p=(m/n)*((m-1)/(n-1))+(1-m/n)*(m/(n-1))=m/n。  
   以此类推，每个数被输出的概率为m/n。  

原理可参考抽签顺序和概率无关。

********************************************************************************************************/

#include<iostream>

#include<ctime>
#include<cstdlib>
using namespace std;

knuth(int n, int m)
{
srand((unsigned int)time(0));
for (int i = 0; i < n; i++) {
if ( rand()%(n-i)<m) {
cout << i << endl;
(m-- );
}
}
}
int main()

{

knuth(1000,5);
return 0;
}

发表于 2018-04-02 16:46:24 回复(1)

牛客950847号

这个代码有问题。这样算出来的数并不是等概率的。

引用排名第一的答案：

为了方便解释假设n等于10，m等于5：

第一次rand()%(n-0)的余数范围是0~9,有可能小于m(=5)，可以输出i=0；随后i++,m--
第二次rand()%(n-1)的余数范围是0~8,有可能小于m(=4)，可以输出i=1；随后i++,m--
...

i=0这个数被选中的概率为：5/10

i=1这个数被选中的概率为：4/9

...

从前面两个就可看出被选中的概率并不相等。

如果我说的有不对的地方，欢迎指出

发表于 2015-09-04 18:02:59 回复(9)

my_adu

引用楼下的假设，贴个图

应该很明了了

发表于 2015-05-15 10:42:03 回复(5)

牛客3821038号

题目：从0到n-1中等概率取m个数字

思路转换：一共n个人抽签，抽签的序号为0到n-1（我们不妨把题目转换为在这n个人当中等概率选取m个人去参加C++程序大赛）

因此：这n个人排队抽签，一共n个序号，第一个人抽签，如果抽到前m个，那么他就被choose。总签数n--。同时名额就少了一个，m--;

第二个人，也去抽签，如果抽到前m-1个，他就被choose了。总签数n--，同时名额就又少了一个，m--;

第三个人，也去抽签，如果没有抽到前m-2个，那么总签数仍然少了一个，n--,但是名额不变，所以，下次rand%(n-2) < m-2,时，就choose

发表于 2017-08-03 17:53:12 回复(1)

牛客752636号

经典的蓄水池抽样

发表于 2015-09-12 18:31:50 回复(0)

Alliswell31

我第一个就把b给排除了，我琢磨着怎么也该有个m--，看了下解析，应该是选项少东西了吧

发表于 2022-02-14 16:10:19 回复(0)

牛客888833994号

A%B的余数取值范围只能是0~(m - 1)，题目要求输出m个不重复的数，重点是m个，所以没输出一个数字，m的值都要减1，当m的值等于1的时候，说明按照程序运行的逻辑，在刚进入循环体中，当m为1时，就输出了m个数，接着运行m--，说明当m==0的时候，就不能满足if条件了，rand %（n - i)的取值范围是（0~（n-i-1）)，所以要求当m==0的时候，rand % ( n - i )必须大于0, 即rand % ( n - i ) - m > 0，所以rand % ( n - i )>m

发表于 2021-03-18 11:08:38 回复(0)

牛客457050893号

简单点：首先是对i的遍历，输出是i，这样保证了每次输出的i不会重复。

为了限定输出数量，肯定是m--和<m的。因为

rand()%(n-i)是个随机数，m=0时不会在打印数据。所以实际打印的个数是1~m时打印，即m个，取小于号。若取等，m=0的时候，还会再打印一个数。

发表于 2019-12-31 11:48:04 回复(0)

提交观点

问题信息

C语言迅雷

来自：C/C++工程师能力评估

上传者：小小

难度：

57条回答 5920收藏 29182浏览

下面的程序可以从0....n-1中随机等概率的输出m个不重复

问题信息

热门推荐

相关试题