小技巧2-随机发生器

佚名 6年前 (2019-04-08) 随笔 1441人围观抢沙发百度已收录

问题一：

　　你有一个1-10的随机数发生器。转换成1-9的随机数发生器。

思想：

　　随机到1-9就直接取出来，随机到10就再随机一次。这样做就可以把随机到10的概率平均分到1-9上。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

//设g()会返回一个1-10的随机数
int f(int r){
    while(r==10){
        r=g();
    }
    return r;
}

问题二：

　　你有一个1-10的随机数发生器，转换成0-9的随机数发生器。

思想：

　　区间大小不变，y-x不变，所以给整体加z就好了

//设g()会返回一个1-10的随机数
int f(int r){
    r--;
    return r;
}

问题三：

　　你有一个1-11的随机数发生器，转换成1-15的随机数发生器。

思想：

　　第一步，将1-11的随机数发生器转化成一个01发生器。如果结果时1-5就返回0，6-10就返回1，11就再随机一次。

　　第二步，将1-15的随机数发生器转化为0-14的随机数发生器。

　　第三部，看14需要几个二级制位，如此题14需要4个二进制位，那么随机4次01发生器我们可以等概率得到0-15的一个二进制随机数。

　　第四步，如果得到的2进制数再0-14的范围内，直接返回，如果不在，就再随机一次。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>

using namespace std;

int g(){//g()为1-11的随机数发生器
    return rand()%11+1;
}

int f(){//f()为01发生器
    int r=g();
    if(r<6)return 0;
    else if(r<11)return 1;
    return f();
}

int d(int n,int c){//0-c的发生器
    int num=0;
    for(int i=0;i<n;i++){
        num=num*2+f();
    }
    if(num<=c)return num;
    else return d(n,c);
}

int main()
{
    int a,b;
    a=1,b=15;
    int c=b-a;
    int cc=c;
    int n=0;
    while(cc>0){
        cc=cc/2;
        n++;
    }
    for(int i=0;i<11;i++)
        printf("%d\n",d(n,c)+a);
    return 0;
}

问题四：

　　你有一个01发生器，但不是等概率，以p概率返回0，以1-p概率返回1，转换成一个等概率的01发生器。

思想：

　　用两次不等概率的01发生器。如果是00或者11那么就再重复一次，如果是01就返回0，如果是10就返回1。

//设g()是不等概率的01发生器
int f(){//f()为等概率01发生器
    int l=g();
    int r=g();
    if(l==1&&r==0)return 1;
    else if(l==0&&r==1)return 0;
    else return f();
}