概率/随机数算法

概率/随机数算法包含主要的概率/随机数问题相关算法

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

0-1等概率问题

问题描述

  • 一个随机数产生器以概率P生成0,以概率(1-P)生成1,怎样生成等概率的0和1?

主要思路

  • 如果用这个产生器产生两个位,出现00的概率为P^2,出现01的概率为P(1-P),出现10的概率为P(1-P),而出现11的概率为(1-P)^2。故而可以用10表示1,01表示0,从而保证生成0和1的概率是相同的。

代码实现

int generate01(int (*func)()) {    if (func == NULL)        return -1;    int num1 = -1;    int num2 = -1;    int ret = -1;    while(num1 != num2){        num1 = func();        num2 = func();        if (num1 == 1 && num2 == 0) {            ret = 1;            break;        } else if (num1 == 0 && num2 == 1) {            ret = 0;            break;        }    }        return ret;}

0-1问题扩展

  • 利用这个随机数生成器,等概率的生成1,2,……,n

主要思路

  • 利用上面实现的等概率生成0-1的生成器,等概率的生成k为二进制的bit,而其表示的整数值X在0~n-1的范围时,输出X+1,否则重复产生。

代码实现

int generateRandomNum(int max) {    if (max < 1) {        return -1;    }    int bit_num = 0, i = 0;    int result = 0;        while((0x01 << bit_num) < max)         ++bit_num;    //while(result > n) {        while(bit_num > i) {            if (generate01())                result |= 0x01 <<bit_num; //result |= 0x01<<i            i++;        }        i = 0;   // }    return result;}

不重复随机数的产生

问题描述

  • 随机产生0~n-1中的k个不重复的随机数。

主要思路

  • 借用蓄水池算法。先定义一个1~n-1的数组,然后从中抽样K个数。

生成给定范围的随机数

问题描述

  • 给定能随机生成整数1~5的函数,写出能随机生成整数1~7的函数

解决思路

  • 产生K个数(k>1),假定产生的数分别为N1,N2,……Nk,则产生的数为:N1-1+(N2-1)*5 + (N3-1)*5^2,……,(Nk-1)*5^(k-1),即产生的数位于(0,5^(k-1))区间呢。然后把区间等分成k分,则产生的随机数位于(0~6),然后+1即可。如果位于K等分的余数范围,则重新执行上述过程。(PS:不用担心余数问题,当K取3时,落到余数范围的概率已经降为6/125,而且余数不会导致概率的问题,只会影响效率。次解法相当于五进制)

代码实现

int generateRandom(int n) {
    if (n < 1)
        return -1;

    unsigned long long result = 0;

    for (int i = 0; i < n; i++) {
        result += rand5();
    }
    result /= 5;

    return result;
}

如何随机选取1000个关键字

问题描述

  • 给定一个数据流,其中包含无穷尽的搜索关键字(比如,人们在谷歌搜索时不断输入的关键字)。如何才能从这个无穷尽的流中随机的选取1000个关键字?

主要思路

  • 利用蓄水池算法。先生成一个大小为1000的数组,将前1000个关键字填入数组中,随后的关键字随机进行交换。

在半径为1的圆中随机选取一点

主要思路

  • 假设圆心(0,0)。在X轴[-1,1],Y轴[-1,1]的正方形内随机选点,然后判断该点是否在圆内。正方形的面积为4,圆形的面积为Pi,故而正方形内的随机点落在圆内的概率为: Pi/4

代码实现

void generatePoint(double*x, double *y, int r){    int base = 10000;        while (pow(*x, 2) + pow(*y, 2) > pow(r, 2)) {        *x = random() % 10000;        *y = random() % 10000;        *x = (2 * r / (*x)) - r;        *y = (2 * r / (*y)) - r;    }}

蓄水池算法

问题描述

  • 从N个数中,随机抽取K个,是的每个数的抽取概率相同,并且事先不知道K的值

主要思想:

  •     保持一个集合(这个集合中的每个数字出现),作为蓄水池,依次遍历所有数据的时候以一定概率替换这个蓄水池中的数字。将前K个元素都放到水库中,然后对之后的第i个元素,以k/i的概率替换掉这个水库中的某一个元素。

方法证明:

  1. 初始情况。水库中k个元素的出现概率都一致,都是1。
  2. 第一步:处理第k+1个元素。分两种情况:① 元素全部都没有替换;② 其中某个元素被k+1元素替换。
    • 对于case ②:第k+1个元素被选中的概率是k/(k+1),故而这个新元素在水库中出现的概率就一定是k/(k+1)。而水库中剩余的元素出现的概率也就是1-P(P为元素被替换的概率)。水库中任意一个元素被替换的概率为:(k/k+1) * (1/k) = 1/(k+1)。而旧元素出现的概率为k/k+1。即旧元素和新元素出现的概率是相等的。
    • 对于case①:当没有元素被替换时,每个元素出现的概率是一样的。具体为:1-P(P为第k+1个元素被选中) = 1 – k/(k+1) = 1/(k+1)
  3.  利用归纳法:
    • 对于第k+i个元素,其中i ∈(0, length-k)。其出现在水库中的概率为k/(k+i)。利用上面的两步可以得出结论。

算法实现:

int impounding_reservoir(int *array,int length, int k) {    if (k <= 0 || array == NULL         || length <= 0 || k > length) {        return 0;    }        int result[k];    int i = 0, j = 0;    srand((unsigned) time(NULL));     for (i = 0; i < k; i++) {        result[i] = array[i];    }           for (i = k; i < length; i++) {        j = random() % length;        if(j < k)            result[j] = array[i];    }           for (i = 0; i < k; i++)        printf("%d ", result[i]);    printf("\n");     return k;}

产生1~400范围内不重复的20个随机数

int * generateRandom(int *array, int num, int start, int end)
{
    int size = end / 32 + end % 32 > 0 ? 1: 0;

    int tmp_arr[size] = {0};

    int index = 1, count = 0;

    srand(time(NULL));


    while(count < num){

        index += rand() ;
        index %= 400 + 1;

        if (test_bit(tmp_arr, index)) {
            continue;
        } else {
            set_bit(tmp_arr, index);
            array[count] = index;
            index = 1;
            count++;
        } 
    }
    return array;

}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/158929.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 【转】游戏黑客亲述盗号全过程 揭露黑客产业链

    【转】游戏黑客亲述盗号全过程 揭露黑客产业链

    2021年8月16日
    126
  • Postman教程大全「建议收藏」

    Postman是一款功能强大的网页调试与发送网页HTTP请求的Chrome插件Postman背景介绍用户在开发或者调试网络程序或者是网页B/S模式的程序的时候是需要一些方法来跟踪网页请求的,用户可以使用一些网络的监视工具比如著名的Firebug等网页调试工具。今天给大家介绍的这款网页调试工具不仅可以调试简单的css、html、脚本等简单的网页基本信息,它还可以发送几乎所有类型的HTTP请求!Postman在发送网络HTTP请求方面可以说是Chrome插件类产品中的代表产品之一。Postman的操

    2022年4月6日
    45
  • ABAP调用外部接口

    ABAP调用外部接口DATA:lc_http_clientTYPEREFTOif_http_client,LENTYPEI,”发送报文长度l_json_dataTYPEstring,l_json_stringTYPEstring,l_result_dataTYPEstring,l_urlTYPEstring.DATAlc_jsonTYP..

    2022年5月10日
    73
  • file_get_contents()获取https出现这个错误Unable to find the wrapper “https” – did

    file_get_contents()获取https出现这个错误Unable to find the wrapper “https” – did

    2021年10月17日
    47
  • 无人驾驶汽车系统入门(一)——卡尔曼滤波与目标追踪

    无人驾驶汽车系统入门(一)——卡尔曼滤波与目标追踪前言:随着深度学习近几年来的突破性进展,无人驾驶汽车也在这些年开始不断向商用化推进。很显然,无人驾驶汽车已经不是遥不可及的“未来技术”了,未来10年必将成为一个巨大的市场。本系列博客将围绕当前使用的最先进的无人驾驶汽车相关技术,一步一步地带领大家学习并且掌握无人驾驶系统的每一个模块的理论基础和实现细节。由于无人驾驶汽车系统构成及其复杂,本系列博客仅讨论软件部分的内容,关于汽车,传感器和底层的硬件,不

    2022年6月18日
    25
  • 命名规范与规则

    命名规范与规则命名规范1、项目名全部小写,就是如果项目名是多个英语单词组成的,每个单词都要全部小写。如:doubanssm。2、包名全部小写。3、类名首字母大写,若类名由多个单词构成,每个单词首字母大写,即

    2022年7月1日
    29

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号