立即注册 登录
返回首页

残废的名侦探的个人空间

日志

经常使用的小程序

已有 190 次阅读2019-12-15 22:51 |个人分类:程序算法| 程序算法

声明:摘自牛客
输出随机数:从0...n-1中等概率随机输出m个不重复的数字,并且假设n远大于m
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--;
        }
     }
}
由这个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

路过

鸡蛋

鲜花

握手

雷人

评论 (0 个评论)

facelist

您需要登录后才可以评论 登录 | 立即注册

手机版|小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

返回顶部